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;

[ofrobots, 2016/05/11 16:48:13]

Going forward it would be better to call this `CallSiteId` as it may not
necessarily correspond to the start of a function.

[alph, 2016/05/11 17:37:17]

I assume (need) it to be the function start position, not the call site
position. Am I wrong?

[ofrobots, 2016/05/11 22:48:09]

I am considering making it the call-site position in the future, as that can
provide more accurate path information leading to allocations sites. I am not
sure at this point if this is worthwhile, but I don't want to close the door on
this possibility just yet. What's the reason for your assumption (need) for it
to be the function start rather than the call site?

[alph, 2016/05/11 23:17:34]

It just reflects the current state of the nodes, which is function. We can
easily change the name to CallSiteId as soon as we support them. The name is not
exposed into the API. 

[ofrobots, 2016/05/12 00:03:05]

sgtm.

+    static FunctionId function_id(int script_id, int start_position,
+                                  const char* name) {
+      return script_id
+                 ? (static_cast<uint64_t>(script_id) << 32) + start_position
+                 : static_cast<uint32_t>(reinterpret_cast<intptr_t>(name));

[ofrobots, 2016/05/11 16:48:13]

Why the truncation to 32 bits on 64-bit platforms? FunctionId is 64 bits, could
you keep all the bits?

[alph, 2016/05/11 17:37:17]

The name is used only for system "functions", i.e. (V8), (COMPILER). I don't
want them to clash with the rest of the user code what has a non-zero script id.
That's why I want to keep the script id portion of the FunctionId zero. 

[ofrobots, 2016/05/11 22:48:09]

When called from sampling-heap-profiler.cc:204 (original source), I think it is
possible to reach this side of the if for a non-system "function". Or am I
misunderstanding things? 

BTW, the script_id checkout should explicitly compare against kNoScriptId.

[alph, 2016/05/11 23:17:34]

Yes, you can reach it for builtin functions like charCodeAt. There are not too
many of them, so chances for lower 32-bits of pointers clash are quite small.
If you think this is still unacceptable, I can play with bit tagging, e.g.
assuming the pointers low bit is zero.
Thanks, fixed.

[ofrobots, 2016/05/12 00:03:05]

If easy to do, it would be best to avoid the possibility of the clash to guard
against how builtin names are generated in the future. This code shouldn't
silently start generating misleading profiles when something else in the
codebase changes.

However.. I am not sure we can depend on pointers-to-char to have > byte
alignment. Any other ideas?

[alph, 2016/05/12 01:37:44]

Well, these are not pointers to arbitrary chars, but to the beginning of
allocated strings, so I would assume they are aligned...

However to be on the safe side I propose to set the last bit on the pointer, so
it would still point inside the string, so we get unique ids for unique strings.
wdyt?

+    }
+    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_