How are 2D static arrays allocated?

[bearophile]

Robert Fraser:
> The only reason static arrays seem to exist at all (as well as good 
> explanation for their incongruity with other types) is C compatibility.

They also can give you more performance, if you know how to use them well.


Jarrett Billingsley>Fixed-size 2D arrays are not faster _because_ they are on the
stack, they just happen to be allocated on the stack.  They are faster (usually) because they don't need two pointer dereferences.<

Right. You can allocate a single block of dynamic memory, and then find items using something like: col+row*ncols. But fixed-size 2D arrays can be faster also because the compiler knows the sides of the matrix at compile time. So to find the position of the cells it can often (if you have chosen the right sizes) use shifts and similar tricks, that are faster than that general multiplication row*ncols.

For example here I have written a small C program (exactly the same code can be written in D, I have used C because GCC optimizes more than DMD):
http://www.fantascienza.net/leonardo/js/wirun2.c

As main data structure it uses a large matrix:
#define SIZEX 1024
#define SIZEY 1024
int lists[4][SIZEX * SIZEY];

That program wastes some space on the right of that tensor, to keep the sizes as powers of two. Those numbers are powers of two, so to compute the index positions it uses just shifts, and it's fast. If you use the same code in D you have a higher performance than using dynamic arrays, even if you carve it from a single chunk of heap memory.
Note that modern caches have quite weird performance problems with arrays with sizes as powers of two, so you have to benchmark your code every time, or you have to know a LOT of details about your CPU caches.

Bye,
bearophile