Hacker News Reader

Comment by sparkie | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com