Dynamically Allocating 2D Arrays Efficiently (and Correctly!) in C
Tags: c
Published: 2023-06-17 21:25:00

---
title: Dynamically Allocating 2D Arrays Efficiently (and Correctly!) in C
published: true
description: How to dynamically allocate two dimensional arrays efficiently (and correctly).
tags: #c
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-06-15 12:37 +0000
---

## Introduction

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

```c
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](https://en.wikipedia.org/wiki/Syntactic_sugar) of two-dimensional arrays, the compiler actually does:

```c
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_:

![2d matrix layout](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xtwh2xczfjbdibaq5jct.png)

(This is known as [row-major order](https://en.wikipedia.org/wiki/Row-_and_column-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:

1. The name of an array in an expression “decays” into a pointer to its first element.  For example:
    ```c
    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 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.

3. 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:
    ```c
    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_](https://www.bell-labs.com/usr/dmr/www/chist.html), 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:

![2D matrix v1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i7b5140s6jib0rhdcljr.png)

The code to implement this is:
```c
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:
```c
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 `int`s 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_ &le; _J_ so you get the most elements per pointer.
>
> On the other hand, if you just need a [triangular matrix](https://en.wikipedia.org/wiki/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_ &ge; 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:

![2D matrix v2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/shs5ts5er98eb1erj0wn.png)

The code to implement this is:
```c
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:

![2D matrix v3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bsd8f51rohncso4t8fys.png)

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](https://en.wikipedia.org/wiki/Data_structure_alignment).

Specifically, `&elements[0][0]` _must_ be properly aligned — which means `ptrs_size` _must_ be rounded up to be a multiple of [`_Alignof(T)`](https://en.cppreference.com/w/c/language/_Alignof).  (A lot of implementations I’ve seen omit this and just so happen to work by luck because `_Alignof(T)` &le; `sizeof(void*)`.)

The code to implement this with proper alignment is:
```c
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):

```c
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:

```c
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](https://dev.to/pauljlucas/dynamically-allocating-2d-arrays-in-c-36c5).