Revision: 3536 Author: [email protected] Date: Tue Jan 5 03:38:36 2010 Log: Added rehashing of hash tables when there are too many deleted elements.
Review URL: http://codereview.chromium.org/525024 http://code.google.com/p/v8/source/detail?r=3536 Modified: /branches/bleeding_edge/src/objects.cc /branches/bleeding_edge/src/objects.h ======================================= --- /branches/bleeding_edge/src/objects.cc Wed Dec 16 07:43:20 2009 +++ /branches/bleeding_edge/src/objects.cc Tue Jan 5 03:38:36 2010 @@ -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 + // at most 50% of the free elements are deleted elements. + 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); } ======================================= --- /branches/bleeding_edge/src/objects.h Tue Dec 22 05:34:02 2009 +++ /branches/bleeding_edge/src/objects.h Tue Jan 5 03:38:36 2010 @@ -1885,6 +1885,11 @@ int NumberOfElements() { return Smi::cast(get(kNumberOfElementsIndex))->value(); } + + // Returns the number of deleted elements in the hash table. + int NumberOfDeletedElements() { + return Smi::cast(get(kNumberOfDeletedElementsIndex))->value(); + } // Returns the capacity of the hash table. int Capacity() { @@ -1897,8 +1902,14 @@ // ElementRemoved should be called whenever an element is removed from // a hash table. - void ElementRemoved() { SetNumberOfElements(NumberOfElements() - 1); } - void ElementsRemoved(int n) { SetNumberOfElements(NumberOfElements() - n); } + void ElementRemoved() { + SetNumberOfElements(NumberOfElements() - 1); + SetNumberOfDeletedElements(NumberOfDeletedElements() + 1); + } + void ElementsRemoved(int n) { + SetNumberOfElements(NumberOfElements() - n); + SetNumberOfDeletedElements(NumberOfDeletedElements() + n); + } // Returns a new HashTable object. Might return Failure. static Object* Allocate(int at_least_space_for); @@ -1925,12 +1936,13 @@ } static const int kNumberOfElementsIndex = 0; - static const int kCapacityIndex = 1; - static const int kPrefixStartIndex = 2; - static const int kElementsStartIndex = + static const int kNumberOfDeletedElementsIndex = 1; + static const int kCapacityIndex = 2; + static const int kPrefixStartIndex = 3; + static const int kElementsStartIndex = kPrefixStartIndex + Shape::kPrefixSize; - static const int kEntrySize = Shape::kEntrySize; - static const int kElementsStartOffset = + static const int kEntrySize = Shape::kEntrySize; + static const int kElementsStartOffset = kHeaderSize + kElementsStartIndex * kPointerSize; // Constant used for denoting a absent entry. @@ -1954,6 +1966,11 @@ void SetNumberOfElements(int nof) { fast_set(this, kNumberOfElementsIndex, Smi::FromInt(nof)); } + + // Update the number of deleted elements in the hash table. + void SetNumberOfDeletedElements(int nod) { + fast_set(this, kNumberOfDeletedElementsIndex, Smi::FromInt(nod)); + } // Sets the capacity of the hash table. void SetCapacity(int capacity) { -- v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev
