2

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.

Improve this question
6
  • 1
    write and test... that's the way to be sure. Probably the flat array will be faster, though not by much. A flat array is easier to (de-)allocate anyway Commented Nov 14, 2013 at 9:01
  • If the array has fixed size (stack-allocated array) and the original type if preserved (like int arr[4][2][9][4]), then probably the multidimensional array is faster, as is carries more type information for the compiler to use in optimizations, compared to a flat array whose indices still needs to be calculated. Commented Nov 14, 2013 at 9:04
  • @Elias: I wouldn't be so sure, especially when accessing it sequentially, e.g. iterating over the d index. In the former case 'a','b' and 'c' would remain cached, in the latter the whole arithmetic expression would be re-evaluated. But personally, I believe optimizer will optimize away both to the same code. Commented Nov 14, 2013 at 9:05
  • @SF.: I'm not sure. My first thought was that a flat array would be faster, but I'm having second thoughts, to be honest. As far as the optimizer goes: that all depends on how the array(s) will be used. However, the OP doesn't declare a standard array, but declares pointers... allocated on the heap Commented Nov 14, 2013 at 9:08
  • 2
    @EliasVanOotegem: ah, yes. Quadruple dereference. If the first array was declared not as ****multidim_arr but as multidim arr[SIZE_A][SIZE_B][SIZE_C][SIZE_D] I'd stand by my previous statement. In this case I'm not really so sure. Commented Nov 14, 2013 at 9:16

2 Answers 2

Reset to default
9

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Extra fetches, sure, because of the extra pointer lookups. But each slice of the flat array will also live in a different cache line (assuming this isn't a trivially small inner dimension).
+1 for pointing out the difference between arrays of pointers and pointers to ints
3

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.

Improve this answer

2 Comments

@oli I think I missused the term, thanks for pointing it out. Edited.
Let's suppose that access to elements is random. How about that?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.