What is the most efficient way of storing data between a multi-dimension array, and a single array?

Question

Essentially I'm not sure how to store a 3D data structure for the fastest access possible as I'm not sure what is going on under the hood for multi-dimensional arrays.

NOTE: The arrays will be a constant and known size each and every time, and each element will be exactly 16 bits.

Option one is to have a multi-dimension array data[16, 16, 16] and simply access via data[x, y, z] option two is to have a single dimension array data[16 * 16 * 16] and access via data[x + (y * 16) + (z * 16 * 16)].

As each element should only be 16 bits long, and I have a suspicion that a multi-dimension array would store a lot of references to other arrays internally at a minimum of 32 bits per one, that is a lot of wasted memory. However, I fear it may be faster than running the equation specified in option two each time, and speed is key to this project.

So, can anyone enlighten me as to how much difference in speed there would likely to be compared to how much difference in memory consumption?

Answer 1

I think it's worth pointing out that if your array dimensions are really all 16, then you can calculate the index for the array from (x, y, z) much more efficiently:

int index = x | y << 4 | z << 8;

And the inverse:

int x = index & 0xf;
int y = (index >> 4) & 0xf;
int z = (index >> 8) & 0xf;

If this is the case, then I recommend using the single-dimensional array since it will almost certainly be faster.

Note that it's entirely possible that the JIT compiler would perform this optimisation anyway (assuming that the multiplication is hard-coded as per your OP), but it's worth doing explicitly.

The reason that I say the single-dimensional array would be faster is because the latest compiler is lacking some of the optimisations for multi-dimensional array access, as discussed in this thread.

That said, you should perform careful timings to see what really is the fastest.

As Eric Lippert says: "If you want to know which horse is faster, race your horses".

Answer 2

C# stores multidimensional arrays as a single block of memory, so they compile to almost the same thing. (One difference is that there are three sets of bounds to check).

I.e. arr[x,y,z] is just about equivalent to arr[x + y*ny +z*nz*ny] and will generally have similar performance characteristics.

The exact performance however will be dominated by the pattern of memory access, and how this affects cache coherence (at least for large amounts of data). You may find that nested loops over x, then y then z may be faster or slower than doing the loops in a different order, if one does a better job of keeping currently used data in the processor cache.

This is highly dependent on the exact algorithm, so it isn't possible to give an answer which is correct for all algorithms.

The other cause of any speed reduction versus C or C++ is the bounds-checking, which will still be needed in the one-dimensional array case. However these will often, but not always, be removed automatically.

• https://blogs.msdn.microsoft.com/clrcodegeneration/2009/08/13/array-bounds-check-elimination-in-the-clr/

Again, the exact algorithm will affect whether the optimiser is able to remove the bounds checks.

Your course of action should be as follows:

• Write a naïve version of the algorithm with arr[x,y,z].
• If it's fast enough you can stop.
• Otherwise profile the algorithm to check it is actually array accesses which are the issue, analyse the memory access patterns and so on.

Answer 3

I would vote for single-demension array, it should work much faster. Basically you can write some tests, performing your most common tasks and measuring the time spent. Also if you have 2^n array sizes it is much faster to access element position by using left shift operation instead of multiplication.