Shrink dictionaries on deletion if number of elements are less than a

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 6c9f52b2df89839306e30b8f925f87412fc111f4..4cbbcb3168b3ea81298ae0366f15dcb999ecb5a5 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -493,7 +493,16 @@ MaybeObject* JSObject::DeleteNormalizedProperty(String* name, DeleteMode mode) {
       cell->set_value(cell->heap()->the_hole_value());
       dictionary->DetailsAtPut(entry, details.AsDeleted());
     } else {
-      return dictionary->DeleteProperty(entry, mode);
+      Object* deleted = dictionary->DeleteProperty(entry, mode);
+      if (deleted == GetHeap()->true_value()) {
+        FixedArray* new_properties = NULL;
+        MaybeObject* maybe_properties = dictionary->Shrink(name);
+        if (!maybe_properties->To(&new_properties)) {
+          return maybe_properties;
+        }
+        set_properties(new_properties);
+      }
+      return deleted;
     }
   }
   return GetHeap()->true_value();
@@ -2955,7 +2964,16 @@ MaybeObject* JSObject::DeleteElementPostInterceptor(uint32_t index,
       NumberDictionary* dictionary = element_dictionary();
       int entry = dictionary->FindEntry(index);
       if (entry != NumberDictionary::kNotFound) {
-        return dictionary->DeleteProperty(entry, mode);
+        Object* deleted = dictionary->DeleteProperty(entry, mode);
+        if (deleted == GetHeap()->true_value()) {
+          MaybeObject* maybe_elements = dictionary->Shrink(index);
+          FixedArray* new_elements = NULL;
+          if (!maybe_elements->To(&new_elements)) {
+            return maybe_elements;
+          }
+          set_elements(new_elements);
+        }
+        return deleted;
       }
       break;
     }
@@ -3035,6 +3053,14 @@ MaybeObject* JSObject::DeleteDictionaryElement(uint32_t index,
   int entry = dictionary->FindEntry(index);
   if (entry != NumberDictionary::kNotFound) {
     Object* result = dictionary->DeleteProperty(entry, mode);
+    if (result == heap->true_value()) {
+      MaybeObject* maybe_elements = dictionary->Shrink(index);
+      FixedArray* new_elements = NULL;
+      if (!maybe_elements->To(&new_elements)) {
+        return maybe_elements;
+      }
+      set_elements(new_elements);
+    }
     if (mode == STRICT_DELETION && result == heap->false_value()) {
       // In strict mode, attempting to delete a non-configurable property
       // throws an exception.
@@ -8230,7 +8256,7 @@ MaybeObject* JSObject::SetFastElement(uint32_t index,
     if (found) return result;
   }
 
-  // Check whether there is extra space in fixed array..
+  // Check whether there is extra space in fixed array.
   if (index < length) {
     backing_store->set(index, value);
     if (IsJSArray()) {
@@ -9954,6 +9980,40 @@ int StringDictionary::FindEntry(String* key) {
 
 
 template<typename Shape, typename Key>
+MaybeObject* HashTable<Shape, Key>::Rehash(HashTable* new_table, Key key) {
+  ASSERT(NumberOfElements() < new_table->Capacity());
+
+  AssertNoAllocation no_gc;
+  WriteBarrierMode mode = new_table->GetWriteBarrierMode(no_gc);
+
+  // Copy prefix to new array.
+  for (int i = kPrefixStartIndex;
+       i < kPrefixStartIndex + Shape::kPrefixSize;
+       i++) {
+    new_table->set(i, get(i), mode);
+  }
+
+  // Rehash the elements.
+  int capacity = Capacity();
+  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(new_table->FindInsertionEntry(hash));
+      for (int j = 0; j < Shape::kEntrySize; j++) {
+        new_table->set(insertion_index + j, get(from_index + j), mode);
+      }
+    }
+  }
+  new_table->SetNumberOfElements(NumberOfElements());
+  new_table->SetNumberOfDeletedElements(0);
+  return new_table;
+}
+
+
+template<typename Shape, typename Key>
 MaybeObject* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
   int capacity = Capacity();
   int nof = NumberOfElements() + n;
@@ -9975,32 +10035,32 @@ MaybeObject* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
 
-  AssertNoAllocation no_gc;
-  HashTable* table = HashTable::cast(obj);
-  WriteBarrierMode mode = table->GetWriteBarrierMode(no_gc);
+  return Rehash(HashTable::cast(obj), key);
+}
 
-  // 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);
-      }
-    }
+
+template<typename Shape, typename Key>
+MaybeObject* HashTable<Shape, Key>::Shrink(Key key) {
+  int capacity = Capacity();
+  int nof = NumberOfElements();
+
+  // Shrink to double the amount of elements if only a quarter of the
+  // capacity is filled with elements and the new capacity is more
+  // than 16 elements.
+  if (nof > (capacity >> 2)) return this;
+  int new_capacity = capacity >> 2;
+  if (new_capacity < 16) return this;

[Vyacheslav Egorov (Chromium), 2011/06/22 14:39:36]

This is a bit strange. 

I would ensure that (new_capacity >= 2 * nof) otherwise will get another
rehashing immediately when we try to add a new element after Shrink'ing. Also
not very good for conflicts.

[Mads Ager (chromium), 2011/06/22 14:55:20]

Ah, I actually mean this. However, I did not mean new_capacity to be capacity >>
2. I meant it to be capacity >> 1. Since nof can be zero I want to make sure
that we do not go below 16.

+
+  const int kMinCapacityForPretenure = 256;
+  bool pretenure =
+      (new_capacity > kMinCapacityForPretenure) && !GetHeap()->InNewSpace(this);
+  Object* obj;
+  { MaybeObject* maybe_obj =
+        Allocate(new_capacity, pretenure ? TENURED : NOT_TENURED);
+    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
-  table->SetNumberOfElements(NumberOfElements());
-  table->SetNumberOfDeletedElements(0);
-  return table;
+
+  return Rehash(HashTable::cast(obj), key);
 }
 
 
@@ -10055,6 +10115,12 @@ template Object* Dictionary<StringDictionaryShape, String*>::DeleteProperty(
 template Object* Dictionary<NumberDictionaryShape, uint32_t>::DeleteProperty(
     int, JSObject::DeleteMode);
 
+template MaybeObject* Dictionary<StringDictionaryShape, String*>::Shrink(
+    String*);
+
+template MaybeObject* Dictionary<NumberDictionaryShape, uint32_t>::Shrink(
+    uint32_t);
+
 template void Dictionary<StringDictionaryShape, String*>::CopyKeysTo(
     FixedArray*);
 
@@ -10954,6 +11020,12 @@ Object* Dictionary<Shape, Key>::DeleteProperty(int entry,
 
 
 template<typename Shape, typename Key>
+MaybeObject* Dictionary<Shape, Key>::Shrink(Key key) {
+  return HashTable<Shape, Key>::Shrink(key);
+}
+
+
+template<typename Shape, typename Key>
 MaybeObject* Dictionary<Shape, Key>::AtPut(Key key, Object* value) {
   int entry = this->FindEntry(key);