add generic ReusableSet

10 files changed, 284 insertions, 0 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index 3530fb816df..98d50bcefba 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -131,6 +131,7 @@ vespa_define_module(
     src/tests/util/generationhandler_stress
     src/tests/util/md5
     src/tests/util/rcuvector
+    src/tests/util/reusable_set
     src/tests/valgrind
     src/tests/visit_ranges
     src/tests/websocket
diff --git a/vespalib/src/tests/util/reusable_set/CMakeLists.txt b/vespalib/src/tests/util/reusable_set/CMakeLists.txt
new file mode 100644
index 00000000000..9c46b5ba61e
--- /dev/null
+++ b/vespalib/src/tests/util/reusable_set/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_reusable_set_test_app TEST
+    SOURCES
+    reusable_set_test.cpp
+    DEPENDS
+    vespalib
+    gtest
+)
+vespa_add_test(NAME vespalib_reusable_set_test_app COMMAND vespalib_reusable_set_test_app)
diff --git a/vespalib/src/tests/util/reusable_set/reusable_set_test.cpp b/vespalib/src/tests/util/reusable_set/reusable_set_test.cpp
new file mode 100644
index 00000000000..f46cbb6c2f3
--- /dev/null
+++ b/vespalib/src/tests/util/reusable_set/reusable_set_test.cpp
@@ -0,0 +1,106 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/reusable_set_pool.h>
+#include <vespa/vespalib/gtest/gtest.h>
+
+using namespace vespalib;
+
+using Mark = ReusableSet::Mark;
+
+void verify_set(const ReusableSet &set, size_t sz, Mark val, size_t marked) {
+    EXPECT_EQ(sz, set.sz);
+    EXPECT_EQ(val, set.curval);
+    size_t count = 0;
+    for (size_t i = 0; i < set.sz; ++i) {
+        if (set.isMarked(i)) ++count;
+    }
+    EXPECT_EQ(marked, count);
+}
+
+void verify_handle(const ReusableSetHandle &set, size_t sz, Mark val, size_t marked) {
+    EXPECT_EQ(sz, set.capacity());
+    EXPECT_EQ(val, set.generation());
+    size_t count = 0;
+    for (size_t i = 0; i < set.capacity(); ++i) {
+        if (set.isMarked(i)) ++count;
+    }
+    EXPECT_EQ(marked, count);
+}
+
+class Pool : public ::testing::Test {
+public:
+    ReusableSetPool pool;
+    Pool() : pool() {}
+    ~Pool() {}
+    void exercise(ReusableSetHandle &set) {
+        size_t sz = set.capacity();
+        size_t count = 0;
+        for (size_t i = 0; i < sz; ++i) {
+            if (set.isMarked(i)) ++count;
+        }
+        EXPECT_EQ(0, count);
+        for (int i = 0; i < 17; ++i) {
+            set.mark((i * 711) % sz);
+        }
+        count = 0;
+        for (size_t i = 0; i < sz; ++i) {
+            if (set.isMarked(i)) ++count;
+        }
+        EXPECT_EQ(17, count);
+        for (int i = 0; i < 17; ++i) {
+            set.mark((i * 711) % sz);
+        }
+        count = 0;
+        for (size_t i = 0; i < sz; ++i) {
+            if (set.isMarked(i)) ++count;
+        }
+        EXPECT_EQ(17, count);
+   }
+};
+
+
+TEST(ReusableSetTest, simple_usage)
+{
+    ReusableSet visited(7);
+    verify_set(visited, 7, 1, 0);
+    visited.mark(1);
+    visited.mark(2);
+    visited.mark(4);
+    verify_set(visited, 7, 1, 3);
+    visited.mark(4);
+    visited.mark(1);
+    visited.mark(2);
+    verify_set(visited, 7, 1, 3);
+    visited.clear();
+    verify_set(visited, 7, 2, 0);
+    visited.clear();
+    verify_set(visited, 7, 3, 0);
+}
+
+TEST_F(Pool, reuse_works)
+{
+    for (int i = 0; i < 65535; ++i) {
+        auto handle = pool.get(7);
+        EXPECT_EQ(i, pool.reuse_count());
+        EXPECT_EQ(1, pool.create_count());
+        verify_handle(handle, 250, i+1, 0);
+        exercise(handle);
+    }
+    for (int i = 0; i < 5; ++i) {
+        auto handle = pool.get(7);
+        EXPECT_EQ(65535+i, pool.reuse_count());
+        EXPECT_EQ(1, pool.create_count());
+        verify_handle(handle, 250, i+1, 0);
+        exercise(handle);
+    }
+    auto handle3 = pool.get(300);
+    EXPECT_EQ(2, pool.create_count());
+    verify_handle(handle3, 600, 1, 0);
+    exercise(handle3);
+    auto handle7 = pool.get(700);
+    EXPECT_EQ(3, pool.create_count());
+    verify_handle(handle7, 1400, 1, 0);
+    exercise(handle7);
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/util/CMakeLists.txt b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
index da81556bb61..e3397b54740 100644
--- a/vespalib/src/vespa/vespalib/util/CMakeLists.txt
+++ b/vespalib/src/vespa/vespalib/util/CMakeLists.txt
@@ -36,6 +36,9 @@ vespa_add_library(vespalib_vespalib_util OBJECT
     random.cpp
     rcuvector.cpp
     regexp.cpp
+    reusable_set.cpp
+    reusable_set_handle.cpp
+    reusable_set_pool.cpp
     runnable.cpp
     runnable_pair.cpp
     rwlock.cpp
diff --git a/vespalib/src/vespa/vespalib/util/reusable_set.cpp b/vespalib/src/vespa/vespalib/util/reusable_set.cpp
new file mode 100644
index 00000000000..395fbf505ba
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/reusable_set.cpp
@@ -0,0 +1,3 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "reusable_set.h"
diff --git a/vespalib/src/vespa/vespalib/util/reusable_set.h b/vespalib/src/vespa/vespalib/util/reusable_set.h
new file mode 100644
index 00000000000..5263b32d51f
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/reusable_set.h
@@ -0,0 +1,47 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <vector>
+#include <memory>
+#include <cstring>
+
+namespace vespalib {
+
+struct ReusableSet
+{
+    using Mark = unsigned short;
+
+    Mark *bits;
+    Mark curval;
+    size_t sz;
+
+    explicit ReusableSet(size_t size)
+      : bits((Mark *)malloc(size * sizeof(Mark))),
+        curval(-1),
+        sz(size)
+    {
+        clear();
+    }
+
+    ~ReusableSet() {
+        free(bits);
+    }
+
+    void clear() {
+        if (++curval == 0) {
+            memset(bits, 0, sz * sizeof(Mark));
+            ++curval;
+        }
+    }
+
+    void mark(size_t id) {
+        bits[id] = curval;
+    }
+
+    bool isMarked(size_t id) const {
+        return (bits[id] == curval);
+    }
+};
+
+} // namespace
diff --git a/vespalib/src/vespa/vespalib/util/reusable_set_handle.cpp b/vespalib/src/vespa/vespalib/util/reusable_set_handle.cpp
new file mode 100644
index 00000000000..e69fc1b8abd
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/reusable_set_handle.cpp
@@ -0,0 +1,13 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "reusable_set_handle.h"
+#include "reusable_set_pool.h"
+
+namespace vespalib {
+
+ReusableSetHandle::~ReusableSetHandle()
+{
+    _pool.reuse(std::move(_owned));
+}
+
+} // namespace
diff --git a/vespalib/src/vespa/vespalib/util/reusable_set_handle.h b/vespalib/src/vespa/vespalib/util/reusable_set_handle.h
new file mode 100644
index 00000000000..7855d4febbc
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/reusable_set_handle.h
@@ -0,0 +1,45 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "reusable_set.h"
+
+namespace vespalib {
+
+class ReusableSetPool;
+
+class ReusableSetHandle
+{
+private:
+    using Mark = ReusableSet::Mark;
+    using RSUP = std::unique_ptr<ReusableSet>;
+
+    Mark *_bits;
+    Mark _curval;
+    RSUP _owned;
+    ReusableSetPool &_pool;
+
+public:
+    ReusableSetHandle(RSUP backing, ReusableSetPool& owner)
+      : _bits(backing->bits),
+        _curval(backing->curval),
+        _owned(std::move(backing)),
+        _pool(owner)
+    {}
+
+    ~ReusableSetHandle();
+
+    void mark(uint32_t id) {
+        _bits[id] = _curval;
+    }
+
+    bool isMarked(uint32_t id) const {
+        return (_bits[id] == _curval);
+    }
+
+    // for unit tests and statistics
+    size_t capacity() const { return _owned->sz; }
+    Mark generation() const { return _curval; }
+};
+
+} // namespace
diff --git a/vespalib/src/vespa/vespalib/util/reusable_set_pool.cpp b/vespalib/src/vespa/vespalib/util/reusable_set_pool.cpp
new file mode 100644
index 00000000000..ed4c8a4af46
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/reusable_set_pool.cpp
@@ -0,0 +1,3 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "reusable_set_pool.h"
diff --git a/vespalib/src/vespa/vespalib/util/reusable_set_pool.h b/vespalib/src/vespa/vespalib/util/reusable_set_pool.h
new file mode 100644
index 00000000000..3a4a1caa4dd
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/reusable_set_pool.h
@@ -0,0 +1,54 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "reusable_set.h"
+#include "reusable_set_handle.h"
+
+#include <mutex>
+
+namespace vespalib {
+
+class ReusableSetPool
+{
+    using RSUP = std::unique_ptr<ReusableSet>;
+    using Guard = std::lock_guard<std::mutex>;
+    std::vector<RSUP> _lru_stack;
+    std::mutex _lock;
+    size_t _reuse_count;
+    size_t _create_count;
+    
+
+    ReusableSetPool(const ReusableSetPool &) = delete;
+    ReusableSetPool& operator= (const ReusableSetPool &) = delete;
+
+public:
+    ReusableSetPool() : _lru_stack(), _lock(), _reuse_count(0), _create_count(0) {}
+
+    ReusableSetHandle get(size_t size) {
+        Guard guard(_lock);
+        while (! _lru_stack.empty()) {
+            RSUP r = std::move(_lru_stack.back());
+            _lru_stack.pop_back();
+            if (r->sz >= size) {
+                r->clear();
+		++_reuse_count;
+                return ReusableSetHandle(std::move(r), *this);
+            }
+        }
+        RSUP r = std::make_unique<ReusableSet>(std::max((size_t)250, size*2));
+	++_create_count;
+        return ReusableSetHandle(std::move(r), *this);
+    }
+
+    void reuse(RSUP used) {
+        Guard guard(_lock);
+        _lru_stack.push_back(std::move(used));
+    }
+
+    // for unit testing and statistics
+    size_t reuse_count() const { return _reuse_count; }
+    size_t create_count() const { return _create_count; }
+};
+
+} // namespace