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

src/objects.cc

 // Copyright 2011 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 475 matching lines @@
         { MaybeObject* maybe_new_map = map()->CopyDropDescriptors();
           if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
         }
         set_map(Map::cast(new_map));
       }
       JSGlobalPropertyCell* cell =
           JSGlobalPropertyCell::cast(dictionary->ValueAt(entry));
       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();
 }
 
 
 bool JSObject::IsDirty() {
   Object* cons_obj = map()->constructor();
   if (!cons_obj->IsJSFunction())
     return true;
@@ skipping 2441 matching lines @@
       static_cast<uint32_t>(FixedArray::cast(elements())->length());
       if (index < length) {
         FixedArray::cast(elements())->set_the_hole(index);
       }
       break;
     }
     case DICTIONARY_ELEMENTS: {
       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;
     }
     default:
       UNREACHABLE();
       break;
   }
   return GetHeap()->true_value();
 }
 
@@ skipping 59 matching lines @@
   Isolate* isolate = GetIsolate();
   Heap* heap = isolate->heap();
   FixedArray* backing_store = FixedArray::cast(elements());
   if (backing_store->map() == heap->non_strict_arguments_elements_map()) {
     backing_store = FixedArray::cast(backing_store->get(1));
   }
   NumberDictionary* dictionary = NumberDictionary::cast(backing_store);
   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.
       HandleScope scope(isolate);
       Handle<Object> name = isolate->factory()->NewNumberFromUint(index);
       Handle<Object> args[2] = { name, Handle<Object>(this) };
       Handle<Object> error =
           isolate->factory()->NewTypeError("strict_delete_property",
                                            HandleVector(args, 2));
       return isolate->Throw(*error);
@@ skipping 5175 matching lines @@
   if (check_prototype &&
       (index >= length || backing_store->get(index)->IsTheHole())) {
     bool found;
     MaybeObject* result = SetElementWithCallbackSetterInPrototypes(index,
                                                                    value,
                                                                    &found,
                                                                    strict_mode);
     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()) {
       // Update the length of the array if needed.
       uint32_t array_length = 0;
       CHECK(JSArray::cast(this)->length()->ToArrayIndex(&array_length));
       if (index >= array_length) {
         JSArray::cast(this)->set_length(Smi::FromInt(index + 1));
       }
     }
@@ skipping 1703 matching lines @@
       return entry;
     }
     ASSERT(element->IsNull() || !String::cast(element)->Equals(key));
     entry = NextProbe(entry, count++, capacity);
   }
   return kNotFound;
 }
 
 
 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;
   int nod = NumberOfDeletedElements();
   // Return if:
   //   50% is still free after adding n elements and
   //   at most 50% of the free elements are deleted elements.
   if (nod <= (capacity - nof) >> 1) {
     int needed_free = nof >> 1;
     if (nof + needed_free <= capacity) return this;
   }
 
   const int kMinCapacityForPretenure = 256;
   bool pretenure =
       (capacity > kMinCapacityForPretenure) && !GetHeap()->InNewSpace(this);
   Object* obj;
   { MaybeObject* maybe_obj =
         Allocate(nof * 2, pretenure ? TENURED : NOT_TENURED);
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
 
-  AssertNoAllocation no_gc;
-  HashTable* table = HashTable::cast(obj);
-  WriteBarrierMode mode = table->GetWriteBarrierMode(no_gc);
-
-  // 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;
+  return Rehash(HashTable::cast(obj), key);
 }
 
 
+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;
+  }
+
+  return Rehash(HashTable::cast(obj), key);
+}
+
+
 template<typename Shape, typename Key>
 uint32_t HashTable<Shape, Key>::FindInsertionEntry(uint32_t hash) {
   uint32_t capacity = Capacity();
   uint32_t entry = FirstProbe(hash, capacity);
   uint32_t count = 1;
   // EnsureCapacity will guarantee the hash table is never full.
   while (true) {
     Object* element = KeyAt(entry);
     if (element->IsUndefined() || element->IsNull()) break;
     entry = NextProbe(entry, count++, capacity);
@@ skipping 31 matching lines @@
 
 template void Dictionary<NumberDictionaryShape, uint32_t>::CopyKeysTo(
     FixedArray*, PropertyAttributes);
 
 template Object* Dictionary<StringDictionaryShape, String*>::DeleteProperty(
     int, JSObject::DeleteMode);
 
 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*);
 
 template int
 Dictionary<StringDictionaryShape, String*>::NumberOfElementsFilterAttributes(
     PropertyAttributes);
 
 template MaybeObject* Dictionary<StringDictionaryShape, String*>::Add(
     String*, Object*, PropertyDetails);
 
@@ skipping 879 matching lines @@
   if (details.IsDontDelete() && mode != JSObject::FORCE_DELETION) {
     return heap->false_value();
   }
   SetEntry(entry, heap->null_value(), heap->null_value());
   HashTable<Shape, Key>::ElementRemoved();
   return heap->true_value();
 }
 
 
 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);
 
   // If the entry is present set the value;
   if (entry != Dictionary<Shape, Key>::kNotFound) {
     ValueAtPut(entry, value);
     return this;
   }
 
   // Check whether the dictionary should be extended.
@@ skipping 594 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