Added rehashing of hash tables when there are too many deleted elements.

src/objects.cc

Index: src/objects.cc
===================================================================
--- src/objects.cc	(revision 3533)
+++ src/objects.cc	(working copy)
@@ -6841,6 +6841,7 @@
   Object* obj = Heap::AllocateHashTable(EntryToIndex(capacity));
   if (!obj->IsFailure()) {
     HashTable::cast(obj)->SetNumberOfElements(0);
+    HashTable::cast(obj)->SetNumberOfDeletedElements(0);
     HashTable::cast(obj)->SetCapacity(capacity);
   }
   return obj;
@@ -6880,8 +6881,12 @@
 Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
   int capacity = Capacity();
   int nof = NumberOfElements() + n;
-  // Make sure 50% is free
-  if (nof + (nof >> 1) <= capacity) return this;
+  int nod = NumberOfDeletedElements();
+  // Return if:
+  //   50% is still free after adding n elements and
+  //   atmost 50% of the free elements are deleted elements.

[Mads Ager (chromium), 2010/01/05 11:36:17]

atmost -> at most

+  if ((nof + (nof >> 1) <= capacity) &&
+      (nod <= (capacity - nof) >> 1) ) return this;
 
   Object* obj = Allocate(nof * 2);
   if (obj->IsFailure()) return obj;
@@ -6908,6 +6913,7 @@
     }
   }
   table->SetNumberOfElements(NumberOfElements());
+  table->SetNumberOfDeletedElements(0);
   return table;
 }
 
@@ -7703,7 +7709,7 @@
   }
 
   // Update the number of elements.
-  SetNumberOfElements(NumberOfElements() - removed_entries);
+  ElementsRemoved(removed_entries);
 }