Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

gist.github.com

Post reply on HN
Print view View original

21–30 of 38 posts

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

#21

Post by userbinator »

astrobe_ wrote: post #17
sparkie wrote: post #12

Earlier quoted context omitted.

Really? It's been done plenty and I thought was quite common knowledge. Some of the 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 i…

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.

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

#22

Post by OskarS »

userbinator wrote: post #5

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.

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.

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

#23

Post by OskarS »

sparkie wrote: post #12
userbinator wrote: post #5

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 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 i…

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.

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

#24

Post by flohofwoe »

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).

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

#25

Post by sparkie »

OskarS wrote: post #23
sparkie wrote: post #12

Earlier quoted context omitted.

Really? It's been done plenty and I thought was quite common knowledge. Some of the 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 i…

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

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

#26

Post by sparkie »

OskarS wrote: post #22
userbinator wrote: post #5

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.

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).

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

#27

Post by amluto »

userbinator wrote: post #5

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.

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.

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

#28

Post by entrope »

sparkie wrote: post #12
userbinator wrote: post #5

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 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 i…

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.

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

#29

Post by mananaysiempre »

amluto wrote: post #27
userbinator wrote: post #5

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.

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.

Post reply on HN