Sampling heap profiler: use map instead of vector for children.

src/profiler/sampling-heap-profiler.h

 // Copyright 2015 the V8 project 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 V8_PROFILER_SAMPLING_HEAP_PROFILER_H_
 #define V8_PROFILER_SAMPLING_HEAP_PROFILER_H_
 
 #include <deque>
 #include <map>
 #include <set>
@@ skipping 62 matching lines @@
    public:
     AllocationNode(AllocationNode* parent, const char* name, int script_id,
                    int start_position)
         : parent_(parent),
           script_id_(script_id),
           script_position_(start_position),
           name_(name),
           pinned_(false) {}
     ~AllocationNode() {
       for (auto child : children_) {
-        delete child;
+        delete child.second;
       }
     }
 
    private:
+    typedef uint64_t FunctionId;
+    static FunctionId function_id(int script_id, int start_position,

[ulan, 2016/05/13 09:05:00]

Please add a comment describing what this function returns and assumptions it
makes:
1. If script_id != kNoScriptId then start_position uniquely determines the node.
2. If script_id == kNoScriptId then name uniquely determines the node. Names
derived from VM state must not collide with the builtin names.

[alph, 2016/05/13 18:34:35]

Done.

+                                  const char* name) {

[ulan, 2016/05/12 10:01:20]

Instead of relying on name pointers, can we use "impossible" start_position to
encode the case with "(system)" names?

We already assume that start_position is at most 30-bits (see SharedFunctionInfo
comment).

So instead of storing script_id_ and script_position_ directly in node,
we could store NodeId (or NodePosition).
Something like:

struct NodeId {
 public:
  static NodeId fromFrame(script_id, script_position) {
     CHECK_LT(script_position, kMaxScriptPosition);
     ...
  }
  static NodeId fromSystemState(SystemState system_state) {
     NodeId result;
     result.script_id_ = kNoScriptId;
     result.script_position_ = kMaxScriptPosition +
static_cast<int>(system_state);
     ...
  }
  int script_id() { return script_id_; }
  int script_position() {
    return script_position_ < kMaxScriptPosition ? script_position_ : 0;
  }
 private:
  int script_id_;
  int script_position_;
};

It can be passed directly to std::map assuming that there is operator< defined.

wdyt?

+      return script_id != v8::UnboundScript::kNoScriptId
+                 ? (static_cast<uint64_t>(script_id) << 32) +
+                       (start_position << 1)

[ulan, 2016/05/13 09:05:00]

DCHECK(start_position >= 0 && start_position < (1 << 30));

[alph, 2016/05/13 18:34:35]

Done.

+                 : reinterpret_cast<intptr_t>(name) | 1;
+    }
+    AllocationNode* FindOrAddChildNode(const char* name, int script_id,
+                                       int start_position);
+    // TODO(alph): make use of unordered_map's here. Pay attention to
+    // iterator invalidation during TranslateAllocationNode.
     std::map<size_t, unsigned int> allocations_;
-    std::vector<AllocationNode*> children_;
+    std::map<FunctionId, AllocationNode*> children_;
     AllocationNode* const parent_;
     const int script_id_;
     const int script_position_;
     const char* const name_;
     bool pinned_;
 
     friend class SamplingHeapProfiler;
 
     DISALLOW_COPY_AND_ASSIGN(AllocationNode);
   };
@@ skipping 11 matching lines @@
   // AllocationProfile::Node. The newly created AllocationProfile::Node is added
   // to the provided AllocationProfile *profile*. Line numbers, column numbers,
   // and script names are resolved using *scripts* which maps all currently
   // loaded scripts keyed by their script id.
   v8::AllocationProfile::Node* TranslateAllocationNode(
       AllocationProfile* profile, SamplingHeapProfiler::AllocationNode* node,
       const std::map<int, Handle<Script>>& scripts);
   v8::AllocationProfile::Allocation ScaleSample(size_t size,
                                                 unsigned int count);
   AllocationNode* AddStack();
-  AllocationNode* FindOrAddChildNode(AllocationNode* parent, const char* name,
-                                     int script_id, int start_position);
 
   Isolate* const isolate_;
   Heap* const heap_;
   base::SmartPointer<SamplingAllocationObserver> new_space_observer_;
   base::SmartPointer<SamplingAllocationObserver> other_spaces_observer_;
   StringsStorage* const names_;
   AllocationNode profile_root_;
   std::set<Sample*> samples_;
   const int stack_depth_;
   const uint64_t rate_;
@@ skipping 29 matching lines @@
   SamplingHeapProfiler* const profiler_;
   Heap* const heap_;
   base::RandomNumberGenerator* const random_;
   uint64_t const rate_;
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_PROFILER_SAMPLING_HEAP_PROFILER_H_