Multi-dimensional dynamically allocated arrays in C

Creating multi-dimensional arrays in C with malloc or calloc can be challenging. Suppose we need an array dimensioned [kmax][jmax][imax]. There are at least a couple of ways of doing it.

Here is the straightforward way:

dat = (float ***)calloc((size_t)kmax, sizeof(float **));
for (k = 0; k < kmax; k++) {
    dat[k] = (float **)calloc((size_t)jmax, sizeof(float *));
    if ( !dat[k] ) {
	fprintf(stderr, "Could not allocate memory.\n");
	exit(1);
    }
    for (j = 0; j < jmax; j++) {
	dat[k][j] = (float *)calloc((size_t)imax, sizeof(float));
	if ( !dat[k][j] ) {
	    fprintf(stderr, "Could not allocate memory.\n");
	    exit(1);
	}
    }
}

Above method is safe and straightforward, but it calls calloc a total of kmax + kmax * jmax times. That might be a lot of system overhead.

The next method takes a bit more bookkeeping, but it only makes one allocation for each dimension:

dat = (float ***)calloc((size_t)kmax, sizeof(float **));
if ( !dat ) {
    fprintf(stderr, "Could not allocate memory.\n");
    exit(1);
}
dat[0] = (float **)calloc((size_t)(kmax * jmax), sizeof(float *));
if ( !dat[0] ) {
    fprintf(stderr, "Could not allocate memory.\n");
    exit(1);
}
dat[0][0] = (float *)calloc((size_t)(kmax * jmax * imax), sizeof(float));
if ( !dat[0][0] ) {
    fprintf(stderr, "Could not allocate memory.\n");
    exit(1);
}
for (n = 1; n < kmax; n++) {
    dat[n] = dat[n - 1] + jmax;
}
for (n = 1, ne = kmax * jmax; n < ne; n++) {
    dat[0][n] = dat[0][n - 1] + imax;
}

The resulting array is equivalent to that produced in the previous example. The loops that set up the indexing are a bit obscure. To help visualize what is happening, look at this cartoon version for kmax = 2, jmax = 3, imax = 4. (made with memtoon.c, which is in alloc_cmp.tar.gz)

The smaller number of calls to calloc should speed array creation. It will also be more contiguous, which might speed access. However, this approach is tricky, because calloc (and malloc) expect size_t (usually the same as unsigned long) arguments, but pointer arithmetic implicitly casts addends to long, which might overflow when given unsigned values.

Is the second method significantly faster? Tar ball alloc_cmp.tar.gz contains some programs that compare the two. Extract the files from the tar ball, cd into alloc_cmp, put some dimension sizes into sizes.h, and run make time. This will produce two applications, frag, that makes a three dimensional array using the first method, and contg that does the same using the second method. Both programs then assign some arbitrary values and print some meaningless output. The unix time application reports how long each takes.

I ran the comparisons on various machines available to me. The frag application always took longer - 10% to 100% longer, depending on the system. So, making individual allocations per the first method will noticeablely slow a process that creates and destroys a lot of large arrays. Optimization often leads to needless confusion, but sometimes it is worth while.

If you see any bugs or have any comments, drop me a line. (gcarrie)