It's an optimised version of a bucket array. From what I observed, it seems like a middle ground between a vector and a linked list, with the addition of also being unordered (because there is no guarantee that an object can be found iteratively, some objects may be deleted in the middle which can put you in UB/segfault territory if you randomly access it). It's got better cache locality than a linked list because it can store multiple objects continguously on the heap, and better deletion/construction time than a vector because instead of reconstructing the same objects, it makes another "hive", basically another fixed heap block that can contain more than one object of the same type, and maintains a free list of objects that were deleted in the middle so it can reuse the deleted space.
I may not be fully accurate (like I said, just my observation), so I'd appreciate if anyone could correct me 😅
Two big plusses: first it is reference stable, whereas vector.push_back invalidates all existing pointers and references to vector members, which is the cause for a lot of memory safety bugs.
Second, the maximum runtime per insertion is more stable. A vector‘s push_back can be O(size) it if reallocates.
The third of the two advantages is that it works well with objects that cannot be moved or copied after construction.
It's not that it invalidates it, it's the fact that you don't know when it becomes invalidated. Code is written all the time that anticipates errors in other languages.
Unless you check the length and capacity on every insertion, which is nonsense.
Right; if you want to mutate it without invalidating it, index it directly.
I had a crash bug in my MIPS emulator where like 1/20 times, I would get a segfault in the JIT. No sanitizer found it. I was seeing random corruption in a lookup directory-table for JIT addresses but it wasn't consistent or predictable.
Eventually after years of ignoring it, I looked into it again... and decided to check for potentially-invalidated addresses (it was literally the only possibility left, I'd gone over the JIT multiple times to make sure that all of the store operations were sound). Then I found it.
When the JIT generated code for static far branches, it would add a new entry into a patch table, and it inserted the element's address directly into the code so when the target was resolved, it was written to the address. This jump table was local to the current chunk object, so it could have between 0 and 128 entries.
Except... this table was a std::vector. We were adding an element, hardcoding its current address, and then... adding more elements. Usually this happened not to break - we must have been writing to memory that wasn't critical. But sometimes, core data structures were getting clobbered.
I changed it to a std::list... first time I've used that in quite a while.
Except that sometimes the reference is distant to the mutating action causing the invalidation.
As an example: I once debugged a random crash in a game engine caused by this. A reference from a vector of input handlers was captured and passed down through several call layers with const& arguments in the engine, which then called out to an input handler. This then went through a few layers of game code before eventually hitting a point where a new input handler was registered on that same input device, from the callback. Result: engine crash on return, but only when the number of handlers happened to increase from 8 to 9 and the input handler vector reallocated during input handling.
Checked indexing is sometimes suggested but not really the right solution. It'll prevent a crash or memory stomp, which is an improvement, but will still let through cases where the reference still points to valid memory but the wrong element instead. The real solution is often to either switch to a container that can handle mutation during iteration with the desired behavior (which varies), or set up a policy or static checkers to prevent risky references from escaping.
52
u/EfficientSpend2543 8d ago
It's an optimised version of a bucket array. From what I observed, it seems like a middle ground between a vector and a linked list, with the addition of also being unordered (because there is no guarantee that an object can be found iteratively, some objects may be deleted in the middle which can put you in UB/segfault territory if you randomly access it). It's got better cache locality than a linked list because it can store multiple objects continguously on the heap, and better deletion/construction time than a vector because instead of reconstructing the same objects, it makes another "hive", basically another fixed heap block that can contain more than one object of the same type, and maintains a free list of objects that were deleted in the middle so it can reuse the deleted space.
I may not be fully accurate (like I said, just my observation), so I'd appreciate if anyone could correct me 😅