Dynamically Allocating 2D Arrays Efficiently (and Correctly!) in C

Introduction

Like many other programming languages, C supports multidimensional arrays (matrices). However, it uses an unconventional syntax for it:

int a2d[3][3];  // not: a2d[3,3]

That is, we put each dimension within its own pair of []. Conceptually, think of 2D matrix as an array of arrays. Under the hood, memory is (always) one-dimensional. To implement the syntactic sugar of two-dimensional arrays, the compiler actually does:

int *const a1d = &a2d[0][0];

a2d[i][j] = 0;  // really: a1d[ i * 3 + j ]

That is in C, all the elements are allocated contiguously such that a2d[i][0] and a2d[i][1] are adjacent in memory for a given row i:

(This is known as row-major order.) Given that, the compiler can calculate the address of a2d[i][j] by multiplying i by the length of the row (in this case, 3), then adding j — all scaled by sizeof(T) where T is the element type.

This all works fine for statically allocated 2D matrices where the dimensions are known at compile-time, but what if we don’t know the dimensions at compile-time? We then have to dynamically allocate it. But all C has is malloc() that simply allocates the given number of bytes. How can we allocate the right number of bytes? And how would the compiler know how big each row is to calculate an element’s address so that the [][] syntax still works?

Arrays & Pointers in C

There are a couple of quirky features of C when it comes to arrays and pointers:

The name of an array in an expression “decays” into a pointer to its first element. For example:
```
int a1d[3];
int *p = a1d;  // as if: p = &a1d[0]
```
That is, the name a1d is a shorthand for &a1d[0].
The a1d[i] syntax for arrays is just syntactic sugar for *(a1d+i). That is, take a1d (which is the address of its first element), add sizeof i elements to that address, then dereference that element.

Since addition is commutative, *(a1d+i) can be alternatively written as *(i+a1d); that in turn can be written as i[a1d]. Writing it this way has no practical use. It’s just even even quirkier consequence of the [] syntactic sugar.
Equivalently for any pointer p, *p can be alternatively written as p[0] (which is a degenerate case of *(p+0)). More generally, p[i] is the element at the memory address p plus the offset of i scaled by sizeof(T). This equivalence allows a one dimensional array to be dynamically allocated and have the [] syntax still work:
```
int *p = malloc( 3 * sizeof(int) );
// ...
p[i] = 42;     // as if: *(p + i) = 42;
```
This equivalence is a remnant of how pointers are dereferenced in New B (the precursor to C). See The Development of the C Language, Dennis M. Ritchie, April, 1993.

These quirky features of C allow a multidimensional array to be dynamically allocated and have the [][] syntax still work. But how?

Initial Implementation

The trick is instead of allocating a matrix of elements directly, allocate an array of i pointers (one for each row) where each pointer points to an allocated array of j elements for that row:

The code to implement this is:

void** matrix2d_new( size_t esize, size_t idim, size_t jdim ) {
  size_t const ptrs_size = sizeof(void*) * idim;
  size_t const row_size = esize * jdim;
  void **const rows = malloc( ptrs_size );
  for ( size_t i = 0; i < idim; ++i )
    rows[i] = malloc( row_size );
  return rows;
}

Given that:

int **m2d = matrix2d_new( sizeof(int), 3, 3 );
// ...
m2d[i][j] = 42;    // as if: *(*(m2d + i) + j) = 42

That is, m2d[i] yields a pointer to the ith row array of ints that we then index by j. Otherwise unnecessary parentheses can be added as (m2d[i])[j] to make this clearer.

One caveat is that, unlike a statically allocated 2D matrix, a dynamically allocated 2D matrix uses additional memory for the row pointers. Therefore whenever possible for a matrix with dimensions [I][J], make I ≤ J so you get the most elements per pointer.

On the other hand, if you just need a triangular matrix, then it’s possible to write a variant of matrix2d_new() that allocates only i elements for row i. This will only use memory for N(N+1)/2 elements (if we include the diagonal elements, or N(N-1)/2 if not), plus N pointers. For a triangular matrix where N ≥ 4, this yields a memory savings.

However, while this implementation is straightforward, the problems with this implementation are that it requires i + 1 calls to malloc() and we’d need to write a corresponding matrix2d_free() function that calls free() an equal number of times.

Better Implementation

If you look at the first illustration, you might realize that there’s no reason the row arrays can’t be coalesced into a single chunk of memory. The row pointers just have to point at the [i][0] element for each row:

The code to implement this is:

void** matrix2d_new( size_t esize, size_t idim,
                     size_t jdim ) {
  size_t const ptrs_size = sizeof(void*) * idim;
  size_t const row_size = esize * jdim;
  void **const rows = malloc( ptrs_size );
  char *const elements = malloc( idim * row_size );
  for ( size_t i = 0; i < idim; ++i )
    rows[i] = &elements[ i * row_size ];
  return rows;
}

Declaring elements as char* rather than void* is necessary because we can’t do pointer arithmetic using void*. We need char* specifically because we’re working in terms of bytes.

This is better in that we now only need exactly two calls to malloc(), but we still need to write a corresponding matrix2d_free() function.

Best Implementation

If you look at the second illustration, you might eventually wonder whether the row pointers and elements can be coalesced into one chunk of memory. Yes, they can, but with a pitfall:

The pitfall is shown as the shaded area between the row pointers and the elements. This is padding that may be necessary to ensure that the elements are properly aligned.

Specifically, &elements[0][0] must be properly aligned — which means ptrs_size must be rounded up to be a multiple of _Alignof(T). (A lot of implementations I’ve seen omit this and just so happen to work by luck because _Alignof(T) ≤ sizeof(void*).)

The code to implement this with proper alignment is:

size_t round_up_to( size_t n, size_t multiple ) {
  size_t const remainder = n % multiple;
  return remainder == 0 ? n : n + multiple - remainder;
}

void** matrix2d_new( size_t esize, size_t ealign,
                     size_t idim, size_t jdim ) {
  // ensure &elements[0][0] is suitably aligned
  size_t const ptrs_size = round_up_to( sizeof(void*) * idim, ealign );
  size_t const row_size = esize * jdim;
  // allocate the row pointers followed by the elements
  void **const rows = malloc( ptrs_size + idim * row_size );
  char *const elements = (char*)rows + ptrs_size;
  for ( size_t i = 0; i < idim; ++i )
    rows[i] = &elements[ i * row_size ];
  return rows;
}

Notice that the function takes a new ealign parameter that’s _Alignof(T) (or alignof(T) when stdalign.h is included):

int **m2d = matrix2d_new( sizeof(int), alignof(int), 3, 3 );

This is the best implementation because we now need only one call to malloc() and we don’t need a special matrix2d_free() function: an ordinary free() will do.

Conclusion

The quirky interplay between arrays and pointers in C allows dynamically allocating multidimensional arrays efficiently while still allowing the [][] syntax to work.

Note that we could write matrix3d_new() to dynamically allocate a 3D matrix by using an array of pointers to arrays of pointers to elements; and so on for any number of dimensions; or even a completely generic matrixNd_new() function that takes the number of dimensions as a parameter. (These are left as exercises for the reader.)

Epilogue

If the aforementioned cost of the additional row pointers is too much for your use-case, you can eliminate them, but you have to sacrifice the use of the [][] syntax and write your own accessor function that does what the compiler does under the hood, something like:

inline void* m2da( void *m2d, size_t esize, size_t row_size,
                   size_t i, size_t j ) {
  return &((char*)m2d)[ (i * row_size + j) * esize ];
}

void f() {
  int *m2d = malloc( sizeof(int) * 3 * 3 );
  // ...
  *(int*)m2da( m2d, sizeof(int), 3, i, j ) = 0;
}

But that’s pretty ugly. Like many other things in computer science, it’s a trade-off.

In C++, you can eliminate the row pointers and still use the [][] syntax by use of templates and overloading operator[](), but that’s a story for another time.