Get rid of HeapEntry to ID map in heap profile serializer

src/profile-generator.cc

Index: src/profile-generator.cc
===================================================================
--- src/profile-generator.cc	(revision 11244)
+++ src/profile-generator.cc	(working copy)
@@ -975,6 +975,7 @@
   name_ = name;
   self_size_ = self_size;
   retained_size_ = 0;
+  entry_index_ = -1;
   children_count_ = children_count;
   retainers_count_ = retainers_count;
   dominator_ = NULL;
@@ -1108,7 +1109,7 @@
 
 template <> struct SnapshotSizeConstants<4> {
   static const int kExpectedHeapGraphEdgeSize = 12;
-  static const int kExpectedHeapEntrySize = 32;
+  static const int kExpectedHeapEntrySize = 36;
   static const size_t kMaxSerializableSnapshotRawSize = 256 * MB;
 };
 
@@ -1133,7 +1134,6 @@
       gc_roots_entry_(NULL),
       natives_root_entry_(NULL),
       raw_entries_(NULL),
-      entries_sorted_(false),
       max_snapshot_js_object_id_(0) {
   STATIC_CHECK(
       sizeof(HeapGraphEdge) ==
@@ -1185,6 +1185,7 @@
 
 HeapEntry* HeapSnapshot::AddRootEntry(int children_count) {
   ASSERT(root_entry_ == NULL);
+  ASSERT(entries_.is_empty()); // Root entry must be the first one.
   return (root_entry_ = AddEntry(HeapEntry::kObject,
                                  "",
                                  HeapObjectsMap::kInternalRootObjectId,
@@ -1285,11 +1286,11 @@
 
 
 List<HeapEntry*>* HeapSnapshot::GetSortedEntriesList() {
-  if (!entries_sorted_) {
-    entries_.Sort(SortByIds);
-    entries_sorted_ = true;
+  if (sorted_entries_.is_empty()) {
+    sorted_entries_.AddAll(entries_);
+    sorted_entries_.Sort(SortByIds);
   }
-  return &entries_;
+  return &sorted_entries_;
 }
 
 
@@ -1514,20 +1515,39 @@
 }
 
 
-void HeapEntriesMap::AllocateEntries() {
-  for (HashMap::Entry* p = entries_.Start();
-       p != NULL;
-       p = entries_.Next(p)) {
-    EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(p->value);
+void HeapEntriesMap::AllocateHeapEntryForMapEntry(HashMap::Entry* map_entry) {
+    EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(map_entry->value);
     entry_info->entry = entry_info->allocator->AllocateEntry(
-        p->key,
+        map_entry->key,
         entry_info->children_count,
         entry_info->retainers_count);
     ASSERT(entry_info->entry != NULL);
     ASSERT(entry_info->entry != kHeapEntryPlaceholder);
     entry_info->children_count = 0;
     entry_info->retainers_count = 0;
+}
+
+
+void HeapEntriesMap::AllocateEntries(HeapThing root_object) {
+  HashMap::Entry* root_entry =
+      entries_.Lookup(root_object, Hash(root_object), false);
+  ASSERT(root_entry != NULL);
+  // Make sure root entry is allocated first.
+  AllocateHeapEntryForMapEntry(root_entry);
+  void* root_entry_value = root_entry->value;
+  // Remove the root object from map while iterating through other entries.
+  entries_.Remove(root_object, Hash(root_object));
+  root_entry = NULL;
+
+  for (HashMap::Entry* p = entries_.Start();
+       p != NULL;
+       p = entries_.Next(p)) {
+    AllocateHeapEntryForMapEntry(p);
   }
+
+  // Insert root entry back.
+  root_entry = entries_.Lookup(root_object, Hash(root_object), true);
+  root_entry->value = root_entry_value;
 }
 
 
@@ -3106,7 +3126,7 @@
                              entries_.total_retainers_count());
 
   // Allocate heap objects to entries hash map.
-  entries_.AllocateEntries();
+  entries_.AllocateEntries(V8HeapExplorer::kInternalRootObject);
 
   // Pass 2. Fill references.
   if (!FillReferences()) return false;
@@ -3417,7 +3437,6 @@
   }
   // Since nodes graph is cyclic, we need the first pass to enumerate
   // them. Strings can be serialized in one pass.
-  EnumerateNodes();
   SerializeImpl();
 
   delete writer_;
@@ -3470,34 +3489,6 @@
 }
 
 
-class HeapSnapshotJSONSerializerEnumerator {
- public:
-  explicit HeapSnapshotJSONSerializerEnumerator(HeapSnapshotJSONSerializer* s)
-      : s_(s) {
-  }
-  void Apply(HeapEntry** entry) {
-    s_->GetNodeId(*entry);
-  }
- private:
-  HeapSnapshotJSONSerializer* s_;
-};
-
-void HeapSnapshotJSONSerializer::EnumerateNodes() {
-  GetNodeId(snapshot_->root());  // Make sure root gets the first id.
-  HeapSnapshotJSONSerializerEnumerator iter(this);
-  snapshot_->IterateEntries(&iter);
-}
-
-
-int HeapSnapshotJSONSerializer::GetNodeId(HeapEntry* entry) {
-  HashMap::Entry* cache_entry = nodes_.Lookup(entry, ObjectHash(entry), true);
-  if (cache_entry->value == NULL) {
-    cache_entry->value = reinterpret_cast<void*>(next_node_id_++);
-  }
-  return static_cast<int>(reinterpret_cast<intptr_t>(cache_entry->value));
-}
-
-
 int HeapSnapshotJSONSerializer::GetStringId(const char* s) {
   HashMap::Entry* cache_entry = strings_.Lookup(
       const_cast<char*>(s), ObjectHash(s), true);
@@ -3548,7 +3539,7 @@
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(edge_name_or_index, buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
-  buffer_pos = itoa(GetNodeId(edge->to()), buffer, buffer_pos);
+  buffer_pos = itoa(edge->to()->entry_index(), buffer, buffer_pos);
   buffer[buffer_pos++] = '\0';
   writer_->AddString(buffer.start());
 }
@@ -3575,7 +3566,7 @@
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(entry->retained_size(), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
-  buffer_pos = itoa(GetNodeId(entry->dominator()), buffer, buffer_pos);
+  buffer_pos = itoa(entry->dominator()->entry_index(), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(children.length(), buffer, buffer_pos);
   buffer[buffer_pos++] = '\0';
@@ -3645,23 +3636,25 @@
   const int node_fields_count = 7;
   // type,name,id,self_size,retained_size,dominator,children_count.
   const int edge_fields_count = 3;  // type,name|index,to_node.
-  List<HashMap::Entry*> sorted_nodes;
-  SortHashMap(&nodes_, &sorted_nodes);
-  // Rewrite node ids, so they refer to actual array positions.
-  if (sorted_nodes.length() > 1) {
+
+  List<HeapEntry*>& nodes = *(snapshot_->entries());
+  // Root must be the first.
+  ASSERT(nodes.first() == snapshot_->root());
+  // Rewrite node indexes, so they refer to actual array positions. Do this
+  // only once.
+  if (nodes[0]->entry_index() == -1) {
     // Nodes start from array index 1.
-    int prev_value = 1;
-    sorted_nodes[0]->value = reinterpret_cast<void*>(prev_value);
-    for (int i = 1; i < sorted_nodes.length(); ++i) {
-      HeapEntry* prev_heap_entry =
-          reinterpret_cast<HeapEntry*>(sorted_nodes[i-1]->key);
-      prev_value += node_fields_count +
-          prev_heap_entry->children().length() * edge_fields_count;
-      sorted_nodes[i]->value = reinterpret_cast<void*>(prev_value);
+    int index = 1;
+    for (int i = 0; i < nodes.length(); ++i) {
+      HeapEntry* node = nodes[i];
+      node->set_entry_index(index);
+      index += node_fields_count +
+          node->children().length() * edge_fields_count;
     }
   }
-  for (int i = 0; i < sorted_nodes.length(); ++i) {
-    SerializeNode(reinterpret_cast<HeapEntry*>(sorted_nodes[i]->key));
+
+  for (int i = 0; i < nodes.length(); ++i) {
+    SerializeNode(nodes[i]);
     if (writer_->aborted()) return;
   }
 }