Merge pull request #24419 from vespa-engine/geirst/hash-map-hold-list

Use the generic generation hold list for node indexes.

2 files changed, 35 insertions, 48 deletions

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 5338ce0c6b2..47c64722785 100644
--- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp
+++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp
@@ -5,10 +5,15 @@
 #include "entry_ref_filter.h"
 #include "i_compactable.h"
 #include <vespa/vespalib/util/array.hpp>
+#include <vespa/vespalib/util/generation_hold_list.hpp>
 #include <vespa/vespalib/util/memoryusage.h>
 #include <cassert>
 #include <stdexcept>
 
+namespace vespalib {
+template class GenerationHoldList<uint32_t, false, true>;
+}
+
 namespace vespalib::datastore {
 
 FixedSizeHashMap::Node::Node(Node&&)
@@ -30,8 +35,7 @@ FixedSizeHashMap::FixedSizeHashMap(uint32_t modulo, uint32_t capacity, uint32_t
       _free_head(no_node_idx),
       _free_count(0u),
       _hold_count(0u),
-      _hold_1_list(),
-      _hold_2_list(),
+      _hold_list(),
       _num_shards(num_shards)
 {
     _nodes.reserve(capacity);
@@ -49,7 +53,10 @@ FixedSizeHashMap::FixedSizeHashMap(uint32_t modulo, uint32_t capacity, uint32_t
     }
 }
 
-FixedSizeHashMap::~FixedSizeHashMap() = default;
+FixedSizeHashMap::~FixedSizeHashMap()
+{
+    _hold_list.reclaim_all();
+}
 
 void
 FixedSizeHashMap::force_add(const EntryComparator& comp, const KvType& kv)
@@ -96,36 +103,6 @@ FixedSizeHashMap::add(const ShardedHashComparator & comp, std::function<EntryRef
     return _nodes[node_idx].get_kv();
 }
 
-void
-FixedSizeHashMap::assign_generation_slow(generation_t current_gen)
-{
-    auto &hold_2_list = _hold_2_list;
-    for (uint32_t node_idx : _hold_1_list) {
-        hold_2_list.push_back(std::make_pair(current_gen, node_idx));
-    }
-    _hold_1_list.clear();
-}
-
-
-void
-FixedSizeHashMap::reclaim_memory_slow(generation_t oldest_used_gen)
-{
-    while (!_hold_2_list.empty()) {
-        auto& first = _hold_2_list.front();
-        if (static_cast<sgeneration_t>(first.first - oldest_used_gen) >= 0) {
-            break;
-        }
-        uint32_t node_idx = first.second;
-        auto& node = _nodes[node_idx];
-        node.get_next_node_idx().store(_free_head, std::memory_order_relaxed);
-        _free_head = node_idx;
-        ++_free_count;
-        --_hold_count;
-        node.on_free();
-        _hold_2_list.erase(_hold_2_list.begin());
-    }
-}
-
 FixedSizeHashMap::KvType*
 FixedSizeHashMap::remove(const ShardedHashComparator & comp)
 {
@@ -144,7 +121,7 @@ FixedSizeHashMap::remove(const ShardedHashComparator & comp)
             }
             --_count;
             ++_hold_count;
-            _hold_1_list.push_back(node_idx);
+            _hold_list.insert(node_idx);
             return &_nodes[node_idx].get_kv();
         }
         prev_node_idx = node_idx;
@@ -153,6 +130,19 @@ FixedSizeHashMap::remove(const ShardedHashComparator & comp)
     return nullptr;
 }
 
+void
+FixedSizeHashMap::reclaim_memory(generation_t oldest_used_gen)
+{
+    _hold_list.reclaim(oldest_used_gen, [this](uint32_t node_idx) {
+        auto& node = _nodes[node_idx];
+        node.get_next_node_idx().store(_free_head, std::memory_order_relaxed);
+        _free_head = node_idx;
+        ++_free_count;
+        --_hold_count;
+        node.on_free();
+    });
+}
+
 MemoryUsage
 FixedSizeHashMap::get_memory_usage() const
 {
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 de05ec1deb0..1e13f206adb 100644
--- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h
+++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h
@@ -6,11 +6,12 @@
 #include "entry_comparator.h"
 #include <vespa/vespalib/util/array.h>
 #include <vespa/vespalib/util/arrayref.h>
+#include <vespa/vespalib/util/generation_hold_list.h>
 #include <vespa/vespalib/util/generationhandler.h>
-#include <limits>
 #include <atomic>
 #include <deque>
 #include <functional>
+#include <limits>
 
 namespace vespalib {
 class GenerationHolder;
@@ -65,7 +66,6 @@ public:
     static constexpr uint32_t no_node_idx = std::numeric_limits<uint32_t>::max();
     using KvType = std::pair<AtomicEntryRef, AtomicEntryRef>;
     using generation_t = GenerationHandler::generation_t;
-    using sgeneration_t = GenerationHandler::sgeneration_t;
 private:
     class ChainHead {
         std::atomic<uint32_t> _node_idx;
@@ -103,6 +103,8 @@ private:
         const KvType& get_kv() const noexcept { return _kv; }
     };
 
+    using NodeIdxHoldList = GenerationHoldList<uint32_t, false, true>;
+
     Array<ChainHead>  _chain_heads;
     Array<Node>       _nodes;
     uint32_t          _modulo;
@@ -110,12 +112,9 @@ private:
     uint32_t          _free_head;
     uint32_t          _free_count;
     uint32_t          _hold_count;
-    Array<uint32_t>   _hold_1_list;
-    std::deque<std::pair<generation_t, uint32_t>> _hold_2_list;
+    NodeIdxHoldList   _hold_list;
     uint32_t          _num_shards;
 
-    void assign_generation_slow(generation_t current_gen);
-    void reclaim_memory_slow(generation_t oldest_used_gen);
     void force_add(const EntryComparator& comp, const KvType& kv);
 public:
     FixedSizeHashMap(uint32_t module, uint32_t capacity, uint32_t num_shards);
@@ -144,16 +143,10 @@ public:
     }
 
     void assign_generation(generation_t current_gen) {
-        if (!_hold_1_list.empty()) {
-            assign_generation_slow(current_gen);
-        }
+        _hold_list.assign_generation(current_gen);
     }
 
-    void reclaim_memory(generation_t oldest_used_gen) {
-        if (!_hold_2_list.empty() && static_cast<sgeneration_t>(_hold_2_list.front().first - oldest_used_gen) < 0) {
-            reclaim_memory_slow(oldest_used_gen);
-        }
-    }
+    void reclaim_memory(generation_t oldest_used_gen);
 
     bool full() const noexcept { return _nodes.size() == _nodes.capacity() && _free_count == 0u; }
     size_t size() const noexcept { return _count; }
@@ -182,3 +175,7 @@ public:
 };
 
 }
+
+namespace vespalib {
+extern template class GenerationHoldList<uint32_t, false, true>;
+}