Initially thought i'd go with a) for simplicity
I know that Java doesn't store arrays linearly in memory like C does. But what implications does this have for my program?
Usually the best thing to do when searching anwers for such questions is to see how the choices are compiled into JVM bytecode:
this is translated into
so as you can see the JVM already knows that we are talking about a multi dimensional array..
keeping it further:
this is translated (skipping the cycles) into:
So as you can see the multi-dimensional array is treated internally into the VM, no overhead generated by useless instructions, while using a sigle one uses more instructions since offset is calculated by hand.
I don't think that performance will be such an issue..
I did some simple benchmarks to see what's going down here. I chose try different examples: linear read, linear write and random access. Time are expressed in millisecs (and calculated using
But random one is a little bit misleading since it generates 2 random numbers for multi-dimensional array while just one for single dimensional (and PNRGs may consume some CPU).
Mind that I tried to let JIT work by benchmarking only after the 20th run of the same loop. For completeness my java VM is the following:
On current CPUs, non-cached memory access is hundreds of times slower than arithmetics (see this presentation and read What every programmer should know about memory). The a) option will result in about 3 memory lookups whereas the b) option will result in about 1 memory lookup. Also the CPU's prefetching algorithms might not work as well. So the b) option can be faster in some situations (it's a hot spot and the array does not fit into the CPU's cache). How much faster? - that will depend on the application.
Personally I would first use the a) option, because it will result in simpler code. If a profiler shows that array access to be a bottleneck, then I would convert it to the b) option, so that there is a pair of helper methods for reading and writing array values (that way the messy code will be restricted to those two methods).
I made a benchmark for comparing 3-dimensional int arrays ("Multi" column) to the equivalent 1-dimensional int arrays ("Single" column). The code is here and tests here. I ran it on 64-bit jdk1.6.0_18, Windows 7 x64, Core 2 Quad Q6600 @ 3.0 GHz, 4 GB DDR2, using the JVM options
This shows the 1-dimensional array to be faster. Though the differences are so small, that for 99% applications it won't be noticable.
I did also some measurements to estimate the overhead of generating the random numbers in the Random Read benchmark by replacing
Use first variant (3-dimensional) because it's easier for understanding and there are less chances to make some logical error (especially if you're using it for modeling 3-dimensional space)
If you choose the latter route then you're going to have to perform arithmetic for every single array access. That's going to be a pain and error prone (unless you wrap it in a class providing this functionality).
I don't believe that there's any (significant) optimisation in choosing your flat array (especially given the arithmetic taken to index into it). As always with optimisations, you would need to perform some measurements and determine if it's really worth it.