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 1319 matching lines @@
 
 
 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((uint32_t)entries_->length() >= entries_map_.occupancy());

[yurys, 2012/04/10 14:03:35]

Please use static_cast<uint32_t>

   return id;
 }
 
 
+int HeapObjectsMap::UpdateEntryInfoAddress(Address addr,

[mnaganov (inactive), 2012/04/10 13:50:14]

I don't see a clear reason for having EntryInfo lookup and address update in a
single function. I think, restricting the scope to only making a lookup will
make it more clean. Also this should simplify logic in MoveObject (see below).

+                                           uint32_t hash,
+                                           Address new_addr) {
+  HashMap::Entry* entry = entries_map_.Lookup(addr, hash, false);
+  if (entry == NULL) return -1;
+  int entry_index =
+      static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
+  EntryInfo& entry_info = entries_->at(entry_index);
+  entry_info.addr = new_addr;
+  return entry_index;
+}
+
+
 void HeapObjectsMap::MoveObject(Address from, Address to) {
+  ASSERT(to != NULL);
+  ASSERT(from != to);
   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;
-    }
+  // 1. lookup for From address entry in the map and update EntryInfo.addr.

[yurys, 2012/04/10 14:03:35]

From -> |from|, To -> |to|

+  // 2. remove From address entry from the map.
+  // 3. lookup for To address entry in the map and clear EntryInfo.addr.
+  // 4. create/update the map entry for To address and point it to
+  //    From's entry_info index.
+  uint32_t from_hash = AddressHash(from);
+  int from_entry_info_index = UpdateEntryInfoAddress(from, from_hash, to);
+  if (from_entry_info_index != -1) {
+    entries_map_.Remove(from, from_hash);
+    uint32_t to_hash = AddressHash(to);
+    UpdateEntryInfoAddress(to, to_hash, NULL);

[mnaganov (inactive), 2012/04/10 13:50:14]

Why are you making 2 map lookups here?

[yurys, 2012/04/10 14:03:35]

This is an overhead, we should instead do
 entries_->at(entry_index).addr = to;
below line 1374, this way we will need 1 Lookup less.

+    HashMap::Entry* entry = entries_map_.Lookup(to, to_hash, true);
+    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() || entries_->at(entries_->length() - 1).id < id);
   entry->value = reinterpret_cast<void*>(entries_->length());
-  entries_->Add(EntryInfo(id));
+  entries_->Add(EntryInfo(id, addr));
+  ASSERT((uint32_t)entries_->length() >= entries_map_.occupancy());

[yurys, 2012/04/10 14:03:35]

static_cast please.

 }
 
 
 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());

[yurys, 2012/04/10 14:03:35]

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);
+  int first_free_entry = 0;
+  for (int i = 0; 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((uint32_t)entries_->length() == entries_map_.occupancy());

[yurys, 2012/04/10 14:03:35]

ditto.

 }
 
 
 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