Show HN: Generic dynamic array in almost 2k lines of C(github.com)

Show HN: Generic dynamic array in almost 2k lines of C

https://github.com/qiolol/just-c-things/tree/main/Vec

Yet another C vector implementation! For both it and the title, I took inspiration from an implementation posted a few months ago: https://news.ycombinator.com/item?id=34973210

That implementation's impressive, over my head, and unsafe, containing overflows and footguns. Its approach, to quote the author, is "all C code is unsafe". ;p As a Rust fan, I agree, and that's in line with my impression of the intrepid spirit of C. But, in Sisyphean defiance, I tried to make an implementation that's the boring antithesis of that: long, straightforward, free of macros, and full of overflow checks and even agonizing nanny hand-holding like forcing the caller to check the size of the elements they're adding to the vector or `memset()`ing removed elements' bytes to zero (which totally won't get optimized out by the compiler, I'm sure).

While doing it, I learned two C techniques which I ended up using:

1)

You can have "abstract data types" (almost like classes!) in C, which is how the vector struct's exposed.

The header just has the following typedef with no struct definition after it:

    typedef struct Vec Vec;

https://github.com/qiolol/just-c-things/blob/main/Vec/Vec.h#...

`struct Vec` is never defined in the header at all -- only in the `.c` file! This way, the internals are encapsulated in the implementation and only accessible/modifiable via the functions exposed in the header, like a class's private members would be!

There are apparently downsides to this, such as not being able to control how vectors are allocated and only being able to include vectors in other structs via such pointers. Someone described this as winding up with "an everything-is-heap-allocated nest of pointers": https://news.ycombinator.com/item?id=35594787

2)

You can use contiguous memory to minimize allocations (and perhaps improve cache performance):

    struct Vec
    {
        uint8_t* data;
        // ...
    };

https://github.com/qiolol/just-c-things/blob/main/Vec/Vec.c#...

The vector stores everything in `data`, a `uint8_t` block.

`uint8_t`s are 8-bit (1-byte) integers, making `data` a block of bytes. This lets you do bytewise addressing with pointer arithmetic (unlike `void*`).

A vector's elements are generic; all it can do is treat elements as generic bytes, so it would make sense to use `void*`s. But we can't do pointer arithmetic with `void` pointers, meaning we can't do things like traverse the data block or return pointers to arbitrary places within it. Hence `uint8_t`. `unsigned char` would also work (it's also 1 byte); `uint8_t` is just more explicit.

SO: you can just allocate a big block of bytes called `data`! Whenever you wanna add an element, instead of doing an (expensive) allocation for that element, you just write the element's bytes into the data block! When you wanna remove an element, you zero out its bytes or update your metadata so you remember those bytes are now unoccupied.

The thing that looks most useful about it is that all the elements' memory is "contiguous" (nearby, in one big block), unlike it might be with multiple, per-element allocations. And having to fetch different blocks of memory scattered throughout RAM is slower than loading one chunk of memory from RAM and having all (or many) elements in the CPU cache is faster: https://youtu.be/WDIkqP4JbkE?t=1464

FOR ALL THAT, though, it still gets CRUSHED by `std::vector`, which my benchmarking reports as 2 to 20 times faster (depending on operation)! The only time my vector beat `std::vector` was when I had forgotten to employ the erase-remove idiom (https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom#Exa...) for `std::vector` (https://github.com/qiolol/just-c-things/blob/main/Vec/benchm...) despite having implemented it in my vector's multi-removal function. Fixing that crushed my brief sense of triumph. Haha. :B

0 comments

—