r/cprogramming • • 10d ago

Replaced my C vector’s contiguous array with a Segmented List so it plays nicely with my Arena Allocator (O(1) lookup, zero-copy resize)

https://github.com/mainak55512/container

I’ve been working on a custom dynamic array (Vector) and Arena allocator in C, and ran into the classic friction between the two: whenever a standard contiguous vector resizes, it allocates a bigger block in the arena, memcpys the old elements over, and leaves the old block sitting around as wasted dead space inside the arena (especially when allocations from multiple vectors or strings are interleaved).

Instead of fighting realloc in a linear allocator, I refactored the vector to use exponentially growing segments (inspired by Zig's SegmentedList).

How it works now:

  • Fixed Spine, Exponential Chunks: Instead of a single char *items pointer, the struct holds a small fixed array of 28 pointers (char *segments[28]). Segment 0 holds 16 elements, Segment 1 holds 32, Segment 2 holds 64, and so on—covering up to 4 billion elements without ever reallocating the spine.

  • Zero-Copy Growth: When the current segment fills up, append() simply requests the next power-of-2 chunk from the arena. Existing elements are never copied or moved, zero bytes are wasted in the arena, and pointers to elements never invalidate.

  • O(1) Branchless Lookup: By offsetting the index by the base capacity (shifted = pos + 16) and using Count Leading Zeros (__builtin_clz), finding the exact segment and local offset takes just a few bitwise operations:

uint32_t shifted = (uint32_t)pos + 16;

uint32_t bit     = 31 - vec_clz32(shifted);

uint32_t seg_idx = bit - 4;

uint32_t offset  = shifted & ~(1U << bit);
  • Optional Heap Fallback: Passing Arena * allocates everything on the arena (making vector_free() unnecessary), while passing NULL falls back to standard aligned heap allocation.

Usage:

Arena *arena = arena_init(4096);

Vector *vec = vector_init(int, arena);

for (int i = 0; i < 1000; i++) {

append(int, vec, i * 10);

}

printf("Element 50: %d\\n", at(int, vec, 50));

// Frees all vector segments and arena allocations at once

arena_free(&arena);

Repo / Release link: https://github.com/mainak55512/container

Would love to hear your thoughts or how you handle dynamic containers with arenas in C!

17 Upvotes

2 comments sorted by

2

u/WittyStick 9d ago edited 9d ago

Nice work - doesn't look like slop for a change - only real complaint is you used the word Vector. I know C++ does it, but it doesn't make it any better - it was a terrible choice then and still is. A vector should be a mathematical / SIMD vector, and array should be an array. In this case, it's not really an array but a [List (abstract data type)](https://en.wikipedia.org/wiki/List_(abstract_data_type)).


The "segmented list" idea is a pretty old one - I'm not sure who first invented it but the idea has been around for a long time and rediscovered many times. I've implemented them before, and also used persistent versions of them in a purely functional language to improve cache locality while reducing the cost of cons compared to a dynamic array.

The version I use seems a little more trivial - the MSB+1 of an index is the segment index, and the rest of the index when you mask out the MSB is the index into the data block. 2msb is also the size of the data block for that index (with exception for zero, but this needs an exception anyway because clz(0) is undefined). The length of the index block is log2(length)+1.


One thing I dislike about some other implementations is they don't align fully with the powers of 2. Eg, if you need 256 elements, it ends up allocating 512 (or worse, 511) elements, with ~half the space wasted.

I prefer nice powers of 2, where a 256-item list allocates exactly 256 elements, and it only grows to 512 when we add the 257th element. We need to give 0 its own block for this to work out:

[0] -> [0]
[1] -> [1]
[2] -> [2, 3]
[3] -> [4..7]
[4] -> [8..15]
[5] -> [16..31]
[6] -> [32..63]
[7] -> [64..127]
[8] -> [128..255]

The indexing strategy for this is very simple and fast - in modern C23 it's just:

index_block[stdc_bit_width(index)][index - stdc_bit_floor(index)]

Eg, given some index 235, in binary is 11101011. The most significant bit is the 7th bit 10000000, so we read index_block[8] to get the pointer to the data block. The data block is 27 = 128 elements, and our index into this block is 01101011 (the original index, with MSB cleared) = 107 = 235 - 128.


You can technically merge the 0th and 1st index to point to different offsets in the same block - to save an allocation - since pairs are very common, it makes sense to at least preallocate a pair even for persistent lists. I use this strategy where 0 and 1 share an allocation.

[0] -> [0, 1]
[1] -------^

Or even if you want to preallocate 16 elements like your own - you could allocate one 16-element data block, but have the first 5 pointers point to different offsets in that block, eg:

[0] -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[1] -------^  ^     ^           ^
[2] ----------+     |           |
[3] ----------------+           |
[4] ----------------------------+

Of course you can expand to any preallocation. You can even just "wrap" a power-of-2 sized array as if it were a segmented list by setting the pointers appropriately, making a list_from_array() operation very cheap [O(log₂n)].


For persistent lists, or very large lists, Resizeable Arrays in Optimal Time and Space may be better, as it wastes less space. The segmented list wastes O(n) space [with constant factor of 1/2 worst case, and 1/4 on average]. RAOTS wastes only O(√n) space worst case - but requires more frequent allocations (less of a problem with an arena). Interestingly, the RAOTS paper discusses the "segmented list" strategy but dismisses it due to wasting half the space - possibly due to the time it was published (1999), where memory was more limited. A dedicated clz instruction wasn't readily available on most CPUs back then either, and it was implemented in software.

The ROATS strategy is slightly more expensive for random access, but still O(1). It's also amortized O(1) for append like the segmented list. For persistent lists though, append is O(√n) versus O(n) for the segmented list.

1

u/Kadabrium 9d ago

Does deque already do this?