I'd like to add addr field into EntryInfo struct.

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 1297 matching lines @@
 const SnapshotObjectId HeapObjectsMap::kGcRootsFirstSubrootId =
     HeapObjectsMap::kGcRootsObjectId + HeapObjectsMap::kObjectIdStep;
 const SnapshotObjectId HeapObjectsMap::kFirstAvailableObjectId =
     HeapObjectsMap::kGcRootsFirstSubrootId +
     VisitorSynchronization::kNumberOfSyncTags * HeapObjectsMap::kObjectIdStep;
 
 HeapObjectsMap::HeapObjectsMap()
     : initial_fill_mode_(true),
       next_id_(kFirstAvailableObjectId),
       entries_map_(AddressesMatch),
-      entries_(new List<EntryInfo>()) { }
+      entries_(new List<EntryInfo>()) {
+  entries_->Add(EntryInfo(0, NULL));

[yurys, 2012/04/10 16:46:35]

Could you add a comment that it is for simplifying HeapObjectsMap::MoveObject ?

+}
 
 
 HeapObjectsMap::~HeapObjectsMap() {
   delete entries_;
 }
 
 
 void HeapObjectsMap::SnapshotGenerationFinished() {
   initial_fill_mode_ = false;
   RemoveDeadEntries();
 }
 
 
 SnapshotObjectId HeapObjectsMap::FindObject(Address addr) {
   if (!initial_fill_mode_) {
     SnapshotObjectId existing = FindEntry(addr);
     if (existing != 0) return existing;
   }
   SnapshotObjectId id = next_id_;
   next_id_ += kObjectIdStep;
   AddEntry(addr, id);
+  ASSERT(static_cast<uint32_t>(entries_->length()) > entries_map_.occupancy());
   return id;
 }
 
 
 void HeapObjectsMap::MoveObject(Address from, Address to) {
+  ASSERT(to != NULL);
+  ASSERT(from != NULL);
+  ASSERT(from != to);

[mnaganov (inactive), 2012/04/10 21:12:04]

I'm sure you will be hitting this assert. I think you should remove it.

   if (from == to) return;
-  HashMap::Entry* entry = entries_map_.Lookup(from, AddressHash(from), false);
-  if (entry != NULL) {
-    void* value = entry->value;
-    entries_map_.Remove(from, AddressHash(from));
-    if (to != NULL) {
-      entry = entries_map_.Lookup(to, AddressHash(to), true);
-      // We can have an entry at the new location, it is OK, as GC can overwrite
-      // dead objects with alive objects being moved.
-      entry->value = value;
-    }
+  void* from_value = entries_map_.Remove(from, AddressHash(from));
+  if (from_value == NULL) return;
+  int from_entry_info_index =
+      static_cast<int>(reinterpret_cast<intptr_t>(from_value));
+  entries_->at(from_entry_info_index).addr = to;
+  HashMap::Entry* to_entry = entries_map_.Lookup(to, AddressHash(to), true);
+  if (to_entry->value != NULL) {
+    int to_entry_info_index =
+        static_cast<int>(reinterpret_cast<intptr_t>(to_entry->value));
+    entries_->at(to_entry_info_index).addr = NULL;
   }
+  to_entry->value = reinterpret_cast<void*>(from_entry_info_index);
 }
 
 
 void HeapObjectsMap::AddEntry(Address addr, SnapshotObjectId id) {
   HashMap::Entry* entry = entries_map_.Lookup(addr, AddressHash(addr), true);
   ASSERT(entry->value == NULL);
+  ASSERT(entries_->length() > 0 &&
+         entries_->at(0).id == 0 &&
+         entries_->at(0).addr == NULL);
+  ASSERT(entries_->length() == 1 ||

[mnaganov (inactive), 2012/04/10 21:12:04]

The first part seems to be superfluous, as if entries_ contains only the dummy
element, its id -- 0 will not exceed any other id.

+         entries_->at(entries_->length() - 1).id < id);
   entry->value = reinterpret_cast<void*>(entries_->length());
-  entries_->Add(EntryInfo(id));
+  entries_->Add(EntryInfo(id, addr));
+  ASSERT(static_cast<uint32_t>(entries_->length()) > entries_map_.occupancy());

[yurys, 2012/04/10 16:46:35]

Comment on why it is strictly greater?

 }
 
 
 SnapshotObjectId HeapObjectsMap::FindEntry(Address addr) {
   HashMap::Entry* entry = entries_map_.Lookup(addr, AddressHash(addr), false);
   if (entry != NULL) {
     int entry_index =
         static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
     EntryInfo& entry_info = entries_->at(entry_index);
     entry_info.accessed = true;
+    ASSERT((uint32_t)entries_->length() > entries_map_.occupancy());

[alexeif, 2012/04/10 16:55:24]

still ditto ;-)

     return entry_info.id;
   } else {
     return 0;
   }
 }
 
 
 void HeapObjectsMap::RemoveDeadEntries() {
-  List<EntryInfo>* new_entries = new List<EntryInfo>();
-  List<void*> dead_entries;
-  for (HashMap::Entry* entry = entries_map_.Start();
-       entry != NULL;
-       entry = entries_map_.Next(entry)) {
-    int entry_index =
-        static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
-    EntryInfo& entry_info = entries_->at(entry_index);
+  ASSERT(entries_->length() > 0 &&
+         entries_->at(0).id == 0 &&
+         entries_->at(0).addr == NULL);
+  int first_free_entry = 1;
+  for (int i = 1; i < entries_->length(); ++i) {
+    EntryInfo& entry_info = entries_->at(i);
     if (entry_info.accessed) {
-      entry->value = reinterpret_cast<void*>(new_entries->length());
-      new_entries->Add(EntryInfo(entry_info.id, false));
+      if (first_free_entry != i) {
+        entries_->at(first_free_entry) = entry_info;
+      }
+      entries_->at(first_free_entry).accessed = false;
+      HashMap::Entry* entry = entries_map_.Lookup(
+          entry_info.addr, AddressHash(entry_info.addr), false);
+      ASSERT(entry);
+      entry->value = reinterpret_cast<void*>(first_free_entry);
+      ++first_free_entry;
     } else {
-      dead_entries.Add(entry->key);
+      if (entry_info.addr) {
+        entries_map_.Remove(entry_info.addr, AddressHash(entry_info.addr));
+      }
     }
   }
-  for (int i = 0; i < dead_entries.length(); ++i) {
-    void* raw_entry = dead_entries[i];
-    entries_map_.Remove(
-        raw_entry, AddressHash(reinterpret_cast<Address>(raw_entry)));
-  }
-  delete entries_;
-  entries_ = new_entries;
+  entries_->Rewind(first_free_entry);
+  ASSERT(static_cast<uint32_t>(entries_->length()) - 1 ==
+         entries_map_.occupancy());
 }
 
 
 SnapshotObjectId HeapObjectsMap::GenerateId(v8::RetainedObjectInfo* info) {
   SnapshotObjectId id = static_cast<SnapshotObjectId>(info->GetHash());
   const char* label = info->GetLabel();
   id ^= HashSequentialString(label,
                              static_cast<int>(strlen(label)),
                              HEAP->HashSeed());
   intptr_t element_count = info->GetElementCount();
@@ skipping 2341 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