Revision: 3539
Author: [email protected]
Date: Tue Jan 5 05:29:12 2010
Log: Merge r3536 and r3538 to trunk to fix performance issue with
hash tables.
Review URL: http://codereview.chromium.org/525025
http://code.google.com/p/v8/source/detail?r=3539
Modified:
/trunk/src/objects.cc
/trunk/src/objects.h
/trunk/src/runtime.cc
/trunk/src/version.cc
=======================================
--- /trunk/src/objects.cc Fri Dec 18 00:56:33 2009
+++ /trunk/src/objects.cc Tue Jan 5 05:29:12 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);
}
=======================================
--- /trunk/src/objects.h Fri Dec 18 00:56:33 2009
+++ /trunk/src/objects.h Tue Jan 5 05:29:12 2010
@@ -1874,6 +1874,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() {
@@ -1886,8 +1891,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);
@@ -1914,12 +1925,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.
@@ -1943,6 +1955,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) {
=======================================
--- /trunk/src/runtime.cc Fri Dec 18 00:56:33 2009
+++ /trunk/src/runtime.cc Tue Jan 5 05:29:12 2010
@@ -5408,6 +5408,8 @@
void increase_index_offset(uint32_t delta) {
index_offset_ += delta;
}
+
+ Handle<FixedArray> storage() { return storage_; }
private:
Handle<FixedArray> storage_;
@@ -5718,7 +5720,8 @@
IterateArguments(arguments, &visitor);
result->set_length(*len);
- result->set_elements(*storage);
+ // Please note the storage might have changed in the visitor.
+ result->set_elements(*visitor.storage());
return *result;
}
=======================================
--- /trunk/src/version.cc Mon Dec 28 02:25:11 2009
+++ /trunk/src/version.cc Tue Jan 5 05:29:12 2010
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 2
#define MINOR_VERSION 0
#define BUILD_NUMBER 5
-#define PATCH_LEVEL 4
+#define PATCH_LEVEL 5
#define CANDIDATE_VERSION false
// Define SONAME to have the SCons build the put a specific SONAME into the
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
