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 make it 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:

1. 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].

2. 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 return that element.

3. Equivalently for any pointer p, *p can be alternatively be written as p[0]. This equivalence allows a one dimensional array to be dynamically allocated and have the [] syntax still work:

   int *p3 = malloc( 3 * sizeof(int) );
   // ...
   p3[i] = 42;    // as if: *(p3 + i) = 42;
   

   This equivalence is 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 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 do this is:

void** matrix2_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 = matrix2_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.

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 matrix2_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 do this is:

void** matrix2_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 matrix2_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 sizeof(T). (A lot of implementations I’ve seen omit this and just so happen to work by luck because sizeof(T) ≤ sizeof(void*).)

The code to do this is 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** matrix2_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( char, 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 = matrix2_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 matrix2_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() functions that takes the number of dimensions as a parameter. (These are left as exercises for the reader.)