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
diff --git a/Android.bp b/Android.bp
index 732b11a..bc02fbf 100644
--- a/Android.bp
+++ b/Android.bp
@@ -6905,6 +6905,7 @@
srcs: [
"src/base/base64_unittest.cc",
"src/base/circular_queue_unittest.cc",
+ "src/base/flat_hash_map_unittest.cc",
"src/base/flat_set_unittest.cc",
"src/base/getopt_compat_unittest.cc",
"src/base/logging_unittest.cc",
