A Fast, Growable Array With Stable Pointers in C
2 days ago
- The segment array provides constant time indexing, stable pointers, and works well with arena allocators.
- It stores pointers to fixed-size segments that double in size, avoiding memory relocation and holes.
- Fixed-size segment array (e.g., 26 segments) ensures cache efficiency and supports up to 4,294,967,232 items.
- Bit shift operations and compiler intrinsics enable fast index calculation, resulting in approximately 10 x86-64 instructions.
- The data structure can be type-checked using macros without relying on `typeof()` if desired.
- Compared to other list structures, the segment array offers full support for growth, stable pointers, random access, and contiguity.
- It is most beneficial in conjunction with arena allocators and for central arrays storing many entities or samples.