Correctly allocating multi-dimensional arrays

Question

The intent of this question is to provide a reference about how to correctly allocate multi-dimensional arrays dynamically in C. This is a topic often misunderstood and poorly explained even in some C programming books. Therefore even seasoned C programmers struggle to get it right.

---

I have been taught from my programming teacher/book/tutorial that the correct way to dynamically allocate a multi-dimensional array is by using pointer-to-pointers.

However, several high rep users on SO now tell me that this is wrong and bad practice. They say that pointer-to-pointers are not arrays, that I am not actually allocating arrays and that my code is needlessly slow.

This is how I was taught to allocate multi-dimensional arrays:

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int** arr_alloc (size_t x, size_t y)
{
  int** pp = malloc(sizeof(*pp) * x);
  assert(pp != NULL);
  for(size_t i=0; i<x; i++)
  {
    pp[i] = malloc(sizeof(**pp) * y);
    assert(pp[i] != NULL);
  }

  return pp;
}

int** arr_fill (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      pp[i][j] = (int)j + 1;
    }
  }

  return pp;
}

void arr_print (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", pp[i][j]);
    }
    printf("\n");
  }
}

void arr_free (int** pp, size_t x, size_t y)
{
  (void) y;

  for(size_t i=0; i<x; i++)
  {
    free(pp[i]);
    pp[i] = NULL;
  }
  free(pp);
  pp = NULL;
}


int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int** pp;

  pp = arr_alloc(x, y);
  pp = arr_fill(pp, x, y);
  arr_print(pp, x, y);
  arr_free(pp, x, y);

  return 0;
}

Output

1 2 3
1 2 3

This code works just fine! How could it be wrong?

Solution

In order to answer the question, we should first clear up some concepts. What is an array and how can it be used? And what is the code in the question, if not an array?

---

What is an array?

The formal definition of an array is found in the C standard, ISO 9899:2011 6.2.5/20 Types.

An array type describes a contiguously allocated non-empty set of objects with a particular member object type, called the element type.

In plain English, an array is a collection of items of the same type allocated contiguously, in adjacent memory cells.

For example an array of 3 integers int arr[3] = {1,2,3}; would be allocated in memory like this:

+-------+-------+-------+
|       |       |       |
|   1   |   2   |   3   |
|       |       |       |
+-------+-------+-------+

So what about the formal definition of a multi-dimensional array? Actually, it is the very same definition as cited above. It applies recursively.

If we would allocate a 2D array, int arr[2][3] = { {1,2,3}, {1,2,3} }; it would get allocated in memory like this:

+-------+-------+-------+-------+-------+-------+
|       |       |       |       |       |       |
|   1   |   2   |   3   |   1   |   2   |   3   |
|       |       |       |       |       |       |
+-------+-------+-------+-------+-------+-------+

What we have in this example is actually an array of arrays. An array which has 2 items, each of them an array of 3 integers.

---

An array is a type like any other

Arrays in C often follow the same type system as regular variables. As shown above, you can have an array of arrays, like you can have an array of any other type.

You can also apply the same kind of pointer arithmetic on n-dimensional arrays as on plain one-dimensional arrays. With a regular one-dimensional arrays, applying pointer arithmetic should be trivial:

int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.

for(size_t i=0; i<3; i++)
{
  printf("%d ", *ptr); // print contents.
  ptr++; // set pointer to point at the next element.
}

This was made possible through "array decay". When arr was used inside an expression, it "decayed" into a pointer to the first element.

Similarly, we can use the very same kind of pointer arithmetic to iterate through an array of arrays, by using an array pointer:

int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.

for(size_t i=0; i<2; i++)
{
  printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
  ptr++; // set pointer to point at the next element
}

Again there was array decay. The variable arr which was of type int [2][3] decayed into a pointer to the first element. The first element was an int [3] and a pointer to such an element is declared as int(*)[3] - an array pointer.

Understanding array pointers and array decay is necessary in order to work with multi-dimensional arrays.

---

There are more cases where arrays behave just like regular variables. The sizeof operator works just the same for (non-VLA) arrays as for regular variables. Examples for a 32 bit system:

int x; printf("%zu", sizeof(x)); prints 4.
int arr[3] = {1,2,3}; printf("%zu", sizeof(arr)); prints 12 (3*4=12)
int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr)); prints 24 (2*3*4=24)

---

Like any other type, arrays can be used with library functions and generic APIs. Since arrays fulfil the requirement of being allocated contiguously, we can for example safely copy them with memcpy:

int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));

Contiguous allocation is also the reason why other similar standard library functions like memset, strcpy, bsearch and qsort work. They are designed to work on arrays allocated contiguously. So if you have a multi-dimensional array, you can efficiently search it and sort it with bsearch and qsort, saving you the fuss of implementing binary search and quick sort yourself and thereby re-inventing the wheel for every project.

All of the above consistencies between arrays and other types is a very good thing that we want to take advantage of, particularly when doing generic programming.

---

What is the pointer-to-pointer thing, if not an array?

Now to get back to the code in the question, which used a different syntax with a pointer-to-pointer. There is nothing mysterious about it. It is a pointer to pointer to type, no more no less. It is not an array. It is not a 2D array. Strictly speaking, it cannot be used to point at an array, nor can it be used to point at a 2D array.

A pointer-to-pointer can however be used to point at the first element of an array of pointers, instead of pointing at the array as whole. And that is how it is used in the question - as a way to "emulate" an array pointer. In the question, it is used to point at an array of 2 pointers. And then each of the 2 pointers is used to point at an array of 3 integers.

This is known as a look-up table, which is a kind of abstract data type (ADT), which is something different from the lower level concept of plain arrays. The main difference is how the look-up table is allocated:

+------------+
|            |
| 0x12340000 |
|            |
+------------+
      |
      |
      v
+------------+     +-------+-------+-------+
|            |     |       |       |       |
| 0x22223333 |---->|   1   |   2   |   3   |
|            |     |       |       |       |
+------------+     +-------+-------+-------+
|            | 
| 0xAAAABBBB |--+
|            |  | 
+------------+  |  
                |
                |  +-------+-------+-------+
                |  |       |       |       |
                +->|   1   |   2   |   3   |
                   |       |       |       |
                   +-------+-------+-------+

The 32 bit addresses in this example are made-up. The 0x12340000 box represents the pointer-to-pointer. It contains an address 0x12340000 to the first item in an array of pointers. Each pointer in that array in turn, contains an address pointing at the first item in an array of integers.

And here is where the problems start.

---

Problems with the look-up table version

The look-up table is scattered all over the heap memory. It is not contiguously allocated memory in adjacent cells, because each call to malloc() gives a new memory area, not necessarily located adjacently to the others. This in turn gives us lots of problems:

• We can't use pointer arithmetic as expected. While we can use a form of pointer arithmetic to index and access the items in the look-up table, we can't do so using array pointers.

• We can't use the sizeof operator. Used on the pointer-to-pointer, it would give us the size of a pointer-to-pointer. Used to the first item pointed at, it would give us the size of a pointer. Neither of them is the size of an array.

• We can't use standard library functions that excepts an array type (memcpy, memset, strcpy, bsearch, qsort and so on). All such functions assume to get arrays as input, with data allocated contiguously. Calling them with our look-up table as parameter would result in undefined behavior bugs, such as program crashes.

• Repeated calls of malloc to allocate several segments leads to heap fragmentation, which in turn results in poor use of RAM memory.

• Since the memory is scattered, the CPU cannot utilize cache memory when iterating through the look-up table. Efficient use of the data cache requires a contiguous chunk of memory which is iterated through from top to bottom. This means that the look-up table, by design, has significantly slower access time than a real multi-dimensional array.

• For each call to malloc(), the library code managing the heap has to calculate where there is free space. Similarly for each call to free(), there is overhead code which has to be executed. Therefore, as few calls to these functions as possible is often preferable, for the sake of performance.

---

Are look-up tables all bad?

As we can see, there are a lot of problems with pointer-based look-up tables. But they aren't all bad, it is a tool like any other. It just has to be used for the right purpose. If you are looking for a multi-dimensional array, which should be used as an array, look-up tables are clearly the wrong tool. But they can be used for other purposes.

A look-up table is the right choice when you need all dimensions to have completely variable sizes, individually. Such a container can be handy when for example creating a list of C strings. It is then often justified to take the above mentioned execution speed performance loss in order to save memory.

Also, the look-up table has the advantage that you can re-alloce parts of the table in run-time without the need to re-allocate a whole multi-dimensional array. If this is something that needs to be done frequently, the look-up table might even outperform the multi-dimensional array in terms of execution speed. For example, similar look-up tables can be used when implementing a chained hash table.

---

How to properly allocate a multi-dimensional array dynamically then?

The easiest form in modern C is to simply use a variable-length array (VLA). int array[x][y]; where x and y are variables given values in run-time, prior array declaration. However, VLAs have local scope and do not persist throughout the duration of the program - they have automatic storage duration. So while VLAs may be convenient and fast to use for temporary arrays, it is not an universal replacement to the look-up table in the question.

To truly allocate a multi-dimensional array dynamically, so that it gets allocated storage duration, we have to use malloc()/calloc()/realloc(). I'll give one example below.

In modern C, you would use array pointers to a VLA. You can use such pointers even when no actual VLA is present in the program. The benefit of using them over a plain type* or a void* is increased type-safety. Using a pointer to a VLA also allows you to pass the array dimensions as parameters to the function using the array, making it both variable and type safe at once.

Unfortunately, in order to use the benefits of having a pointer to VLA, we can't return that pointer as a function result. So if we need to return a pointer to the array to the caller, it must be passed as a parameter (for the reasons described in Dynamic memory access only works inside function). This is fine practice in C, but makes the code a bit hard to read. It would look something like this:

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

While this syntax with a pointer to an array pointer might look a bit strange and intimidating, it doesn't get more complex than this even if we add more dimensions:

void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
  *aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
  assert(*aptr != NULL);
}

Now compare that code with the code for adding one more dimension to the look-up table version:

/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
  int*** ppp = malloc(sizeof(*ppp) * x);
  assert(ppp != NULL);
  for(size_t i=0; i<x; i++)
  {
    ppp[i] = malloc(sizeof(**ppp) * y);
    assert(ppp[i] != NULL);
    for(size_t j=0; j<y; j++)
    {
      ppp[i][j] = malloc(sizeof(***ppp) * z);
      assert(ppp[i][j] != NULL);
    }
  }

  return ppp;
}

Now that is one unreadble mess of "three-star programming". And lets not even consider 4 dimensions...

---

The full code of a version using true 2D arrays

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

void arr_fill (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      array[i][j] = (int)j + 1;
    }
  }
}

void arr_print (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", array[i][j]);
    }
    printf("\n");
  }
}

int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int (*aptr)[x][y];

  arr_alloc(x, y, &aptr);
  arr_fill(x, y, *aptr);
  arr_print(x, y, *aptr);
  free(aptr); // free the whole 2D array

  return 0;
}

Comments

[Lundin]

Further explanation about array pointers, array decay and tips & tricks about how to use them together with dynamic allocation.

[yano]

just to be clear, your final solution here relies on support for VLAs, which came about in C99?

[Lundin]

@yano Yes, VLAs were introduced 18 years ago.

[Lundin]

@DavidBowling This was written specifically for questions about how to correctly allocate multi-dimensional arrays dynamically. Array decay and array versus pointer etc were already covered by fairly good "canonical duplicates".

[user694733]

Well written and needed answer. But one thing bugs me: Why mention bsearch/qsort? Those are intended to operate on single dimension. If you use them to sort pointers on first dimension of p2p array, it works as well as sorting rows on 2D array, assuming user defines appropriate comparison function and gives valid arguments.

[Lundin]

@user694733 Well of course you could dodge the problem by handling the access in the passed function, bsearch/qsort are quite flexible. But suppose that you would for example want to search/sort through a generic chunk of raw data. You can do this just fine by passing a n-dimensional array to bsearch/qsort. Or suppose you have a n-dimensional array of uint32_t and want to search for individual byte values. Sort pixels in a graphical bitmap by color etc etc.

[Lundin]

Another point here is that if you pass a true n-dimensional array to those functions, it will still work, because int array[x][y][z] is actually a single dimension array. It is a 1D array of x items with type int [y][z].

[user694733]

OK, I see what you mean. I was going to suggest that you that add to the answer, but maybe it's not that necessary. It's already a long answer, and main point is more important.

[StoryTeller - Unslander Monica]

"saving you the fuss of implementing binary search and quick sort yourself" - nitpick, but qsort isn't obligated to be implemented as quicksort. That sentence may mislead people into thinking things about the memory/time footprint of the function that they shouldn't.

[Lundin]

@RestlessC0bra 1) Correct, although the definition of what's "rows" and what's "columns" lies in the application. The C standard only requires that there are y contiguous segments of x contiguous variables of the given type. 2) Correct. 3) Indeed - a pointer to a VLA does not necessarily have to point at an object with automatic storage duration, or even to a VLA. A pointer of the form type (*name)[n] where n is a run-time value, can be set to point to any array of the same type and size, no matter where it is allocated.

[Lundin]

@RestlessC0bra If it isn't allocated in contiguous memory, it is not an array. The essence of this whole post was to straighten our that incorrect belief.

[Toby]

@Lundin Great write-up! Always impressed by the comprehensiveness of your C knowledge and your ability to explaining things so well!

[Seek Addo]

@Lundin since when did you realise you were doing it wrong and acquired all this deep understanding.? Well written answer, worth following your page,i have learnt alot. I have always had the wrong idea, i thought the pointer-to-pointer was faster and efficient.

[Ilja Everilä]

I have to agree with @user694733, and add that the whole "We can't use standard library functions that excepts an array type (memcpy, memset, strcpy, bsearch, qsort and so on)." sounds too broad. memcpy, qsort etc. work nicely for array of pointer to T, or in other words pointer to pointer to T pointing to first element of such. While you'd make "shallow" copies only, it is very useful for strings for example. For some situations sorting an array of pointers can be beneficial, compared to moving arrays around. Still, an excellent writeup.

[chux - Reinstate Monica]

Alternative to *aptr = malloc( sizeof(int[x][y]) );, use *aptr = malloc(sizeof **aptr); to match the idiomatically correct pointer = malloc(sizeof *pointer);.

[M.M]

You say "The formal definition of an array is found..." but then you quote the formal definition of array type. In fact the standard doesn't formally define array anywhere.

[Ajay Brahmakshatriya]

Instead of having a pointer to int[x][y], wouldn't it be better to have a pointer to int[y]? Saves an extra dereference while using (mainly avoids confusion). I agree it strips the outermost size information.

[Lundin]

@AjayBrahmakshatriya Yes that's a common trick, but I didn't use it on purpose here, as the reader might be unfamiliar with array pointers in the first place.

[Lundin]

How does that answer the question "what is wrong with this method of dynamically allocating 2D arrays/arrays of arrays"?

[Basile Starynkevitch]

2D arrays don't exist.

[Lundin]

It is a very common industry de facto standard term, meaning array of arrays. Still, the question does not contain an array of arrays, which is the whole point here. If you wish to clutter down this post then at least add something meaningful. It is completely unclear how flexible array members can be a useful solution here or what their benefit would be.

[Basile Starynkevitch]

The solution is not in flexible array members, but in defining and implementing some abstract data type. In this answer I am using flexible array members, but the OP could use some other approach. I am not even trying to guess what is the original problem of OP and what abstract data type he should consider (because I don't have the text of the homework given to OP).

[Lundin]

Rather, you are using a C90 "mangled array", which is not a modern C, we've had pointers to VLA for almost 20 years. Further, the ADT solution suffers from very poor access times, since you effectively block any possibility of data cache use when iterating through the container. And it isn't possible to grab blocks of data from the matrix either. Although I agree that the ADT is a good solution system design-wise, the performance will be very poor.

[Basile Starynkevitch]

I don't see how the ADT solution suffers from poor access times. The functions could be inlined if efficiency is a concern.

[Lundin]

It will most likely not get inlined by the compiler. Even if it was and this doesn't screw up cache access, you still have multiple extra branches per iteration, killing performance.

[Andrew Henle]

Repeated calls of malloc to allocate several segments leads to heap fragmentation, which in turn results in poor use of RAM memory It's almost trivial to dynamically allocate an N-dimensional "array" with only N+1 calls to malloc(), and it's possible though not trivial to allocate one with a single call.

[Varad Bhatnagar]

Thank you for such a detailed answer. Cleared all my misconceptions.

[Bob__]

I think that this answer could be improved (if you are still interested in) by showing a minimal implementation and the use cases were an abstract data type could be used (while a VLA cant), like as a member of a struct or in an array or simply as a return value.

[bca]

@Lundin int (*arr)[5]; printf("%d\n", &arr[0]); printf("%d\n", &arr[1]); It prints 0 and 20 Is it possible when you do type (*ptr)[x][y] you set step size(++ptr) as y * sizeof(type)? When I tried same thing in 2D array I observed same thing.

[Et7f3XIV]

we can malloc un big table for instance 301x301 and we can do math for acces the logically (200, 100) with the index 100 * 300 + 200. With this logic we can have a unique call to malloc and with this math trick that we can hide in MACROs to access like before. And because it is contigus we can use memset or calloc to empty (and not having to create ou own function: like arr_alloc and arr_free in the first message)

[Eric Postpischil]

“C don't have multidimensional arrays” is akin to saying C does not have negative numbers. Check the grammar; there are no negative constants. You can only use positive constants and apply the unary - operator. Of course C does have negative numbers, and it does have multidimensional arrays. Both are simply built from primitives instead of being primitives themselves.

[anastaciu]

Very detailed and compreensive aswer, deserves UV.

[Andrew Henle]

C doesn't have multidimensional arrays? I think you're driving pedantry a bit too far with that. Per 6.5.2.1 Array subscripting, paragraph 3 of the C 11 standard (bolding mine): "Successive subscript operators designate an element of a multidimensional array object. If E is an n-dimensional array (n >= 2) with dimensions i x j x . . . x k, then E (used as other than an lvalue) is converted to a pointer to an (n - 1)-dimensional array ..." If the C standard can use the term "multidimensional array object"...

[Andrew Henle]

(cont) saying multidimensional arrays aren't primitive objects is about as useful as saying a struct or union isn't a primitive object.

[ryyker]

@chux - Regarding your comment on idiomatic alternative - Its interesting that In my environment, while using a break-point, to observe value of sizeof **aptr it indicates0 as opposed to observing sizeof(int[x][y]), where value shows what is expected. This causes me to wonder how the malloc() call was able to determine the correct value. (nevertheless memory seems to have been allocated correctly) Paradoxically, with this, for example: int *pptr = malloc( sizeof *pptr );, the value shows correctly, as expected.

[chux - Reinstate Monica]

@ryyker "while using a break-point, " --> I suspect the debugger. I find them buggy from time to time. (Of course if x, or y were 0, at that time, then 0 is the right size.)

[ryyker]

@chux - yes, debuggers can be buggy, but in this case, the statements were both looked at in the same executable, two lines away from each other. And x,y were defined at the time the **aptr was looked at. However, you may be right that this is an artifact of how my debugger interprets pointers configured and viewed in this way. i.e. my variable browser does not show any depth or width for on the *aptr array until locations are populated with non-zero values. Once populated, I can see a fully expanded tree of all the locations and their values. Normal

[cesss]

Very good answer, it helps clear a lot of confusion. The only thing I miss is to mention the flattened single-dimension approach to multidimensional arrays. Even if you cannot use with them the same syntax as in true multidimensional arrays (this would require a cast whose defined behaviour I wouldn't be sure about), however, with the only drawback of losing Ndim syntax, you can get all the same performance benefits as in VLAs. So, flattened arrays are a good approach when you work in a project where VLAs are not permitted for some reason.

[Lundin]

@cesss I left them ("mangled/flattened 2D arrays") out on purpose since I consider them old C90 style and the code turns less readable if they are used. It is true that they should be as fast as pointer to VLA style on modern compilers though (wasn't always the case back in the days). It looks like the C committee has come to their senses and will make VLA types (but not necessarily VLA allocated on the stack) mandatory once more in the upcoming C23 standard, so we are once again running out of reasons not to use pointer to VLA.

[cesss]

@Lundin I'm very happy to know the news, and I really hope C23 defines a way for using VLAs in a completely stack-safe fashion. It was very unfortunate to get a nice feature as VLAs but that it lasted only until people realized their stack-related risks.

[Lundin]

@cesss See proposal n2778. I'm not in the committee, but from what I hear this has been "voted in".