From 0e8e0030775518b69eb8522823ea3754e6bddc69 Mon Sep 17 00:00:00 2001 From: "ulan@chromium.org" Date: Thu, 12 Sep 2013 11:03:27 +0000 Subject: [PATCH] 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. R=mstarzinger@chromium.org Review URL: https://chromiumcodereview.appspot.com/23658031 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@16678 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/objects.cc | 68 ++++++++++++++++++++++++++++++++++++++++++ src/objects.h | 10 +++++++ test/cctest/test-dictionary.cc | 51 +++++++++++++++++++++++++++++++ 3 files changed, 129 insertions(+) diff --git a/src/objects.cc b/src/objects.cc index 43e3f53..362b363 100644 --- a/src/objects.cc +++ b/src/objects.cc @@ -13806,6 +13806,74 @@ MaybeObject* HashTable::Rehash(HashTable* new_table, Key key) { template +uint32_t HashTable::EntryForProbe(Key key, + Object* k, + int probe, + uint32_t expected) { + uint32_t hash = HashTable::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 +void HashTable::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 +void HashTable::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 MaybeObject* HashTable::EnsureCapacity(int n, Key key) { int capacity = Capacity(); int nof = NumberOfElements() + n; diff --git a/src/objects.h b/src/objects.h index af0a891..fff2717 100644 --- a/src/objects.h +++ b/src/objects.h @@ -3473,6 +3473,9 @@ class HashTable: public FixedArray { 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. @@ -3519,6 +3522,13 @@ class HashTable: public FixedArray { 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); diff --git a/test/cctest/test-dictionary.cc b/test/cctest/test-dictionary.cc index 21c20bd..b9e8b1e 100644 --- a/test/cctest/test-dictionary.cc +++ b/test/cctest/test-dictionary.cc @@ -101,6 +101,57 @@ TEST(ObjectHashTable) { } +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 table = factory->NewObjectHashTable(100); + ObjectHashTableTest* t = reinterpret_cast(*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 table = factory->NewObjectHashTable(100); + ObjectHashTableTest* t = reinterpret_cast(*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 TEST(ObjectHashSetCausesGC) { i::FLAG_stress_compaction = false; -- 2.7.4