[tracing] Optimize StackFrameDeduplicator.

[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}
Committed: https://chromium.googlesource.com/chromium/src/+/3de608576703311817c69a8a64bdbc4feb87519b

[DmitrySkiba, 2017-07-12 02:54:33]

dskiba@chromium.org changed reviewers:
+ primiano@chromium.org

[Primiano Tucci (use gerrit), 2017-07-12 15:31:14]

Can you plz add some comments? The code itself looks good, but I have no idea
what to expect from that StackFrameDeduplicator::Match, so no idea if what it
does is intended or not .

https://codereview.chromium.org/2977783002/diff/1/base/trace_event/heap_profi...
File base/trace_event/heap_profiler_stack_frame_deduplicator.h (right):

https://codereview.chromium.org/2977783002/diff/1/base/trace_event/heap_profi...
base/trace_event/heap_profiler_stack_frame_deduplicator.h:77: bool Match(int
frame_index,
I have no idea what this function does. Matches what with what?

https://codereview.chromium.org/2977783002/diff/1/base/trace_event/heap_profi...
base/trace_event/heap_profiler_stack_frame_deduplicator.h:87:
std::unordered_map<size_t, int> lookup_table_;
can yuou add a comment and call this in a more significative name?
I havent look at the cc yet, but right now this is a super-generic lookup table
tha maps size_t to int?
Can we be a bit more specific?

[DmitrySkiba, 2017-07-13 00:15:15]

On 2017/07/12 15:31:14, Primiano Tucci wrote:
> Can you plz add some comments? The code itself looks good, but I have no idea
> what to expect from that StackFrameDeduplicator::Match, so no idea if what it
> does is intended or not .
> 
>
https://codereview.chromium.org/2977783002/diff/1/base/trace_event/heap_profi...
> File base/trace_event/heap_profiler_stack_frame_deduplicator.h (right):
> 
>
https://codereview.chromium.org/2977783002/diff/1/base/trace_event/heap_profi...
> base/trace_event/heap_profiler_stack_frame_deduplicator.h:77: bool Match(int
> frame_index,
> I have no idea what this function does. Matches what with what?
> 
>
https://codereview.chromium.org/2977783002/diff/1/base/trace_event/heap_profi...
> base/trace_event/heap_profiler_stack_frame_deduplicator.h:87:
> std::unordered_map<size_t, int> lookup_table_;
> can yuou add a comment and call this in a more significative name?
> I havent look at the cc yet, but right now this is a super-generic lookup
table
> tha maps size_t to int?
> Can we be a bit more specific?

Sorry, I was in a hurry :) Added couple of comments - let me know if more is
needed.

[Primiano Tucci (use gerrit), 2017-07-13 17:47:00]

Cool LGTM. would be great to land the perftests first to see the bump :)

https://codereview.chromium.org/2977783002/diff/20001/base/trace_event/heap_p...
File base/trace_event/heap_profiler_stack_frame_deduplicator.cc (right):

https://codereview.chromium.org/2977783002/diff/20001/base/trace_event/heap_p...
base/trace_event/heap_profiler_stack_frame_deduplicator.cc:29: size_t summary =
0;
summary -> hash ?

[DmitrySkiba, 2017-07-14 02:07:33]

The CQ bit was checked by dskiba@chromium.org

[DmitrySkiba, 2017-07-14 02:07:34]

The patchset sent to the CQ was uploaded after l-g-t-m from
primiano@chromium.org
Link to the patchset: https://codereview.chromium.org/2977783002/#ps80001
(title: "summary -> hash")

[commit-bot: I haz the power, 2017-07-14 02:07:49]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-07-14 02:59:19]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-07-14 02:59:21]

Try jobs failed on following builders:
  linux_chromium_tsan_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[DmitrySkiba, 2017-07-14 15:12:58]

The CQ bit was checked by dskiba@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-07-14 15:13:10]

Dry run: CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-07-14 16:32:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-07-14 16:32:25]

Dry run: This issue passed the CQ dry run.

[DmitrySkiba, 2017-07-16 15:08:34]

The CQ bit was checked by dskiba@chromium.org

[DmitrySkiba, 2017-07-16 15:08:35]

The patchset sent to the CQ was uploaded after l-g-t-m from
primiano@chromium.org
Link to the patchset: https://codereview.chromium.org/2977783002/#ps100001
(title: "Don't use ASSERT_EQ on deque iterators (see goo.gl/9gkBf7)")

[commit-bot: I haz the power, 2017-07-16 15:08:43]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-07-16 17:45:48]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1500217714995250,
"parent_rev": "53e9a8c76989fc910b36f3945134f24b63fb0ae2", "commit_rev":
"d952f15a234a24724b1d59cb8c8c1e77ad1e08d7"}

[commit-bot: I haz the power, 2017-07-16 17:46:08]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1500217714995250,
"parent_rev": "eb12aa53060d9397de49ed5c2e72a0bdf36833e2", "commit_rev":
"3de608576703311817c69a8a64bdbc4feb87519b"}

[commit-bot: I haz the power, 2017-07-16 17:46:23]

Description was changed from

==========
[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
==========

to

==========
[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}
Committed:
https://chromium.googlesource.com/chromium/src/+/3de608576703311817c69a8a64bd...
==========

[commit-bot: I haz the power, 2017-07-16 17:46:25]

Committed patchset #6 (id:100001) as
https://chromium.googlesource.com/chromium/src/+/3de608576703311817c69a8a64bd...