LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 06-14-2005, 03:44 AM   #1
leeach
Member
 
Registered: Sep 2003
Location: /dev/null
Distribution: FreeBSD 5.4, OpenBSD 3.7
Posts: 95

Rep: Reputation: 15
Unhappy 3 dimensional array help


Code:
int largeArray[1024][64][4];
In another particular function I only need a part of the array.
therefore, I'm using a new variable and assign it the following way:

int (*smallArray)[64][4];
smallArray = &largeArray[42];

Is this code correct if I want to get the value of an element?

int x = smallArray[0][0];


Also, Is there a performance difference between retrieving many elements of the
small and the large array in my function?

thanks in advance...

Last edited by leeach; 06-14-2005 at 03:46 AM.
 
Old 06-14-2005, 01:58 PM   #2
jonaskoelker
Senior Member
 
Registered: Jul 2004
Location: Denmark
Distribution: Ubuntu, Debian
Posts: 1,524

Rep: Reputation: 47
Quote:
Is this code correct if I want to get the value of an element?
I would think so.

Perhaps writing a small test will sort it out?

Quote:
Also, Is there a performance difference <snip>
They're both O(1), so no.

Oh, you mean wall time?
That depends on your os, arch, cc, time of day and density of cosmic rays.
This should sort it out:
$ for i in $(seq 10); do time version1; done
$ for i in $(seq 10); do time version2; done
... or use a profiler.

hth --Jonas
 
Old 06-14-2005, 02:00 PM   #3
rjlee
Senior Member
 
Registered: Jul 2004
Distribution: Ubuntu 7.04
Posts: 1,991

Rep: Reputation: 76
Re: 3 dimensional array help

Quote:
Originally posted by leeach
Code:
int largeArray[1024][64][4];
In another particular function I only need a part of the array.
therefore, I'm using a new variable and assign it the following way:

int (*smallArray)[64][4];
smallArray = &largeArray[42];

Is this code correct if I want to get the value of an element?

int x = smallArray[0][0];


Also, Is there a performance difference between retrieving many elements of the
small and the large array in my function?

thanks in advance...
The only way I can get to work to take a 2D slice of a 3D array is:
Code:
int *smallarray[4] = largeArray[42];
This compiles without warnings on c++ (GCC) 3.3.3 and gives the expected array contents.

After your x assignment, x would hold the value of largeArray[42][0][0];

Note that you will need to use some sort of loop if you want to copy a part of the array rather than taking a pointer to it.

There is no performance difference to using either array, except that if you retrieve all the elements of the large array in order, then this might give you a slight performance increase on MMX-optimised compilers; this is less unlikely to happen if you use the large array than repeated slices.
 
Old 06-15-2005, 05:05 AM   #4
leeach
Member
 
Registered: Sep 2003
Location: /dev/null
Distribution: FreeBSD 5.4, OpenBSD 3.7
Posts: 95

Original Poster
Rep: Reputation: 15
but I thought there may be a small performance difference resulting from index calculation with the array of _greater_ dimension.

Then again, a good compiler might optimize away the indirect references for me. the key performance problem in multi-dimensional arrays is the element ordering. If I remember correctly, C uses row-major ordering which means it's much more efficient to iterate over _rows_ than columns...

the index into the first dimension would keep getting re-calculated and there would be a lot of cache misses/page faults/etc.. because non-sequential areas of memory would be accessed. I hope I didn't lose you on this..

Last edited by leeach; 06-15-2005 at 05:13 AM.
 
Old 06-15-2005, 07:04 AM   #5
rjlee
Senior Member
 
Registered: Jul 2004
Distribution: Ubuntu 7.04
Posts: 1,991

Rep: Reputation: 76
Quote:
Originally posted by leeach
but I thought there may be a small performance difference resulting from index calculation with the array of _greater_ dimension.

Then again, a good compiler might optimize away the indirect references for me. the key performance problem in multi-dimensional arrays is the element ordering. If I remember correctly, C uses row-major ordering which means it's much more efficient to iterate over _rows_ than columns...
Pretty much. The square brackets operator [b]a is just a short-hand for *(a + b * sizeof(*a)).

A three-dimensional array is built up out of a contiguous “list” (or array) of two-dimensional arrays, so by taking a 2D slice you get a pointer into the start of the 2D array you're interested in.

All of the above ignores byte-alignment, but that's just an optimisation anyway.

For accessing an individual element, the choice is between:
Code:
int smallarray = largearray + 42 * sizeof(int);
int result = (smallarray + 1 * sizeof(int)) + 2 * sizeof(int);
and:
Code:
int result = ((smallarray + 42 * sizeof(int)) + 1 * sizeof(int)) + 2 * sizeof(int);
In other words, this is the same calculation; the only difference being that the original calculation names an intermediate pointer variable.

Quote:
the index into the first dimension would keep getting re-calculated and there would be a lot of cache misses/page faults/etc.. because non-sequential areas of memory would be accessed. I hope I didn't lose you on this..
Correct. Changing the right-hand indexes more frequenetly than the left-hand indexes causes the program to access bytes of memory that are more close together. This causes your program to have a higher degree of locality and thus swap more efficiently. The array in question is still only 64 pages, though (assuming an i386-type architecture with a 4kb page size), so you may find it never gets swapped out in the first place, making this a non-issue. (Caveat that 2.6 series kernels can be configured to swap out unused pages in any case to increase buffer size).

A bigger issue is that the optimiser can cache the value of the left-most array index while the right-most element is changing — taking a 2D array slice as per the original question. In which case there really would be no difference between doing it yourself and getting the optimiser to do it for you.
 
Old 06-15-2005, 07:11 AM   #6
jonaskoelker
Senior Member
 
Registered: Jul 2004
Location: Denmark
Distribution: Ubuntu, Debian
Posts: 1,524

Rep: Reputation: 47
Quote:
but I thought there may be a small performance difference resulting from index calculation with the array of _greater_ dimension.
(see below about pointer arithmetic).

Quote:
C uses row-major ordering
Correct.

Code:
int A[2][3][4] = {
    1, 2, 3, 4, ..., 24
};
The elements are in increasing order with increasing address.

Quote:
which means it's much more efficient to iterate over _rows_ than columns...
I don't understand exactly what's faster than what--some pseudo-code would be nice.

if you iterate (in pseudo-code) like
Code:
for(i = 0; i < n; ++i) for(j) ... for(m) A[i][j]...[m]
then you will be accessing all memory sequentially (and it can thus be flattened to one level of looping--perhaps using pointer arithmetic instead of indices).

Quote:
the index into the first dimension <snip> I hope I didn't lose you on this.
Some clarification would be nice.

--Jonas
 
Old 06-15-2005, 07:38 AM   #7
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
Quote:
but I thought there may be a small performance difference resulting from index calculation with the array of _greater_ dimension.
You get one * per-[]; largeArray is essentially an int***, largeArray[42] is an int**, but smallArray is still an int*** because you take the address of largeArray[42]. Each time you use [] against the array, you dereference one * by essentially doing this: *(largeArray + 42), making smallArray equal to &*(largeArray + 42).

In order to get [0][0] from smallArray, you first need to dereference smallArray since it is really just largeArray + 42; instead of smallArray[0][0] you need (*smallArray)[0][0], giving you 3 dereferences, which is the same number of dereferences as largeArray[42][0][0].

largeArray + 42 and smallArray point to the same area of memory and are the same value, however you might get a VERY VERY slight savings because the largeArray + 42 operation isn't evaluated every time. So whatever savings you obtain is the adding of 2 integers, which will likely be done in a processor register, which is extremely fast. On a modern processor you'd have to perform the operation a billion times in order to see any time difference, which would be negligible at that. Your kernel could burp while cleaning up another process and that would be the end of your time savings. Optimization isn't everything, especially in this case.

Clarity and the ability for you and others to easily see what is going on (making code easier to maintain and debug) is generally better than most low-level optimizations in a high-level language. The compiler and linker take care of optimizations from asm downward (gcc 4.0.0 supposedly optimizes from C++ downward also); what you should worry about is conceptual optimization. If you use literals in your [] (as in largeArray[42] as opposed to largeArray[x]) then chances are there is 0% benefit to smallArray because the compiler will optimize the addition away. If I were you I would specify all 3 [] wherever possible.
ta0kira

PS I take some of that back; You COULD make it a little faster by making smallArray int**:
Code:
int **smallArray = largeArray[42];
int x = smallArray[0][0];
This can be a little faster (and maybe worth looking into) because you have 1/3 less dereferences with smallArray[0][0] than largeArray[42][0][0]. Again, only if you are using the operation an extreme number of times. In this case I'll let you get away with a MILLION instead of a billion...

Last edited by ta0kira; 06-15-2005 at 07:44 AM.
 
Old 06-15-2005, 07:49 AM   #8
rjlee
Senior Member
 
Registered: Jul 2004
Distribution: Ubuntu 7.04
Posts: 1,991

Rep: Reputation: 76
Quote:
Originally posted by ta0kira
Clarity and the ability for you and others to easily see what is going on (making code easier to maintain and debug) is generally better than most low-level optimizations in a high-level language.
This post is slightly off-topic, but I would like to reiterate that this is an important point; for more information, try Googling for the phrase “premature optimization”.
 
Old 06-15-2005, 08:30 AM   #9
leeach
Member
 
Registered: Sep 2003
Location: /dev/null
Distribution: FreeBSD 5.4, OpenBSD 3.7
Posts: 95

Original Poster
Rep: Reputation: 15
Quote:
Originally posted by jonaskoelker
(see below about pointer arithmetic).


Correct.

Code:
int A[2][3][4] = {
    1, 2, 3, 4, ..., 24
};
The elements are in increasing order with increasing address.


I don't understand exactly what's faster than what--some pseudo-code would be nice.

if you iterate (in pseudo-code) like
Code:
for(i = 0; i < n; ++i) for(j) ... for(m) A[i][j]...[m]
then you will be accessing all memory sequentially (and it can thus be flattened to one level of looping--perhaps using pointer arithmetic instead of indices).


Some clarification would be nice.

--Jonas
ok point taken:

a nested loop for example
for(i=0;i<n;i++) for(j=0;j<n;j++){...}


It's much more efficient to put the statement:

a[i][j]*=2

..inside the curly braces as opposed to:

a[j][i]*=2

Hope I made myself a little clearer on this Jonas.

----------------------

ta0kira, I actually will be using it quite often, but not quite a million.. but this is exactly why I asked and the answers I was looking for , thank you all.

Last edited by leeach; 06-15-2005 at 08:31 AM.
 
Old 06-15-2005, 10:24 AM   #10
rjlee
Senior Member
 
Registered: Jul 2004
Distribution: Ubuntu 7.04
Posts: 1,991

Rep: Reputation: 76
Quote:
Originally posted by leeach
It's much more efficient to put the statement:

a[i][j]*=2

..inside the curly braces as opposed to:

a[j][i]*=2
If we're talking about unoptimised code, then it's even more efficient to use ++i and ++j in the loops rather than i++ and j++; it removes the temporary copies of i and j.

(Not much in it for C, as an int allocation/copy/deallocation is trivial, but in C++ it can make a huge difference as i and j would probably be iterator objects. Mind you, if you were using C++ then you'd be using vectors instead of arrays anyway; see previous post on premature optimisation).
 
Old 06-15-2005, 11:18 AM   #11
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
Quote:
If we're talking about unoptimised code, then it's even more efficient to use ++i and ++j in the loops rather than i++ and j++; it removes the temporary copies of i and j.
If we are using C then we can't use those operators; it needs to add the size of the type. It will work in C++ though. It is messy to work around the pre-increment when checking the array bounds though:
Code:
int *start, *end;
if (start < end) do
{
int x = *start;
}
while (++start < end);
as opposed to:
Code:
int *start, *end;
while (start < end)
{
int x = *start++;
}
That would look odd in a cubic situation don't you think?
Code:
const int X = 100, Y = 100, Z = 100;
int cube[X][Y][Z];

int (*startX)[Y][Z] = cube, (*endX)[Y][Z] = cube + X;
if (startX < endX) do
{

int (*startXY)[Z] = *startX, (*endXY)[Z] = *endX + Y;
if (startXY < endXY) do
{

int *startXYZ = *startXY, *endXYZ = *endXY + Z;
if (startXYZ < endXYZ) do
{
int x = *startXYZ;
}
while (++startXYZ < endXYZ);

}
while (++startXY < endXY);

}
while (++startX < endX);
as opposed to:
Code:
const int X = 100, Y = 100, Z = 100;
int cube[X][Y][Z];

for (int I = 0; I < X; I++)
for (int J = 0; J < Y; J++)
for (int K = 0; K < Z; K++)
int x = cube[I][J][K];
Correction to my last post: you would need a C-cast to use an int**:
Code:
int **smallArray = (int**) largeArray[42];
ta0kira

Last edited by ta0kira; 06-20-2005 at 12:21 PM.
 
Old 06-15-2005, 11:46 AM   #12
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
Sorry, this is a really fun thread. I'd really rather use a single dimentional array with an adapter function:
Code:
typedef unsigned int position;

inline position pos3( position X,    position Y,    position Z,
                      position maxX, position maxY, position maxZ )
{ return X * maxY * maxZ + Y * maxZ + Z; } //Doesn't matter what order if you always use this function...

//...

const position X = 100, Y = 100, Z = 100;
int cube[ X * Y * Z ];

for (position I = 0; I < X; I++)
for (position J = 0; J < Y; J++)
for (position K = 0; K < Z; K++)
int x = cube[ pos3(I, J, K, X, Y, Z) ];
I think multi-dimentional arrays get too confusing, and they cause bugs too easily...
ta0kira
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Double pointers and two dimensional arrays in C kponenation Programming 23 03-16-2011 12:43 PM
Two Dimensional Character Problem Mistro116@yahoo.com Programming 8 11-26-2005 09:13 PM
building a three dimensional array in vb6 mrobertson Programming 0 08-18-2005 10:12 AM
Bash 2 dimensional array ldp Linux - General 5 07-29-2005 12:29 PM
memory managment problem; higher dimensional array doesn't delete qanopus Programming 5 06-15-2005 05:18 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 09:17 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration