I did a small test. It's 100ms just to visit all the nodes of all the trees (no vector building). So, good luck~
>flat_map
flat_map still never beats unordered_map in insertion and random searching performance. The reason people need flat_map is because it's faster than map, and, like map, it gives you something unordered_map can't, which is, ordered traversal.
Even Adaptive Radix Tree, which is the ultimate tree-like structure for strings, is still 2-3 times slower than the hash map.
Anyway, if we absolutely needed to make some hot path fast, there's is a way to do that. Let's say we're currently doing:
reader.tryRead("foo", _foo)
reader.tryRead("bar", _bar)
reader.tryRead("baz", _baz)Building an index has an overhead. But without an index it's problematic if we try looking for a key that doesn't exist. If a mapping node doesn't have any children with a key, it means you spent a lot of time looping through the children and doing string comparisons and returned empty-handed. To avoid that, a more optimal way of deserializing would be:
for (const auto& child : reader.children())
{
switch(child.key())
{
case("foo"): child.tryReadVal(_foo); break;
case("bar"): child.tryReadVal(_bar); break;
case("boo"): child.tryReadVal(_boo); break;
}
}So instead of searching for the keys that node's children may not have, we instead loop through the children. The obvious problem is, we can't do switch(string) in C++. So we would have to create a switch tree comparing one character at a time:
for (const auto& child : reader.children())
{
std::string_view key = child.key();
switch(key[0])
{
case('f'): if (key == "foo") child.tryReadVal(_foo); break;
case('b'):
switch(key[1])
{
case('a'): if (key == "bar") child.tryReadVal(_bar); break;
case('o'): if (key == "boo") child.tryReadVal(_boo); break;
}
}
}Heh, it's like we're simulating a Trie data structure. This would work, but not only does it look ugly, it's a nightmare to construct and nightmare to maintain. Unless we used some sort of
fancy library or whatever for it.
Lastly, I'd like to mention hashing. Hashing to the rescue!
for (const auto& child : reader.children())
{
//Uint32 newSeed = findPerfectSeed({"foo", "bar", "baz"}); // when the array of keys changes, update and run this, and replace seed with newSeed's value
Uint32 seed = 12345;
const std::string_view& key = child.key();
switch(ourHash(key, seed))
{ //ourHash is constexpr function, so case(x) will have constants for x, or fail to compile if seed is not perfect
case(ourHash("foo", seed)): if (key == "foo") child.tryReadVal(_foo); break;
case(ourHash("bar", seed)): if (key == "bar") child.tryReadVal(_bar); break;
case(ourHash("boo", seed)): if (key == "boo") child.tryReadVal(_boo); break;
default: break;
}
}
This would probably be the fastest performance-wise. It doesn't look the best, but it's easy to maintain.
