This is embarrassing. I read "well known" and for some reason I misfired and Googled the wrong implementation. Very sorry.
The code you actually linked me to is written at a high level of abstraction and I just sent you the lowest level of abstraction I could write. But you are right, it is the same algorithm.
I am using a power of 2 sized array for the handle table. That means the index into the table can be found with (handle & mask). Where mask is (capacity - 1). This allows me to just mask off the index and check the handle found at that index. That allowed me to write a template specialization where the mask can be a compile time constant for a statically sized array. And a bitwise operation on a small constant makes for cheap compact assembly. On 32-bit hardware I break even with the reference implementation due to 64-bit emulation, but on 64-bit hardware it looks like a compare gets shaved off, and I get a larger generation counter out of the deal. The trade off is the size constraint.
As for the reverse mapping, I went and folded my reverse map into the handle array. Once I decided to have more generation bits than 32 (again, I am using all the bits in the 64-bit handle except the masked off index bits) it made sense to have the additional free list index outside the handle. (In hindsight, having seen your code, I could have packed the free list in the index bits obviously, but that isn't what I shared with you.) That left an alignment hole and I decided to put the backwards reference in the hole. In an ideal world (one the reference code appears to check for) the backwards reference would be in the same slot as the handle to the value being erased (because it never moved) maintaining cache coherence.
What can I say, I just independently invented it. At least I ended up in the right neighborhood.
>
sg14::slot_map supports arbitrary (user-defined) `key_type`. There are unit tests for that scenario (for values of "40–50" equal to 5).
Fair enough.
I think I have a slightly more optimal implementation, but I'd want encouragement about moving forward before getting into a bake-off.
> (Merged to where? Whose GitHub?)
How unpopular do you want me to make myself on this list.
Can I unpack your view though. It sort of sounds like you are saying you are happy to provide sloppy tools to sloppy programmers, because they don't know better anyway. Meanwhile the elite can go read the white papers for their CPU architectures and write bespoke solutions for them. Hmm. That actually does sound like the C++ ecosystem.
I have been working on normal looking containers and algorithms that try not to be able to do anything sloppy. In theory that would make sloppy programmers (and sloppy AI) smarter. "You can't get there from here."
Regards,
Adrian
The details of that implementation are the opposite of what I was trying to advocate for. slot_map uses sparse paged allocation with stable pointers the same way std::hive does. My arguments about high frequency iteration over std::hive apply the same w.r.t. slot_map. I would like a dense non-paged array of values
That's what template parameter `Container` is for, and it defaults to `std::vector`, which
is a dense (in fact, contiguous) array of values. The
innards of sg14::slot_map are just three std::vectors.
`this->reverse_map_` and `this->values_` both obey the invariant that their `size()` is always equal to `this->size()` (i.e., they contain no irrelevant elements).
Your `m_values_` is my `values_`; your `m_slots_` is my `slots_` + `reverse_map_`
AoS'ed together. Your `m_mask_` is the part I don't understand at the moment.
and the ability for references held by other languages to be broken without RAII.
That's what the template parameter `Key` is for, right? (In sg14::slot_map, `Key` defaults to `pair<unsigned, unsigned>`, where the first element of the pair is the index and the second element is the generation counter.) The fact that `insert` returns a `key_type` (your `hxhandle_t`), rather than an `iterator`, is what makes the thing a slot-map instead of an ordinary std::map or std::flat_map.
I also proposed a 40-50 bit "generation" counter (even on 32-bits as compared to 10) before the handle id wraps. That is far larger than slot_map as I didn't want to be responsible for causing data corruption at scale.
sg14::slot_map supports arbitrary (user-defined) `key_type`. There are
unit tests for that scenario (for values of "40–50" equal to 5).
In my mind the question is as much about the kind of language C++ is trying to be. I have been "writing the world from scratch" in C++ for 20 years. And maybe we like it that way. Other languages offer you a soup to nuts experience and all I would be doing right now is submitting a pull request on GitHub to get this merged.
(Merged to where? Whose GitHub?)
In this case I am talking about 400 LOC so far
Coincidentally, <sg14/slot_map.h> is also about 400 LOC. :) The unit tests are longer than the facility itself.
–Arthur