[tracing] Optimize StackFrameDeduplicator.

base/trace_event/heap_profiler_stack_frame_deduplicator.h

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
 #define BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_
 
-#include <map>
+#include <deque>
 #include <string>
-#include <vector>
+#include <unordered_map>
 
 #include "base/base_export.h"
+#include "base/containers/flat_map.h"
 #include "base/macros.h"
 #include "base/trace_event/heap_profiler_allocation_context.h"
 
 namespace base {
 namespace trace_event {
 
 class StringDeduplicator;
 class TraceEventMemoryOverhead;
 class TracedValue;
 
@@ skipping 15 matching lines @@
     size_t EstimateMemoryUsage() const;
 
     StackFrame frame;
 
     // The index of the parent stack frame in |frames_|, or kInvalidFrameIndex
     // if there is no parent frame (when it is at the bottom of the call stack).
     int parent_frame_index;
     constexpr static int kInvalidFrameIndex = -1;
 
     // Indices into |frames_| of frames called from the current frame.
-    std::map<StackFrame, int> children;
+    base::flat_map<StackFrame, int> children;
   };
 
-  using ConstIterator = std::vector<FrameNode>::const_iterator;
+  using ConstIterator = std::deque<FrameNode>::const_iterator;
 
   // |string_deduplication| is used during serialization, and is expected
   // to outlive instances of this class.
   explicit StackFrameDeduplicator(StringDeduplicator* string_deduplicator);
   ~StackFrameDeduplicator();
 
   // Inserts a backtrace where |beginFrame| is a pointer to the bottom frame
   // (e.g. main) and |endFrame| is a pointer past the top frame (most recently
   // called function), and returns the index of its leaf node in |frames_|.
   // Returns -1 if the backtrace is empty.
   int Insert(const StackFrame* beginFrame, const StackFrame* endFrame);
 
   // Iterators over the frame nodes in the call tree.
   ConstIterator begin() const { return frames_.begin(); }
   ConstIterator end() const { return frames_.end(); }
 
   // Appends new |stackFrames| dictionary items that were added after the
   // last call to this function.
   void SerializeIncrementally(TracedValue* traced_value);
 
   // Estimates memory overhead including |sizeof(StackFrameDeduplicator)|.
   void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead);
 
  private:
+  // Checks that existing backtrace identified by |frame_index| equals
+  // to the one identified by |begin_frame|, |end_frame|.
+  bool Match(int frame_index,
+             const StackFrame* begin_frame,
+             const StackFrame* end_frame) const;
+
   StringDeduplicator* string_deduplicator_;
 
-  std::map<StackFrame, int> roots_;
-  std::vector<FrameNode> frames_;
+  base::flat_map<StackFrame, int> roots_;
+  std::deque<FrameNode> frames_;
   size_t last_exported_index_;
 
+  // {backtrace_hash -> frame_index} map for finding backtraces that are
+  // already added. Backtraces themselves are not stored in the map, instead
+  // Match() is used on the found frame_index to detect collisions.
+  std::unordered_map<size_t, int> backtrace_lookup_table_;
+
   DISALLOW_COPY_AND_ASSIGN(StackFrameDeduplicator);
 };
 
 }  // namespace trace_event
 }  // namespace base
 
 #endif  // BASE_TRACE_EVENT_HEAP_PROFILER_STACK_FRAME_DEDUPLICATOR_H_