diff options
12 files changed, 108 insertions, 15 deletions
diff --git a/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.cpp b/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.cpp index 34e913a4c07..18e34c89ad0 100644 --- a/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.cpp +++ b/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.cpp @@ -89,6 +89,10 @@ EnumStoreDictionary<DictionaryT, UnorderedDictionaryT>::remove(const EntryCompar assert(EntryRef(itr.getData()) == EntryRef()); } this->_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 UnorderedDictionaryT> @@ -217,6 +221,21 @@ EnumStoreDictionary<DictionaryT, UnorderedDictionaryT>::update_posting_list(Inde itr.writeData(new_posting_idx.ref()); } +template <typename DictionaryT, typename UnorderedDictionaryT> +void +EnumStoreDictionary<DictionaryT, UnorderedDictionaryT>::sync_unordered_after_load() +{ + if constexpr (has_unordered_dictionary) { + for (auto itr = this->_dict.begin(); itr.valid(); ++itr) { + EntryRef ref(itr.getKey()); + 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); + add_result.second.store_relaxed(EntryRef(itr.getData())); + } + } +} + template <> EnumPostingTree & EnumStoreDictionary<EnumTree>::get_posting_dictionary() @@ -256,6 +275,7 @@ EnumStoreFoldedDictionary::~EnumStoreFoldedDictionary() = default; UniqueStoreAddResult EnumStoreFoldedDictionary::add(const EntryComparator& comp, std::function<EntryRef(void)> insertEntry) { + static_assert(!has_unordered_dictionary, "Folded Dictionary does not support unordered"); auto it = _dict.lowerBound(EntryRef(), comp); if (it.valid() && !comp.less(EntryRef(), it.getKey())) { // Entry already exists @@ -279,6 +299,7 @@ EnumStoreFoldedDictionary::add(const EntryComparator& comp, std::function<EntryR void EnumStoreFoldedDictionary::remove(const EntryComparator& comp, EntryRef ref) { + static_assert(!has_unordered_dictionary, "Folded Dictionary does not support unordered"); assert(ref.valid()); auto it = _dict.lowerBound(ref, comp); assert(it.valid() && it.getKey() == ref); diff --git a/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.h b/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.h index 63ccb2efac7..2c2c39451c0 100644 --- a/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.h +++ b/searchlib/src/vespa/searchlib/attribute/enum_store_dictionary.h @@ -24,7 +24,9 @@ private: using IndexVector = IEnumStoreDictionary::IndexVector; using ParentUniqueStoreDictionary = vespalib::datastore::UniqueStoreDictionary<DictionaryT, IEnumStoreDictionary, UnorderedDictionaryT>; using generation_t = IEnumStoreDictionary::generation_t; - +protected: + using ParentUniqueStoreDictionary::has_unordered_dictionary; +private: IEnumStore& _enumStore; void remove_unused_values(const IndexSet& unused, @@ -56,6 +58,7 @@ public: Index remap_index(Index idx) override; void clear_all_posting_lists(std::function<void(EntryRef)> clearer) override; void update_posting_list(Index idx, const vespalib::datastore::EntryComparator& cmp, std::function<EntryRef(EntryRef)> updater) override; + void sync_unordered_after_load() override; EnumPostingTree& get_posting_dictionary() override; const EnumPostingTree& get_posting_dictionary() const override; }; diff --git a/searchlib/src/vespa/searchlib/attribute/i_enum_store_dictionary.h b/searchlib/src/vespa/searchlib/attribute/i_enum_store_dictionary.h index 968d1fa8747..309f037ac84 100644 --- a/searchlib/src/vespa/searchlib/attribute/i_enum_store_dictionary.h +++ b/searchlib/src/vespa/searchlib/attribute/i_enum_store_dictionary.h @@ -53,6 +53,7 @@ public: virtual Index remap_index(Index idx) = 0; virtual void clear_all_posting_lists(std::function<void(EntryRef)> clearer) = 0; virtual void update_posting_list(Index idx, const vespalib::datastore::EntryComparator& cmp, std::function<EntryRef(EntryRef)> updater) = 0; + virtual void sync_unordered_after_load() = 0; virtual EnumPostingTree& get_posting_dictionary() = 0; virtual const EnumPostingTree& get_posting_dictionary() const = 0; }; diff --git a/searchlib/src/vespa/searchlib/attribute/postinglistattribute.cpp b/searchlib/src/vespa/searchlib/attribute/postinglistattribute.cpp index d3223901a71..c76571b151d 100644 --- a/searchlib/src/vespa/searchlib/attribute/postinglistattribute.cpp +++ b/searchlib/src/vespa/searchlib/attribute/postinglistattribute.cpp @@ -102,6 +102,7 @@ PostingListAttributeBase<P>::handle_load_posting_lists_and_update_enum_store(enu &postings._removals[0] + postings._removals.size()); posting_itr.writeData(newIndex.ref()); loader.free_unused_values(); + _dictionary.sync_unordered_after_load(); } template <typename P> 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> |