Revision: 16678
Author: [email protected]
Date: Thu Sep 12 11:03:27 2013 UTC
Log: Implement in-place rehashing of HashTable.
The algorithm puts elements into correct positions in multiple iterations.
On the first iteration it tries to put elements at entries specified by
their first hash probe. On the second iteration -- by the second
hash probe, and so on. Overall it does O(k*n) memory accesses, where
k is the maximum number of probes required for an element and n is the
capacity of the hash table. The expectation is that k will be small.
[email protected]
Review URL: https://chromiumcodereview.appspot.com/23658031
http://code.google.com/p/v8/source/detail?r=16678
Modified:
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/test/cctest/test-dictionary.cc
=======================================
--- /branches/bleeding_edge/src/objects.cc Wed Sep 11 13:42:57 2013 UTC
+++ /branches/bleeding_edge/src/objects.cc Thu Sep 12 11:03:27 2013 UTC
@@ -13803,6 +13803,74 @@
new_table->SetNumberOfDeletedElements(0);
return new_table;
}
+
+
+template<typename Shape, typename Key>
+uint32_t HashTable<Shape, Key>::EntryForProbe(Key key,
+ Object* k,
+ int probe,
+ uint32_t expected) {
+ uint32_t hash = HashTable<Shape, Key>::HashForObject(key, k);
+ uint32_t capacity = Capacity();
+ uint32_t entry = FirstProbe(hash, capacity);
+ for (int i = 1; i < probe; i++) {
+ if (entry == expected) return expected;
+ entry = NextProbe(entry, i, capacity);
+ }
+ return entry;
+}
+
+
+template<typename Shape, typename Key>
+void HashTable<Shape, Key>::Swap(uint32_t entry1,
+ uint32_t entry2,
+ WriteBarrierMode mode) {
+ int index1 = EntryToIndex(entry1);
+ int index2 = EntryToIndex(entry2);
+ Object* temp[Shape::kEntrySize];
+ for (int j = 0; j < Shape::kEntrySize; j++) {
+ temp[j] = get(index1 + j);
+ }
+ for (int j = 0; j < Shape::kEntrySize; j++) {
+ set(index1 + j, get(index2 + j), mode);
+ }
+ for (int j = 0; j < Shape::kEntrySize; j++) {
+ set(index2 + j, temp[j], mode);
+ }
+}
+
+
+template<typename Shape, typename Key>
+void HashTable<Shape, Key>::Rehash(Key key) {
+ DisallowHeapAllocation no_gc;
+ WriteBarrierMode mode = GetWriteBarrierMode(no_gc);
+ uint32_t capacity = Capacity();
+ bool done = false;
+ for (int probe = 1; !done; probe++) {
+ // All elements at entries given by one of the first _probe_ probes
+ // are placed correctly. Other elements might need to be moved.
+ done = true;
+ for (uint32_t current = 0; current < capacity; current++) {
+ Object* current_key = get(EntryToIndex(current));
+ if (IsKey(current_key)) {
+ uint32_t target = EntryForProbe(key, current_key, probe, current);
+ if (current == target) continue;
+ Object* target_key = get(EntryToIndex(target));
+ if (!IsKey(target_key) ||
+ EntryForProbe(key, target_key, probe, target) != target) {
+ // Put the current element into the correct position.
+ Swap(current, target, mode);
+ // The other element will be processed on the next iteration.
+ current--;
+ } else {
+ // The place for the current element is occupied. Leave the
element
+ // for the next probe.
+ done = false;
+ }
+ }
+ }
+ }
+}
template<typename Shape, typename Key>
=======================================
--- /branches/bleeding_edge/src/objects.h Wed Sep 11 15:16:56 2013 UTC
+++ /branches/bleeding_edge/src/objects.h Thu Sep 12 11:03:27 2013 UTC
@@ -3473,6 +3473,9 @@
inline int FindEntry(Key key);
int FindEntry(Isolate* isolate, Key key);
+ // Rehashes the table in-place.
+ void Rehash(Key key);
+
protected:
// Find the entry at which to insert element with the given key that
// has the given hash value.
@@ -3518,6 +3521,13 @@
uint32_t last, uint32_t number, uint32_t size) {
return (last + number) & (size - 1);
}
+
+ // Returns _expected_ if one of entries given by the first _probe_
probes is
+ // equal to _expected_. Otherwise, returns the entry given by the probe
+ // number _probe_.
+ uint32_t EntryForProbe(Key key, Object* k, int probe, uint32_t expected);
+
+ void Swap(uint32_t entry1, uint32_t entry2, WriteBarrierMode mode);
// Rehashes this hash-table into the new table.
MUST_USE_RESULT MaybeObject* Rehash(HashTable* new_table, Key key);
=======================================
--- /branches/bleeding_edge/test/cctest/test-dictionary.cc Fri Aug 30
13:42:16 2013 UTC
+++ /branches/bleeding_edge/test/cctest/test-dictionary.cc Thu Sep 12
11:03:27 2013 UTC
@@ -99,6 +99,57 @@
CHECK_EQ(key->GetIdentityHash(OMIT_CREATION), HEAP->undefined_value());
}
}
+
+
+class ObjectHashTableTest: public ObjectHashTable {
+ public:
+ void insert(int entry, int key, int value) {
+ set(EntryToIndex(entry), Smi::FromInt(key));
+ set(EntryToIndex(entry) + 1, Smi::FromInt(value));
+ }
+
+ int lookup(int key) {
+ return Smi::cast(Lookup(Smi::FromInt(key)))->value();
+ }
+
+ int capacity() {
+ return Capacity();
+ }
+};
+
+
+TEST(HashTableRehash) {
+ LocalContext context;
+ Isolate* isolate = Isolate::Current();
+ Factory* factory = isolate->factory();
+ v8::HandleScope scope(context->GetIsolate());
+ // Test almost filled table.
+ {
+ Handle<ObjectHashTable> table = factory->NewObjectHashTable(100);
+ ObjectHashTableTest* t =
reinterpret_cast<ObjectHashTableTest*>(*table);
+ int capacity = t->capacity();
+ for (int i = 0; i < capacity - 1; i++) {
+ t->insert(i, i * i, i);
+ }
+ t->Rehash(Smi::FromInt(0));
+ for (int i = 0; i < capacity - 1; i++) {
+ CHECK_EQ(i, t->lookup(i * i));
+ }
+ }
+ // Test half-filled table.
+ {
+ Handle<ObjectHashTable> table = factory->NewObjectHashTable(100);
+ ObjectHashTableTest* t =
reinterpret_cast<ObjectHashTableTest*>(*table);
+ int capacity = t->capacity();
+ for (int i = 0; i < capacity / 2; i++) {
+ t->insert(i, i * i, i);
+ }
+ t->Rehash(Smi::FromInt(0));
+ for (int i = 0; i < capacity / 2; i++) {
+ CHECK_EQ(i, t->lookup(i * i));
+ }
+ }
+}
#ifdef DEBUG
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
