A generic dynamic array in C that stores no capacity and needs no struct | Hacker News Reader

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

gist.github.com

27 pointsalurm33 comments

The most idiomatic and elegant 'dynamic array in C' solution is stb_ds.h, it's as simple as that :)

The 'public handle' is a pointer to the array elements so it has the same semantics as a regular C array, the meta-data (capacity and length) are stored directly in front of the array items. Growing the array has the same behaviour as realloc (e.g. you may get a new pointer back).

Thanks for mentioning it, I've heard about stb, but this time around I actually looked at the code. Their approach is very nice.

No structs, just an array that accomplishes the same thing, without field names or other niceties. Enjoy the pleasure of not using a struct when you inevitably add/reduce/reorder fields later.

Good point! Added `vec_ptr[vec]` and `vec_len[vec]` helpers to mitigate this somewhat.

Why would you want to avoid using a struct? Add a macro that declares the appropriate struct and get at least a tiny bit of type checking.

With some clever use of _Generic you could even build specialised functions for that type and get pretty good type checking

In C23 this approach is nice, but in older versions of C we end up with awful macros where we need to define the structure before we use it.

    #define Array(T) struct array_##T
    #define DEFINE_ARRAY(T) struct array_##T { size_t len; T *elems; }
    
    DEFINE_ARRAY(int);
    Array(int) foo;
    Array(int) bar;

C23 has relaxed rules for redefining the same struct, so we can avoid having to create the struct up front.

    #define Array(T) struct array_##T { size_t len; T *elems; }

    Array(int) foo;
    Array(int) bar;

The C standard doesn’t guarantee that arbitrary integer values converted to a pointer and back result in the same integer values again. It only guarantees the other direction, that a valid pointer to void, when converted to uintptr_t and back again, will result in a pointer that compares equal to the original. The conversion from uintptr_t to pointer may for example clear or truncate some of the bits of the integer value, or normalize it in some other way.

You're right, I added some more clarity in the README.

Interestingly, I think my approach will work fine on CHERI, since the pointer is never dereferenced, but I didn't test this. But yeah, there are some architectures where it would fail.

capacity isn't stored at all. Instead, it's computed on demand when the length of the vec is either zero or a power of two.

Brilliant insight. This is the first time I've seen this observation in over 3 decades of working with C.

Really? It's been done plenty and I thought was quite common knowledge. Some of the <stdbit.h> provided functions are basically for this purpose.

stdc_bit_ceil(len) gets the smallest power of 2 not less than len, which is our capacity. This is usually implemented with a clz instruction.

stdc_has_single_bit(len) determines if it's a power of 2 - typically implemented with a popcount instruction (popcount(len)==1).

The approach isn't used in older (90s and earlier) texts because hardware support for popcount/clz wasn't commonplace and the cost to do it in software wasn't worth it, but it is mentioned in some texts.

I think it was sarcasm. I have about as much experience as them in low-level C programming, and I was wondering why this is on front page. I've also discovered again a few things too, so I won't look down on OP. It's certainly better than vibe coding.

No, I'm being serious.

I know about XOR-linked lists and a few other tricks for very efficient memory usage in embedded systems, but it's my first time seeing implicit allocation lengths.

Everyone knows about bit-fiddling functions, what the poster was referring to is using this trick to not have to store the capacity for a dynamic vector. Which is genuinely very clever and rare, I don’t think I’ve ever seen it done quite like this either. I think that’s probably because it’s not really that good of an idea, if the vector can shrink, you really should store the capacity.

I don't think it's that rare. I've been using the technique for years, and I've seen it done in other work. Bagwell's VList[1] for example uses the equivalent of `bit_ceil` to determine the size of each block without having to store it - and there are earlier works based on the same trick. RAOTS, which is referenced by the VList, mentions using the technique, but itself uses a slightly more complex trick where we can calculate the size of a block based on the approx square root of the length.

You can use the trick if the array can shrink as long as you always shrink the allocation when length goes below the next power of 2 not greater than len (which may make use of stdc_bit_floor).

[1]:https://cl-pdx.com/static/techlists.pdf

Ignoring multiple evaluation, one can also #define stdc_has_single_bit(X) !((X) & ((X)-1)). If X isn't a power of two, the -1 will leave the MSB in place.

It doesn’t really work though for generic vectors. If you support not just vec_push but vec_pop as well, then you really do need to store capacity separately or else call realloc way more often than you normally need to.

That may be true, but it may also mean you utilize more memory than you need to. If you aren't shrinking the array when you no longer need previously allocated capacity then you're wasting memory. You could end up with an array of 10 elements and an allocation of 2^10.

The capacity as bit_ceil(len) ensures that at most, half of the allocated space is wasted - excess space is O(n).

It’s not so brilliant when you have an array of size 2^n and you append and then pop off the end in a loop and each operation takes time proportional to the length of the vector.

Usually, dynamic arrays aim for amortized constant time for append and pop. This trick loses that property.

Restoring it only needs one additional bit of storage, however (whether the buffer is currently 2⌊n/2⌋ or 4⌊n/2⌋ elements in size), which we can probably squeeze in somewhere.

More disappointing is that libc still forces us to use the free(p) API, without a length argument, meaning we are still paying to store a(n approximation of) the length somewhere in the allocation metadata.

Thank you! I implemented this pattern initially about a year ago, but decided to write about it now. Since you liked it, it wasn't for nothing. :)

https://github.com/gritzko/libabc/blob/main/Sx.h

https://github.com/gritzko/libabc/blob/main/S.md

ABC uses s[2] for slices, g[3] for gauges, b[4] for (ring) buffers. Also containers on top of those (heaps, hash sets, etc etc)

> First of all, structs aren't used so you don't have to invent names for them (e.g. there is no IntVec)

But since it’s storing a void pointer any way, they wouldn’t need separate names right? You could use one struct everywhere regardless of the type of the items

Which IMO is a better idea than using an array here because the fields can be properly named and typed to prevent accidental misuse

If you use a struct with a `void*`, you also need to specify the type on usage, where here it's done with `typeof`.

Clever!

I don't like the use of uintptr_t, though. Why not storing the array begin in v[0] and a pointer to the first free item in v[1]? You avoid casts by defining len as ptrdiff_t and calculating it as v[1]-v[0].

Enjoy the annoying-to-debug errors when someone inevitably mixes arr[0] with arr[1] and tramples the heap (this could be mitigated by accessing the fields with macros), or writes arr[3] because they forgot this is not a regular array.

Yeah, I've added macros `vec_len` and `vec_ptr` (or, enums, actually), which help somewhat.

`arr[3]` should be flagged by the compiler it is known to the compiler that you're operating on an array.

You can pass `arr` as `&arr` to functions, then compiler will know the length of the array since the type would be `T ()[2]`.

And you can then use it like this:

  void f(int *(*ints)[2]) {
      for (size_t i = 0; i < (size_t)vec_len[*ints]; i++) printf("f: %d\n", vec_ptr[*ints][i]);
  }

Curiously, this is a rare case where the "inverted" `a[b]` requires less typing compared to `(b)[a]`.

A compiler will not be able to flag `vec_len[ints]` though, which is unfortunate.

That's pretty clever code. Too clever for my tastes.

Strictly speaking, the capacity is still stored internally to the allocation (it needs to be, in order to implement realloc)

You don't, as the capacity is always the next power of 2 of the length.

If you were to implement your own realloc for the purpose of this data structure, you could do that. However, a generic realloc implementation needs to know how many bytes to copy, and generally that means storing the capacity just in front of the allocated region. I don't think there is another feasible way. On e.g. glibc, you can use `malloc_usable_size` to extract this information (modulo certain caveats).

This is just silly. You can't even reserve capacity because you only store size and capacity is implicitly the next power of 2 >= size.

The concept of not storing capacity isn't silly. If you need to reserve space then it's not the appropriate structure, but it's otherwise fine.

However, using an 2-element array to avoid using a struct is silly.

Reply on news.ycombinator.com