N-Dimensional Array Allocation in C

Posted: 31 May 2013

Tagged: C Snippet

As languages go, C is not well known for its support of multi-dimensional arrays. While recent standards updates in the C99 and C11 releases have increased the support for allocation and use of both statically and dynamically allocated arrays using the type name[size1][size2]...[sizen] syntax, it retains significant limitations. The biggest of which is that it allocates the array entirely on the stack, limiting data scope and - in my experience - often leading to overflows.

When working with scientific codes, especially those which were originally written in Fortran with its efficient native Multi-Dimensional Array support, it is very common to run into applications that use heap allocated multi-dimensional arrays allocated more or less like this.

The result works fine for the main purpose of generating such an array, accessibility by the arr[i][j] syntax, just as though it were allocated on the stack with the first method. Even so, this method has significant downsides. Now we have len2+1 arrays which are likely non-contiguous in memory, hurting caching behavior and increasing allocation time. As a result, I find myself frequently writing little allocators to allocate a single flat array with the necessary references in it. While each of these is simple, it bothers me to have multiple copies of functions like alloc2d(...) and alloc3d and so-forth where it seems a single function should do.

Working with a particularly nasty code this week that uses multi-dimensional arrays of varying size and dimension from one to seven this week convinced me to finally do something about it. I make no claim that the following is optimal nor that it is pretty or as safe as possible, but it is a general multi-dimensional allocator in C.

The md_alloc() and md_free() functions have been tested to correctly manage arrays of up to 12 dimensions with a single allocation to store both the data and all associated pointer state. It may be complex, but no more duplicated allocator functions, finally! Now if only there were a way to get rid of the need for all the pointers in C as one does in c++ with the likes of boost::multi_array or blitz++. Maybe someday.

blog comments powered by Disqus