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.
Brilliant insight. This is the first time I've seen this observation in over 3 decades of working with C.
Usually, dynamic arrays aim for amortized constant time for append and pop. This trick loses that property.
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.
The capacity as bit_ceil(len) ensures that at most, half of the allocated space is wasted - excess space is O(n).
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 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.
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).