Using macros to implement a generic vector in C. Is this a good idea?

Question

I am a programmer who knows both C and C++. I have used both languages in my own projects but I do not know which one I prefer.

When I program in C the feature that I miss the most from C++ is std::vector from the STL (Standard Template Library)

I still haven't figured out how I should represent growing arrays in C. Up to this point I duplicated my memory allocation code all over the place in my projects. I do not like code duplication and I know that it is bad practice so this does not seems like a very good solution to me.

I thought about this problem some time ago and came up with the idea to implement a generic vector using preprocessor macros.

This is how the implementation looks:

#ifndef VECTOR_H_
#define VECTOR_H_

#include <stdlib.h>
#include <stdio.h>

/* Declare a vector of type `TYPE`. */
#define VECTOR_OF(TYPE) struct { \
    TYPE *data; \
    size_t size; \
    size_t capacity; \
}

/* Initialize `VEC` with `N` capacity. */
#define VECTOR_INIT_CAPACITY(VEC, N) do { \
    (VEC).data = malloc((N) * sizeof(*(VEC).data)); \
    if (!(VEC).data) { \
        fputs("malloc failed!\n", stderr); \
        abort(); \
    } \
    (VEC).size = 0; \
    (VEC).capacity = (N); \
} while (0)

/* Initialize `VEC` with zero elements. */
#define VECTOR_INIT(VEC) VECTOR_INIT_CAPACITY(VEC, 1)

/* Get the amount of elements in `VEC`. */
#define VECTOR_SIZE(VEC) (VEC).size

/* Get the amount of elements that are allocated for `VEC`. */
#define VECTOR_CAPACITY(VEC) (VEC).capacity

/* Test if `VEC` is empty. */
#define VECTOR_EMPTY(VEC) ((VEC).size == 0)

/* Push `VAL` at the back of the vector. This function will reallocate the buffer if
   necessary. */
#define VECTOR_PUSH_BACK(VEC, VAL) do { \
    if ((VEC).size + 1 > (VEC).capacity) { \
        size_t n = (VEC).capacity * 2; \
        void *p = realloc((VEC).data, n * sizeof(*(VEC).data)); \
        if (!p) { \
            fputs("realloc failed!\n", stderr); \
            abort(); \
        } \
        (VEC).data = p; \
        (VEC).capacity = n; \
    } \
    (VEC).data[VECTOR_SIZE(VEC)] = (VAL); \
    (VEC).size += 1; \
} while (0)

/* Get the value of `VEC` at `INDEX`. */
#define VECTOR_AT(VEC, INDEX) (VEC).data[INDEX]

/* Get the value at the front of `VEC`. */
#define VECTOR_FRONT(VEC) (VEC).data[0]

/* Get the value at the back of `VEC`. */
#define VECTOR_BACK(VEC) (VEC).data[VECTOR_SIZE(VEC) - 1]

#define VECTOR_FREE(VEC) do { \
    (VEC).size = 0; \
    (VEC).capacity = 0; \
    free((VEC).data); \
} while(0)

#endif /* !defined VECTOR_H_ */

This code goes in the header file called "vector.h".

Note that it does miss some functionality (like VECTOR_INSERT and VECTOR_ERASE) but I think that it is good enough to show my concept.

The use of the vector looks like this:

int main()
{
    VECTOR_OF(int) int_vec;
    VECTOR_OF(double) dbl_vec;
    int i;

    VECTOR_INIT(int_vec);
    VECTOR_INIT(dbl_vec);

    for (i = 0; i < 100000000; ++i) {
        VECTOR_PUSH_BACK(int_vec, i);
        VECTOR_PUSH_BACK(dbl_vec, i);
    }

    for (i = 0; i < 100; ++i) {
        printf("int_vec[%d] = %d\n", i, VECTOR_AT(int_vec, i));
        printf("dbl_vec[%d] = %f\n", i, VECTOR_AT(dbl_vec, i));
    }

    VECTOR_FREE(int_vec);
    VECTOR_FREE(dbl_vec);

    return 0;
}

It uses the same allocation rules as std::vector (the size starts as 1 and then doubles each time that is required).

To my surprise I found out that this code runs more than twice as fast as the same code written using std::vector and generates a smaller executable! (compiled with GCC and G++ using -O3 in both cases).

My questions to you are:

• Are there any serious faults with this approach?
• Would you recommend using this in a serious project?
• If not then I would like you to explain why and tell me what a better alternative would be.

Answer 1

To my surprise I found out that this code runs more than twice as fast as the same code written using std::vector and generates a smaller executable! (compiled with GCC and G++ using -O3 in both cases).

There are three reasons why your C version is faster/smaller than the C++ version:

1. The implementation of new in the standard C++ library that is used by g++ is suboptimal. If you implement void* operator new (size_t size) as a call-through to malloc() you get better performance than with the built-in version.

2. If realloc() has to use a new chunk of memory, it moves the old data over in the fashion of memmove(), i. e. it ignores the logical structure of the data and simply moves the bits. That operation can easily be accelerated to the point that the memory bus is the bottleneck. std::vector<>, on the other hand, must take care of possibly calling constructors/destructors correctly, it can't just call through to memmove(). In the case of int and double that boils down to moving the data one int/double at a time, the loop is in the code generated for the std::vector<>. That is not too bad, but its worse than using SSE instructions which a good memmove() implementation will do.

3. The realloc() function is part of the standard C library which is dynamically linked to your executable. The memory management code generated by std::vector<>, however, is precisely that: generated. As such, it must be a part of your executable.

Are there any serious faults with this approach?

This is a matter of taste, but I think, the approach is smelly: Your macro definitions are far away from their uses, and they do not all behave like simple constants or inline function. In fact, they act suspiciously like elements of a programming language (i. e. templates), which is not a good thing for preprocessor macros. It is generally a bad idea to try to modify the language by use of the preprocessor.

You also have a serious issue with your macro implementations: The VECTOR_INIT_CAPACITY(VEC, N) macro evaluates its VEC argument four times and the N argument twice. Now think about what happens if you do a call VECTOR_INIT_CAPACITY(foo, baz++): The size stored in the capacity field of the new vector will be larger than the size of the memory allocated for it. The line with the malloc() call will increment the baz variable, and that new value will be stored in the capacity member before baz is incremented a second time. You should write all macros in a way that the evaluate their arguments exactly once.

Would you recommend using this in a serious project?

I think, I wouldn't bother. The realloc() code is trivial enough that some replications won't hurt too much. But again, your mileage may vary.

If not then I would like you to explain why and tell me what a better alternative would be.

As I said before, I wouldn't bother trying to write a general container class in the style of std::vector<>, neither by (ab)using the preprocessor, nor by (ab)using void*.

But I would take a close look at the memory handling on the system that I write for: With many kernels, it is extremely unlikely that you ever get a return value of NULL out of a malloc()/realloc() call. They over-commit their memory, making promises they cannot be certain to be able to fulfill. And when they realize that they can't back up their promises, they start shooting processes via the OOM-killer. On such a system (linux is one of them), your error handling is simply pointless. It will never get executed. As such, you can avoid the pain of adding it and replicating it to all the places where you need a dynamically growing array.

My memory reallocation code in C usually looks something like this:

if(size == capacity) {
    array = realloc(array, (capacity *= 2) * sizeof(*array));
}
array[size++] = ...;

Without the functionless error handling code, this is so short that it can safely be replicated as many times as it is needed.