diff options
author | Tor Egge <Tor.Egge@broadpark.no> | 2021-03-18 16:43:47 +0100 |
---|---|---|
committer | Tor Egge <Tor.Egge@broadpark.no> | 2021-03-18 16:43:47 +0100 |
commit | a2d99ca3b74ea6568624d7ce252694016bcea33d (patch) | |
tree | 1e9b1b98270dd5bb9e0b905a89bfe611365a9124 /vespalib | |
parent | de87b1f0eeffe3963c2f22cc4d5e55166e519380 (diff) |
Update unordered dictionary.
Diffstat (limited to 'vespalib')
8 files changed, 81 insertions, 14 deletions
diff --git a/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp b/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp index 2f5e5b9295d..0fad98af10b 100644 --- a/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp +++ b/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp @@ -108,7 +108,7 @@ DataStoreFixedSizeHashTest::insert(uint32_t key) { MyCompare comp(_store, key); std::function<EntryRef(void)> insert_entry([this, key]() -> EntryRef { return _allocator.allocate(key); }); - auto& result = _hash_map->add(comp, insert_entry); + auto& result = _hash_map->add(comp, EntryRef(), insert_entry); auto ref = result.first.load_relaxed(); auto &wrapped_entry = _allocator.get_wrapped(ref); EXPECT_EQ(key, wrapped_entry.value()); diff --git a/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp b/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp index e89a0aab038..4dbb35d8516 100644 --- a/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp +++ b/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp @@ -102,8 +102,8 @@ void DataStoreSimpleHashTest::insert(uint32_t key) { MyCompare comp(_store, key); -std::function<EntryRef(void)> insert_entry([this, key]() -> EntryRef { return _allocator.allocate(key); }); - auto& result = _hash_map.add(comp, insert_entry); + std::function<EntryRef(void)> insert_entry([this, key]() -> EntryRef { return _allocator.allocate(key); }); + auto& result = _hash_map.add(comp, EntryRef(), insert_entry); auto ref = result.first.load_relaxed(); auto &wrapped_entry = _allocator.get_wrapped(ref); EXPECT_EQ(key, wrapped_entry.value()); diff --git a/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h b/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h index 3ec2d6b163e..f4724e563ca 100644 --- a/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h +++ b/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h @@ -34,6 +34,9 @@ public: void store_release(EntryRef ref) noexcept { _ref.store(ref.ref(), std::memory_order_release); } + void store_relaxed(EntryRef ref) noexcept { + _ref.store(ref.ref(), std::memory_order_relaxed); + } EntryRef load_acquire() const noexcept { return EntryRef(_ref.load(std::memory_order_acquire)); } diff --git a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp index 14dbc841691..be67e0b1863 100644 --- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp +++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp @@ -62,15 +62,15 @@ FixedSizeHashMap::force_add(const EntryComparator& comp, const KvType& kv) } FixedSizeHashMap::KvType& -FixedSizeHashMap::add(const EntryComparator& comp, std::function<EntryRef(void)>& insert_entry) +FixedSizeHashMap::add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)>& insert_entry) { - size_t hash_idx = comp.hash(EntryRef()) / _num_stripes; + size_t hash_idx = comp.hash(key_ref) / _num_stripes; hash_idx %= _modulo; auto& chain_head = _chain_heads[hash_idx]; uint32_t node_idx = chain_head.load_relaxed(); while (node_idx != no_node_idx) { auto& node = _nodes[node_idx]; - if (comp.equal(EntryRef(), node.get_kv().first.load_relaxed())) { + if (comp.equal(key_ref, node.get_kv().first.load_relaxed())) { return node.get_kv(); } node_idx = node.get_next_node_idx().load(std::memory_order_relaxed); @@ -153,8 +153,8 @@ FixedSizeHashMap::remove(const EntryComparator& comp, EntryRef key_ref) return nullptr; } -const FixedSizeHashMap::KvType* -FixedSizeHashMap::find(const EntryComparator& comp, EntryRef key_ref) const +FixedSizeHashMap::KvType* +FixedSizeHashMap::find(const EntryComparator& comp, EntryRef key_ref) { size_t hash_idx = comp.hash(key_ref) / _num_stripes; hash_idx %= _modulo; diff --git a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h index 326c3cef765..72373f909df 100644 --- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h +++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h @@ -96,9 +96,9 @@ public: FixedSizeHashMap(uint32_t module, uint32_t capacity, uint32_t num_stripes, const FixedSizeHashMap &orig, const EntryComparator& comp); ~FixedSizeHashMap(); - KvType& add(const EntryComparator& comp, std::function<EntryRef(void)>& insert_entry); + KvType& add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)>& insert_entry); KvType* remove(const EntryComparator& comp, EntryRef key_ref); - const KvType* find(const EntryComparator& comp, EntryRef key_ref) const; + KvType* find(const EntryComparator& comp, EntryRef key_ref); void transfer_hold_lists(generation_t generation) { if (!_hold_1_list.empty()) { diff --git a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp index e397eca579a..6995acc5bb4 100644 --- a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp +++ b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp @@ -31,6 +31,7 @@ SimpleHashMap::SimpleHashMap(std::unique_ptr<const EntryComparator> comp) SimpleHashMap::~SimpleHashMap() { + _gen_holder.clearHoldLists(); for (size_t i = 0; i < num_stripes; ++i) { auto map = _maps[i].load(std::memory_order_relaxed); delete map; @@ -66,15 +67,15 @@ SimpleHashMap::hold_stripe(std::unique_ptr<const FixedSizeHashMap> map) } SimpleHashMap::KvType& -SimpleHashMap::add(const EntryComparator& comp, std::function<EntryRef(void)>& insert_entry) +SimpleHashMap::add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)>& insert_entry) { - size_t stripe = get_stripe(comp, EntryRef()); + size_t stripe = get_stripe(comp, key_ref); auto map = _maps[stripe].load(std::memory_order_relaxed); if (map == nullptr || map->full()) { alloc_stripe(stripe); map = _maps[stripe].load(std::memory_order_relaxed); } - return map->add(comp, insert_entry); + return map->add(comp, key_ref, insert_entry); } SimpleHashMap::KvType* @@ -88,6 +89,17 @@ SimpleHashMap::remove(const EntryComparator& comp, EntryRef key_ref) return map->remove(comp, key_ref); } +SimpleHashMap::KvType* +SimpleHashMap::find(const EntryComparator& comp, EntryRef key_ref) +{ + size_t stripe = get_stripe(comp, key_ref); + auto map = _maps[stripe].load(std::memory_order_relaxed); + if (map == nullptr) { + return nullptr; + } + return map->find(comp, key_ref); +} + const SimpleHashMap::KvType* SimpleHashMap::find(const EntryComparator& comp, EntryRef key_ref) const { diff --git a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h index 1acc11d50c8..78e224c65df 100644 --- a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h +++ b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h @@ -46,12 +46,14 @@ private: public: SimpleHashMap(std::unique_ptr<const EntryComparator> comp); ~SimpleHashMap(); - KvType& add(const EntryComparator& comp, std::function<EntryRef(void)> &insert_entry); + KvType& add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)> &insert_entry); KvType* remove(const EntryComparator& comp, EntryRef key_ref); + KvType* find(const EntryComparator& comp, EntryRef key_ref); const KvType* find(const EntryComparator& comp, EntryRef key_ref) const; void transfer_hold_lists(generation_t generation); void trim_hold_lists(generation_t first_used); size_t size() const noexcept; + const EntryComparator &get_default_comparator() const noexcept { return *_comp; } }; } diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp index 713438f8419..2483ae9b4b2 100644 --- a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp +++ b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp @@ -80,6 +80,9 @@ void UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::transfer_hold_lists(generation_t generation) { _dict.getAllocator().transferHoldLists(generation); + if constexpr (has_unordered_dictionary) { + this->_unordered_dict.transfer_hold_lists(generation); + } } template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT> @@ -87,6 +90,9 @@ void UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::trim_hold_lists(generation_t firstUsed) { _dict.getAllocator().trimHoldLists(firstUsed); + if constexpr (has_unordered_dictionary) { + this->_unordered_dict.trim_hold_lists(firstUsed); + } } template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT> @@ -96,11 +102,20 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::add(const Ent { auto itr = _dict.lowerBound(EntryRef(), comp); if (itr.valid() && !comp.less(EntryRef(), itr.getKey())) { + if constexpr (has_unordered_dictionary) { + auto* result = this->_unordered_dict.find(comp, EntryRef()); + assert(result != nullptr && result->first.load_relaxed() == itr.getKey()); + } return UniqueStoreAddResult(itr.getKey(), false); } else { EntryRef newRef = insertEntry(); _dict.insert(itr, newRef, DataType()); + if constexpr (has_unordered_dictionary) { + std::function<EntryRef(void)> insert_unordered_entry([newRef]() -> EntryRef { return newRef; }); + auto& add_result = this->_unordered_dict.add(comp, newRef, insert_unordered_entry); + assert(add_result.first.load_relaxed() == newRef); + } return UniqueStoreAddResult(newRef, true); } } @@ -111,8 +126,16 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::find(const En { auto itr = _dict.lowerBound(EntryRef(), comp); if (itr.valid() && !comp.less(EntryRef(), itr.getKey())) { + if constexpr (has_unordered_dictionary) { + auto* result = this->_unordered_dict.find(comp, EntryRef()); + assert(result != nullptr && result->first.load_relaxed() == itr.getKey()); + } return itr.getKey(); } else { + if constexpr (has_unordered_dictionary) { + auto* result = this->_unordered_dict.find(comp, EntryRef()); + assert(result == nullptr); + } return EntryRef(); } } @@ -125,6 +148,10 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::remove(const auto itr = _dict.lowerBound(ref, comp); assert(itr.valid() && itr.getKey() == ref); _dict.remove(itr); + if constexpr (has_unordered_dictionary) { + auto *result = this->_unordered_dict.remove(comp, ref); + assert(result != nullptr && result->first.load_relaxed() == ref); + } } template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT> @@ -138,6 +165,11 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::move_entries( if (newRef != oldRef) { _dict.thaw(itr); itr.writeKey(newRef); + if constexpr (has_unordered_dictionary) { + auto result = this->_unordered_dict.find(this->_unordered_dict.get_default_comparator(), oldRef); + assert(result != nullptr && result->first.load_relaxed() == oldRef); + result->first.store_release(newRef); + } } ++itr; } @@ -185,6 +217,13 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::build(vespali builder.insert(ref, DataType()); } _dict.assign(builder); + if constexpr (has_unordered_dictionary) { + for (const auto& ref : refs) { + std::function<EntryRef(void)> insert_unordered_entry([ref]() -> EntryRef { return ref; }); + auto& add_result = this->_unordered_dict.add(this->_unordered_dict.get_default_comparator(), ref, insert_unordered_entry); + assert(add_result.first.load_relaxed() == ref); + } + } } template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT> @@ -202,6 +241,17 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::build_with_pa } } _dict.assign(builder); + if constexpr (has_unordered_dictionary) { + for (size_t i = 0; i < refs.size(); ++i) { + EntryRef ref = refs[i]; + std::function<EntryRef(void)> insert_unordered_entry([ref]() -> EntryRef { return ref; }); + auto& add_result = this->_unordered_dict.add(this->_unordered_dict.get_default_comparator(), ref, insert_unordered_entry); + assert(add_result.first.load_relaxed() == refs[i]); + if constexpr (std::is_same_v<DataType, uint32_t>) { + add_result.second.store_relaxed(EntryRef(payloads[i])); + } + } + } } template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT> |