diff options
Diffstat (limited to 'vespalib')
4 files changed, 93 insertions, 42 deletions
diff --git a/vespalib/src/tests/util/reusable_set/reusable_set_test.cpp b/vespalib/src/tests/util/reusable_set/reusable_set_test.cpp index f46cbb6c2f3..bc3db27a2fd 100644 --- a/vespalib/src/tests/util/reusable_set/reusable_set_test.cpp +++ b/vespalib/src/tests/util/reusable_set/reusable_set_test.cpp @@ -8,11 +8,11 @@ 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); + EXPECT_EQ(sz, set.capacity()); + EXPECT_EQ(val, set.generation()); size_t count = 0; - for (size_t i = 0; i < set.sz; ++i) { - if (set.isMarked(i)) ++count; + for (size_t i = 0; i < set.capacity(); ++i) { + if (set.is_marked(i)) ++count; } EXPECT_EQ(marked, count); } @@ -22,7 +22,7 @@ void verify_handle(const ReusableSetHandle &set, size_t sz, Mark val, size_t mar EXPECT_EQ(val, set.generation()); size_t count = 0; for (size_t i = 0; i < set.capacity(); ++i) { - if (set.isMarked(i)) ++count; + if (set.is_marked(i)) ++count; } EXPECT_EQ(marked, count); } @@ -36,7 +36,7 @@ public: size_t sz = set.capacity(); size_t count = 0; for (size_t i = 0; i < sz; ++i) { - if (set.isMarked(i)) ++count; + if (set.is_marked(i)) ++count; } EXPECT_EQ(0, count); for (int i = 0; i < 17; ++i) { @@ -44,7 +44,7 @@ public: } count = 0; for (size_t i = 0; i < sz; ++i) { - if (set.isMarked(i)) ++count; + if (set.is_marked(i)) ++count; } EXPECT_EQ(17, count); for (int i = 0; i < 17; ++i) { @@ -52,7 +52,7 @@ public: } count = 0; for (size_t i = 0; i < sz; ++i) { - if (set.isMarked(i)) ++count; + if (set.is_marked(i)) ++count; } EXPECT_EQ(17, count); } @@ -66,11 +66,19 @@ TEST(ReusableSetTest, simple_usage) visited.mark(1); visited.mark(2); visited.mark(4); + EXPECT_EQ(false, visited.is_marked(0)); + EXPECT_EQ(true, visited.is_marked(1)); + EXPECT_EQ(true, visited.is_marked(2)); + EXPECT_EQ(false, visited.is_marked(3)); verify_set(visited, 7, 1, 3); visited.mark(4); visited.mark(1); visited.mark(2); verify_set(visited, 7, 1, 3); + EXPECT_EQ(false, visited.is_marked(0)); + EXPECT_EQ(true, visited.is_marked(1)); + EXPECT_EQ(true, visited.is_marked(2)); + EXPECT_EQ(false, visited.is_marked(3)); visited.clear(); verify_set(visited, 7, 2, 0); visited.clear(); @@ -83,24 +91,38 @@ TEST_F(Pool, reuse_works) auto handle = pool.get(7); EXPECT_EQ(i, pool.reuse_count()); EXPECT_EQ(1, pool.create_count()); - verify_handle(handle, 250, i+1, 0); + verify_handle(handle, 248, i+1, 0); exercise(handle); } + EXPECT_TRUE(500 < pool.memory_usage()); + EXPECT_TRUE(1000 > pool.memory_usage()); 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); + verify_handle(handle, 248, i+1, 0); exercise(handle); } - auto handle3 = pool.get(300); + auto handle3 = pool.get(260); EXPECT_EQ(2, pool.create_count()); - verify_handle(handle3, 600, 1, 0); + verify_handle(handle3, 297, 1, 0); exercise(handle3); - auto handle7 = pool.get(700); - EXPECT_EQ(3, pool.create_count()); - verify_handle(handle7, 1400, 1, 0); + { + auto handle4 = pool.get(400); + EXPECT_EQ(3, pool.create_count()); + verify_handle(handle4, 400, 1, 0); + exercise(handle4); + } + auto handle7 = pool.get(401); + EXPECT_EQ(4, pool.create_count()); + verify_handle(handle7, 480, 1, 0); exercise(handle7); + EXPECT_TRUE(1000 < pool.memory_usage()); + EXPECT_TRUE(3000 > pool.memory_usage()); + auto handle8 = pool.get(2500); + auto handle9 = pool.get(2500); + EXPECT_TRUE(11000 < pool.memory_usage()); + EXPECT_TRUE(13000 > pool.memory_usage()); } GTEST_MAIN_RUN_ALL_TESTS() diff --git a/vespalib/src/vespa/vespalib/util/reusable_set.h b/vespalib/src/vespa/vespalib/util/reusable_set.h index 5263b32d51f..1896b171e88 100644 --- a/vespalib/src/vespa/vespalib/util/reusable_set.h +++ b/vespalib/src/vespa/vespalib/util/reusable_set.h @@ -2,46 +2,59 @@ #pragma once -#include <vector> +#include "array.h" +#include "array.hpp" #include <memory> #include <cstring> + namespace vespalib { -struct ReusableSet +class ReusableSet { +public: 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) + : _array(size), + _curval(-1), + _sz(size) { clear(); } ~ReusableSet() { - free(bits); } void clear() { - if (++curval == 0) { - memset(bits, 0, sz * sizeof(Mark)); - ++curval; + if (++_curval == 0) { + memset(bits(), 0, _sz * sizeof(Mark)); + ++_curval; } } void mark(size_t id) { - bits[id] = curval; + _array[id] = _curval; + } + + bool is_marked(size_t id) const { + return (_array[id] == _curval); } - bool isMarked(size_t id) const { - return (bits[id] == curval); + Mark *bits() { return _array.begin(); } + + Mark generation() const { return _curval; } + + size_t memory_usage() const { + return (_sz * sizeof(Mark)) + sizeof(ReusableSet); } + + size_t capacity() const { return _sz; } + +private: + Array<Mark> _array; + Mark _curval; + size_t _sz; }; } // namespace diff --git a/vespalib/src/vespa/vespalib/util/reusable_set_handle.h b/vespalib/src/vespa/vespalib/util/reusable_set_handle.h index 7855d4febbc..386370bdd62 100644 --- a/vespalib/src/vespa/vespalib/util/reusable_set_handle.h +++ b/vespalib/src/vespa/vespalib/util/reusable_set_handle.h @@ -21,24 +21,24 @@ private: public: ReusableSetHandle(RSUP backing, ReusableSetPool& owner) - : _bits(backing->bits), - _curval(backing->curval), + : _bits(backing->bits()), + _curval(backing->generation()), _owned(std::move(backing)), _pool(owner) {} ~ReusableSetHandle(); - void mark(uint32_t id) { + void mark(size_t id) { _bits[id] = _curval; } - bool isMarked(uint32_t id) const { + bool is_marked(size_t id) const { return (_bits[id] == _curval); } // for unit tests and statistics - size_t capacity() const { return _owned->sz; } + size_t capacity() const { return _owned->capacity(); } Mark generation() const { return _curval; } }; diff --git a/vespalib/src/vespa/vespalib/util/reusable_set_pool.h b/vespalib/src/vespa/vespalib/util/reusable_set_pool.h index 3a4a1caa4dd..e5e9d4e64d7 100644 --- a/vespalib/src/vespa/vespalib/util/reusable_set_pool.h +++ b/vespalib/src/vespa/vespalib/util/reusable_set_pool.h @@ -5,6 +5,7 @@ #include "reusable_set.h" #include "reusable_set_handle.h" +#include <vector> #include <mutex> namespace vespalib { @@ -17,27 +18,41 @@ class ReusableSetPool std::mutex _lock; size_t _reuse_count; size_t _create_count; - + size_t _total_memory_used; + const size_t _min_size; + const size_t _grow_percent; ReusableSetPool(const ReusableSetPool &) = delete; ReusableSetPool& operator= (const ReusableSetPool &) = delete; public: - ReusableSetPool() : _lru_stack(), _lock(), _reuse_count(0), _create_count(0) {} + ReusableSetPool() + : _lru_stack(), _lock(), + _reuse_count(0), _create_count(0), + _total_memory_used(sizeof(ReusableSetPool)), + _min_size(248), _grow_percent(20) + {} ReusableSetHandle get(size_t size) { Guard guard(_lock); + size_t last_used_size = 0; while (! _lru_stack.empty()) { RSUP r = std::move(_lru_stack.back()); _lru_stack.pop_back(); - if (r->sz >= size) { + if (r->capacity() >= size) { r->clear(); - ++_reuse_count; + ++_reuse_count; return ReusableSetHandle(std::move(r), *this); } + _total_memory_used -= r->memory_usage(); + last_used_size = std::max(last_used_size, r->capacity()); } - RSUP r = std::make_unique<ReusableSet>(std::max((size_t)250, size*2)); - ++_create_count; + double grow_factor = (1.0 + _grow_percent / 100.0); + last_used_size *= grow_factor; + size_t at_least_size = std::max(_min_size, last_used_size); + RSUP r = std::make_unique<ReusableSet>(std::max(at_least_size, size)); + ++_create_count; + _total_memory_used += r->memory_usage(); return ReusableSetHandle(std::move(r), *this); } @@ -49,6 +64,7 @@ public: // for unit testing and statistics size_t reuse_count() const { return _reuse_count; } size_t create_count() const { return _create_count; } + size_t memory_usage() const { return _total_memory_used; } }; } // namespace |