commit 58a20ff2ccc115e50cf3a04616c9358ce318621e
author Primiano Tucci <primiano@google.com> Thu Nov 18 18:38:55 2021 +0000
committer Primiano Tucci <primiano@google.com> Thu Nov 18 18:38:55 2021 +0000
tree 7e59a46cd6f3901d5c140110f3e829e93f982692
parent 942de254bd93e48ac8307d8df20293eaf0a85c05

base: Add FlatHashMap - open addressing hashtable

It is 7x faster than unordered_map and as fast as a RobinHood hashmap.
I benchmarked this against a real 4GB trace. I extracted all the strings
appending a line into a file every time StringPool.Insert() was called
(before deduping) and then replayed in a benchmark.
The strings file was 2.3GB large and contained 226M strings (1.17M after
deduping).

See design doc for details and numbers:
go/perfetto-hashtables


Replay 226M string insertions from a 4GB trace
----------------------------------------------
InsertTraceStrings_AppendOnly            875,771,930 ns  rate=259.07M/s
InsertTraceStrings<Ours_LinearProbing>   889,191,936 ns  rate=255.17M/s
InsertTraceStrings<Ours_QuadProbing>   1,042,440,801 ns  rate=217.694M/s
InsertTraceStrings<StdUnorderedMap>    6,156,277,902 ns  rate=36.8552M/s
InsertTraceStrings<RobinMap>             940,660,623 ns  rate=241.213M/s
InsertTraceStrings<AbslFlatHashMap>    1,020,857,090 ns  rate=222.258M/s
InsertTraceStrings<FollyF14FastMap>    1,202,585,000 ns  rate=188.68M/s

Replay 135M process tracker tids from a 4GB trace
-------------------------------------------------
TraceTids<Ours<TID_ARGS, QuadraticProbe>>      633,785,658 ns  rate=214.143M/s
TraceTids<Ours<TID_ARGS, QuadraticHalfProbe>>  635,951,855 ns  rate=213.432M/s
TraceTids<std::unordered_map<TID_ARGS>>      1,667,530,648 ns  rate=81.3932M/s
TraceTids<tsl::robin_map<TID_ARGS>>            703,594,821 ns  rate=192.902M/s
TraceTids<absl::flat_hash_map<TID_ARGS>>    11,161,951,632 ns rate=12.1597M/s
TraceTids<folly::F14FastMap<TID_ARGS>>         782,057,900 ns  rate=173.558M/s

Bug: 205302474
Change-Id: I6b2e6d875b5321e4c5874bbebf1de945ce21a95d