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.
Ah, good. I hoped I wasn't embarrassing myself by assuming your thing was slot_map without understanding the "mask" part. ;)
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).
Theoretically one can get something of roughly that shape by passing `inplace_vector` as the underlying container.
template<size_t N>
struct Helper {
template<class T>
using VectorN = std::inplace_vector<T, N>;
template<class T>
using Map = sg14::slot_map<T, std::pair<unsigned, unsigned>, VectorN>;
};
template<class T, int N>
using MySlotMap = Helper<N>::template Map<T>;
MySlotMap<int, 16> m1; // uses inplace_vector<T, 16> for each of MySlotMap's three data members, rather than ordinary vector<T>
Of course `sg14::slot_map` isn't perfectly efficient: since it stores two vectors of the same size(), it necessarily stores the size() twice (once in the first vector and once in the second vector). So that's like 8 bytes wasted right there.
I think I have a slightly more optimal implementation, but I'd want encouragement about moving forward before getting into a bake-off.
[...]
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.
Yes, basically. There's no point getting into a bake-off, because everyone will always be happiest to eat their own baked goods. If you bake it yourself, you can bake it just the way you like it. Maybe Alice loves the genericity of sg14::slot_map, while Bob hates that it wastes 8 bytes to store the size twice (among other inefficiencies) and prefers hxhandle_map. Meanwhile, Charlie needs it to be allocator-aware (so that he can pass in his own allocator), and so he hates both of these libraries.
I definitely think that if you think "reading whitepapers about your particular CPU architecture" is necessary for success, then you're going to have to read those whitepapers on your own; I guarantee your STL vendor won't read them. Your STL vendor ships code whose primary requirements are to be (1) highly portable and (2) visibly bug-free, both of which goals work against the idea of being as fast as possible (or small as possible, or whatever) on your specific architecture.
I don't read CPU-specific whitepapers myself; I read style guides. ;) So I'd unpack it as something like: "Meanwhile the elites can go look at their actual codebases, think hard about what they need to do and what they need not to do, and then write bespoke solutions for them."
For example, whenever I reimplement std::function for one of my codebases, I make sure it's move-only, and has no
implicit conversion to `bool`, and that you can't
store an `int()` into a `Function<void()>` by accident. (C++23 std::move_only_function fails the latter two requirements.)
my $.02,
Arthur