3
\$\begingroup\$

This library is a fork of eteran/c-vector. It is macro based, so that it is generic, without void pointers and additional functions. This of course means that it has the downsides of macros in C. The repository for the project is hosted here. It is still in its early stages, in the future I will upload the unit tests for the library, documentation, a readme and more C goodies. It passes all the tests (which are written with MinUnit), but we have found and fixed 2-3 sneaky bugs that the tests did in fact miss.

What I'm looking to get from this code review is feedback about the quality of the code, adherence to convetions, usage of C idioms and so on. A discussion of a potential implementation of the library using functions instead of macros is also welcome. Lastly, if this library is up to standard, feel free to use in your own projects, I hope that it saves you time (after all a list is very useful usually).

Here is the code:

#ifndef LIB_DYNAMIC_ARRAY_H
#define LIB_DYNAMIC_ARRAY_H

#ifndef DYNAMIC_ARRAY_malloc
#define DYNAMIC_ARRAY_malloc malloc
#endif

#ifndef DYNAMIC_ARRAY_realloc
#define DYNAMIC_ARRAY_realloc realloc
#endif

#ifndef DYNAMIC_ARRAY_free
#define DYNAMIC_ARRAY_free free
#endif

#ifndef DYNAMIC_ARRAY_GROWTH_FACTOR
#define DYNAMIC_ARRAY_GROWTH_FACTOR 1.5
#endif

#ifndef DYNAMIC_ARRAY_INITIAL_CAPACITY
#define DYNAMIC_ARRAY_INITIAL_CAPACITY 2
#endif

#include <stddef.h>
#include <assert.h>
#include <stdlib.h>

#ifdef NDEBUG

#define CHECK(_pointer)         \
    do {                        \
        if (!(_pointer))        \
        {                       \
            exit(EXIT_FAILURE); \
        }                       \
    } while (0)

#else

#include <stdio.h>
#include <errno.h>
#include <string.h>

#define CHECK(_pointer)                                                  \
    do {                                                                 \
        if (!(_pointer))                                                 \
        {                                                                \
            fprintf(stderr, "errno: %d\n%s\n", errno, strerror(errno));  \
            exit(EXIT_FAILURE);                                          \
        }                                                                \
    } while (0)

#endif

#define DYNAMIC_ARRAY_SIZE(dynamic_array)   \
    ((dynamic_array) ? ((size_t *)(dynamic_array))[-2] : (size_t)0)

#define DYNAMIC_ARRAY_CAPACITY(dynamic_array)   \
    ((dynamic_array) ? ((size_t *)(dynamic_array))[-1] : (size_t)0)

#define DYNAMIC_ARRAY_EMPTY(dynamic_array)  \
    (DYNAMIC_ARRAY_SIZE(dynamic_array) == 0)

#define DYNAMIC_ARRAY_PEEK(dynamic_array) \
    (dynamic_array)[DYNAMIC_ARRAY_SIZE(dynamic_array) - 1]

#define DYNAMIC_ARRAY_ALLOCATE(dynamic_array, requested_capacity)                                                               \
    do {                                                                                                                        \
        assert((requested_capacity) > 0);                                                                                       \
        const size_t _total_capacity = (requested_capacity) * sizeof(*(dynamic_array)) + (sizeof(size_t) * 2);                  \
        if (!(dynamic_array))                                                                                                   \
        {                                                                                                                       \
            const size_t * _dynamic_array_pointer = DYNAMIC_ARRAY_malloc(_total_capacity);                                      \
            CHECK(_dynamic_array_pointer);                                                                                      \
            (dynamic_array) = (void *)(&_dynamic_array_pointer[2]);                                                             \
            ((size_t *)(dynamic_array))[-1] = (requested_capacity);                                                             \
            ((size_t *)(dynamic_array))[-2] = 0;                                                                                \
        }                                                                                                                       \
        else                                                                                                                    \
        {                                                                                                                       \
            const size_t * _dynamic_array_pointer = DYNAMIC_ARRAY_realloc(&((size_t *)(dynamic_array))[-2], _total_capacity);   \
            CHECK(_dynamic_array_pointer);                                                                                      \
            (dynamic_array) = (void *)(&_dynamic_array_pointer[2]);                                                             \
            ((size_t *)(dynamic_array))[-1] = (requested_capacity);                                                             \
            if ((requested_capacity) < DYNAMIC_ARRAY_SIZE(dynamic_array))                                                       \
            {                                                                                                                   \
                ((size_t *)(dynamic_array))[-2] = (requested_capacity);                                                         \
            }                                                                                                                   \
        }                                                                                                                       \
    } while (0)

#define DYNAMIC_ARRAY_FREE(dynamic_array)       \
    do {                                        \
        assert(dynamic_array);                  \
        free(&((size_t *)(dynamic_array))[-2]); \
        (dynamic_array) = NULL;                 \
    } while (0)

#define DYNAMIC_ARRAY_RESERVE(dynamic_array, requested_capacity)            \
    do {                                                                    \
        assert((requested_capacity) > 0);                                   \
        if ((requested_capacity) > DYNAMIC_ARRAY_CAPACITY(dynamic_array))   \
        {                                                                   \
            DYNAMIC_ARRAY_ALLOCATE(dynamic_array, requested_capacity);      \
        }                                                                   \
    } while (0)

#define DYNAMIC_ARRAY_FIT(dynamic_array)                                                \
    do {                                                                                \
        assert(dynamic_array);                                                          \
        if(!DYNAMIC_ARRAY_EMPTY(dynamic_array))                                         \
        {                                                                               \
            DYNAMIC_ARRAY_ALLOCATE(dynamic_array, DYNAMIC_ARRAY_SIZE(dynamic_array));   \
        }                                                                               \
    } while (0)

#define DYNAMIC_ARRAY_PUSH_BACK(dynamic_array, value)                                                                                                   \
    do {                                                                                                                                                \
        const size_t _capacity_ = DYNAMIC_ARRAY_CAPACITY(dynamic_array), _size_ = DYNAMIC_ARRAY_SIZE(dynamic_array);                                    \
        if (_capacity_ == _size_)                                                                                                                       \
        {                                                                                                                                               \
            DYNAMIC_ARRAY_ALLOCATE((dynamic_array), !_capacity_ ? DYNAMIC_ARRAY_INITIAL_CAPACITY : (size_t)(_capacity_ * DYNAMIC_ARRAY_GROWTH_FACTOR)); \
        }                                                                                                                                               \
        (dynamic_array)[_size_] = (value);                                                                                                              \
        ((size_t *)(dynamic_array))[-2] = _size_ + 1;                                                                                                   \
    } while (0)

#define DYNAMIC_ARRAY_REMOVE_BACK(dynamic_array)                                                                                    \
    do {                                                                                                                            \
        assert((dynamic_array) && DYNAMIC_ARRAY_SIZE(dynamic_array) > 0);                                                           \
        ((size_t *)(dynamic_array))[-2] = ((size_t *)(dynamic_array))[-2] - 1;                                                      \
        if (DYNAMIC_ARRAY_SIZE(dynamic_array) == (size_t)(DYNAMIC_ARRAY_CAPACITY(dynamic_array) / DYNAMIC_ARRAY_GROWTH_FACTOR))     \
        {                                                                                                                           \
            DYNAMIC_ARRAY_FIT(dynamic_array);                                                                                       \
        }                                                                                                                           \
    } while (0)

#define DYNAMIC_ARRAY_POP_BACK(dynamic_array, destination)                  \
    do {                                                                    \
        assert((dynamic_array) && DYNAMIC_ARRAY_SIZE(dynamic_array) > 0);   \
        (destination) = DYNAMIC_ARRAY_PEEK(dynamic_array);                  \
        DYNAMIC_ARRAY_REMOVE_BACK(dynamic_array);                           \
    } while (0)

#define DYNAMIC_ARRAY_INSERT(dynamic_array, value, index)                                                       \
    do {                                                                                                        \
        const long _size = DYNAMIC_ARRAY_SIZE(dynamic_array), _move = (_size - 1 - (index));                    \
        assert((index) >= 0 && (index) <= _size);                                                               \
        if (_move)                                                                                              \
        {                                                                                                       \
            DYNAMIC_ARRAY_PUSH_BACK(dynamic_array, (dynamic_array)[_size - 1]);                                 \
            memmove(&(dynamic_array)[index + 1], &(dynamic_array)[index], _move * sizeof(*(dynamic_array)));    \
            (dynamic_array)[index] = (value);                                                                   \
        }                                                                                                       \
        else                                                                                                    \
        {                                                                                                       \
            DYNAMIC_ARRAY_PUSH_BACK(dynamic_array, value);                                                      \
        }                                                                                                       \
    } while (0)

#define DYNAMIC_ARRAY_REMOVE(dynamic_array, index)                                                                          \
    do {                                                                                                                    \
        const size_t _size = DYNAMIC_ARRAY_SIZE(dynamic_array);                                                             \
        assert((dynamic_array) && (index) >= 0 && (index) <= _size - 1);                                                    \
        memmove(&(dynamic_array)[index], &(dynamic_array)[index + 1], (_size - 1 - (index)) * sizeof(*(dynamic_array)));    \
        DYNAMIC_ARRAY_REMOVE_BACK(dynamic_array);                                                                           \
    } while (0)

#define DYNAMIC_ARRAY_ERASE(dynamic_array, index, destination)                                                              \
    do {                                                                                                                    \
        assert((dynamic_array) && (index) >= 0 && (index) < DYNAMIC_ARRAY_SIZE(dynamic_array));                             \
        (destination) = (dynamic_array)[index];                                                                             \
        DYNAMIC_ARRAY_REMOVE(dynamic_array, index);                                                                         \
    } while (0)

#define DYNAMIC_ARRAY_TRUNCATE(dynamic_array, requested_size)                               \
    do {                                                                                    \
        assert((dynamic_array) && (requested_size) < DYNAMIC_ARRAY_SIZE(dynamic_array));    \
        ((size_t *)(dynamic_array))[-2] = (requested_size);                                 \
    } while (0)

#define DYNAMIC_ARRAY_EXTEND(dynamic_array, requested_size, value)      \
    do {                                                                \
        assert((requested_size) > DYNAMIC_ARRAY_SIZE(dynamic_array));   \
        while (DYNAMIC_ARRAY_SIZE(dynamic_array) < (requested_size))    \
        {                                                               \
            DYNAMIC_ARRAY_PUSH_BACK(dynamic_array, value);              \
        }                                                               \
    } while (0)

#define DYNAMIC_ARRAY_RESIZE(dynamic_array, requested_size, value)                              \
    do {                                                                                        \
        assert((requested_size) >= 0 && (requested_size) != DYNAMIC_ARRAY_SIZE(dynamic_array)); \
        if (DYNAMIC_ARRAY_SIZE(dynamic_array) > (requested_size))                               \
        {                                                                                       \
            DYNAMIC_ARRAY_TRUNCATE(dynamic_array, requested_size);                              \
        }                                                                                       \
        else                                                                                    \
        {                                                                                       \
            DYNAMIC_ARRAY_EXTEND(dynamic_array, requested_size, value);                         \
        }                                                                                       \
    } while (0)

#define DYNAMIC_ARRAY_CLEAR(dynamic_array)              \
    do {                                                \
        assert(!DYNAMIC_ARRAY_EMPTY(dynamic_array));    \
        ((size_t *)(dynamic_array))[-2] = 0;            \
    } while (0)

#define DYNAMIC_ARRAY_COPY(destination, source)                                                                                                 \
    do {                                                                                                                                        \
        assert(!DYNAMIC_ARRAY_EMPTY(source));                                                                                                   \
        DYNAMIC_ARRAY_ALLOCATE(destination, DYNAMIC_ARRAY_SIZE(source));                                                                        \
        memcpy(&((size_t *)(destination))[-2], &((size_t *)(source))[-2], DYNAMIC_ARRAY_SIZE(source) * sizeof(*(source)) + 2 * sizeof(size_t)); \
    } while (0)

#define DYNAMIC_ARRAY_CONCATENATE(destination, source)                                                                          \
    do {                                                                                                                        \
        assert(source);                                                                                                         \
        if(DYNAMIC_ARRAY_EMPTY(destination))                                                                                    \
        {                                                                                                                       \
            DYNAMIC_ARRAY_COPY(destination, source);                                                                            \
        }                                                                                                                       \
        else                                                                                                                    \
        {                                                                                                                       \
            DYNAMIC_ARRAY_ALLOCATE(destination, DYNAMIC_ARRAY_SIZE(destination) + DYNAMIC_ARRAY_SIZE(source));                  \
            memcpy(&(destination)[DYNAMIC_ARRAY_SIZE(destination)], source, DYNAMIC_ARRAY_SIZE(source) * sizeof(*(source)));    \
            ((size_t *)(destination))[-2] = DYNAMIC_ARRAY_SIZE(source) + DYNAMIC_ARRAY_SIZE(destination);                       \
        }                                                                                                                       \
    } while (0)

#endif

Notes:

  • The reason I have defined macros for malloc(), calloc() and realloc() is that there is a possibility that alternative memory allocators may be used to improve performance, such as jemalloc.
  • Many macros access the size and capacity properties of the dynamic array, sometimes through the relevant macros, other do so directly. One of the two methods will be used for the sake of consistency, the functionality should be the same though.
  • The rule of thumb, in order to optimize for speed, was that if something is to fail internally, it should be checked explicitly. If the user makes an error in using a macro with inappropriate arguments, assertions are in place to assist in the debugging process, but no checks are in place. I am aware that if people use this library they will shoot themselves in the foot one way or another, is my approach acceptable?
  • The API provided is similar to C++'s std::vector, as well as eteran/c-vector, but the aim is for it to feel familiar, not to be exactly the same.
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Please provide your unit tests as part of the code to be reviewed. \$\endgroup\$
    – pacmaninbw
    Feb 3, 2023 at 19:26

2 Answers 2

2
\$\begingroup\$

Consider alphabetizing each little stanza of includes. It's a way of communicating to the reader that they don't depend on one another, plus it can reduce merge conflicts during maintenance when multiple developers add new includes.


#define DYNAMIC_ARRAY_SIZE(dynamic_array)

Kudos for being descriptive. But maybe abbreviate such parameter names? Whatever.

#define DYNAMIC_ARRAY_SIZE(array)

(Or maybe you want to minimize diffs from upstream. That's cool.)

The DYNAMIC_ARRAY_COPY(destination, source) and DYNAMIC_ARRAY_CONCATENATE signatures are very nice.


We use this expression for capacity: ((size_t *)(dynamic_array))[-1]. I get what's going on here. I'm just slightly surprised that it is valid portable C. I'm also concerned that various code checking tools will spuriously flag an out-of-bounds reference.

Maybe introduce a helper function that backs up to the true start-of-allocation, and de-references using a positive offset? (If this is "too slow", at least document the benchmark result in the source code.)

Same item for "size", of course.

Also, prepending some bookkeeping fields makes me concerned about cache-line alignment. If the app-level developer was trying to use strides that match cache-line size, being slightly offset might invalidate such reasoning. Maybe pad the bookkeeping with a few bytes? At least when the allocation is "large"?


Do we want to arrange for DYNAMIC_ARRAY_PEEK to fail when it attempts to peek an empty array? Looks like it could return the capacity, as currently written.


#define DYNAMIC_ARRAY_ALLOCATE(dynamic_array, requested_capacity)                                                               \
...
            ((size_t *)(dynamic_array))[-1] = (requested_capacity);                                                             \
            ((size_t *)(dynamic_array))[-2] = 0;                                                                                \

This is pretty ordinary code, there's nothing especially wrong with it. And you graciously explained the _SIZE & _CAPACITY immediately above it. But the magic numbers do make me a little sad, plus there's the whole cache-line thing. Consider defining manifest constants for -1 & -2. Or, better, make a macro that can be used in both getter and setter macros such as seen here.

One of the two methods will be used for the sake of consistency

Oh, I see, it's on the TODO list already. Cool.

_total_capacity = (requested_capacity) * sizeof(*(dynamic_array)) + ...

I find that calling both of these a "capacity" makes it hard to reason about them, since "total" has units of bytes. Maybe call it _total_bytes ?

For example, that naming approach didn't make it any easier for me to figure out what was going on in this test:

            if ((requested_capacity) < DYNAMIC_ARRAY_SIZE(dynamic_array))                                                       \

Consider adding a comment which explains the need for the conditional.


Consider adding a comment that explains to app developers the value-add offered by DYNAMIC_ARRAY_RESERVE over DYNAMIC_ARRAY_ALLOCATE.

It's not obvious to me why DYNAMIC_ARRAY_FIT should skip an empty array.


Put these two on separate lines for readability, please.

        const size_t _capacity_ = DYNAMIC_ARRAY_CAPACITY(dynamic_array), _size_ = DYNAMIC_ARRAY_SIZE(dynamic_array);                                    \

Similarly in DYNAMIC_ARRAY_INSERT.


#define DYNAMIC_ARRAY_REMOVE_BACK(dynamic_array)                                                                                    \
...
        if (DYNAMIC_ARRAY_SIZE(dynamic_array) == (size_t)(DYNAMIC_ARRAY_CAPACITY(dynamic_array) / DYNAMIC_ARRAY_GROWTH_FACTOR))     \

The / division seems slightly more expensive than folks might want. Maybe cache the result in a third bookkeeping slot?

Maybe offer a variant REMOVE macro that won't auto FIT, for an app developer who knows about the app's memory pattern?


It's not obvious to me why wanting to DYNAMIC_ARRAY_COPY an empty source array would be Bad. I would expect an empty destination array as a result.

Aha! The COPY macro is starting to spell out why the ALLOCATE macro was making size comparisons. This needs to be much better documented. Consider defining "private" macro(s) for your use that you don't expect an app developer to use.


Suppose I have a pair of arrays: a of float, and b of double. And then I try a crazy operation like trying to COPY or CONCATENATE them. I was in error when I tried that, right? Would the current implementation notice the difference in sizeof ? Do we expect it to report failure?


if people use this library they will shoot themselves in the foot one way or another, is my approach acceptable?

Sure, that's C for you, life in the big city.

There's already pretty explicit debug support, which affects both assert and whether stderr receives an "I'm melting!" message upon fatal exit. Consider adding sentinel support, before and after the app-level array. So allocate some additonal padding at the end, and write 0xdeadbeef or whatever at both start and end. If the application ever overwrites the sentinel you can check and report it, in the debug version.

In a similar vein, consider rolling some constant MAGIC_NUMBER and writing that as the initial portion of your bookkeeping bytes. And verify that it never changes. The ISC BIND9 consistently performs such checks, and it has been a big help for fault isolation.


Looking forward to those unit tests!

Please distinguish between public tests that do what you feel an app developer should do, and private tests which might use private macros. It was clear to me that an app developer should not be accessing [-2] for size directly, but it wasn't clear if all macros would be fair game for app-level use.


Overall, here are the big items to focus on:

  1. Get around to that [-1], [-2] TODO item.
  2. Distinguish public from private macros, if you want any private ones.
  3. Better document the public macros, or for unchanged semantics you might cite upstream documentation.
  4. Document or improve app-level interaction with cache lines.

Then ship it!

\$\endgroup\$
4
  • \$\begingroup\$ Very nice feedback, much better than I'd hoped for! In the following few days I will attempt to address each and every point you've made, as well as come back with the unit tests and documentation. Out of curiosity, how would you ship such a library? Moreover, are there other ways to improve its performance other than optimizing it for cache usage and using other memory allocators? Thanks again for the reply. \$\endgroup\$ Feb 4, 2023 at 2:08
  • \$\begingroup\$ Well, decide if each point is important to you rather than to me. I just kind of do stream-of-consciousness reaction to what I'm reading, essentially "do I believe this line of code?", does it do what it claims to do? Also, this time around I had Beginner's Eyes -- for another pass to review the documented interface, you kind of need another newbie to look at it. Ship? IDK, usually I ship via pypi.org or anaconda.org/conda-forge . Debian apt install and Mac brew? Publish on github and call it a day? The perf items I mentioned were cache divide, and optional FIT upon shrink. \$\endgroup\$
    – J_H
    Feb 4, 2023 at 3:59
  • \$\begingroup\$ Addressing the cache alignment issue will impact the other macros, so I have decided to start here. How much padding would you add? Would padding = sizeof(*(array)) - 2 * sizeof(size_t) do the job so that bookkeeping is the same size as the data? What if the data is smaller than the bookkeeping fields? Apologies for the barrage of questions, but I am unsure of how to deal with this issue. \$\endgroup\$ Feb 4, 2023 at 21:03
  • \$\begingroup\$ First, ignore what I say, since it may be true or false. Instead, make some benchmark timings, with some workload that you believe is representative of people who would be using this library. Then, and only then, adjust the alignment, so that the bookkeeping preamble takes up exactly one cache line. And repeat the timing exercises. We would only see timing differences for arrays larger than L3 cache size. Size of preamble is independent of how many bytes each cell occupies. By the way, if you choose to settle at the end, that has no interest in performance consequences. \$\endgroup\$
    – J_H
    Feb 4, 2023 at 22:07
4
\$\begingroup\$

This code

(dynamic_array) = (void *)(&_dynamic_array_pointer[2]);

potentially violates 7.22.3 Memory management functions, paragraph 1 of the (draft) C11 standard:

... The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement and then used to access such an object or an array of such objects in the space allocated ...

The original allocation of _dynamic_array_pointer comes from

const size_t * _dynamic_array_pointer = DYNAMIC_ARRAY_malloc(_total_capacity);

with DYNAMIC_ARRAY_malloc defined as

#ifndef DYNAMIC_ARRAY_malloc
#define DYNAMIC_ARRAY_malloc malloc
#endif

Thus, _dynamic_array_pointer will be "suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement".

But the address of

_dynamic_array_pointer[2]

is not guaranteed to be "suitably aligned".

For example, imagine a system where addresses that are "suitably aligned" must be multiples of 16, but that have 4-byte size_t. On such a system, if values of long double, for example, have a 16-byte alignment requirement, this code will fail because the address _dynamic_array_pointer[2] will not be aligned on a 16-byte boundary.

The code needs to use _Alignof(max_align_t) in some manner to ensure all pointers returned to the caller are "suitably aligned".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.