Get rid of HeapEntry to ID map in heap profile serializer

src/profile-generator.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 957 matching lines @@
                      SnapshotObjectId id,
                      int self_size,
                      int children_count,
                      int retainers_count) {
   snapshot_ = snapshot;
   type_ = type;
   painted_ = false;
   name_ = name;
   self_size_ = self_size;
   retained_size_ = 0;
+  entry_index_ = -1;
   children_count_ = children_count;
   retainers_count_ = retainers_count;
   dominator_ = NULL;
   id_ = id;
 }
 
 
 void HeapEntry::SetNamedReference(HeapGraphEdge::Type type,
                                   int child_index,
                                   const char* name,
@@ skipping 113 matching lines @@
 
 
 // It is very important to keep objects that form a heap snapshot
 // as small as possible.
 namespace {  // Avoid littering the global namespace.
 
 template <size_t ptr_size> struct SnapshotSizeConstants;
 
 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;
 };
 
 template <> struct SnapshotSizeConstants<8> {
   static const int kExpectedHeapGraphEdgeSize = 24;
   static const int kExpectedHeapEntrySize = 48;
   static const uint64_t kMaxSerializableSnapshotRawSize =
       static_cast<uint64_t>(6000) * MB;
 };
 
 }  // namespace
 
 HeapSnapshot::HeapSnapshot(HeapSnapshotsCollection* collection,
                            HeapSnapshot::Type type,
                            const char* title,
                            unsigned uid)
     : collection_(collection),
       type_(type),
       title_(title),
       uid_(uid),
       root_entry_(NULL),
       gc_roots_entry_(NULL),
       natives_root_entry_(NULL),
       raw_entries_(NULL),
-      entries_sorted_(false),
       max_snapshot_js_object_id_(0) {
   STATIC_CHECK(
       sizeof(HeapGraphEdge) ==
       SnapshotSizeConstants<kPointerSize>::kExpectedHeapGraphEdgeSize);
   STATIC_CHECK(
       sizeof(HeapEntry) ==
       SnapshotSizeConstants<kPointerSize>::kExpectedHeapEntrySize);
   for (int i = 0; i < VisitorSynchronization::kNumberOfSyncTags; ++i) {
     gc_subroot_entries_[i] = NULL;
   }
@@ skipping 31 matching lines @@
 }
 
 
 void HeapSnapshot::ClearPaint() {
   entries_.Iterate(HeapEntryClearPaint);
 }
 
 
 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,
                                  0,
                                  children_count,
                                  0));
 }
 
 
 HeapEntry* HeapSnapshot::AddGcRootsEntry(int children_count,
@@ skipping 80 matching lines @@
 
 template<class T>
 static int SortByIds(const T* entry1_ptr,
                      const T* entry2_ptr) {
   if ((*entry1_ptr)->id() == (*entry2_ptr)->id()) return 0;
   return (*entry1_ptr)->id() < (*entry2_ptr)->id() ? -1 : 1;
 }
 
 
 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_;
 }
 
 
 void HeapSnapshot::Print(int max_depth) {
   root()->Print("", "", max_depth, 0);
 }
 
 
 // We split IDs on evens for embedder objects (see
 // HeapObjectsMap::GenerateId) and odds for native objects.
@@ skipping 204 matching lines @@
 }
 
 
 HeapEntriesMap::~HeapEntriesMap() {
   for (HashMap::Entry* p = entries_.Start(); p != NULL; p = entries_.Next(p)) {
     delete reinterpret_cast<EntryInfo*>(p->value);
   }
 }
 
 
-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;
+}
+
+
 HeapEntry* HeapEntriesMap::Map(HeapThing thing) {
   HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), false);
   if (cache_entry != NULL) {
     EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(cache_entry->value);
     return entry_info->entry;
   } else {
     return NULL;
   }
 }
 
@@ skipping 1555 matching lines @@
 #ifdef DEBUG
   debug_heap->Verify();
 #endif
 
   // Allocate memory for entries and references.
   snapshot_->AllocateEntries(entries_.entries_count(),
                              entries_.total_children_count(),
                              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;
 
   snapshot_->RememberLastJSObjectId();
 
   if (!SetEntriesDominators()) return false;
   if (!CalculateRetainedSizes()) return false;
 
   progress_counter_ = progress_total_;
@@ skipping 290 matching lines @@
 
   HeapSnapshot* original_snapshot = NULL;
   if (snapshot_->raw_entries_size() >=
       SnapshotSizeConstants<kPointerSize>::kMaxSerializableSnapshotRawSize) {
     // The snapshot is too big. Serialize a fake snapshot.
     original_snapshot = snapshot_;
     snapshot_ = CreateFakeSnapshot();
   }
   // Since nodes graph is cyclic, we need the first pass to enumerate
   // them. Strings can be serialized in one pass.
-  EnumerateNodes();
   SerializeImpl();
 
   delete writer_;
   writer_ = NULL;
 
   if (original_snapshot != NULL) {
     delete snapshot_;
     snapshot_ = original_snapshot;
   }
 }
@@ skipping 32 matching lines @@
   writer_->AddString("],\n");
   writer_->AddString("\"strings\":[");
   SerializeStrings();
   if (writer_->aborted()) return;
   writer_->AddCharacter(']');
   writer_->AddCharacter('}');
   writer_->Finalize();
 }
 
 
-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);
   if (cache_entry->value == NULL) {
     cache_entry->value = reinterpret_cast<void*>(next_string_id_++);
   }
   return static_cast<int>(reinterpret_cast<intptr_t>(cache_entry->value));
 }
 
 
@@ skipping 30 matching lines @@
   int edge_name_or_index = edge->type() == HeapGraphEdge::kElement
       || edge->type() == HeapGraphEdge::kHidden
       || edge->type() == HeapGraphEdge::kWeak
       ? edge->index() : GetStringId(edge->name());
   int buffer_pos = 0;
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(edge->type(), buffer, buffer_pos);
   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());
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry) {
   // The buffer needs space for 6 ints, 1 uint32_t, 7 commas, \n and \0
   static const int kBufferSize =
       6 * MaxDecimalDigitsIn<sizeof(int)>::kSigned  // NOLINT
       + MaxDecimalDigitsIn<sizeof(uint32_t)>::kUnsigned  // NOLINT
       + 7 + 1 + 1;
   EmbeddedVector<char, kBufferSize> buffer;
   Vector<HeapGraphEdge> children = entry->children();
   int buffer_pos = 0;
   buffer[buffer_pos++] = '\n';
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(entry->type(), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(GetStringId(entry->name()), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(entry->id(), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(entry->self_size(), buffer, buffer_pos);
   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';
   writer_->AddString(buffer.start());
   for (int i = 0; i < children.length(); ++i) {
     SerializeEdge(&children[i]);
     if (writer_->aborted()) return;
   }
 }
 
@@ skipping 49 matching lines @@
                     "," JSON_S("weak"))
                 "," JSON_S("string_or_number")
                 "," JSON_S("node"))))));
 #undef JSON_S
 #undef JSON_O
 #undef JSON_A
 
   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;
   }
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeSnapshot() {
   writer_->AddString("\"title\":\"");
   writer_->AddString(snapshot_->title());
   writer_->AddString("\"");
   writer_->AddString(",\"uid\":");
@@ skipping 88 matching lines @@
 
 
 void HeapSnapshotJSONSerializer::SortHashMap(
     HashMap* map, List<HashMap::Entry*>* sorted_entries) {
   for (HashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p))
     sorted_entries->Add(p);
   sorted_entries->Sort(SortUsingEntryValue);
 }
 
 } }  // namespace v8::internal