I would like to show the list the kind of data structure I have used in real-time contexts where std::hive is also recommended.

As an old games programmer, if I'm going to have to spend the next 5 years reading about how std::hive swooped in and rescued me from my "hand rolled" spaghetti code, I figured I would respond with something I consider a better design in some use cases.

The handle_map is a mapping from a 64-bit handle to a templated value type. The handle_map uses a single array for the handle table (and other accounting) and a single contiguous array of values for the value array. This addresses a number of issues, please allow me to explain.

The first issue is language interoperability. A handle is an integer you can pass off to Lua, JavaScript or Python and not have to worry about bolting unrelated memory management schemes together in scripts written at 3 AM. (The Bun rewrite everyone is talking about chose Rust because this kind of interoperability was deemed too hard otherwise.)

And once you add handles as a requirement, you have a handle table that can be updated and therefore the requirement for stable iterators goes away. This applies to the entities, the entity components, and their associated resources managed by the various systems. And once streaming resources get deleted unilaterally in a different thread this becomes a valuable requirement.

That brings me to my second issue, which is cache coherence. Games consoles typically have much weaker caches because their makers can gain a competitive advantage by adding custom accelerator hardware instead and then forcing developers to write cache aware code. Having a handle table allows a container to compact the array of values by swapping end elements down as values are erased. This allows iteration over a dense values array by engine components with perfect CPU prefetching and no bucket accounting. This is a major advantage considering full array iteration could happen at 200Hz with modifications at 0-20Hz.

My other cache concern is instruction cache issues. This is something intentionally zeroed out by micro-benchmarking frameworks... For some reason. However, if you have a performance analyzer that can show you the CPU stalls caused by normal code on a CPU with an anemic cache you might find the CPU easily spends 2/3 of its time waiting for the system bus, when things are going well. And so I would suggest that the I-cache consequences of adding a bucketing algorithm also has a hidden cost. Unfortunately, I can't offer you numbers as I don't have access to the kinds of tools I used to.

Yes, having a single array does not allow for incremental growth, but the artists used up all the remaining memory anyway so we don't have that. In all seriousness, if you have a desktop or server processor with lots of cache and unbounded spare memory (e.g. high-frequency trading) std::hive may be a better option. My point with this design is that there are still tradeoffs remaining and for that matter, std::flat map offers precedent for using simple arrays as a backing store for a map. This is soft real-time after all.

Below are links to the header and implementation for this. I'm using __restrict and local variables extensively to avoid aliasing. This design places the references back from the values to the handles into the handle table array. That allowed for perfect structure packing on 32 and 64-bit and provided begin()/end() iteration over the values without unsightly accounting wrecking the alignment of the values array. A "hand rolled" implementation might find an alignment hole in the values array to tuck that backwards reference in. The top of the implementation file provides more implementation details.

hxhandle_map.hpp. hxhandle_map<> header and Doxygen markdown. Static and dynamic allocation modes are supported by hxallocator<> as with all containers in this library.

https://github.com/whatchamacallem/libhatchet/blob/main/include/hx/hxhandle_map.hpp

hxhandle_map.inl. Implementation and brief explanation at the top.

https://github.com/whatchamacallem/libhatchet/blob/main/include/hx/detail/hxhandle_map.inl