HN Debrief

A generic dynamic array in C that stores no capacity and needs no struct

  • Programming
  • Developer Tools
  • Open Source

The gist proposes a generic dynamic array in C that avoids a dedicated struct entirely. The public handle is just a small array, and the current capacity is not stored as a field. Instead it is recomputed from length using the next power of two. That saves one piece of metadata and keeps the element pointer typed, which is the author’s main reason for not using a `void*`-based struct.

If you want a production C vector, keep explicit metadata and a clear type boundary. The implicit-capacity trick is useful as a niche space-saving idea, but the moment you need reserve, stable performance under push/pop, or easier debugging, the missing struct becomes a liability.

Discussion mood

Mixed but mostly negative. People liked the capacity-from-length idea as a clever bit-level optimization, but the dominant reaction was that the no-struct design is too clever, fragile, and inferior to existing C dynamic array patterns.

Key insights

  1. 01

    Push and pop break the nice complexity

    Inferring capacity from length works cleanly only while the array mostly grows. As soon as code alternates between appending and popping around a power-of-two boundary, it can trigger repeated `realloc` calls and turn cheap operations into work proportional to the array size. You can still make it function for shrinking arrays, but then you are accepting either more churn or more wasted space. That changes the technique from a general vector design into a workload-specific optimization.

    Use this pattern only when your array is effectively append-only or when resize churn is acceptable. If your code hovers around thresholds or needs predictable latency, store capacity explicitly.

      Attribution:
    • amluto #1
    • OskarS #1
    • sparkie #1 #2
  2. 02

    C23 weakens the case for ditching structs

    The strongest practical defense of the gist was that a struct-based generic array in older C gets macro-heavy fast. You either predeclare one struct per element type or fall back to `void*` and lose type information at use sites. Commenters pointed out that C23 relaxes repeated struct declarations enough to make macro-generated typed structs much less awkward. That removes a lot of the motivation for encoding metadata in anonymous array slots just to keep element types visible.

    If you control the toolchain and can use C23, revisit old macro hacks before adopting pointer tricks. A generated typed struct will usually give you a safer API with little extra ceremony.

      Attribution:
    • sparkie #1 #2 #3
    • dwroberts #1
    • procaryote #1
  3. 03

    stb_ds shows a cleaner C interface

    `stb_ds.h` came up as the more mature version of the same underlying idea. It exposes a normal element pointer as the public handle, so calling code feels like it is working with a regular C array, while length and capacity live in memory just before the returned pointer. That keeps the ergonomic win without forcing callers to remember that `arr[0]` is metadata and not data.

    If you like header-only C containers and want array syntax, study established designs like `stb_ds.h` before inventing a new ABI. You can keep the call-site simplicity without making metadata indexing part of everyday use.

      Attribution:
    • flohofwoe #1
  4. 04

    Pointer integer casting may be nonportable

    One comment flagged a standards issue with converting arbitrary integer values to pointers and back. C only guarantees that a valid pointer can round-trip through `uintptr_t` and compare equal afterward. It does not guarantee that every integer survives conversion into a pointer unchanged. If the gist relies on stuffing state into pointer-typed values through integer casts, that is weaker than it may look on mainstream machines.

    If you ship low-level C beyond mainstream x86 and ARM targets, audit any pointer tagging or integer-pointer encoding against the actual standard guarantees. Tricks that work on today's hardware can still be undefined or implementation-specific C.

      Attribution:
    • layer8 #1

Against the grain

  1. 01

    The capacity trick is genuinely uncommon

    Against the dismissive reaction, several comments argued the core idea deserves more credit. The novelty is not `popcount` or `clz`, it is using power-of-two growth to derive capacity from length and remove one field from the vector state. Even experienced C programmers said they had not seen that applied this way before. That does not make it a better container, but it does make it a real design insight rather than empty cleverness.

    Separate novelty from usefulness when you evaluate low-level code. A trick can be worth learning even if you decide not to use it as your default container design.

      Attribution:
    • sparkie #1
    • userbinator #1
    • OskarS #1

In plain english

amortized O(1) ↩
Average constant-time cost per operation over a long sequence of operations, even if some individual operations are more expensive.
C23 ↩
The 2023 revision of the C programming language standard, which adds and changes language and library features.
clz ↩
Count leading zeros, a CPU instruction or compiler builtin that reports how many zero bits appear before the highest set bit.
popcount ↩
A CPU instruction or compiler builtin that counts how many bits are set to 1 in an integer.
realloc ↩
A C standard library function that resizes a previously allocated memory block, possibly moving it to a new address.
stb_ds.h ↩
A popular single-header C library that provides dynamic arrays and hash tables using macros and hidden metadata.
uintptr_t ↩
An unsigned integer type defined by C that is capable of storing a pointer value when the implementation provides it.
void* ↩
A generic pointer type in C that can hold the address of any object but does not itself carry the pointed-to type.

Reference links

Alternative C container implementations

  • stb_ds.h
    Named as the idiomatic C dynamic array design that exposes a plain pointer while hiding metadata before the allocation.
  • libabc Sx.h
    Shared as another C container approach using compact array-based representations.
  • libabc S.md
    Documentation for the libabc container approach referenced alongside its source.

Related data structure references