From 31f4b914d502f01f5a7887b03158d80e2ab9e330 Mon Sep 17 00:00:00 2001 From: Arne Juul Date: Thu, 5 Mar 2020 10:11:50 +0000 Subject: add generic ReusableSet --- vespalib/CMakeLists.txt | 1 + .../src/tests/util/reusable_set/CMakeLists.txt | 9 ++ .../tests/util/reusable_set/reusable_set_test.cpp | 106 +++++++++++++++++++++ vespalib/src/vespa/vespalib/util/CMakeLists.txt | 3 + vespalib/src/vespa/vespalib/util/reusable_set.cpp | 3 + vespalib/src/vespa/vespalib/util/reusable_set.h | 47 +++++++++ .../vespa/vespalib/util/reusable_set_handle.cpp | 13 +++ .../src/vespa/vespalib/util/reusable_set_handle.h | 45 +++++++++ .../src/vespa/vespalib/util/reusable_set_pool.cpp | 3 + .../src/vespa/vespalib/util/reusable_set_pool.h | 54 +++++++++++ 10 files changed, 284 insertions(+) create mode 100644 vespalib/src/tests/util/reusable_set/CMakeLists.txt create mode 100644 vespalib/src/tests/util/reusable_set/reusable_set_test.cpp create mode 100644 vespalib/src/vespa/vespalib/util/reusable_set.cpp create mode 100644 vespalib/src/vespa/vespalib/util/reusable_set.h create mode 100644 vespalib/src/vespa/vespalib/util/reusable_set_handle.cpp create mode 100644 vespalib/src/vespa/vespalib/util/reusable_set_handle.h create mode 100644 vespalib/src/vespa/vespalib/util/reusable_set_pool.cpp create mode 100644 vespalib/src/vespa/vespalib/util/reusable_set_pool.h (limited to 'vespalib') 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 +#include + +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 +#include +#include + +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; + + 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 + +namespace vespalib { + +class ReusableSetPool +{ + using RSUP = std::unique_ptr; + using Guard = std::lock_guard; + std::vector _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(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 -- cgit v1.2.3