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())
{
switch(somePortableHash<uint8_t>(child.key())) //1 byte makes it likely the switch will be compiled into a jump table
{
case(17): if (key == "foo") child.tryReadVal(_foo); break;
case(183): if (key == "bar") child.tryReadVal(_bar); break;
case(211): if (key == "boo") child.tryReadVal(_boo); break;
default: break;
}
}This would probably be the fastest performance-wise. While it does suffer from having all those magic numbers that we calculated to be hashing results, it wouldn't be too difficult to maintain - if a new possible key is added, then just compute its hash and add it to the switch.
Right, there's also a thing called Perfect Minimal Hash, but that wouldn't be maintainable.
