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.