Revision: 3549
Author: [email protected]
Date: Thu Jan 7 00:01:27 2010
Log: Merge r3536 and r3538 to branches/1.3 to fix performance issue
with hash tables with many deleted elements.
Review URL: http://codereview.chromium.org/523122
http://code.google.com/p/v8/source/detail?r=3549
Modified:
/branches/1.3/src/objects.cc
/branches/1.3/src/objects.h
/branches/1.3/src/runtime.cc
/branches/1.3/src/version.cc
=======================================
--- /branches/1.3/src/objects.cc Fri Nov 13 00:04:17 2009
+++ /branches/1.3/src/objects.cc Thu Jan 7 00:01:27 2010
@@ -6938,6 +6938,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;
@@ -6977,8 +6978,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;
@@ -7005,6 +7010,7 @@
}
}
table->SetNumberOfElements(NumberOfElements());
+ table->SetNumberOfDeletedElements(0);
return table;
}
@@ -7723,7 +7729,7 @@
}
// Update the number of elements.
- SetNumberOfElements(NumberOfElements() - removed_entries);
+ ElementsRemoved(removed_entries);
}
=======================================
--- /branches/1.3/src/objects.h Wed Jan 6 23:49:31 2010
+++ /branches/1.3/src/objects.h Thu Jan 7 00:01:27 2010
@@ -2131,6 +2131,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() {
@@ -2143,8 +2148,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);
@@ -2171,12 +2182,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.
@@ -2200,6 +2212,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) {
=======================================
--- /branches/1.3/src/runtime.cc Tue Nov 17 13:43:00 2009
+++ /branches/1.3/src/runtime.cc Thu Jan 7 00:01:27 2010
@@ -5254,6 +5254,8 @@
void increase_index_offset(uint32_t delta) {
index_offset_ += delta;
}
+
+ Handle<FixedArray> storage() { return storage_; }
private:
Handle<FixedArray> storage_;
@@ -5564,7 +5566,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;
}
=======================================
--- /branches/1.3/src/version.cc Wed Jan 6 23:49:31 2010
+++ /branches/1.3/src/version.cc Thu Jan 7 00:01:27 2010
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 1
#define MINOR_VERSION 3
#define BUILD_NUMBER 18
-#define PATCH_LEVEL 18
+#define PATCH_LEVEL 19
#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
