Multidimmensional array vs flat array - performance comparison

Question

Is there any performance issue while using one of below methods? Which is faster (if any)? It would be great if is there any performance tests.

Multidimmentional array:

// Using multidimmentional array:
int ****multidim_arr;
// ... initialization, etc. ...
int val = multidim_arr[a][b][c][d];

Flat array:

// Using flat array (or single array)
int *flat_arr;
// ... initialization, etc. ...
int val2 = flat_arr[a * a_lvl + b * b_lvl + c * c_lvl + d];

UPDATE:

Arrays have fixed size, but memory is allocated by malloc() function because size is known while program is working.

Answer 1

As with all performance questions, profile and see. But it's quite likely the flat array will be faster. That's because you're not comparing multidimensional array with a flat one - you're comparing an array of pointers to an array of pointers to ... to an array with a flat array.

A multidimensional array would be int multidim_array[dim1][dim2][dim3][dim4]. And that could be expected to have the same speed as the flat array. That's because that is contiguous in memory.

On the other hand, yours is based on pointers, so each slice resides in a different memory location, which means extra fetches, cache misses etc. This will almost definitely be slower.

Answer 2

It depends on how you iterate over elements and sizes. The performance in such cases heavily depends on cache performance (hit/miss ratio).

It is very hard to generalize.

The "flat" arrays tend to be faster because access to elements is more direct. You compute the index once. Also by, "flat" I mean continuous memory block, where index of arbiraty element can be computed in one expression. I would expect int a[X][Y][Z][W] to work same fast as int a[X*Y*Z*W], the computation you perform to manually get index is the same as would compielr do.

The real difference is between int**** a;

With multi-dimensional "pointer" arrays. This is actually high level pointer reference, and you need to fetch appropriate address on every level. This can impact performance quite hard in certain cases.