1. Hello Std Proposals,


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

Regards,
Adrian