4

This morning I've had a discussion with a colleague about this topic. He says that it's always better to allocate arrays as arrays of pointers, since allocating every single element separately has better chances to get a free memory chunk. Somethink like this:

// 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));
}

As opposed to his approach, I think that is better to allocate arrays of elements, just because you'll get a compact memory chunk and not a bunch of references spread around the heap. Something like this:

int n_elements = 10;
int *ary = (int *) malloc(sizeof(int) * n_elements);

ary[0] = 100;

After this conversation I've been thinking about it, and my final conclusion is that it depends. I find the second solution a better approach when dealing with small datatypes for the reason I mentioned above, but when allocating arrays of large structs is probably better the first one.

Apart of my conclusion, what do you think about it?

Hardy
  • 49
  • 4
  • 2
    Like you said, "it depends". :) – lurker Aug 28 '13 at 16:42
  • 4
    For needing 10 integers, you'd be crazy to do either. Use `int a[10];` For a single contiguous sequence of N items, the latter (minus the cast of `malloc()`) would be the way to go (*rarely* is this not the case). The former is only generally done when you require an arbitrary-length list of arbitrary length lists of items, serving up the *syntax* during usage of a 2D array (when in reality it is anything-but). It is, however, ultimately dependent on your very-specific needs. – WhozCraig Aug 28 '13 at 16:44
  • 1
    This is not primarily opinion based. lol. – Justin Meiners Aug 28 '13 at 16:53
  • @WhozCraig That's why* I pointed out "consider n_elements as a dynamic value" :) – Hardy Aug 28 '13 at 17:11
  • 1
    "It can scarcely be denied that the supreme goal of all theory is to make the irreducible basic elements as simple and as few as possible without having to surrender the adequate representation of a single datum of experience." AE 1933 – chux - Reinstate Monica Aug 28 '13 at 20:42

1 Answers1

6

He is wrong for any mainstream hardware I can think of. (at least in general). It could vary a little and there could be some special cases. Choose array of elements over array of pointers when you can.

CPU caches like data to be contiguously packed. Allocating each element separately will increase cache misses, slow allocation time, and waste memory (due to allocation alignment). The gap between CPU speeds and memory grows every year, increasing the benefits of contiguously packed data and batch operations.

You should read the document described in this question What Every Programmer Should Know About Memory. It describes all the ins and outs of modern CPU/Memory relationship in detail and why contiguous data is very important.

Community
  • 1
  • 1
Justin Meiners
  • 10,754
  • 6
  • 50
  • 92
  • 2
    And also, for user defined types if huge lead to memory fragmentation – Uchia Itachi Aug 28 '13 at 16:44
  • 3
    The exception being a large, sparsely-accessed array, where it's better that each entry be likely to be allocated near other stuff it references. But this depends on having a heap that is likely to allocate near-in-time stuff near-in-address. – Hot Licks Aug 28 '13 at 16:45
  • 2
    Should also be noted that many caches have a cache header per allocation, so allocating multiple entries separately takes more heap. Plus, rounding to an allocation boundary will take more heap for separate allocations. – Hot Licks Aug 28 '13 at 16:47
  • @HotLicks yes, I just recalled that and mentioned it. Thank you – Justin Meiners Aug 28 '13 at 16:49
  • 1
    @JustinMeiners that's actually what I expected to hear. I'll take a look at this document. Thank you! – Hardy Aug 28 '13 at 17:10
  • 1
    Oops -- above I said "cache" and I should have said "heap". The heap entry often has a header per allocation, plus rounding to an allocation boundary. This can add 32 bytes or more to an allocation. – Hot Licks Aug 28 '13 at 17:53