[tracing] Optimize StackFrameDeduplicator.
Profiling StackFrameDeduplicator with new heap format revealed that:
1. At least 60% of all insertions are hits, i.e. they insert backtraces
that already exist.
2. There can be as many as 500K frames.
3. The average child count at each level is ~1.2.
This CL optimizes StackFrameDeduplicator based on that data:
1. Adds a hash-based backtrace lookup to cut down number of lookups
in FrameNode::children maps.
2. Changes FrameNode storage from std::vector to std::deque, avoiding
costly vector reallocations.
3. Changes FrameNode::children storage from std::map to std::flat_map.
These changes improve HeapProfilerPerfTest.DeduplicateStackFrames perftest
~1.6x on macOS (1040ms -> 620ms), but real-world impact should be higher
because the perftest is pessimistic.
BUG=739378
Review-Url: https://codereview.chromium.org/2977783002
Cr-Commit-Position: refs/heads/master@{#487015}
CrOS-Libchrome-Original-Commit: 3de608576703311817c69a8a64bdbc4feb87519b
4 files changed