Array of pointers and array of elements

Question

This morning I talked with a colleague on this topic. He says that it is always better to allocate arrays as arrays of pointers, since allocating each individual element is more likely to get a free piece of memory. Something like that:

// Consider n_elements as a dynamic value int n_elements = 10, i; int **ary = (int **) malloc(sizeof(int *) * n_elements); for(i = 0; i < n_elements; i++) { ary[i] = (int *) malloc(sizeof(int)); } 

Unlike his approach, I believe that it is better to allocate arrays of elements, simply because you get a compact piece of memory, and not a bunch of links distributed around the heap. Something like that:

 int n_elements = 10; int *ary = (int *) malloc(sizeof(int) * n_elements); ary[0] = 100; 

After this conversation, I thought about it, and my final conclusion is that it depends. I believe that the second solution is better for working with small data types for the reason I mentioned above, but when distributing arrays of large structures, it is probably better than the first.

Besides my conclusion, what do you think of this?

Answer 1

He is mistaken for any basic equipment that I can think of. (at least in general). This may change a bit, and there may be some special cases. Select an array of elements by an array of pointers when you can.

The CPU caches as data that must be contiguously packed. Selecting each element individually will lead to an increase in cache misses, slower allocation time and waste memory (due to equalization of distribution). The gap between processor speed and memory is growing every year, which increases the benefits of adjacent packed data and batch operations.

You should read the document described in this question What every programmer should know about memory . It describes in detail all the inputs and outputs of the modern relationship between the processor and the memory and why related data is very important.