Revision: 8391
Author: [email protected]
Date: Thu Jun 23 02:30:39 2011
Log: Shrink dictionaries on deletion if number of elements are less
than a
quarter of the capacity.
[email protected]
Review URL: http://codereview.chromium.org/7190032
http://code.google.com/p/v8/source/detail?r=8391
Modified:
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
=======================================
--- /branches/bleeding_edge/src/objects.cc Tue Jun 21 02:27:38 2011
+++ /branches/bleeding_edge/src/objects.cc Thu Jun 23 02:30:39 2011
@@ -493,7 +493,16 @@
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 @@
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 @@
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 @@
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()) {
@@ -9951,6 +9977,40 @@
}
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>
@@ -9975,32 +10035,36 @@
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 fit the number of elements if only a quarter of the
+ // capacity is filled with elements.
+ if (nof > (capacity >> 2)) return this;
+ // Allocate a new dictionary with room for at least the current
+ // number of elements. The allocation method will make sure that
+ // there is extra room in the dictionary for additions. Don't go
+ // lower than room for 16 elements.
+ int at_least_room_for = nof;
+ if (at_least_room_for < 16) return this;
+
+ const int kMinCapacityForPretenure = 256;
+ bool pretenure =
+ (at_least_room_for > kMinCapacityForPretenure) &&
+ !GetHeap()->InNewSpace(this);
+ Object* obj;
+ { MaybeObject* maybe_obj =
+ Allocate(at_least_room_for, pretenure ? TENURED : NOT_TENURED);
+ if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+ }
+
+ return Rehash(HashTable::cast(obj), key);
}
@@ -10055,6 +10119,12 @@
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*);
@@ -10951,6 +11021,12 @@
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>
=======================================
--- /branches/bleeding_edge/src/objects.h Wed Jun 22 05:39:45 2011
+++ /branches/bleeding_edge/src/objects.h Thu Jun 23 02:30:39 2011
@@ -2589,6 +2589,12 @@
static uint32_t NextProbe(uint32_t last, uint32_t number, uint32_t size)
{
return (last + number) & (size - 1);
}
+
+ // Rehashes this hash-table into the new table.
+ MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key);
+
+ // Attempt to shrink hash table after removal of key.
+ MUST_USE_RESULT MaybeObject* Shrink(Key key);
// Ensure enough space for n additional elements.
MUST_USE_RESULT MaybeObject* EnsureCapacity(int n, Key key);
@@ -2754,6 +2760,9 @@
// Delete a property from the dictionary.
Object* DeleteProperty(int entry, JSObject::DeleteMode mode);
+ // Attempt to shrink the dictionary after deletion of key.
+ MUST_USE_RESULT MaybeObject* Shrink(Key key);
+
// Returns the number of elements in the dictionary filtering out
properties
// with the specified attributes.
int NumberOfElementsFilterAttributes(PropertyAttributes filter);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
