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

src/objects.cc

 // Copyright 2006-2009 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 6823 matching lines @@
 
 
 template<typename Shape, typename Key>
 Object* HashTable<Shape, Key>::Allocate(
     int at_least_space_for) {
   int capacity = RoundUpToPowerOf2(at_least_space_for);
   if (capacity < 4) capacity = 4;  // Guarantee min capacity.
   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;
 }
 
 
 
 // Find entry for key otherwise return -1.
 template<typename Shape, typename Key>
 int HashTable<Shape, Key>::FindEntry(Key key) {
@@ skipping 19 matching lines @@
     }
   }
   return kNotFound;
 }
 
 
 template<typename Shape, typename Key>
 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;
   HashTable* table = HashTable::cast(obj);
   WriteBarrierMode mode = table->GetWriteBarrierMode();
 
   // Copy prefix to new array.
   for (int i = kPrefixStartIndex;
        i < kPrefixStartIndex + Shape::kPrefixSize;
        i++) {
     table->set(i, get(i), mode);
   }
   // Rehash the elements.
   for (int i = 0; i < capacity; i++) {
     uint32_t from_index = EntryToIndex(i);
     Object* k = get(from_index);
     if (IsKey(k)) {
       uint32_t hash = Shape::HashForObject(key, k);
       uint32_t insertion_index =
           EntryToIndex(table->FindInsertionEntry(hash));
       for (int j = 0; j < Shape::kEntrySize; j++) {
         table->set(insertion_index + j, get(from_index + j), mode);
       }
     }
   }
   table->SetNumberOfElements(NumberOfElements());
+  table->SetNumberOfDeletedElements(0);
   return table;
 }
 
 
 template<typename Shape, typename Key>
 uint32_t HashTable<Shape, Key>::FindInsertionEntry(uint32_t hash) {
   uint32_t capacity = Capacity();
   uint32_t entry = GetProbe(hash, 0, capacity);
   Object* element = KeyAt(entry);
 
@@ skipping 775 matching lines @@
     if (key->IsNumber()) {
       uint32_t number = static_cast<uint32_t>(key->Number());
       if (from <= number && number < to) {
         SetEntry(i, sentinel, sentinel, Smi::FromInt(0));
         removed_entries++;
       }
     }
   }
 
   // Update the number of elements.
-  SetNumberOfElements(NumberOfElements() - removed_entries);
+  ElementsRemoved(removed_entries);
 }
 
 
 template<typename Shape, typename Key>
 Object* Dictionary<Shape, Key>::DeleteProperty(int entry,
                                                JSObject::DeleteMode mode) {
   PropertyDetails details = DetailsAt(entry);
   // Ignore attributes if forcing a deletion.
   if (details.IsDontDelete() && mode == JSObject::NORMAL_DELETION) {
     return Heap::false_value();
@@ skipping 577 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal