Sign in to follow this  

Accessing planes of a 3 dimensional array

This topic is 4666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a 256x256x256 data structure with which I need to quickly access planes from any of the 3 dimensions. The problem is that accessing the first dimension is very quick because it's linear in memory, while the others are painfully slow and require nested for loops. Is there any way around this without storing the data three times?

Share this post


Link to post
Share on other sites
Not really; memory is linear by nature, so you're going to incur cache misses and so forth for the other n-1 dimensions no matter what you do. However, assuming all those dimensions are static, and you're just using a plain Foo[256][256][256], then it won't be too bad; it's really a 1-d 'array' where each index will be calculated all at once. (If you allocate things with a vector<vector<vector<Foo> > > for example, the array is no longer rectangular; because of the flexibility that is designed in, some indirection is required, and a few pointers will be dereferenced for each element access - which is slower).

If you need a multi-dimensional container which is resizable but which will maintain 'rectangularity' (and treat things in an optimized way), consider boost::multi_array.

Share this post


Link to post
Share on other sites
3D array is fine in this case. What's the issue? You'll need a loop to access its indices anyways if you want to traverse the indices in that order.

Kuphryn

Share this post


Link to post
Share on other sites
I don't think nested for-loops which performs a total of 256^3 iterations would be much slower than only one for-loop performing a total of 256^3 iterations. The only extra operations having to be made is incrementing the additional indices and testing whether they are < SIZE (see below).

What makes the operations performed on a several-dimensional array a little slower is maybe the additional indices which would have to be retrieved to access an element. Also the address to an element has to calculated based on the size of the dimensions and the indices, or the address has to be retrieved from memory if it's a pointer to pointer to value-array.

Below is the general nested loop structure where indices a, b and c are retrieved every time to access an element in the array.


char unsigned array[SIZE][SIZE][SIZE]; //3d-array
int short a, b, c; //index for each dimension

for (a = 0; a < SIZE; ++a)
{
for (b = 0; b < SIZE; ++b)
{
for (c = 0; c < SIZE; ++c)
{
if (array[a][b][c] > 0) //if the value > 0
--array[a][b][c]; //decrement it
}
}
}



If the code above is considered slow one could do like this instead:


char unsigned array[SIZE][SIZE][SIZE]; //3d-array
int short a, b, c; //index for each dimension
char unsigned* p; //pointer to the "linear" dimension

for (a = 0; a < SIZE; ++a)
{
for (b = 0; b < SIZE; ++b)
{
p = array[a][b]; //get the address to the "linear" dimension only once

for (c = 0; c < SIZE; ++c)
{
if (p[c] > 0) //if the value > 0
--p[c]; //decrement it
}
}
}



Now a and b have to be retrieved a lot less often and the array is accessed via the pointer p using only one index. p is set only once per "linear data". Maybe it's a little faster, maybe :).

I'm unsure what you mean by "without storing the data three times?", could you explain it a little more?

\Jimmy H

Share this post


Link to post
Share on other sites
No, basically what I'm doing is taking 2 dimensional slices out of the 3 dimensional array. In the first dimension this can be accomplished with one memcpy. In the other 2 I can maybe reduce it to 256 memcpys so they are slower. But, Zahlman is right, the cost isn't as bad as I initially thought. :/

Share this post


Link to post
Share on other sites

This topic is 4666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this