Split nodes and edges into separate arrays in heap profiler.

src/profile-generator.h

Index: src/profile-generator.h
diff --git a/src/profile-generator.h b/src/profile-generator.h
index e04ddbf3e277dd3b1b2710ad25e109e343310bee..ec386d3f9535ef9ee10315abff8e0aaf77b46603 100644
--- a/src/profile-generator.h
+++ b/src/profile-generator.h
@@ -446,6 +446,7 @@ class ProfileGenerator {
 
 
 class HeapEntry;
+class HeapSnapshot;
 
 class HeapGraphEdge BASE_EMBEDDED {
  public:
@@ -460,9 +461,9 @@ class HeapGraphEdge BASE_EMBEDDED {
   };
 
   HeapGraphEdge() { }
-  void Init(int child_index, Type type, const char* name, HeapEntry* to);
-  void Init(int child_index, Type type, int index, HeapEntry* to);
-  void Init(int child_index, int index, HeapEntry* to);
+  HeapGraphEdge(Type type, const char* name, int from, int to);
+  HeapGraphEdge(Type type, int index, int from, int to);
+  void ReplaceToIndexWithEntry(HeapSnapshot* snapshot);
 
   Type type() const { return static_cast<Type>(type_); }
   int index() const {
@@ -471,48 +472,34 @@ class HeapGraphEdge BASE_EMBEDDED {
   }
   const char* name() const {
     ASSERT(type_ == kContextVariable
-           || type_ == kProperty
-           || type_ == kInternal
-           || type_ == kShortcut);
+        || type_ == kProperty
+        || type_ == kInternal
+        || type_ == kShortcut);
     return name_;
   }
-  HeapEntry* to() const { return to_; }
   INLINE(HeapEntry* from() const);
+  HeapEntry* to() const { return to_entry_; }
 
  private:
-  int child_index_ : 29;
+  INLINE(HeapSnapshot* snapshot() const);
+
   unsigned type_ : 3;
+  int from_index_ : 29;
+  union {
+    // During entries population |to_| is used for storing the index,

[mnaganov (inactive), 2012/05/08 12:05:20]

nit: |to_| -> |to_index_|

[alexeif, 2012/05/09 12:38:07]

Done.

+    // afterwards it is replaced with a pointer to the entry.
+    int to_index_;
+    HeapEntry* to_entry_;
+  };
   union {
     int index_;
     const char* name_;
   };
-  HeapEntry* to_;
-
-  DISALLOW_COPY_AND_ASSIGN(HeapGraphEdge);
 };
 
 
-class HeapSnapshot;
-
 // HeapEntry instances represent an entity from the heap (or a special
-// virtual node, e.g. root). To make heap snapshots more compact,
-// HeapEntries has a special memory layout (no Vectors or Lists used):
-//
-//   +-----------------+
-//        HeapEntry
-//   +-----------------+
-//      HeapGraphEdge    |
-//           ...         } children_count
-//      HeapGraphEdge    |
-//   +-----------------+
-//      HeapGraphEdge*   |
-//           ...         } retainers_count
-//      HeapGraphEdge*   |
-//   +-----------------+
-//
-// In a HeapSnapshot, all entries are hand-allocated in a continuous array
-// of raw bytes.
-//
+// virtual node, e.g. root).
 class HeapEntry BASE_EMBEDDED {
  public:
   enum Type {
@@ -527,15 +514,14 @@ class HeapEntry BASE_EMBEDDED {
     kNative = v8::HeapGraphNode::kNative,
     kSynthetic = v8::HeapGraphNode::kSynthetic
   };
+  static const int kNoEntry;
 
   HeapEntry() { }
-  void Init(HeapSnapshot* snapshot,
+  HeapEntry(HeapSnapshot* snapshot,
             Type type,
             const char* name,
             SnapshotObjectId id,
-            int self_size,
-            int children_count,
-            int retainers_count);
+            int self_size);
 
   HeapSnapshot* snapshot() { return snapshot_; }
   Type type() { return static_cast<Type>(type_); }
@@ -545,20 +531,27 @@ class HeapEntry BASE_EMBEDDED {
   int self_size() { return self_size_; }
   int retained_size() { return retained_size_; }
   void add_retained_size(int size) { retained_size_ += size; }
-  void set_retained_size(int value) { retained_size_ = value; }
-  int ordered_index() { return ordered_index_; }
-  void set_ordered_index(int value) { ordered_index_ = value; }
-  int entry_index() { return entry_index_; }
-  void set_entry_index(int value) { entry_index_ = value; }
-
-  Vector<HeapGraphEdge> children() {
-    return Vector<HeapGraphEdge>(children_arr(), children_count_); }
+  void set_retained_size(int size) { retained_size_ = size; }
+  INLINE(int index() const);
+  int postorder_index() { return postorder_index_; }
+  void set_postorder_index(int value) { postorder_index_ = value; }
+  int children_count() const { return children_count_; }
+  INLINE(int set_children_index(int index));
+  INLINE(int set_retainers_index(int index));
+  void add_child(HeapGraphEdge* edge) {
+    children_arr()[children_count_++] = edge;
+  }
+  void add_retainer(HeapGraphEdge* edge) {
+    retainers_arr()[retainers_count_++] = edge;
+  }
+  Vector<HeapGraphEdge*> children() {
+    return Vector<HeapGraphEdge*>(children_arr(), children_count_); }
   Vector<HeapGraphEdge*> retainers() {
     return Vector<HeapGraphEdge*>(retainers_arr(), retainers_count_); }
-  HeapEntry* dominator() { return dominator_; }
+  INLINE(HeapEntry* dominator() const);
   void set_dominator(HeapEntry* entry) {
     ASSERT(entry != NULL);
-    dominator_ = entry;
+    dominator_ = entry->index();
   }
   void clear_paint() { painted_ = false; }
   bool painted() { return painted_; }
@@ -566,57 +559,37 @@ class HeapEntry BASE_EMBEDDED {
   bool user_reachable() { return user_reachable_; }
   void set_user_reachable() { user_reachable_ = true; }
 
-  void SetIndexedReference(HeapGraphEdge::Type type,
-                           int child_index,
-                           int index,
-                           HeapEntry* entry,
-                           int retainer_index);
-  void SetNamedReference(HeapGraphEdge::Type type,
-                         int child_index,
-                         const char* name,
-                         HeapEntry* entry,
-                         int retainer_index);
-  void SetUnidirElementReference(int child_index, int index, HeapEntry* entry);
-
-  size_t EntrySize() {
-    return EntriesSize(1, children_count_, retainers_count_);
-  }
+  void SetIndexedReference(
+      HeapGraphEdge::Type type, int index, HeapEntry* entry);
+  void SetNamedReference(
+      HeapGraphEdge::Type type, const char* name, HeapEntry* entry);
 
   void Print(
       const char* prefix, const char* edge_name, int max_depth, int indent);
 
   Handle<HeapObject> GetHeapObject();
 
-  static size_t EntriesSize(int entries_count,
-                            int children_count,
-                            int retainers_count);
-
  private:
-  HeapGraphEdge* children_arr() {
-    return reinterpret_cast<HeapGraphEdge*>(this + 1);
-  }
-  HeapGraphEdge** retainers_arr() {
-    return reinterpret_cast<HeapGraphEdge**>(children_arr() + children_count_);
-  }
+  INLINE(HeapGraphEdge** children_arr());
+  INLINE(HeapGraphEdge** retainers_arr());
   const char* TypeAsString();
 
   unsigned painted_: 1;
   unsigned user_reachable_: 1;
+  int dominator_: 30;
   unsigned type_: 4;
-  int children_count_: 26;
-  int retainers_count_;
+  int retainers_count_: 28;
+  int retainers_index_;
+  int children_count_;
+  int children_index_;
   int self_size_;
   union {
-    int ordered_index_;  // Used during dominator tree building.
-    int retained_size_;  // At that moment, there is no retained size yet.
+    int postorder_index_;  // Used during dominator tree building.
+    int retained_size_;    // At that moment, there is no retained size yet.
   };
-  int entry_index_;
   SnapshotObjectId id_;
-  HeapEntry* dominator_;
   HeapSnapshot* snapshot_;
   const char* name_;
-
-  DISALLOW_COPY_AND_ASSIGN(HeapEntry);
 };
 
 
@@ -637,63 +610,59 @@ class HeapSnapshot {
                Type type,
                const char* title,
                unsigned uid);
-  ~HeapSnapshot();
   void Delete();
 
   HeapSnapshotsCollection* collection() { return collection_; }
   Type type() { return type_; }
   const char* title() { return title_; }
   unsigned uid() { return uid_; }
-  HeapEntry* root() { return root_entry_; }
-  HeapEntry* gc_roots() { return gc_roots_entry_; }
-  HeapEntry* natives_root() { return natives_root_entry_; }
-  HeapEntry* gc_subroot(int index) { return gc_subroot_entries_[index]; }
-  List<HeapEntry*>* entries() { return &entries_; }
-  size_t raw_entries_size() { return raw_entries_size_; }
-  int number_of_edges() { return number_of_edges_; }
+  size_t RawSnapshotSize() const;
+  HeapEntry* root() { return &entries_[root_entry_]; }
+  HeapEntry* gc_roots() { return &entries_[gc_roots_entry_]; }
+  HeapEntry* natives_root() { return &entries_[natives_root_entry_]; }
+  HeapEntry* gc_subroot(int index) {
+    return &entries_[gc_subroot_entries_[index]];
+  }
+  List<HeapEntry>& entries() { return entries_; }
+  List<HeapGraphEdge>& edges() { return edges_; }
+  List<HeapGraphEdge*>& children() { return children_; }
+  List<HeapGraphEdge*>& retainers() { return retainers_; }
   void RememberLastJSObjectId();
   SnapshotObjectId max_snapshot_js_object_id() const {
     return max_snapshot_js_object_id_;
   }
 
-  void AllocateEntries(
-      int entries_count, int children_count, int retainers_count);
   HeapEntry* AddEntry(HeapEntry::Type type,
                       const char* name,
                       SnapshotObjectId id,
-                      int size,
-                      int children_count,
-                      int retainers_count);
-  HeapEntry* AddRootEntry(int children_count);
-  HeapEntry* AddGcRootsEntry(int children_count, int retainers_count);
-  HeapEntry* AddGcSubrootEntry(int tag,
-                               int children_count,
-                               int retainers_count);
-  HeapEntry* AddNativesRootEntry(int children_count, int retainers_count);
+                      int size);
+  HeapEntry* AddRootEntry();
+  HeapEntry* AddGcRootsEntry();
+  HeapEntry* AddGcSubrootEntry(int tag);
+  HeapEntry* AddNativesRootEntry();
   void ClearPaint();
   HeapEntry* GetEntryById(SnapshotObjectId id);
   List<HeapEntry*>* GetSortedEntriesList();
   void SetDominatorsToSelf();
+  void FillChildrenAndRetainers();
 
   void Print(int max_depth);
   void PrintEntriesSize();
 
  private:
-  HeapEntry* GetNextEntryToInit();
-
   HeapSnapshotsCollection* collection_;
   Type type_;
   const char* title_;
   unsigned uid_;
-  HeapEntry* root_entry_;
-  HeapEntry* gc_roots_entry_;
-  HeapEntry* natives_root_entry_;
-  HeapEntry* gc_subroot_entries_[VisitorSynchronization::kNumberOfSyncTags];
-  char* raw_entries_;
-  List<HeapEntry*> entries_;
+  int root_entry_;

[yurys, 2012/05/08 14:55:59]

I'd rename these fields from *_entry_ to *_index_

[alexeif, 2012/05/09 12:38:07]

Done.

+  int gc_roots_entry_;
+  int natives_root_entry_;
+  int gc_subroot_entries_[VisitorSynchronization::kNumberOfSyncTags];
+  List<HeapEntry> entries_;
+  List<HeapGraphEdge> edges_;
+  List<HeapGraphEdge*> children_;
+  List<HeapGraphEdge*> retainers_;
   List<HeapEntry*> sorted_entries_;
-  size_t raw_entries_size_;
-  int number_of_edges_;
   SnapshotObjectId max_snapshot_js_object_id_;
 
   friend class HeapSnapshotTester;
@@ -828,8 +797,7 @@ typedef void* HeapThing;
 class HeapEntriesAllocator {
  public:
   virtual ~HeapEntriesAllocator() { }
-  virtual HeapEntry* AllocateEntry(
-      HeapThing ptr, int children_count, int retainers_count) = 0;
+  virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0;
 };
 
 
@@ -838,37 +806,11 @@ class HeapEntriesAllocator {
 class HeapEntriesMap {
  public:
   HeapEntriesMap();
-  ~HeapEntriesMap();
-
-  void AllocateEntries(HeapThing root_object);
-  HeapEntry* Map(HeapThing thing);
-  void Pair(HeapThing thing, HeapEntriesAllocator* allocator, HeapEntry* entry);
-  void CountReference(HeapThing from, HeapThing to,
-                      int* prev_children_count = NULL,
-                      int* prev_retainers_count = NULL);
 
-  int entries_count() { return entries_count_; }
-  int total_children_count() { return total_children_count_; }
-  int total_retainers_count() { return total_retainers_count_; }
-
-  static HeapEntry* const kHeapEntryPlaceholder;
+  int Map(HeapThing thing);
+  void Pair(HeapThing thing, int entry);
 
  private:
-  struct EntryInfo {
-    EntryInfo(HeapEntry* entry, HeapEntriesAllocator* allocator)
-        : entry(entry),
-          allocator(allocator),
-          children_count(0),
-          retainers_count(0) {
-    }
-    HeapEntry* entry;
-    HeapEntriesAllocator* allocator;
-    int children_count;
-    int retainers_count;
-  };
-
-  static inline void AllocateHeapEntryForMapEntry(HashMap::Entry* map_entry);
-
   static uint32_t Hash(HeapThing thing) {
     return ComputeIntegerHash(
         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)),
@@ -879,9 +821,6 @@ class HeapEntriesMap {
   }
 
   HashMap entries_;
-  int entries_count_;
-  int total_children_count_;
-  int total_retainers_count_;
 
   friend class HeapObjectsSet;
 
@@ -916,26 +855,18 @@ class SnapshotFillerInterface {
   virtual HeapEntry* FindOrAddEntry(HeapThing ptr,
                                     HeapEntriesAllocator* allocator) = 0;
   virtual void SetIndexedReference(HeapGraphEdge::Type type,
-                                   HeapThing parent_ptr,
-                                   HeapEntry* parent_entry,
+                                   int parent_entry,
                                    int index,
-                                   HeapThing child_ptr,
                                    HeapEntry* child_entry) = 0;
   virtual void SetIndexedAutoIndexReference(HeapGraphEdge::Type type,
-                                            HeapThing parent_ptr,
-                                            HeapEntry* parent_entry,
-                                            HeapThing child_ptr,
+                                            int parent_entry,
                                             HeapEntry* child_entry) = 0;
   virtual void SetNamedReference(HeapGraphEdge::Type type,
-                                 HeapThing parent_ptr,
-                                 HeapEntry* parent_entry,
+                                 int parent_entry,
                                  const char* reference_name,
-                                 HeapThing child_ptr,
                                  HeapEntry* child_entry) = 0;
   virtual void SetNamedAutoIndexReference(HeapGraphEdge::Type type,
-                                          HeapThing parent_ptr,
-                                          HeapEntry* parent_entry,
-                                          HeapThing child_ptr,
+                                          int parent_entry,
                                           HeapEntry* child_entry) = 0;
 };
 
@@ -954,8 +885,7 @@ class V8HeapExplorer : public HeapEntriesAllocator {
   V8HeapExplorer(HeapSnapshot* snapshot,
                  SnapshottingProgressReportingInterface* progress);
   virtual ~V8HeapExplorer();
-  virtual HeapEntry* AllocateEntry(
-      HeapThing ptr, int children_count, int retainers_count);
+  virtual HeapEntry* AllocateEntry(HeapThing ptr);
   void AddRootEntries(SnapshotFillerInterface* filler);
   int EstimateObjectsCount(HeapIterator* iterator);
   bool IterateAndExtractReferences(SnapshotFillerInterface* filler);
@@ -967,75 +897,72 @@ class V8HeapExplorer : public HeapEntriesAllocator {
   static HeapObject* const kInternalRootObject;
 
  private:
-  HeapEntry* AddEntry(
-      HeapObject* object, int children_count, int retainers_count);
+  HeapEntry* AddEntry(HeapObject* object);
   HeapEntry* AddEntry(HeapObject* object,
                       HeapEntry::Type type,
-                      const char* name,
-                      int children_count,
-                      int retainers_count);
+                      const char* name);
   const char* GetSystemEntryName(HeapObject* object);
 
   void ExtractReferences(HeapObject* obj);
   void ExtractJSGlobalProxyReferences(JSGlobalProxy* proxy);
-  void ExtractJSObjectReferences(HeapEntry* entry, JSObject* js_obj);
-  void ExtractStringReferences(HeapEntry* entry, String* obj);
-  void ExtractContextReferences(HeapEntry* entry, Context* context);
-  void ExtractMapReferences(HeapEntry* entry, Map* map);
-  void ExtractSharedFunctionInfoReferences(HeapEntry* entry,
+  void ExtractJSObjectReferences(int entry, JSObject* js_obj);
+  void ExtractStringReferences(int entry, String* obj);
+  void ExtractContextReferences(int entry, Context* context);
+  void ExtractMapReferences(int entry, Map* map);
+  void ExtractSharedFunctionInfoReferences(int entry,
                                            SharedFunctionInfo* shared);
-  void ExtractScriptReferences(HeapEntry* entry, Script* script);
-  void ExtractCodeCacheReferences(HeapEntry* entry, CodeCache* code_cache);
-  void ExtractCodeReferences(HeapEntry* entry, Code* code);
-  void ExtractJSGlobalPropertyCellReferences(HeapEntry* entry,
+  void ExtractScriptReferences(int entry, Script* script);
+  void ExtractCodeCacheReferences(int entry, CodeCache* code_cache);
+  void ExtractCodeReferences(int entry, Code* code);
+  void ExtractJSGlobalPropertyCellReferences(int entry,
                                              JSGlobalPropertyCell* cell);
-  void ExtractClosureReferences(JSObject* js_obj, HeapEntry* entry);
-  void ExtractPropertyReferences(JSObject* js_obj, HeapEntry* entry);
-  void ExtractElementReferences(JSObject* js_obj, HeapEntry* entry);
-  void ExtractInternalReferences(JSObject* js_obj, HeapEntry* entry);
+  void ExtractClosureReferences(JSObject* js_obj, int entry);
+  void ExtractPropertyReferences(JSObject* js_obj, int entry);
+  void ExtractElementReferences(JSObject* js_obj, int entry);
+  void ExtractInternalReferences(JSObject* js_obj, int entry);
   bool IsEssentialObject(Object* object);
   void SetClosureReference(HeapObject* parent_obj,
-                           HeapEntry* parent,
+                           int parent,
                            String* reference_name,
                            Object* child);
   void SetNativeBindReference(HeapObject* parent_obj,
-                              HeapEntry* parent,
+                              int parent,
                               const char* reference_name,
                               Object* child);
   void SetElementReference(HeapObject* parent_obj,
-                           HeapEntry* parent,
+                           int parent,
                            int index,
                            Object* child);
   void SetInternalReference(HeapObject* parent_obj,
-                            HeapEntry* parent,
+                            int parent,
                             const char* reference_name,
                             Object* child,
                             int field_offset = -1);
   void SetInternalReference(HeapObject* parent_obj,
-                            HeapEntry* parent,
+                            int parent,
                             int index,
                             Object* child,
                             int field_offset = -1);
   void SetHiddenReference(HeapObject* parent_obj,
-                          HeapEntry* parent,
+                          int parent,
                           int index,
                           Object* child);
   void SetWeakReference(HeapObject* parent_obj,
-                        HeapEntry* parent_entry,
+                        int parent,
                         int index,
                         Object* child_obj,
                         int field_offset);
   void SetPropertyReference(HeapObject* parent_obj,
-                            HeapEntry* parent,
+                            int parent,
                             String* reference_name,
                             Object* child,
                             const char* name_format_string = NULL,
                             int field_offset = -1);
   void SetPropertyShortcutReference(HeapObject* parent_obj,
-                                    HeapEntry* parent,
+                                    int parent,
                                     String* reference_name,
                                     Object* child);
-  void SetUserGlobalReference(Object* window);
+  void SetUserGlobalReference(Object* user_global);
   void SetRootGcRootsReference();
   void SetGcRootsReference(VisitorSynchronization::SyncTag tag);
   void SetGcSubrootReference(
@@ -1139,10 +1066,9 @@ class HeapSnapshotGenerator : public SnapshottingProgressReportingInterface {
   bool BuildDominatorTree(const Vector<HeapEntry*>& entries,
                           Vector<int>* dominators);
   bool CalculateRetainedSizes();
-  bool CountEntriesAndReferences();
   bool FillReferences();
   void FillPostorderIndexes(Vector<HeapEntry*>* entries);
-  bool IsUserGlobalReference(const HeapGraphEdge& edge);
+  bool IsUserGlobalReference(const HeapGraphEdge* edge);
   void MarkUserReachableObjects();
   void ProgressStep();
   bool ProgressReport(bool force = false);
@@ -1186,20 +1112,21 @@ class HeapSnapshotJSONSerializer {
         v8::internal::kZeroHashSeed);
   }
 
-  void CalculateNodeIndexes(const List<HeapEntry*>& nodes);
   HeapSnapshot* CreateFakeSnapshot();
   int GetStringId(const char* s);
+  int entry_index(HeapEntry* e) { return e->index() * kNodeFieldsCount; }
   void SerializeEdge(HeapGraphEdge* edge, bool first_edge);
-  void SerializeEdges(const List<HeapEntry*>& nodes);
+  void SerializeEdges(const List<HeapEntry>& nodes);
   void SerializeImpl();
   void SerializeNode(HeapEntry* entry, int edges_index);
-  void SerializeNodes(const List<HeapEntry*>& nodes);
+  void SerializeNodes(const List<HeapEntry>& nodes);
   void SerializeSnapshot();
   void SerializeString(const unsigned char* s);
   void SerializeStrings();
   void SortHashMap(HashMap* map, List<HashMap::Entry*>* sorted_entries);
 
-  static const int kMaxSerializableSnapshotRawSize;
+  static const int kEdgeFieldsCount;
+  static const int kNodeFieldsCount;
 
   HeapSnapshot* snapshot_;
   HashMap strings_;