Generic dynamic array implementation in C

Question

I'm working on my own generic-type dynamic array in C99 and I would like to hear your input, suggestions, ideas, anything!

What I most care about is: 1) correctness and 2) performance.

So far, I've tested both with standard malloc and mimalloc, although with the standard implementation it seems to be running 50% faster.

I've also ran benchmarks against libsrt, vec and Nim's implementation of dynamic sequences and my code seems to be beating them all.

Also, of major importance is to note that this code is not meant to be used as a library, but as part of a bytecode VM/intepreter that I've been working on - which means I am the one who is going to use it.

Here's the source:

#ifndef __VARRAY_H__
#define __VARRAY_H__

/**************************************
  Type definitions
 **************************************/

#define Array(TYPE) \
    struct { \
        size_t size; \
        size_t cap; \
        size_t typeSize; \
        TYPE *data; \
    }

/**************************************
  Macros
 **************************************/

#define aInit(DEST,TYPE,CAP) { \
    int k=0;                                                                \
    while (powerOfTwo[++k]<CAP);                                            \
                                                                            \
    DEST = malloc(sizeof(Array(TYPE)));                                     \
    DEST->size = 0;                                                         \
    DEST->typeSize = sizeof(TYPE);                                          \
    DEST->cap = powerOfTwo[k];                                              \
    DEST->data = calloc(DEST->cap, DEST->typeSize);                         \
}

#define aNew(NAME,TYPE,CAP) \
    Array(TYPE)* NAME;                                                      \
    aInit(NAME,TYPE,CAP);

#define aResize(DEST) { \
    DEST->cap *= 2;                                                         \
    DEST->data = realloc(DEST->data, DEST->cap * DEST->typeSize);           \
}

#define aAdd(DEST,X) \
    if (++(DEST->size) >= DEST->cap) aResize(DEST);                         \
    DEST->data[DEST->size-1] = X

#define aAppend(DEST,X) \
    DEST->cap += X->cap;                                                    \
    DEST->data = realloc(DEST->data, DEST->cap * DEST->typeSize);           \
    memcpy(DEST->data + DEST->size, X->data, X->size * X->typeSize);        \
    DEST->size += X->size

#define aEach(DEST,INDEX) \
    for (int INDEX=0; INDEX<DEST->size; INDEX++)

#define aFree(DEST) \
    free(DEST->data);                                                       \
    free(DEST)

#endif

The powerOfTwo lookup constant:

/**************************************
  Constants
 **************************************/

static size_t powerOfTwo[] = {
    0,
    1, 2, 4, 8, 16, 32, 64, 128,
    256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
    65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
    16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
    4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888
};

And a little usage example:

Array(int)* arr;
aInit(arr,int,0);
aAdd(arr,0);
aAdd(arr,1);

aEach(fastArr,i) {
    printf("item @ %d = %d\n",i,arr->data[i]);
}

aFree(arr);

Answer 1

See this Stackoverflow answer for a discussion on the optimal growth factor for dynamic arrays. The gist of it is that it depends, but growth factors around the golden ratio are easier for the memory allocator to handle. I'd recommend using 1.5 because it is easy to implement:

DEST->cap += DEST->cap / 2

It likely fares worse on artifical benchmarks but better on real workloads. This requires that the minimum capacity of the dynamic array is 2 which is reasonable. But a more realistic minimum size likely should be 8 or 16 since the minimum malloc size is 32 bytes.

In aAppend you are always realloc:ing which will cause performance to suffer if many small dynamic arrays are collected into one big one in a loop. Instead, you want something like:

size_t req = DEST->size + X->size;
if (req > DEST->cap) {
    aResize(DEST);
}
memcpy(DEST->data + DEST->size, X->data, X->size * X->typeSize);
DEST->size = req;

The last thing I'd change is the alignment of the capacity to a power of two in aInit. On realistic workloads, a good chunk of all variable arrays never grow so the alignment just wastes space. But if you insist on alignment, this function is better than the loop:

static inline int
next_pow2(int v) {
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;
}

I also wonder why you are using macros when C99 has inline functions? They have many advantages in comparison to code macros.

Answer 2

We're missing an include of <stddef.h> to define size_t (or any of the other headers which define it).

We're missing an include of <stdlib.h>, needed for malloc() and friends (and this would define size_t for us, too).

With those fixed, and sufficient minor changes to the test program, I managed to compile with only a few warnings.

DEST = malloc(sizeof(Array(TYPE)));                                     \
DEST->size = 0;                                                         \

Oops! If malloc() returns a null pointer, we have undefined behaviour. Replace with

DEST = malloc(sizeof(Array(TYPE)));                                 \
if (DEST) {                                                         \
    DEST->size = 0;                                                 \

Similarly, when we delete, let's accept a null pointer:

#define aFree(DEST)                             \
    if (DEST) {                                 \
        free(DEST->data);                       \
    }                                           \
    free(DEST)

We have a dangerous realloc():

#define aResize(DEST) { \
    DEST->cap *= 2;                                                         \
    DEST->data = realloc(DEST->data, DEST->cap * DEST->typeSize);           \
}

If the realloc() fails, then we have a null pointer in data and no way to access the old contents. The standard idiom is to check the return value before assigning it to data. We're going to need some way to report failure, too.

In aAppend(), we should be using the aResize() we've defined instead of resizing to fit - as it is, we're going to reallocate on every single call.

---

Overall, I think that writing everything as macros is a poor choice. It's probably better to use macro expansion (or equivalent technique, such is multiple includes with varying definitions) to create a set of (small, inlinable) functions for a given type.

The macros we have here look like functions, but can't be used like functions (in particular, aNew expands to a declaration and a statement, and aAdd and aFree both expand to multiple statements, making them dangerous and confusing near conditionals.

It's frustrating that the array control block must be allocated from dynamic memory - C++ programmers expect to be able to create std::vector objects on the stack, with only the object storage itself on the heap.