Split nodes and edges into separate arrays in heap profiler.

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 913 matching lines @@
     // If no frames were symbolized, put the VM state entry in.
     if (no_symbolized_entries) {
       *entry++ = EntryForVMState(sample.state);
     }
   }
 
   profiles_->AddPathToCurrentProfiles(entries);
 }
 
 
-void HeapGraphEdge::Init(
-    int child_index, Type type, const char* name, HeapEntry* to) {
+HeapGraphEdge::HeapGraphEdge(
+    Type type, const char* name, int from, int to) :
+    type_(type),
+    from_index_(from),
+    to_index_(to),
+    name_(name) {
   ASSERT(type == kContextVariable
-         || type == kProperty
-         || type == kInternal
-         || type == kShortcut);
-  child_index_ = child_index;
-  type_ = type;
-  name_ = name;
-  to_ = to;
+      || type == kProperty
+      || type == kInternal
+      || type == kShortcut);
 }
 
 
-void HeapGraphEdge::Init(int child_index, Type type, int index, HeapEntry* to) {
+HeapGraphEdge::HeapGraphEdge(Type type, int index, int from, int to) :
+    type_(type),
+    from_index_(from),
+    to_index_(to),
+    index_(index) {
   ASSERT(type == kElement || type == kHidden || type == kWeak);
-  child_index_ = child_index;
-  type_ = type;
-  index_ = index;
-  to_ = to;
 }
 
 
-void HeapGraphEdge::Init(int child_index, int index, HeapEntry* to) {
-  Init(child_index, kElement, index, to);
+void HeapGraphEdge::ReplaceToIndexWithEntry(HeapSnapshot* snapshot) {
+  to_entry_ = &snapshot->entries()[to_index_];
 }
 
 
-void HeapEntry::Init(HeapSnapshot* snapshot,
+const int HeapEntry::kNoEntry = -1;
+
+HeapEntry::HeapEntry(HeapSnapshot* snapshot,
                      Type type,
                      const char* name,
                      SnapshotObjectId id,
-                     int self_size,
-                     int children_count,
-                     int retainers_count) {
-  snapshot_ = snapshot;
-  type_ = type;
-  painted_ = false;
-  user_reachable_ = 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;
-}
+                     int self_size) :
+    painted_(false),
+    user_reachable_(false),
+    dominator_(kNoEntry),
+    type_(type),
+    retainers_count_(0),
+    retainers_index_(-1),
+    children_count_(0),
+    children_index_(-1),
+    self_size_(self_size),
+    retained_size_(0),
+    id_(id),
+    snapshot_(snapshot),
+    name_(name) { }
 
 
 void HeapEntry::SetNamedReference(HeapGraphEdge::Type type,
-                                  int child_index,
                                   const char* name,
-                                  HeapEntry* entry,
-                                  int retainer_index) {
-  children()[child_index].Init(child_index, type, name, entry);
-  entry->retainers()[retainer_index] = children_arr() + child_index;
+                                  HeapEntry* entry) {
+  HeapGraphEdge edge(type, name, this->index(), entry->index());
+  snapshot_->edges().Add(edge);
+  ++children_count_;
+  ++entry->retainers_count_;
 }
 
 
 void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type,
-                                    int child_index,
                                     int index,
-                                    HeapEntry* entry,
-                                    int retainer_index) {
-  children()[child_index].Init(child_index, type, index, entry);
-  entry->retainers()[retainer_index] = children_arr() + child_index;
+                                    HeapEntry* entry) {
+  HeapGraphEdge edge(type, index, this->index(), entry->index());
+  snapshot_->edges().Add(edge);
+  ++children_count_;
+  ++entry->retainers_count_;
 }
 
 
-void HeapEntry::SetUnidirElementReference(
-    int child_index, int index, HeapEntry* entry) {
-  children()[child_index].Init(child_index, index, entry);
-}
-
-
 Handle<HeapObject> HeapEntry::GetHeapObject() {
   return snapshot_->collection()->FindHeapObjectById(id());
 }
 
 
 void HeapEntry::Print(
     const char* prefix, const char* edge_name, int max_depth, int indent) {
-  OS::Print("%6d %7d @%6llu %*c %s%s: ",
+  STATIC_CHECK(sizeof(unsigned) == sizeof(id()));
+  OS::Print("%6d %7d @%6u %*c %s%s: ",
             self_size(), retained_size(), id(),
             indent, ' ', prefix, edge_name);
   if (type() != kString) {
     OS::Print("%s %.40s\n", TypeAsString(), name_);
   } else {
     OS::Print("\"");
     const char* c = name_;
     while (*c && (c - name_) <= 40) {
       if (*c != '\n')
         OS::Print("%c", *c);
       else
         OS::Print("\\n");
       ++c;
     }
     OS::Print("\"\n");
   }
   if (--max_depth == 0) return;
-  Vector<HeapGraphEdge> ch = children();
+  Vector<HeapGraphEdge*> ch = children();
   for (int i = 0; i < ch.length(); ++i) {
-    HeapGraphEdge& edge = ch[i];
+    HeapGraphEdge& edge = *ch[i];
     const char* edge_prefix = "";
     EmbeddedVector<char, 64> index;
     const char* edge_name = index.start();
     switch (edge.type()) {
       case HeapGraphEdge::kContextVariable:
         edge_prefix = "#";
         edge_name = edge.name();
         break;
       case HeapGraphEdge::kElement:
         OS::SNPrintF(index, "%d", edge.index());
@@ skipping 35 matching lines @@
     case kArray: return "/array/";
     case kRegExp: return "/regexp/";
     case kHeapNumber: return "/number/";
     case kNative: return "/native/";
     case kSynthetic: return "/synthetic/";
     default: return "???";
   }
 }
 
 
-size_t HeapEntry::EntriesSize(int entries_count,
-                              int children_count,
-                              int retainers_count) {
-  return sizeof(HeapEntry) * entries_count         // NOLINT
-      + sizeof(HeapGraphEdge) * children_count     // NOLINT
-      + sizeof(HeapGraphEdge*) * retainers_count;  // NOLINT
-}
-
-
 // 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 = 36;
+  static const int kExpectedHeapEntrySize = 40;
   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),
-      number_of_edges_(0),
+      root_index_(HeapEntry::kNoEntry),
+      gc_roots_index_(HeapEntry::kNoEntry),
+      natives_root_index_(HeapEntry::kNoEntry),
       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;
+    gc_subroot_indexes_[i] = HeapEntry::kNoEntry;
   }
 }
 
 
-HeapSnapshot::~HeapSnapshot() {
-  DeleteArray(raw_entries_);
-}
-
-
 void HeapSnapshot::Delete() {
   collection_->RemoveSnapshot(this);
   delete this;
 }
 
 
 void HeapSnapshot::RememberLastJSObjectId() {
   max_snapshot_js_object_id_ = collection_->last_assigned_id();
 }
 
 
-void HeapSnapshot::AllocateEntries(int entries_count,
-                                   int children_count,
-                                   int retainers_count) {
-  ASSERT(raw_entries_ == NULL);
-  number_of_edges_ = children_count;
-  raw_entries_size_ =
-      HeapEntry::EntriesSize(entries_count, children_count, retainers_count);
-  raw_entries_ = NewArray<char>(raw_entries_size_);
+static void HeapEntryClearPaint(HeapEntry* entry_ptr) {
+  entry_ptr->clear_paint();
 }
 
 
-static void HeapEntryClearPaint(HeapEntry** entry_ptr) {
-  (*entry_ptr)->clear_paint();
-}
-
-
 void HeapSnapshot::ClearPaint() {
   entries_.Iterate(HeapEntryClearPaint);
 }
 
 
-HeapEntry* HeapSnapshot::AddRootEntry(int children_count) {
-  ASSERT(root_entry_ == NULL);
+HeapEntry* HeapSnapshot::AddRootEntry() {
+  ASSERT(root_index_ == HeapEntry::kNoEntry);
   ASSERT(entries_.is_empty());  // Root entry must be the first one.
-  return (root_entry_ = AddEntry(HeapEntry::kObject,
-                                 "",
-                                 HeapObjectsMap::kInternalRootObjectId,
-                                 0,
-                                 children_count,
-                                 0));
+  HeapEntry* entry = AddEntry(HeapEntry::kObject,
+                              "",
+                              HeapObjectsMap::kInternalRootObjectId,
+                              0);
+  root_index_ = entry->index();
+  ASSERT(root_index_ == 0);
+  return entry;
 }
 
 
-HeapEntry* HeapSnapshot::AddGcRootsEntry(int children_count,
-                                         int retainers_count) {
-  ASSERT(gc_roots_entry_ == NULL);
-  return (gc_roots_entry_ = AddEntry(HeapEntry::kObject,
-                                     "(GC roots)",
-                                     HeapObjectsMap::kGcRootsObjectId,
-                                     0,
-                                     children_count,
-                                     retainers_count));
+HeapEntry* HeapSnapshot::AddGcRootsEntry() {
+  ASSERT(gc_roots_index_ == HeapEntry::kNoEntry);
+  HeapEntry* entry = AddEntry(HeapEntry::kObject,
+                              "(GC roots)",
+                              HeapObjectsMap::kGcRootsObjectId,
+                              0);
+  gc_roots_index_ = entry->index();
+  return entry;
 }
 
 
-HeapEntry* HeapSnapshot::AddGcSubrootEntry(int tag,
-                                           int children_count,
-                                           int retainers_count) {
-  ASSERT(gc_subroot_entries_[tag] == NULL);
+HeapEntry* HeapSnapshot::AddGcSubrootEntry(int tag) {
+  ASSERT(gc_subroot_indexes_[tag] == HeapEntry::kNoEntry);
   ASSERT(0 <= tag && tag < VisitorSynchronization::kNumberOfSyncTags);
-  return (gc_subroot_entries_[tag] = AddEntry(
+  HeapEntry* entry = AddEntry(
       HeapEntry::kObject,
       VisitorSynchronization::kTagNames[tag],
       HeapObjectsMap::GetNthGcSubrootId(tag),
-      0,
-      children_count,
-      retainers_count));
+      0);
+  gc_subroot_indexes_[tag] = entry->index();
+  return entry;
 }
 
 
 HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type,
                                   const char* name,
                                   SnapshotObjectId id,
-                                  int size,
-                                  int children_count,
-                                  int retainers_count) {
-  HeapEntry* entry = GetNextEntryToInit();
-  entry->Init(this, type, name, id, size, children_count, retainers_count);
-  return entry;
+                                  int size) {
+  HeapEntry entry(this, type, name, id, size);
+  entries_.Add(entry);
+  return &entries_.last();
+}
+
+
+void HeapSnapshot::FillChildrenAndRetainers() {
+  ASSERT(children().is_empty());
+  children().Allocate(edges().length());
+  ASSERT(retainers().is_empty());
+  retainers().Allocate(edges().length());
+  int children_index = 0;
+  int retainers_index = 0;
+  for (int i = 0; i < entries().length(); ++i) {
+    HeapEntry* entry = &entries()[i];
+    children_index = entry->set_children_index(children_index);
+    retainers_index = entry->set_retainers_index(retainers_index);
+  }
+  ASSERT(edges().length() == children_index);
+  ASSERT(edges().length() == retainers_index);
+  for (int i = 0; i < edges().length(); ++i) {
+    HeapGraphEdge* edge = &edges()[i];
+    edge->ReplaceToIndexWithEntry(this);
+    edge->from()->add_child(edge);
+    edge->to()->add_retainer(edge);
+  }
 }
 
 
 void HeapSnapshot::SetDominatorsToSelf() {
   for (int i = 0; i < entries_.length(); ++i) {
-    HeapEntry* entry = entries_[i];
-    if (entry->dominator() == NULL) entry->set_dominator(entry);
+    entries_[i].set_dominator(&entries_[i]);
   }
 }
 
 
-HeapEntry* HeapSnapshot::GetNextEntryToInit() {
-  if (entries_.length() > 0) {
-    HeapEntry* last_entry = entries_.last();
-    entries_.Add(reinterpret_cast<HeapEntry*>(
-        reinterpret_cast<char*>(last_entry) + last_entry->EntrySize()));
-  } else {
-    entries_.Add(reinterpret_cast<HeapEntry*>(raw_entries_));
-  }
-  ASSERT(reinterpret_cast<char*>(entries_.last()) <
-         (raw_entries_ + raw_entries_size_));
-  return entries_.last();
-}
-
-
 class FindEntryById {
  public:
   explicit FindEntryById(SnapshotObjectId id) : id_(id) { }
   int operator()(HeapEntry* const* entry) {
     if ((*entry)->id() == id_) return 0;
     return (*entry)->id() < id_ ? -1 : 1;
   }
  private:
   SnapshotObjectId id_;
 };
@@ skipping 12 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 (sorted_entries_.is_empty()) {
-    sorted_entries_.AddAll(entries_);
+    sorted_entries_.Allocate(entries_.length());
+    for (int i = 0; i < entries_.length(); ++i) {
+      sorted_entries_[i] = &entries_[i];
+    }
     sorted_entries_.Sort(SortByIds);
   }
   return &sorted_entries_;
 }
 
 
 void HeapSnapshot::Print(int max_depth) {
   root()->Print("", "", max_depth, 0);
 }
 
 
+template<typename T, class P>
+static size_t GetMemoryUsedByList(const List<T,P>& list) {
+  return list.capacity() * sizeof(T);
+}
+
+
+size_t HeapSnapshot::RawSnapshotSize() const {
+  return
+      GetMemoryUsedByList(entries_) +
+      GetMemoryUsedByList(edges_) +
+      GetMemoryUsedByList(children_) +
+      GetMemoryUsedByList(retainers_) +
+      GetMemoryUsedByList(sorted_entries_);
+}
+
+
 // We split IDs on evens for embedder objects (see
 // HeapObjectsMap::GenerateId) and odds for native objects.
 const SnapshotObjectId HeapObjectsMap::kInternalRootObjectId = 1;
 const SnapshotObjectId HeapObjectsMap::kGcRootsObjectId =
     HeapObjectsMap::kInternalRootObjectId + HeapObjectsMap::kObjectIdStep;
 const SnapshotObjectId HeapObjectsMap::kGcRootsFirstSubrootId =
     HeapObjectsMap::kGcRootsObjectId + HeapObjectsMap::kObjectIdStep;
 const SnapshotObjectId HeapObjectsMap::kFirstAvailableObjectId =
     HeapObjectsMap::kGcRootsFirstSubrootId +
     VisitorSynchronization::kNumberOfSyncTags * HeapObjectsMap::kObjectIdStep;
@@ skipping 248 matching lines @@
     if (ids_.FindEntry(obj->address()) == id) {
       ASSERT(object == NULL);
       object = obj;
       // Can't break -- kFilterUnreachable requires full heap traversal.
     }
   }
   return object != NULL ? Handle<HeapObject>(object) : Handle<HeapObject>();
 }
 
 
-HeapEntry* const HeapEntriesMap::kHeapEntryPlaceholder =
-    reinterpret_cast<HeapEntry*>(1);
-
 HeapEntriesMap::HeapEntriesMap()
-    : entries_(HeapThingsMatch),
-      entries_count_(0),
-      total_children_count_(0),
-      total_retainers_count_(0) {
+    : entries_(HeapThingsMatch) {
 }
 
 
-HeapEntriesMap::~HeapEntriesMap() {
-  for (HashMap::Entry* p = entries_.Start(); p != NULL; p = entries_.Next(p)) {
-    delete reinterpret_cast<EntryInfo*>(p->value);
-  }
+int HeapEntriesMap::Map(HeapThing thing) {
+  HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), false);
+  if (cache_entry == NULL) return HeapEntry::kNoEntry;
+  return static_cast<int>(reinterpret_cast<intptr_t>(cache_entry->value));
 }
 
 
-void HeapEntriesMap::AllocateHeapEntryForMapEntry(HashMap::Entry* map_entry) {
-    EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(map_entry->value);
-    entry_info->entry = entry_info->allocator->AllocateEntry(
-        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::Pair(HeapThing thing, int entry) {
+  HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), true);
+  ASSERT(cache_entry->value == NULL);
+  cache_entry->value = reinterpret_cast<void*>(static_cast<intptr_t>(entry));
 }
 
 
-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;
-  }
-}
-
-
-void HeapEntriesMap::Pair(
-    HeapThing thing, HeapEntriesAllocator* allocator, HeapEntry* entry) {
-  HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), true);
-  ASSERT(cache_entry->value == NULL);
-  cache_entry->value = new EntryInfo(entry, allocator);
-  ++entries_count_;
-}
-
-
-void HeapEntriesMap::CountReference(HeapThing from, HeapThing to,
-                                    int* prev_children_count,
-                                    int* prev_retainers_count) {
-  HashMap::Entry* from_cache_entry = entries_.Lookup(from, Hash(from), false);
-  HashMap::Entry* to_cache_entry = entries_.Lookup(to, Hash(to), false);
-  ASSERT(from_cache_entry != NULL);
-  ASSERT(to_cache_entry != NULL);
-  EntryInfo* from_entry_info =
-      reinterpret_cast<EntryInfo*>(from_cache_entry->value);
-  EntryInfo* to_entry_info =
-      reinterpret_cast<EntryInfo*>(to_cache_entry->value);
-  if (prev_children_count)
-    *prev_children_count = from_entry_info->children_count;
-  if (prev_retainers_count)
-    *prev_retainers_count = to_entry_info->retainers_count;
-  ++from_entry_info->children_count;
-  ++to_entry_info->retainers_count;
-  ++total_children_count_;
-  ++total_retainers_count_;
-}
-
-
 HeapObjectsSet::HeapObjectsSet()
     : entries_(HeapEntriesMap::HeapThingsMatch) {
 }
 
 
 void HeapObjectsSet::Clear() {
   entries_.Clear();
 }
 
 
 bool HeapObjectsSet::Contains(Object* obj) {
   if (!obj->IsHeapObject()) return false;
   HeapObject* object = HeapObject::cast(obj);
-  HashMap::Entry* cache_entry =
-      entries_.Lookup(object, HeapEntriesMap::Hash(object), false);
-  return cache_entry != NULL;
+  return entries_.Lookup(object, HeapEntriesMap::Hash(object), false) != NULL;
 }
 
 
 void HeapObjectsSet::Insert(Object* obj) {
   if (!obj->IsHeapObject()) return;
   HeapObject* object = HeapObject::cast(obj);
-  HashMap::Entry* cache_entry =
-      entries_.Lookup(object, HeapEntriesMap::Hash(object), true);
-  if (cache_entry->value == NULL) {
-    cache_entry->value = HeapEntriesMap::kHeapEntryPlaceholder;
-  }
+  entries_.Lookup(object, HeapEntriesMap::Hash(object), true);
 }
 
 
 const char* HeapObjectsSet::GetTag(Object* obj) {
   HeapObject* object = HeapObject::cast(obj);
   HashMap::Entry* cache_entry =
       entries_.Lookup(object, HeapEntriesMap::Hash(object), false);
-  if (cache_entry != NULL
-      && cache_entry->value != HeapEntriesMap::kHeapEntryPlaceholder) {
-    return reinterpret_cast<const char*>(cache_entry->value);
-  } else {
-    return NULL;
-  }
+  return cache_entry != NULL
+      ? reinterpret_cast<const char*>(cache_entry->value)
+      : NULL;
 }
 
 
 void HeapObjectsSet::SetTag(Object* obj, const char* tag) {
   if (!obj->IsHeapObject()) return;
   HeapObject* object = HeapObject::cast(obj);
   HashMap::Entry* cache_entry =
       entries_.Lookup(object, HeapEntriesMap::Hash(object), true);
   cache_entry->value = const_cast<char*>(tag);
 }
@@ skipping 21 matching lines @@
       collection_(snapshot_->collection()),
       progress_(progress),
       filler_(NULL) {
 }
 
 
 V8HeapExplorer::~V8HeapExplorer() {
 }
 
 
-HeapEntry* V8HeapExplorer::AllocateEntry(
-    HeapThing ptr, int children_count, int retainers_count) {
-  return AddEntry(
-      reinterpret_cast<HeapObject*>(ptr), children_count, retainers_count);
+HeapEntry* V8HeapExplorer::AllocateEntry(HeapThing ptr) {
+  return AddEntry(reinterpret_cast<HeapObject*>(ptr));
 }
 
 
-HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object,
-                                    int children_count,
-                                    int retainers_count) {
+HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object) {
   if (object == kInternalRootObject) {
-    ASSERT(retainers_count == 0);
-    return snapshot_->AddRootEntry(children_count);
+    snapshot_->AddRootEntry();
+    return snapshot_->root();
   } else if (object == kGcRootsObject) {
-    return snapshot_->AddGcRootsEntry(children_count, retainers_count);
+    HeapEntry* entry = snapshot_->AddGcRootsEntry();
+    return entry;
   } else if (object >= kFirstGcSubrootObject && object < kLastGcSubrootObject) {
-    return snapshot_->AddGcSubrootEntry(
-        GetGcSubrootOrder(object),
-        children_count,
-        retainers_count);
+    HeapEntry* entry = snapshot_->AddGcSubrootEntry(GetGcSubrootOrder(object));
+    return entry;
   } else if (object->IsJSFunction()) {
     JSFunction* func = JSFunction::cast(object);
     SharedFunctionInfo* shared = func->shared();
     const char* name = shared->bound() ? "native_bind" :
         collection_->names()->GetName(String::cast(shared->name()));
-    return AddEntry(object,
-                    HeapEntry::kClosure,
-                    name,
-                    children_count,
-                    retainers_count);
+    return AddEntry(object, HeapEntry::kClosure, name);
   } else if (object->IsJSRegExp()) {
     JSRegExp* re = JSRegExp::cast(object);
     return AddEntry(object,
                     HeapEntry::kRegExp,
-                    collection_->names()->GetName(re->Pattern()),
-                    children_count,
-                    retainers_count);
+                    collection_->names()->GetName(re->Pattern()));
   } else if (object->IsJSObject()) {
-    return AddEntry(object,
-                    HeapEntry::kObject,
-                    "",
-                    children_count,
-                    retainers_count);
+    return AddEntry(object, HeapEntry::kObject, "");
   } else if (object->IsString()) {
     return AddEntry(object,
                     HeapEntry::kString,
-                    collection_->names()->GetName(String::cast(object)),
-                    children_count,
-                    retainers_count);
+                    collection_->names()->GetName(String::cast(object)));
   } else if (object->IsCode()) {
+    return AddEntry(object, HeapEntry::kCode, "");
+  } else if (object->IsSharedFunctionInfo()) {
+    String* name = String::cast(SharedFunctionInfo::cast(object)->name());
     return AddEntry(object,
                     HeapEntry::kCode,
-                    "",
-                    children_count,
-                    retainers_count);
-  } else if (object->IsSharedFunctionInfo()) {
-    SharedFunctionInfo* shared = SharedFunctionInfo::cast(object);
+                    collection_->names()->GetName(name));
+  } else if (object->IsScript()) {
+    Object* name = Script::cast(object)->name();
     return AddEntry(object,
                     HeapEntry::kCode,
-                    collection_->names()->GetName(String::cast(shared->name())),
-                    children_count,
-                    retainers_count);
-  } else if (object->IsScript()) {
-    Script* script = Script::cast(object);
-    return AddEntry(object,
-                    HeapEntry::kCode,
-                    script->name()->IsString() ?
-                        collection_->names()->GetName(
-                            String::cast(script->name()))
-                        : "",
-                    children_count,
-                    retainers_count);
+                    name->IsString()
+                        ? collection_->names()->GetName(String::cast(name))
+                        : "");
   } else if (object->IsGlobalContext()) {
-    return AddEntry(object,
-                    HeapEntry::kHidden,
-                    "system / GlobalContext",
-                    children_count,
-                    retainers_count);
+    return AddEntry(object, HeapEntry::kHidden, "system / GlobalContext");
   } else if (object->IsContext()) {
-    return AddEntry(object,
-                    HeapEntry::kHidden,
-                    "system / Context",
-                    children_count,
-                    retainers_count);
+    return AddEntry(object, HeapEntry::kHidden, "system / Context");
   } else if (object->IsFixedArray() ||
              object->IsFixedDoubleArray() ||
              object->IsByteArray() ||
              object->IsExternalArray()) {
     const char* tag = objects_tags_.GetTag(object);
-    return AddEntry(object,
-                    HeapEntry::kArray,
-                    tag != NULL ? tag : "",
-                    children_count,
-                    retainers_count);
+    return AddEntry(object, HeapEntry::kArray, tag != NULL ? tag : "");
   } else if (object->IsHeapNumber()) {
-    return AddEntry(object,
-                    HeapEntry::kHeapNumber,
-                    "number",
-                    children_count,
-                    retainers_count);
+    return AddEntry(object, HeapEntry::kHeapNumber, "number");
   }
-  return AddEntry(object,
-                  HeapEntry::kHidden,
-                  GetSystemEntryName(object),
-                  children_count,
-                  retainers_count);
+  return AddEntry(object, HeapEntry::kHidden, GetSystemEntryName(object));
 }
 
 
 HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object,
                                     HeapEntry::Type type,
-                                    const char* name,
-                                    int children_count,
-                                    int retainers_count) {
+                                    const char* name) {
   int object_size = object->Size();
   SnapshotObjectId object_id =
     collection_->GetObjectId(object->address(), object_size);
-  return snapshot_->AddEntry(type,
-                             name,
-                             object_id,
-                             object_size,
-                             children_count,
-                             retainers_count);
+  return snapshot_->AddEntry(type, name, object_id, object_size);
 }
 
 
 class GcSubrootsEnumerator : public ObjectVisitor {
  public:
   GcSubrootsEnumerator(
       SnapshotFillerInterface* filler, V8HeapExplorer* explorer)
       : filler_(filler),
         explorer_(explorer),
         previous_object_count_(0),
@@ skipping 48 matching lines @@
     objects_count++;
   }
   return objects_count;
 }
 
 
 class IndexedReferencesExtractor : public ObjectVisitor {
  public:
   IndexedReferencesExtractor(V8HeapExplorer* generator,
                              HeapObject* parent_obj,
-                             HeapEntry* parent_entry)
+                             int parent)
       : generator_(generator),
         parent_obj_(parent_obj),
-        parent_(parent_entry),
+        parent_(parent),
         next_index_(1) {
   }
   void VisitPointers(Object** start, Object** end) {
     for (Object** p = start; p < end; p++) {
       if (CheckVisitedAndUnmark(p)) continue;
       generator_->SetHiddenReference(parent_obj_, parent_, next_index_++, *p);
     }
   }
   static void MarkVisitedField(HeapObject* obj, int offset) {
     if (offset < 0) return;
     Address field = obj->address() + offset;
     ASSERT(!Memory::Object_at(field)->IsFailure());
     ASSERT(Memory::Object_at(field)->IsHeapObject());
     *field |= kFailureTag;
   }
 
  private:
   bool CheckVisitedAndUnmark(Object** field) {
     if ((*field)->IsFailure()) {
       intptr_t untagged = reinterpret_cast<intptr_t>(*field) & ~kFailureTagMask;
       *field = reinterpret_cast<Object*>(untagged | kHeapObjectTag);
       ASSERT((*field)->IsHeapObject());
       return true;
     }
     return false;
   }
   V8HeapExplorer* generator_;
   HeapObject* parent_obj_;
-  HeapEntry* parent_;
+  int parent_;
   int next_index_;
 };
 
 
 void V8HeapExplorer::ExtractReferences(HeapObject* obj) {
-  HeapEntry* entry = GetEntry(obj);
-  if (entry == NULL) return;  // No interest in this object.
+  HeapEntry* heap_entry = GetEntry(obj);
+  if (heap_entry == NULL) return;  // No interest in this object.
+  int entry = heap_entry->index();
 
   bool extract_indexed_refs = true;
   if (obj->IsJSGlobalProxy()) {
     ExtractJSGlobalProxyReferences(JSGlobalProxy::cast(obj));
   } else if (obj->IsJSObject()) {
     ExtractJSObjectReferences(entry, JSObject::cast(obj));
   } else if (obj->IsString()) {
     ExtractStringReferences(entry, String::cast(obj));
     extract_indexed_refs = false;
   } else if (obj->IsContext()) {
@@ skipping 31 matching lines @@
   is_debug_object = object->IsGlobalObject() &&
       Isolate::Current()->debug()->IsDebugGlobal(GlobalObject::cast(object));
 #endif
   if (!is_debug_object) {
     SetUserGlobalReference(object);
   }
 }
 
 
 void V8HeapExplorer::ExtractJSObjectReferences(
-    HeapEntry* entry, JSObject* js_obj) {
+    int entry, JSObject* js_obj) {
   HeapObject* obj = js_obj;
   ExtractClosureReferences(js_obj, entry);
   ExtractPropertyReferences(js_obj, entry);
   ExtractElementReferences(js_obj, entry);
   ExtractInternalReferences(js_obj, entry);
   SetPropertyReference(
       obj, entry, heap_->Proto_symbol(), js_obj->GetPrototype());
   if (obj->IsJSFunction()) {
     JSFunction* js_fun = JSFunction::cast(js_obj);
     Object* proto_or_map = js_fun->prototype_or_initial_map();
@@ skipping 48 matching lines @@
   SetInternalReference(obj, entry,
                        "properties", js_obj->properties(),
                        JSObject::kPropertiesOffset);
   TagObject(js_obj->elements(), "(object elements)");
   SetInternalReference(obj, entry,
                        "elements", js_obj->elements(),
                        JSObject::kElementsOffset);
 }
 
 
-void V8HeapExplorer::ExtractStringReferences(HeapEntry* entry, String* string) {
+void V8HeapExplorer::ExtractStringReferences(int entry, String* string) {
   if (string->IsConsString()) {
     ConsString* cs = ConsString::cast(string);
     SetInternalReference(cs, entry, "first", cs->first());
     SetInternalReference(cs, entry, "second", cs->second());
   } else if (string->IsSlicedString()) {
     SlicedString* ss = SlicedString::cast(string);
     SetInternalReference(ss, entry, "parent", ss->parent());
   }
 }
 
 
-void V8HeapExplorer::ExtractContextReferences(
-    HeapEntry* entry, Context* context) {
+void V8HeapExplorer::ExtractContextReferences(int entry, Context* context) {
 #define EXTRACT_CONTEXT_FIELD(index, type, name) \
   SetInternalReference(context, entry, #name, context->get(Context::index), \
       FixedArray::OffsetOfElementAt(Context::index));
   EXTRACT_CONTEXT_FIELD(CLOSURE_INDEX, JSFunction, closure);
   EXTRACT_CONTEXT_FIELD(PREVIOUS_INDEX, Context, previous);
   EXTRACT_CONTEXT_FIELD(EXTENSION_INDEX, Object, extension);
   EXTRACT_CONTEXT_FIELD(GLOBAL_INDEX, GlobalObject, global);
   if (context->IsGlobalContext()) {
     TagObject(context->jsfunction_result_caches(),
               "(context func. result caches)");
     TagObject(context->normalized_map_cache(), "(context norm. map cache)");
     TagObject(context->runtime_context(), "(runtime context)");
     TagObject(context->data(), "(context data)");
     GLOBAL_CONTEXT_FIELDS(EXTRACT_CONTEXT_FIELD);
 #undef EXTRACT_CONTEXT_FIELD
     for (int i = Context::FIRST_WEAK_SLOT;
          i < Context::GLOBAL_CONTEXT_SLOTS;
          ++i) {
       SetWeakReference(context, entry, i, context->get(i),
           FixedArray::OffsetOfElementAt(i));
     }
   }
 }
 
 
-void V8HeapExplorer::ExtractMapReferences(HeapEntry* entry, Map* map) {
+void V8HeapExplorer::ExtractMapReferences(int entry, Map* map) {
   SetInternalReference(map, entry,
                        "prototype", map->prototype(), Map::kPrototypeOffset);
   SetInternalReference(map, entry,
                        "constructor", map->constructor(),
                        Map::kConstructorOffset);
   if (!map->instance_descriptors()->IsEmpty()) {
     TagObject(map->instance_descriptors(), "(map descriptors)");
     SetInternalReference(map, entry,
                          "descriptors", map->instance_descriptors(),
                          Map::kInstanceDescriptorsOrBitField3Offset);
   }
   TagObject(map->prototype_transitions(), "(prototype transitions)");
   SetInternalReference(map, entry,
                        "prototype_transitions", map->prototype_transitions(),
                        Map::kPrototypeTransitionsOffset);
   SetInternalReference(map, entry,
                        "code_cache", map->code_cache(),
                        Map::kCodeCacheOffset);
 }
 
 
 void V8HeapExplorer::ExtractSharedFunctionInfoReferences(
-    HeapEntry* entry, SharedFunctionInfo* shared) {
+    int entry, SharedFunctionInfo* shared) {
   HeapObject* obj = shared;
   SetInternalReference(obj, entry,
                        "name", shared->name(),
                        SharedFunctionInfo::kNameOffset);
   TagObject(shared->code(), "(code)");
   SetInternalReference(obj, entry,
                        "code", shared->code(),
                        SharedFunctionInfo::kCodeOffset);
   TagObject(shared->scope_info(), "(function scope info)");
   SetInternalReference(obj, entry,
@@ skipping 21 matching lines @@
   SetInternalReference(obj, entry,
                        "this_property_assignments",
                        shared->this_property_assignments(),
                        SharedFunctionInfo::kThisPropertyAssignmentsOffset);
   SetWeakReference(obj, entry,
                    1, shared->initial_map(),
                    SharedFunctionInfo::kInitialMapOffset);
 }
 
 
-void V8HeapExplorer::ExtractScriptReferences(HeapEntry* entry, Script* script) {
+void V8HeapExplorer::ExtractScriptReferences(int entry, Script* script) {
   HeapObject* obj = script;
   SetInternalReference(obj, entry,
                        "source", script->source(),
                        Script::kSourceOffset);
   SetInternalReference(obj, entry,
                        "name", script->name(),
                        Script::kNameOffset);
   SetInternalReference(obj, entry,
                        "data", script->data(),
                        Script::kDataOffset);
   SetInternalReference(obj, entry,
                        "context_data", script->context_data(),
                        Script::kContextOffset);
   TagObject(script->line_ends(), "(script line ends)");
   SetInternalReference(obj, entry,
                        "line_ends", script->line_ends(),
                        Script::kLineEndsOffset);
 }
 
 
 void V8HeapExplorer::ExtractCodeCacheReferences(
-    HeapEntry* entry, CodeCache* code_cache) {
+    int entry, CodeCache* code_cache) {
   TagObject(code_cache->default_cache(), "(default code cache)");
   SetInternalReference(code_cache, entry,
                        "default_cache", code_cache->default_cache(),
                        CodeCache::kDefaultCacheOffset);
   TagObject(code_cache->normal_type_cache(), "(code type cache)");
   SetInternalReference(code_cache, entry,
                        "type_cache", code_cache->normal_type_cache(),
                        CodeCache::kNormalTypeCacheOffset);
 }
 
 
-void V8HeapExplorer::ExtractCodeReferences(HeapEntry* entry, Code* code) {
+void V8HeapExplorer::ExtractCodeReferences(int entry, Code* code) {
   TagObject(code->relocation_info(), "(code relocation info)");
   SetInternalReference(code, entry,
                        "relocation_info", code->relocation_info(),
                        Code::kRelocationInfoOffset);
   SetInternalReference(code, entry,
                        "handler_table", code->handler_table(),
                        Code::kHandlerTableOffset);
   TagObject(code->deoptimization_data(), "(code deopt data)");
   SetInternalReference(code, entry,
                        "deoptimization_data", code->deoptimization_data(),
                        Code::kDeoptimizationDataOffset);
   SetInternalReference(code, entry,
                        "type_feedback_info", code->type_feedback_info(),
                        Code::kTypeFeedbackInfoOffset);
   SetInternalReference(code, entry,
                        "gc_metadata", code->gc_metadata(),
                        Code::kGCMetadataOffset);
 }
 
 
 void V8HeapExplorer::ExtractJSGlobalPropertyCellReferences(
-    HeapEntry* entry, JSGlobalPropertyCell* cell) {
+    int entry, JSGlobalPropertyCell* cell) {
   SetInternalReference(cell, entry, "value", cell->value());
 }
 
 
-void V8HeapExplorer::ExtractClosureReferences(JSObject* js_obj,
-                                              HeapEntry* entry) {
+void V8HeapExplorer::ExtractClosureReferences(JSObject* js_obj, int entry) {
   if (!js_obj->IsJSFunction()) return;
 
   JSFunction* func = JSFunction::cast(js_obj);
   if (func->shared()->bound()) {
     FixedArray* bindings = func->function_bindings();
     SetNativeBindReference(js_obj, entry, "bound_this",
                            bindings->get(JSFunction::kBoundThisIndex));
     SetNativeBindReference(js_obj, entry, "bound_function",
                            bindings->get(JSFunction::kBoundFunctionIndex));
     for (int i = JSFunction::kBoundArgumentsStartIndex;
@@ skipping 21 matching lines @@
       VariableMode mode;
       int idx = scope_info->FunctionContextSlotIndex(name, &mode);
       if (idx >= 0) {
         SetClosureReference(js_obj, entry, name, context->get(idx));
       }
     }
   }
 }
 
 
-void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj,
-                                               HeapEntry* entry) {
+void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj, int entry) {
   if (js_obj->HasFastProperties()) {
     DescriptorArray* descs = js_obj->map()->instance_descriptors();
     for (int i = 0; i < descs->number_of_descriptors(); i++) {
       switch (descs->GetType(i)) {
         case FIELD: {
           int index = descs->GetFieldIndex(i);
           if (index < js_obj->map()->inobject_properties()) {
             SetPropertyReference(
                 js_obj, entry,
                 descs->GetKey(i), js_obj->InObjectPropertyAt(index),
@@ skipping 52 matching lines @@
         } else {
           TagObject(value, "(hidden properties)");
           SetInternalReference(js_obj, entry, "hidden_properties", value);
         }
       }
     }
   }
 }
 
 
-void V8HeapExplorer::ExtractElementReferences(JSObject* js_obj,
-                                              HeapEntry* entry) {
+void V8HeapExplorer::ExtractElementReferences(JSObject* js_obj, int entry) {
   if (js_obj->HasFastElements()) {
     FixedArray* elements = FixedArray::cast(js_obj->elements());
     int length = js_obj->IsJSArray() ?
         Smi::cast(JSArray::cast(js_obj)->length())->value() :
         elements->length();
     for (int i = 0; i < length; ++i) {
       if (!elements->get(i)->IsTheHole()) {
         SetElementReference(js_obj, entry, i, elements->get(i));
       }
     }
   } else if (js_obj->HasDictionaryElements()) {
     SeededNumberDictionary* dictionary = js_obj->element_dictionary();
     int length = dictionary->Capacity();
     for (int i = 0; i < length; ++i) {
       Object* k = dictionary->KeyAt(i);
       if (dictionary->IsKey(k)) {
         ASSERT(k->IsNumber());
         uint32_t index = static_cast<uint32_t>(k->Number());
         SetElementReference(js_obj, entry, index, dictionary->ValueAt(i));
       }
     }
   }
 }
 
 
-void V8HeapExplorer::ExtractInternalReferences(JSObject* js_obj,
-                                               HeapEntry* entry) {
+void V8HeapExplorer::ExtractInternalReferences(JSObject* js_obj, int entry) {
   int length = js_obj->GetInternalFieldCount();
   for (int i = 0; i < length; ++i) {
     Object* o = js_obj->GetInternalField(i);
     SetInternalReference(
         js_obj, entry, i, o, js_obj->GetInternalFieldOffset(i));
   }
 }
 
 
 String* V8HeapExplorer::GetConstructorName(JSObject* object) {
@@ skipping 105 matching lines @@
        obj = iterator.next(), progress_->ProgressStep()) {
     if (!interrupted) {
       ExtractReferences(obj);
       if (!progress_->ProgressReport(false)) interrupted = true;
     }
   }
   if (interrupted) {
     filler_ = NULL;
     return false;
   }
+
   SetRootGcRootsReference();
   RootsReferencesExtractor extractor;
   heap_->IterateRoots(&extractor, VISIT_ONLY_STRONG);
   extractor.SetCollectingAllReferences();
   heap_->IterateRoots(&extractor, VISIT_ALL);
   extractor.FillReferences(this);
   filler_ = NULL;
-  return progress_->ProgressReport(false);
+  return progress_->ProgressReport(true);
 }
 
 
 bool V8HeapExplorer::IterateAndSetObjectNames(SnapshotFillerInterface* filler) {
   HeapIterator iterator(HeapIterator::kFilterUnreachable);
   filler_ = filler;
   for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) {
     SetObjectName(obj);
   }
   return true;
@@ skipping 27 matching lines @@
       && object != heap_->raw_unchecked_fixed_array_map()
       && object != heap_->raw_unchecked_global_property_cell_map()
       && object != heap_->raw_unchecked_shared_function_info_map()
       && object != heap_->raw_unchecked_free_space_map()
       && object != heap_->raw_unchecked_one_pointer_filler_map()
       && object != heap_->raw_unchecked_two_pointer_filler_map();
 }
 
 
 void V8HeapExplorer::SetClosureReference(HeapObject* parent_obj,
-                                         HeapEntry* parent_entry,
+                                         int parent_entry,
                                          String* reference_name,
                                          Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetNamedReference(HeapGraphEdge::kContextVariable,
-                               parent_obj,
                                parent_entry,
                                collection_->names()->GetName(reference_name),
-                               child_obj,
                                child_entry);
   }
 }
 
 
 void V8HeapExplorer::SetNativeBindReference(HeapObject* parent_obj,
-                                            HeapEntry* parent_entry,
+                                            int parent_entry,
                                             const char* reference_name,
                                             Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetNamedReference(HeapGraphEdge::kShortcut,
-                               parent_obj,
                                parent_entry,
                                reference_name,
-                               child_obj,
                                child_entry);
   }
 }
 
 
 void V8HeapExplorer::SetElementReference(HeapObject* parent_obj,
-                                         HeapEntry* parent_entry,
+                                         int parent_entry,
                                          int index,
                                          Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetIndexedReference(HeapGraphEdge::kElement,
-                                 parent_obj,
                                  parent_entry,
                                  index,
-                                 child_obj,
                                  child_entry);
   }
 }
 
 
 void V8HeapExplorer::SetInternalReference(HeapObject* parent_obj,
-                                          HeapEntry* parent_entry,
+                                          int parent_entry,
                                           const char* reference_name,
                                           Object* child_obj,
                                           int field_offset) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry == NULL) return;
   if (IsEssentialObject(child_obj)) {
     filler_->SetNamedReference(HeapGraphEdge::kInternal,
-                               parent_obj, parent_entry,
+                               parent_entry,
                                reference_name,
-                               child_obj, child_entry);
+                               child_entry);
   }
   IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
 }
 
 
 void V8HeapExplorer::SetInternalReference(HeapObject* parent_obj,
-                                          HeapEntry* parent_entry,
+                                          int parent_entry,
                                           int index,
                                           Object* child_obj,
                                           int field_offset) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry == NULL) return;
   if (IsEssentialObject(child_obj)) {
     filler_->SetNamedReference(HeapGraphEdge::kInternal,
-                               parent_obj, parent_entry,
+                               parent_entry,
                                collection_->names()->GetName(index),
-                               child_obj, child_entry);
+                               child_entry);
   }
   IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
 }
 
 
 void V8HeapExplorer::SetHiddenReference(HeapObject* parent_obj,
-                                        HeapEntry* parent_entry,
+                                        int parent_entry,
                                         int index,
                                         Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL && IsEssentialObject(child_obj)) {
     filler_->SetIndexedReference(HeapGraphEdge::kHidden,
-                                 parent_obj,
                                  parent_entry,
                                  index,
-                                 child_obj,
                                  child_entry);
   }
 }
 
 
 void V8HeapExplorer::SetWeakReference(HeapObject* parent_obj,
-                                      HeapEntry* parent_entry,
+                                      int parent_entry,
                                       int index,
                                       Object* child_obj,
                                       int field_offset) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetIndexedReference(HeapGraphEdge::kWeak,
-                                 parent_obj,
                                  parent_entry,
                                  index,
-                                 child_obj,
                                  child_entry);
     IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
   }
 }
 
 
 void V8HeapExplorer::SetPropertyReference(HeapObject* parent_obj,
-                                          HeapEntry* parent_entry,
+                                          int parent_entry,
                                           String* reference_name,
                                           Object* child_obj,
                                           const char* name_format_string,
                                           int field_offset) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     HeapGraphEdge::Type type = reference_name->length() > 0 ?
         HeapGraphEdge::kProperty : HeapGraphEdge::kInternal;
     const char* name = name_format_string  != NULL ?
         collection_->names()->GetFormatted(
             name_format_string,
             *reference_name->ToCString(DISALLOW_NULLS,
                                        ROBUST_STRING_TRAVERSAL)) :
         collection_->names()->GetName(reference_name);
 
     filler_->SetNamedReference(type,
-                               parent_obj,
                                parent_entry,
                                name,
-                               child_obj,
                                child_entry);
     IndexedReferencesExtractor::MarkVisitedField(parent_obj, field_offset);
   }
 }
 
 
 void V8HeapExplorer::SetPropertyShortcutReference(HeapObject* parent_obj,
-                                                  HeapEntry* parent_entry,
+                                                  int parent_entry,
                                                   String* reference_name,
                                                   Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetNamedReference(HeapGraphEdge::kShortcut,
-                               parent_obj,
                                parent_entry,
                                collection_->names()->GetName(reference_name),
-                               child_obj,
                                child_entry);
   }
 }
 
 
 void V8HeapExplorer::SetRootGcRootsReference() {
   filler_->SetIndexedAutoIndexReference(
       HeapGraphEdge::kElement,
-      kInternalRootObject, snapshot_->root(),
-      kGcRootsObject, snapshot_->gc_roots());
+      snapshot_->root()->index(),
+      snapshot_->gc_roots());
 }
 
 
 void V8HeapExplorer::SetUserGlobalReference(Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   ASSERT(child_entry != NULL);
   filler_->SetNamedAutoIndexReference(
       HeapGraphEdge::kShortcut,
-      kInternalRootObject, snapshot_->root(),
-      child_obj, child_entry);
+      snapshot_->root()->index(),
+      child_entry);
 }
 
 
 void V8HeapExplorer::SetGcRootsReference(VisitorSynchronization::SyncTag tag) {
   filler_->SetIndexedAutoIndexReference(
       HeapGraphEdge::kElement,
-      kGcRootsObject, snapshot_->gc_roots(),
-      GetNthGcSubrootObject(tag), snapshot_->gc_subroot(tag));
+      snapshot_->gc_roots()->index(),
+      snapshot_->gc_subroot(tag));
 }
 
 
 void V8HeapExplorer::SetGcSubrootReference(
     VisitorSynchronization::SyncTag tag, bool is_weak, Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     const char* name = GetStrongGcSubrootName(child_obj);
     if (name != NULL) {
       filler_->SetNamedReference(
           HeapGraphEdge::kInternal,
-          GetNthGcSubrootObject(tag), snapshot_->gc_subroot(tag),
+          snapshot_->gc_subroot(tag)->index(),
           name,
-          child_obj, child_entry);
+          child_entry);
     } else {
       filler_->SetIndexedAutoIndexReference(
           is_weak ? HeapGraphEdge::kWeak : HeapGraphEdge::kElement,
-          GetNthGcSubrootObject(tag), snapshot_->gc_subroot(tag),
-          child_obj, child_entry);
+          snapshot_->gc_subroot(tag)->index(),
+          child_entry);
     }
   }
 }
 
 
 const char* V8HeapExplorer::GetStrongGcSubrootName(Object* object) {
   if (strong_gc_subroot_names_.is_empty()) {
 #define NAME_ENTRY(name) strong_gc_subroot_names_.SetTag(heap_->name(), #name);
 #define ROOT_NAME(type, name, camel_name) NAME_ENTRY(name)
     STRONG_ROOT_LIST(ROOT_NAME)
@@ skipping 96 matching lines @@
 
 class BasicHeapEntriesAllocator : public HeapEntriesAllocator {
  public:
   BasicHeapEntriesAllocator(
       HeapSnapshot* snapshot,
       HeapEntry::Type entries_type)
     : snapshot_(snapshot),
       collection_(snapshot_->collection()),
       entries_type_(entries_type) {
   }
-  virtual HeapEntry* AllocateEntry(
-      HeapThing ptr, int children_count, int retainers_count);
+  virtual HeapEntry* AllocateEntry(HeapThing ptr);
  private:
   HeapSnapshot* snapshot_;
   HeapSnapshotsCollection* collection_;
   HeapEntry::Type entries_type_;
 };
 
 
-HeapEntry* BasicHeapEntriesAllocator::AllocateEntry(
-    HeapThing ptr, int children_count, int retainers_count) {
+HeapEntry* BasicHeapEntriesAllocator::AllocateEntry(HeapThing ptr) {
   v8::RetainedObjectInfo* info = reinterpret_cast<v8::RetainedObjectInfo*>(ptr);
   intptr_t elements = info->GetElementCount();
   intptr_t size = info->GetSizeInBytes();
+  const char* name = elements != -1
+      ? collection_->names()->GetFormatted(
+            "%s / %" V8_PTR_PREFIX "d entries", info->GetLabel(), elements)
+      : collection_->names()->GetCopy(info->GetLabel());
   return snapshot_->AddEntry(
       entries_type_,
-      elements != -1 ?
-          collection_->names()->GetFormatted(
-              "%s / %" V8_PTR_PREFIX "d entries",
-              info->GetLabel(),
-              info->GetElementCount()) :
-          collection_->names()->GetCopy(info->GetLabel()),
+      name,
       HeapObjectsMap::GenerateId(info),
-      size != -1 ? static_cast<int>(size) : 0,
-      children_count,
-      retainers_count);
+      size != -1 ? static_cast<int>(size) : 0);
 }
 
 
 NativeObjectsExplorer::NativeObjectsExplorer(
     HeapSnapshot* snapshot, SnapshottingProgressReportingInterface* progress)
     : snapshot_(snapshot),
       collection_(snapshot_->collection()),
       progress_(progress),
       embedder_queried_(false),
       objects_by_info_(RetainedInfosMatch),
@@ skipping 60 matching lines @@
   embedder_queried_ = true;
 }
 
 void NativeObjectsExplorer::FillImplicitReferences() {
   Isolate* isolate = Isolate::Current();
   List<ImplicitRefGroup*>* groups =
       isolate->global_handles()->implicit_ref_groups();
   for (int i = 0; i < groups->length(); ++i) {
     ImplicitRefGroup* group = groups->at(i);
     HeapObject* parent = *group->parent_;
-    HeapEntry* parent_entry =
-        filler_->FindOrAddEntry(parent, native_entries_allocator_);
-    ASSERT(parent_entry != NULL);
+    int parent_entry =
+        filler_->FindOrAddEntry(parent, native_entries_allocator_)->index();
+    ASSERT(parent_entry != HeapEntry::kNoEntry);
     Object*** children = group->children_;
     for (size_t j = 0; j < group->length_; ++j) {
       Object* child = *children[j];
       HeapEntry* child_entry =
           filler_->FindOrAddEntry(child, native_entries_allocator_);
       filler_->SetNamedReference(
           HeapGraphEdge::kInternal,
-          parent, parent_entry,
+          parent_entry,
           "native",
-          child, child_entry);
+          child_entry);
     }
   }
 }
 
 List<HeapObject*>* NativeObjectsExplorer::GetListMaybeDisposeInfo(
     v8::RetainedObjectInfo* info) {
   HashMap::Entry* entry =
       objects_by_info_.Lookup(info, InfoHash(info), true);
   if (entry->value != NULL) {
     info->Dispose();
@@ skipping 57 matching lines @@
 
 
 NativeGroupRetainedObjectInfo* NativeObjectsExplorer::FindOrAddGroupInfo(
     const char* label) {
   const char* label_copy = collection_->names()->GetCopy(label);
   uint32_t hash = HashSequentialString(label_copy,
                                        static_cast<int>(strlen(label_copy)),
                                        HEAP->HashSeed());
   HashMap::Entry* entry = native_groups_.Lookup(const_cast<char*>(label_copy),
                                                 hash, true);
-  if (entry->value == NULL)
+  if (entry->value == NULL) {
     entry->value = new NativeGroupRetainedObjectInfo(label);
+  }
   return static_cast<NativeGroupRetainedObjectInfo*>(entry->value);
 }
 
 
 void NativeObjectsExplorer::SetNativeRootReference(
     v8::RetainedObjectInfo* info) {
   HeapEntry* child_entry =
       filler_->FindOrAddEntry(info, native_entries_allocator_);
   ASSERT(child_entry != NULL);
   NativeGroupRetainedObjectInfo* group_info =
       FindOrAddGroupInfo(info->GetGroupLabel());
   HeapEntry* group_entry =
       filler_->FindOrAddEntry(group_info, synthetic_entries_allocator_);
   filler_->SetNamedAutoIndexReference(
       HeapGraphEdge::kInternal,
-      group_info, group_entry,
-      info, child_entry);
+      group_entry->index(),
+      child_entry);
 }
 
 
 void NativeObjectsExplorer::SetWrapperNativeReferences(
     HeapObject* wrapper, v8::RetainedObjectInfo* info) {
   HeapEntry* wrapper_entry = filler_->FindEntry(wrapper);
   ASSERT(wrapper_entry != NULL);
   HeapEntry* info_entry =
       filler_->FindOrAddEntry(info, native_entries_allocator_);
   ASSERT(info_entry != NULL);
   filler_->SetNamedReference(HeapGraphEdge::kInternal,
-                             wrapper, wrapper_entry,
+                             wrapper_entry->index(),
                              "native",
-                             info, info_entry);
+                             info_entry);
   filler_->SetIndexedAutoIndexReference(HeapGraphEdge::kElement,
-                                        info, info_entry,
-                                        wrapper, wrapper_entry);
+                                        info_entry->index(),
+                                        wrapper_entry);
 }
 
 
 void NativeObjectsExplorer::SetRootNativeRootsReference() {
   for (HashMap::Entry* entry = native_groups_.Start();
        entry;
        entry = native_groups_.Next(entry)) {
     NativeGroupRetainedObjectInfo* group_info =
         static_cast<NativeGroupRetainedObjectInfo*>(entry->value);
     HeapEntry* group_entry =
         filler_->FindOrAddEntry(group_info, native_entries_allocator_);
     ASSERT(group_entry != NULL);
     filler_->SetIndexedAutoIndexReference(
         HeapGraphEdge::kElement,
-        V8HeapExplorer::kInternalRootObject, snapshot_->root(),
-        group_info, group_entry);
+        snapshot_->root()->index(),
+        group_entry);
   }
 }
 
 
 void NativeObjectsExplorer::VisitSubtreeWrapper(Object** p, uint16_t class_id) {
   if (in_groups_.Contains(*p)) return;
   Isolate* isolate = Isolate::Current();
   v8::RetainedObjectInfo* info =
       isolate->heap_profiler()->ExecuteWrapperClassCallback(class_id, p);
   if (info == NULL) return;
   GetListMaybeDisposeInfo(info)->Add(HeapObject::cast(*p));
 }
 
 
-class SnapshotCounter : public SnapshotFillerInterface {
- public:
-  explicit SnapshotCounter(HeapEntriesMap* entries) : entries_(entries) { }
-  HeapEntry* AddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
-    entries_->Pair(ptr, allocator, HeapEntriesMap::kHeapEntryPlaceholder);
-    return HeapEntriesMap::kHeapEntryPlaceholder;
-  }
-  HeapEntry* FindEntry(HeapThing ptr) {
-    return entries_->Map(ptr);
-  }
-  HeapEntry* FindOrAddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
-    HeapEntry* entry = FindEntry(ptr);
-    return entry != NULL ? entry : AddEntry(ptr, allocator);
-  }
-  void SetIndexedReference(HeapGraphEdge::Type,
-                           HeapThing parent_ptr,
-                           HeapEntry*,
-                           int,
-                           HeapThing child_ptr,
-                           HeapEntry*) {
-    entries_->CountReference(parent_ptr, child_ptr);
-  }
-  void SetIndexedAutoIndexReference(HeapGraphEdge::Type,
-                                    HeapThing parent_ptr,
-                                    HeapEntry*,
-                                    HeapThing child_ptr,
-                                    HeapEntry*) {
-    entries_->CountReference(parent_ptr, child_ptr);
-  }
-  void SetNamedReference(HeapGraphEdge::Type,
-                         HeapThing parent_ptr,
-                         HeapEntry*,
-                         const char*,
-                         HeapThing child_ptr,
-                         HeapEntry*) {
-    entries_->CountReference(parent_ptr, child_ptr);
-  }
-  void SetNamedAutoIndexReference(HeapGraphEdge::Type,
-                                  HeapThing parent_ptr,
-                                  HeapEntry*,
-                                  HeapThing child_ptr,
-                                  HeapEntry*) {
-    entries_->CountReference(parent_ptr, child_ptr);
-  }
-
- private:
-  HeapEntriesMap* entries_;
-};
-
-
 class SnapshotFiller : public SnapshotFillerInterface {
  public:
   explicit SnapshotFiller(HeapSnapshot* snapshot, HeapEntriesMap* entries)
       : snapshot_(snapshot),
         collection_(snapshot->collection()),
         entries_(entries) { }
   HeapEntry* AddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
-    UNREACHABLE();
-    return NULL;
+    HeapEntry* entry = allocator->AllocateEntry(ptr);
+    entries_->Pair(ptr, entry->index());
+    return entry;
   }
   HeapEntry* FindEntry(HeapThing ptr) {
-    return entries_->Map(ptr);
+    int index = entries_->Map(ptr);
+    return index != HeapEntry::kNoEntry ? &snapshot_->entries()[index] : NULL;
   }
   HeapEntry* FindOrAddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
     HeapEntry* entry = FindEntry(ptr);
     return entry != NULL ? entry : AddEntry(ptr, allocator);
   }
   void SetIndexedReference(HeapGraphEdge::Type type,
-                           HeapThing parent_ptr,
-                           HeapEntry* parent_entry,
+                           int parent,
                            int index,
-                           HeapThing child_ptr,
                            HeapEntry* child_entry) {
-    int child_index, retainer_index;
-    entries_->CountReference(
-        parent_ptr, child_ptr, &child_index, &retainer_index);
-    parent_entry->SetIndexedReference(
-        type, child_index, index, child_entry, retainer_index);
+    HeapEntry* parent_entry = &snapshot_->entries()[parent];
+    parent_entry->SetIndexedReference(type, index, child_entry);
   }
   void SetIndexedAutoIndexReference(HeapGraphEdge::Type type,
-                                    HeapThing parent_ptr,
-                                    HeapEntry* parent_entry,
-                                    HeapThing child_ptr,
+                                    int parent,
                                     HeapEntry* child_entry) {
-    int child_index, retainer_index;
-    entries_->CountReference(
-        parent_ptr, child_ptr, &child_index, &retainer_index);
-    parent_entry->SetIndexedReference(
-        type, child_index, child_index + 1, child_entry, retainer_index);
+    HeapEntry* parent_entry = &snapshot_->entries()[parent];
+    int index = parent_entry->children_count() + 1;
+    parent_entry->SetIndexedReference(type, index, child_entry);
   }
   void SetNamedReference(HeapGraphEdge::Type type,
-                         HeapThing parent_ptr,
-                         HeapEntry* parent_entry,
+                         int parent,
                          const char* reference_name,
-                         HeapThing child_ptr,
                          HeapEntry* child_entry) {
-    int child_index, retainer_index;
-    entries_->CountReference(
-        parent_ptr, child_ptr, &child_index, &retainer_index);
-    parent_entry->SetNamedReference(
-        type, child_index, reference_name, child_entry, retainer_index);
+    HeapEntry* parent_entry = &snapshot_->entries()[parent];
+    parent_entry->SetNamedReference(type, reference_name, child_entry);
   }
   void SetNamedAutoIndexReference(HeapGraphEdge::Type type,
-                                  HeapThing parent_ptr,
-                                  HeapEntry* parent_entry,
-                                  HeapThing child_ptr,
+                                  int parent,
                                   HeapEntry* child_entry) {
-    int child_index, retainer_index;
-    entries_->CountReference(
-        parent_ptr, child_ptr, &child_index, &retainer_index);
-    parent_entry->SetNamedReference(type,
-                              child_index,
-                              collection_->names()->GetName(child_index + 1),
-                              child_entry,
-                              retainer_index);
+    HeapEntry* parent_entry = &snapshot_->entries()[parent];
+    int index = parent_entry->children_count() + 1;
+    parent_entry->SetNamedReference(
+        type,
+        collection_->names()->GetName(index),
+        child_entry);
   }
 
  private:
   HeapSnapshot* snapshot_;
   HeapSnapshotsCollection* collection_;
   HeapEntriesMap* entries_;
 };
 
 
 HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot,
@@ skipping 29 matching lines @@
 #endif
 
   // The following code uses heap iterators, so we want the heap to be
   // stable. It should follow TagGlobalObjects as that can allocate.
   AssertNoAllocation no_alloc;
 
 #ifdef DEBUG
   debug_heap->Verify();
 #endif
 
-  SetProgressTotal(2);  // 2 passes.
+  SetProgressTotal(1);  // 1 pass.
 
 #ifdef DEBUG
   debug_heap->Verify();
 #endif
 
-  // Pass 1. Iterate heap contents to count entries and references.
-  if (!CountEntriesAndReferences()) return false;
-
-#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(V8HeapExplorer::kInternalRootObject);
-
-  // Pass 2. Fill references.
   if (!FillReferences()) return false;
 
+  snapshot_->FillChildrenAndRetainers();
   snapshot_->RememberLastJSObjectId();
 
   if (!SetEntriesDominators()) return false;
   if (!CalculateRetainedSizes()) return false;
 
   progress_counter_ = progress_total_;
   if (!ProgressReport(true)) return false;
   return true;
 }
 
@@ skipping 11 matching lines @@
           control_->ReportProgressValue(progress_counter_, progress_total_) ==
           v8::ActivityControl::kContinue;
   }
   return true;
 }
 
 
 void HeapSnapshotGenerator::SetProgressTotal(int iterations_count) {
   if (control_ == NULL) return;
   HeapIterator iterator(HeapIterator::kFilterUnreachable);
-  progress_total_ = (
+  progress_total_ = iterations_count * (
       v8_heap_explorer_.EstimateObjectsCount(&iterator) +
-      dom_explorer_.EstimateObjectsCount()) * iterations_count;
+      dom_explorer_.EstimateObjectsCount());
   progress_counter_ = 0;
 }
 
 
-bool HeapSnapshotGenerator::CountEntriesAndReferences() {
-  SnapshotCounter counter(&entries_);
-  v8_heap_explorer_.AddRootEntries(&counter);
-  return v8_heap_explorer_.IterateAndExtractReferences(&counter)
-      && dom_explorer_.IterateAndExtractReferences(&counter);
-}
-
-
 bool HeapSnapshotGenerator::FillReferences() {
   SnapshotFiller filler(snapshot_, &entries_);
+  v8_heap_explorer_.AddRootEntries(&filler);
   // IterateAndExtractReferences cannot set object names because
   // it makes call to JSObject::LocalLookupRealNamedProperty which
   // in turn may relocate objects in property maps thus changing the heap
   // layout and affecting retainer counts. This is not acceptable because
   // number of retainers must not change between count and fill passes.
   // To avoid this there's a separate postpass that set object names.
   return v8_heap_explorer_.IterateAndExtractReferences(&filler)
       && dom_explorer_.IterateAndExtractReferences(&filler)
       && v8_heap_explorer_.IterateAndSetObjectNames(&filler);
 }
 
 
-bool HeapSnapshotGenerator::IsUserGlobalReference(const HeapGraphEdge& edge) {
-  ASSERT(edge.from() == snapshot_->root());
-  return edge.type() == HeapGraphEdge::kShortcut;
+bool HeapSnapshotGenerator::IsUserGlobalReference(const HeapGraphEdge* edge) {
+  ASSERT(edge->from() == snapshot_->root());
+  return edge->type() == HeapGraphEdge::kShortcut;
 }
 
 
 void HeapSnapshotGenerator::MarkUserReachableObjects() {
   List<HeapEntry*> worklist;
 
-  Vector<HeapGraphEdge> children = snapshot_->root()->children();
+  Vector<HeapGraphEdge*> children = snapshot_->root()->children();
   for (int i = 0; i < children.length(); ++i) {
     if (IsUserGlobalReference(children[i])) {
-      worklist.Add(children[i].to());
+      worklist.Add(children[i]->to());
     }
   }
 
   while (!worklist.is_empty()) {
     HeapEntry* entry = worklist.RemoveLast();
     if (entry->user_reachable()) continue;
     entry->set_user_reachable();
-    Vector<HeapGraphEdge> children = entry->children();
+    Vector<HeapGraphEdge*> children = entry->children();
     for (int i = 0; i < children.length(); ++i) {
-      HeapEntry* child = children[i].to();
+      HeapEntry* child = children[i]->to();
       if (!child->user_reachable()) {
         worklist.Add(child);
       }
     }
   }
 }
 
 
 static bool IsRetainingEdge(HeapGraphEdge* edge) {
   if (edge->type() == HeapGraphEdge::kShortcut) return false;
   // The edge is not retaining if it goes from system domain
   // (i.e. an object not reachable from window) to the user domain
   // (i.e. a reachable object).
   return edge->from()->user_reachable()
       || !edge->to()->user_reachable();
 }
 
 
 void HeapSnapshotGenerator::FillPostorderIndexes(
     Vector<HeapEntry*>* entries) {
   snapshot_->ClearPaint();
   int current_entry = 0;
   List<HeapEntry*> nodes_to_visit;
   HeapEntry* root = snapshot_->root();
   nodes_to_visit.Add(root);
   snapshot_->root()->paint();
   while (!nodes_to_visit.is_empty()) {
     HeapEntry* entry = nodes_to_visit.last();
-    Vector<HeapGraphEdge> children = entry->children();
+    Vector<HeapGraphEdge*> children = entry->children();
     bool has_new_edges = false;
     for (int i = 0; i < children.length(); ++i) {
-      if (entry != root && !IsRetainingEdge(&children[i])) continue;
-      HeapEntry* child = children[i].to();
+      if (entry != root && !IsRetainingEdge(children[i])) continue;
+      HeapEntry* child = children[i]->to();
       if (!child->painted()) {
         nodes_to_visit.Add(child);
         child->paint();
         has_new_edges = true;
       }
     }
     if (!has_new_edges) {
-      entry->set_ordered_index(current_entry);
+      entry->set_postorder_index(current_entry);
       (*entries)[current_entry++] = entry;
       nodes_to_visit.RemoveLast();
     }
   }
   ASSERT_EQ(current_entry, entries->length());
 }
 
 
 static int Intersect(int i1, int i2, const Vector<int>& dominators) {
   int finger1 = i1, finger2 = i2;
   while (finger1 != finger2) {
     while (finger1 < finger2) finger1 = dominators[finger1];
     while (finger2 < finger1) finger2 = dominators[finger2];
   }
   return finger1;
 }
 
 
 // The algorithm is based on the article:
 // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
 // Softw. Pract. Exper. 4 (2001), pp. 1-10.
 bool HeapSnapshotGenerator::BuildDominatorTree(
     const Vector<HeapEntry*>& entries,
     Vector<int>* dominators) {
   if (entries.length() == 0) return true;
   HeapEntry* root = snapshot_->root();
   const int entries_length = entries.length(), root_index = entries_length - 1;
-  static const int kNoDominator = -1;
-  for (int i = 0; i < root_index; ++i) (*dominators)[i] = kNoDominator;
+  for (int i = 0; i < root_index; ++i) (*dominators)[i] = HeapEntry::kNoEntry;
   (*dominators)[root_index] = root_index;
 
   // The affected array is used to mark entries which dominators
   // have to be racalculated because of changes in their retainers.
   ScopedVector<bool> affected(entries_length);
   for (int i = 0; i < affected.length(); ++i) affected[i] = false;
   // Mark the root direct children as affected.
-  Vector<HeapGraphEdge> children = entries[root_index]->children();
+  Vector<HeapGraphEdge*> children = entries[root_index]->children();
   for (int i = 0; i < children.length(); ++i) {
-    affected[children[i].to()->ordered_index()] = true;
+    affected[children[i]->to()->postorder_index()] = true;
   }
 
   bool changed = true;
   while (changed) {
     changed = false;
-    if (!ProgressReport(true)) return false;
+    if (!ProgressReport(false)) return false;
     for (int i = root_index - 1; i >= 0; --i) {
       if (!affected[i]) continue;
       affected[i] = false;
       // If dominator of the entry has already been set to root,
       // then it can't propagate any further.
       if ((*dominators)[i] == root_index) continue;
-      int new_idom_index = kNoDominator;
+      int new_idom_index = HeapEntry::kNoEntry;
       Vector<HeapGraphEdge*> rets = entries[i]->retainers();
       for (int j = 0; j < rets.length(); ++j) {
         if (rets[j]->from() != root && !IsRetainingEdge(rets[j])) continue;
-        int ret_index = rets[j]->from()->ordered_index();
-        if (dominators->at(ret_index) != kNoDominator) {
-          new_idom_index = new_idom_index == kNoDominator
+        int ret_index = rets[j]->from()->postorder_index();
+        if (dominators->at(ret_index) != HeapEntry::kNoEntry) {
+          new_idom_index = new_idom_index == HeapEntry::kNoEntry
               ? ret_index
               : Intersect(ret_index, new_idom_index, *dominators);
           // If idom has already reached the root, it doesn't make sense
           // to check other retainers.
           if (new_idom_index == root_index) break;
         }
       }
-      if (new_idom_index != kNoDominator
+      if (new_idom_index != HeapEntry::kNoEntry
           && dominators->at(i) != new_idom_index) {
         (*dominators)[i] = new_idom_index;
         changed = true;
-        Vector<HeapGraphEdge> children = entries[i]->children();
+        Vector<HeapGraphEdge*> children = entries[i]->children();
         for (int j = 0; j < children.length(); ++j) {
-          affected[children[j].to()->ordered_index()] = true;
+          affected[children[j]->to()->postorder_index()] = true;
         }
       }
     }
   }
   return true;
 }
 
 
 bool HeapSnapshotGenerator::SetEntriesDominators() {
   MarkUserReachableObjects();
   // This array is used for maintaining postorder of nodes.
-  ScopedVector<HeapEntry*> ordered_entries(snapshot_->entries()->length());
+  ScopedVector<HeapEntry*> ordered_entries(snapshot_->entries().length());
   FillPostorderIndexes(&ordered_entries);
   ScopedVector<int> dominators(ordered_entries.length());
   if (!BuildDominatorTree(ordered_entries, &dominators)) return false;
   for (int i = 0; i < ordered_entries.length(); ++i) {
-    ASSERT(dominators[i] >= 0);
+    ASSERT(dominators[i] != HeapEntry::kNoEntry);
     ordered_entries[i]->set_dominator(ordered_entries[dominators[i]]);
   }
   return true;
 }
 
 
 bool HeapSnapshotGenerator::CalculateRetainedSizes() {
   // As for the dominators tree we only know parent nodes, not
   // children, to sum up total sizes we "bubble" node's self size
   // adding it to all of its parents.
-  List<HeapEntry*>& entries = *snapshot_->entries();
+  List<HeapEntry>& entries = snapshot_->entries();
   for (int i = 0; i < entries.length(); ++i) {
-    HeapEntry* entry = entries[i];
+    HeapEntry* entry = &entries[i];
     entry->set_retained_size(entry->self_size());
   }
   for (int i = 0; i < entries.length(); ++i) {
-    HeapEntry* entry = entries[i];
-    int entry_size = entry->self_size();
-    for (HeapEntry* dominator = entry->dominator();
-         dominator != entry;
-         entry = dominator, dominator = entry->dominator()) {
+    int entry_size = entries[i].self_size();
+    HeapEntry* current = &entries[i];
+    for (HeapEntry* dominator = current->dominator();
+         dominator != current;
+         current = dominator, dominator = current->dominator()) {
+      ASSERT(current->dominator() != NULL);
       dominator->add_retained_size(entry_size);
     }
   }
   return true;
 }
 
 
 template<int bytes> struct MaxDecimalDigitsIn;
 template<> struct MaxDecimalDigitsIn<4> {
   static const int kSigned = 11;
@@ skipping 83 matching lines @@
   }
 
   v8::OutputStream* stream_;
   int chunk_size_;
   ScopedVector<char> chunk_;
   int chunk_pos_;
   bool aborted_;
 };
 
 
+// type, name|index, to_node.
+const int HeapSnapshotJSONSerializer::kEdgeFieldsCount = 3;
+// type, name, id, self_size, retained_size, dominator, children_index.
+const int HeapSnapshotJSONSerializer::kNodeFieldsCount = 7;
+
 void HeapSnapshotJSONSerializer::Serialize(v8::OutputStream* stream) {
   ASSERT(writer_ == NULL);
   writer_ = new OutputStreamWriter(stream);
 
   HeapSnapshot* original_snapshot = NULL;
-  if (snapshot_->raw_entries_size() >=
+  if (snapshot_->RawSnapshotSize() >=
       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.
+
   SerializeImpl();
 
   delete writer_;
   writer_ = NULL;
 
   if (original_snapshot != NULL) {
     delete snapshot_;
     snapshot_ = original_snapshot;
   }
 }
 
 
 HeapSnapshot* HeapSnapshotJSONSerializer::CreateFakeSnapshot() {
   HeapSnapshot* result = new HeapSnapshot(snapshot_->collection(),
                                           HeapSnapshot::kFull,
                                           snapshot_->title(),
                                           snapshot_->uid());
-  result->AllocateEntries(2, 1, 0);
-  HeapEntry* root = result->AddRootEntry(1);
+  result->AddRootEntry();
   const char* text = snapshot_->collection()->names()->GetFormatted(
       "The snapshot is too big. "
       "Maximum snapshot size is %"  V8_PTR_PREFIX "u MB. "
       "Actual snapshot size is %"  V8_PTR_PREFIX "u MB.",
       SnapshotSizeConstants<kPointerSize>::kMaxSerializableSnapshotRawSize / MB,
-      (snapshot_->raw_entries_size() + MB - 1) / MB);
-  HeapEntry* message = result->AddEntry(
-      HeapEntry::kString, text, 0, 4, 0, 0);
-  root->SetUnidirElementReference(0, 1, message);
+      (snapshot_->RawSnapshotSize() + MB - 1) / MB);
+  HeapEntry* message = result->AddEntry(HeapEntry::kString, text, 0, 4);
+  result->root()->SetIndexedReference(HeapGraphEdge::kElement, 1, message);
+  result->FillChildrenAndRetainers();
   result->SetDominatorsToSelf();
   return result;
 }
 
 
-void HeapSnapshotJSONSerializer::CalculateNodeIndexes(
-    const List<HeapEntry*>& nodes) {
-  // type,name,id,self_size,retained_size,dominator,children_index.
-  const int node_fields_count = 7;
-  // 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) {
-    int index = 0;
-    for (int i = 0; i < nodes.length(); ++i, index += node_fields_count) {
-      nodes[i]->set_entry_index(index);
-    }
-  }
-}
-
-
 void HeapSnapshotJSONSerializer::SerializeImpl() {
-  List<HeapEntry*>& nodes = *(snapshot_->entries());
-  CalculateNodeIndexes(nodes);
+  List<HeapEntry>& nodes = snapshot_->entries();
+  ASSERT(0 == snapshot_->root()->index());
   writer_->AddCharacter('{');
   writer_->AddString("\"snapshot\":{");
   SerializeSnapshot();
   if (writer_->aborted()) return;
   writer_->AddString("},\n");
   writer_->AddString("\"nodes\":[");
   SerializeNodes(nodes);
   if (writer_->aborted()) return;
   writer_->AddString("],\n");
   writer_->AddString("\"edges\":[");
@@ skipping 55 matching lines @@
       || edge->type() == HeapGraphEdge::kWeak
       ? edge->index() : GetStringId(edge->name());
   int buffer_pos = 0;
   if (!first_edge) {
     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(edge->to()->entry_index(), buffer, buffer_pos);
+  buffer_pos = itoa(entry_index(edge->to()), buffer, buffer_pos);
   buffer[buffer_pos++] = '\0';
   writer_->AddString(buffer.start());
 }
 
 
-void HeapSnapshotJSONSerializer::SerializeEdges(const List<HeapEntry*>& nodes) {
+void HeapSnapshotJSONSerializer::SerializeEdges(const List<HeapEntry>& nodes) {
   bool first_edge = true;
   for (int i = 0; i < nodes.length(); ++i) {
-    HeapEntry* entry = nodes[i];
-    Vector<HeapGraphEdge> children = entry->children();
+    HeapEntry* entry = &nodes[i];
+    Vector<HeapGraphEdge*> children = entry->children();
     for (int j = 0; j < children.length(); ++j) {
-      SerializeEdge(&children[j], first_edge);
+      SerializeEdge(children[j], first_edge);
       first_edge = false;
       if (writer_->aborted()) return;
     }
   }
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry,
                                                int edges_index) {
   // 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;
   int buffer_pos = 0;
   buffer[buffer_pos++] = '\n';
-  if (entry->entry_index() != 0) {
+  if (entry_index(entry) != 0) {
     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(entry->dominator()->entry_index(), buffer, buffer_pos);
+  buffer_pos = itoa(entry_index(entry->dominator()), buffer, buffer_pos);
   buffer[buffer_pos++] = ',';
   buffer_pos = itoa(edges_index, buffer, buffer_pos);
   buffer[buffer_pos++] = '\0';
   writer_->AddString(buffer.start());
 }
 
 
-void HeapSnapshotJSONSerializer::SerializeNodes(const List<HeapEntry*>& nodes) {
-  const int edge_fields_count = 3;  // type,name|index,to_node.
+void HeapSnapshotJSONSerializer::SerializeNodes(const List<HeapEntry>& nodes) {
   int edges_index = 0;
   for (int i = 0; i < nodes.length(); ++i) {
-    HeapEntry* entry = nodes[i];
+    HeapEntry* entry = &nodes[i];
     SerializeNode(entry, edges_index);
-    edges_index += entry->children().length() * edge_fields_count;
+    edges_index += entry->children().length() * kEdgeFieldsCount;
     if (writer_->aborted()) return;
   }
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeSnapshot() {
   writer_->AddString("\"title\":\"");
   writer_->AddString(snapshot_->title());
   writer_->AddString("\"");
   writer_->AddString(",\"uid\":");
@@ skipping 43 matching lines @@
             JSON_S("internal") ","
             JSON_S("hidden") ","
             JSON_S("shortcut") ","
             JSON_S("weak")) ","
         JSON_S("string_or_number") ","
         JSON_S("node"))));
 #undef JSON_S
 #undef JSON_O
 #undef JSON_A
   writer_->AddString(",\"node_count\":");
-  writer_->AddNumber(snapshot_->entries()->length());
+  writer_->AddNumber(snapshot_->entries().length());
   writer_->AddString(",\"edge_count\":");
-  writer_->AddNumber(snapshot_->number_of_edges());
+  writer_->AddNumber(snapshot_->edges().length());
 }
 
 
 static void WriteUChar(OutputStreamWriter* w, unibrow::uchar u) {
   static const char hex_chars[] = "0123456789ABCDEF";
   w->AddString("\\u");
   w->AddCharacter(hex_chars[(u >> 12) & 0xf]);
   w->AddCharacter(hex_chars[(u >> 8) & 0xf]);
   w->AddCharacter(hex_chars[(u >> 4) & 0xf]);
   w->AddCharacter(hex_chars[u & 0xf]);
@@ skipping 77 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