From a40ad05bfe98dd80cdae6192b027c38e8eaa21a1 Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Thu, 2 Dec 2021 17:26:52 +0100 Subject: Don't try to move dictionary keys that won't move. --- .../sharded_hash_map/sharded_hash_map_test.cpp | 26 +++++++++++++++++++++- vespalib/src/vespa/vespalib/datastore/entryref.h | 2 ++ .../vespalib/datastore/fixed_size_hash_map.cpp | 9 +++++--- .../vespa/vespalib/datastore/fixed_size_hash_map.h | 4 +++- .../vespalib/datastore/i_unique_store_dictionary.h | 2 +- .../vespa/vespalib/datastore/sharded_hash_map.cpp | 4 ++-- .../vespa/vespalib/datastore/sharded_hash_map.h | 5 +++-- .../src/vespa/vespalib/datastore/unique_store.hpp | 21 +++++++---------- .../vespalib/datastore/unique_store_dictionary.h | 2 +- .../vespalib/datastore/unique_store_dictionary.hpp | 18 ++++++++------- 10 files changed, 61 insertions(+), 32 deletions(-) (limited to 'vespalib') diff --git a/vespalib/src/tests/datastore/sharded_hash_map/sharded_hash_map_test.cpp b/vespalib/src/tests/datastore/sharded_hash_map/sharded_hash_map_test.cpp index 3cd3d00645c..6e984f286c1 100644 --- a/vespalib/src/tests/datastore/sharded_hash_map/sharded_hash_map_test.cpp +++ b/vespalib/src/tests/datastore/sharded_hash_map/sharded_hash_map_test.cpp @@ -1,6 +1,7 @@ // Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #include +#include #include #include @@ -17,6 +18,7 @@ LOG_SETUP("vespalib_datastore_shared_hash_test"); using vespalib::datastore::EntryRef; +using vespalib::datastore::ICompactable; using RefT = vespalib::datastore::EntryRefT<22>; using MyAllocator = vespalib::datastore::UniqueStoreAllocator; using MyDataStore = vespalib::datastore::DataStoreT; @@ -35,6 +37,27 @@ void consider_yield(uint32_t i) } } +class MyCompactable : public ICompactable +{ + MyAllocator& _allocator; + std::vector& _new_refs; +public: + MyCompactable(MyAllocator& allocator, std::vector& new_refs) + : ICompactable(), + _allocator(allocator), + _new_refs(new_refs) + { + } + ~MyCompactable() override = default; + + EntryRef move(EntryRef ref) override { + auto new_ref = _allocator.move(ref); + _allocator.hold(ref); + _new_refs.emplace_back(new_ref); + return new_ref; + } +}; + } struct DataStoreShardedHashTest : public ::testing::Test @@ -257,7 +280,8 @@ TEST_F(DataStoreShardedHashTest, move_keys_works) std::vector refs; _hash_map.foreach_key([&refs](EntryRef ref) { refs.emplace_back(ref); }); std::vector new_refs; - _hash_map.move_keys([this, &new_refs](EntryRef ref) { auto new_ref = _allocator.move(ref); _allocator.hold(ref); new_refs.emplace_back(new_ref); return new_ref; }); + MyCompactable my_compactable(_allocator, new_refs); + _hash_map.move_keys(my_compactable, std::vector(RefT::numBuffers(), true), RefT::offset_bits); std::vector verify_new_refs; _hash_map.foreach_key([&verify_new_refs](EntryRef ref) { verify_new_refs.emplace_back(ref); }); EXPECT_EQ(50u, refs.size()); diff --git a/vespalib/src/vespa/vespalib/datastore/entryref.h b/vespalib/src/vespa/vespalib/datastore/entryref.h index ddbc677fc18..7667cc3d2c1 100644 --- a/vespalib/src/vespa/vespalib/datastore/entryref.h +++ b/vespalib/src/vespa/vespalib/datastore/entryref.h @@ -18,6 +18,7 @@ public: uint32_t ref() const noexcept { return _ref; } uint32_t hash() const noexcept { return _ref; } bool valid() const noexcept { return _ref != 0u; } + uint32_t buffer_id(uint32_t offset_bits) const noexcept { return _ref >> offset_bits; } bool operator==(const EntryRef &rhs) const noexcept { return _ref == rhs._ref; } bool operator!=(const EntryRef &rhs) const noexcept { return _ref != rhs._ref; } bool operator <(const EntryRef &rhs) const noexcept { return _ref < rhs._ref; } @@ -31,6 +32,7 @@ public: template class EntryRefT : public EntryRef { public: + static constexpr uint32_t offset_bits = OffsetBits; EntryRefT() noexcept : EntryRef() {} EntryRefT(size_t offset_, uint32_t bufferId_) noexcept; EntryRefT(const EntryRef & ref_) noexcept : EntryRef(ref_.ref()) {} 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 9f56938f49c..db9fee8ea70 100644 --- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp +++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp @@ -2,6 +2,7 @@ #include "fixed_size_hash_map.h" #include "entry_comparator.h" +#include "i_compactable.h" #include #include #include @@ -181,15 +182,17 @@ FixedSizeHashMap::foreach_key(const std::function& callback) con } void -FixedSizeHashMap::move_keys(const std::function& callback) +FixedSizeHashMap::move_keys(ICompactable& compactable, const std::vector& compacting_buffers, uint32_t entry_ref_offset_bits) { for (auto& chain_head : _chain_heads) { uint32_t node_idx = chain_head.load_relaxed(); while (node_idx != no_node_idx) { auto& node = _nodes[node_idx]; EntryRef old_ref = node.get_kv().first.load_relaxed(); - EntryRef new_ref = callback(old_ref); - if (new_ref != old_ref) { + assert(old_ref.valid()); + uint32_t buffer_id = old_ref.buffer_id(entry_ref_offset_bits); + if (compacting_buffers[buffer_id]) { + EntryRef new_ref = compactable.move(old_ref); node.get_kv().first.store_release(new_ref); } node_idx = node.get_next_node_idx().load(std::memory_order_relaxed); 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 f6990646c0c..035cd84dbee 100644 --- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h +++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h @@ -18,6 +18,8 @@ class MemoryUsage; } namespace vespalib::datastore { +struct ICompactable; + class ShardedHashComparator { public: ShardedHashComparator(const EntryComparator& comp, const EntryRef key_ref, uint32_t num_shards) @@ -156,7 +158,7 @@ public: size_t size() const noexcept { return _count; } MemoryUsage get_memory_usage() const; void foreach_key(const std::function& callback) const; - void move_keys(const std::function& callback); + void move_keys(ICompactable& compactable, const std::vector& compacting_buffers, uint32_t entry_ref_offset_bits); bool normalize_values(const std::function& normalize); }; diff --git a/vespalib/src/vespa/vespalib/datastore/i_unique_store_dictionary.h b/vespalib/src/vespa/vespalib/datastore/i_unique_store_dictionary.h index 35dbe1795f6..886ec095dcd 100644 --- a/vespalib/src/vespa/vespalib/datastore/i_unique_store_dictionary.h +++ b/vespalib/src/vespa/vespalib/datastore/i_unique_store_dictionary.h @@ -28,7 +28,7 @@ public: virtual UniqueStoreAddResult add(const EntryComparator& comp, std::function insertEntry) = 0; virtual EntryRef find(const EntryComparator& comp) = 0; virtual void remove(const EntryComparator& comp, EntryRef ref) = 0; - virtual void move_entries(ICompactable& compactable) = 0; + virtual void move_keys(ICompactable& compactable, const std::vector& compacting_buffers, uint32_t entry_ref_offset_bits) = 0; virtual uint32_t get_num_uniques() const = 0; virtual vespalib::MemoryUsage get_memory_usage() const = 0; virtual void build(vespalib::ConstArrayRef, vespalib::ConstArrayRef ref_counts, std::function hold) = 0; diff --git a/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.cpp b/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.cpp index b7766d8a4e3..da4db92a309 100644 --- a/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.cpp +++ b/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.cpp @@ -171,12 +171,12 @@ ShardedHashMap::foreach_key(std::function callback) const } void -ShardedHashMap::move_keys(std::function callback) +ShardedHashMap::move_keys(ICompactable& compactable, const std::vector& compacting_buffers, uint32_t entry_ref_offset_bits) { for (size_t i = 0; i < num_shards; ++i) { auto map = _maps[i].load(std::memory_order_relaxed); if (map != nullptr) { - map->move_keys(callback); + map->move_keys(compactable, compacting_buffers, entry_ref_offset_bits); } } } diff --git a/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.h b/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.h index 0f20c6a6e30..df07f7a1990 100644 --- a/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.h +++ b/vespalib/src/vespa/vespalib/datastore/sharded_hash_map.h @@ -10,8 +10,9 @@ namespace vespalib { class MemoryUsage; } namespace vespalib::datastore { -class FixedSizeHashMap; class EntryComparator; +class FixedSizeHashMap; +struct ICompactable; /* * Hash map over keys in data store, meant to support a faster @@ -56,7 +57,7 @@ public: const EntryComparator &get_default_comparator() const noexcept { return *_comp; } MemoryUsage get_memory_usage() const; void foreach_key(std::function callback) const; - void move_keys(std::function callback); + void move_keys(ICompactable& compactable, const std::vector& compacting_buffers, uint32_t entry_ref_offset_bits); bool normalize_values(std::function normalize); bool has_held_buffers() const; void compact_worst_shard(); diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store.hpp index 85894cfa7dd..d375dbae149 100644 --- a/vespalib/src/vespa/vespalib/datastore/unique_store.hpp +++ b/vespalib/src/vespa/vespalib/datastore/unique_store.hpp @@ -113,23 +113,18 @@ private: EntryRef move(EntryRef oldRef) override { RefT iRef(oldRef); - assert(iRef.valid()); uint32_t buffer_id = iRef.bufferId(); - if (_compacting_buffer[buffer_id]) { - auto &inner_mapping = _mapping[buffer_id]; - assert(iRef.unscaled_offset() < inner_mapping.size()); - EntryRef &mappedRef = inner_mapping[iRef.unscaled_offset()]; - assert(!mappedRef.valid()); - EntryRef newRef = _store.move(oldRef); - mappedRef = newRef; - return newRef; - } else { - return oldRef; - } + auto &inner_mapping = _mapping[buffer_id]; + assert(iRef.unscaled_offset() < inner_mapping.size()); + EntryRef &mappedRef = inner_mapping[iRef.unscaled_offset()]; + assert(!mappedRef.valid()); + EntryRef newRef = _store.move(oldRef); + mappedRef = newRef; + return newRef; } void fillMapping() { - _dict.move_entries(*this); + _dict.move_keys(*this, _compacting_buffer, RefT::offset_bits); } public: diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h index fca8a98d280..3b0169b5a34 100644 --- a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h +++ b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h @@ -79,7 +79,7 @@ public: UniqueStoreAddResult add(const EntryComparator& comp, std::function insertEntry) override; EntryRef find(const EntryComparator& comp) override; void remove(const EntryComparator& comp, EntryRef ref) override; - void move_entries(ICompactable& compactable) override; + void move_keys(ICompactable& compactable, const std::vector& compacting_buffers, uint32_t entry_ref_offset_bits) override; uint32_t get_num_uniques() const override; vespalib::MemoryUsage get_memory_usage() const override; void build(vespalib::ConstArrayRef, vespalib::ConstArrayRef ref_counts, std::function hold) override; diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp index 08be861ba03..e88376be9fb 100644 --- a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp +++ b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp @@ -139,26 +139,28 @@ UniqueStoreDictionary::remove(const template void -UniqueStoreDictionary::move_entries(ICompactable &compactable) +UniqueStoreDictionary::move_keys(ICompactable &compactable, const std::vector& compacting_buffers, uint32_t entry_ref_offset_bits) { if constexpr (has_btree_dictionary) { auto itr = this->_btree_dict.begin(); while (itr.valid()) { EntryRef oldRef(itr.getKey()); - EntryRef newRef(compactable.move(oldRef)); - if (newRef != oldRef) { + assert(oldRef.valid()); + uint32_t buffer_id = oldRef.buffer_id(entry_ref_offset_bits); + if (compacting_buffers[buffer_id]) { + EntryRef newRef(compactable.move(oldRef)); this->_btree_dict.thaw(itr); itr.writeKey(newRef); if constexpr (has_hash_dictionary) { - auto result = this->_hash_dict.find(this->_hash_dict.get_default_comparator(), oldRef); - assert(result != nullptr && result->first.load_relaxed() == oldRef); - result->first.store_release(newRef); - } + auto result = this->_hash_dict.find(this->_hash_dict.get_default_comparator(), oldRef); + assert(result != nullptr && result->first.load_relaxed() == oldRef); + result->first.store_release(newRef); + } } ++itr; } } else { - this->_hash_dict.move_keys([&compactable](EntryRef old_ref) { return compactable.move(old_ref); }); + this->_hash_dict.move_keys(compactable, compacting_buffers, entry_ref_offset_bits); } } -- cgit v1.2.3