diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2022-05-25 21:21:06 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-05-25 21:21:06 +0200 |
commit | 1aa60e70335ef3397d3a987df7ffcf111fad4f7f (patch) | |
tree | 85b1be6edb6c2aa322e373a0fd68ec0fafa1d24e /vespalib | |
parent | 4aab870f158ff1c2dc3f0c2afbb706680c75b220 (diff) | |
parent | 7aef2017e0af21f9b0f1290f2299bcb39319a384 (diff) |
Merge pull request #22729 from vespa-engine/balder/introduce-concept-of-minimum-capacity
- Introduce the concept of minimal capacity for rcu vectors.
Diffstat (limited to 'vespalib')
-rw-r--r-- | vespalib/src/tests/util/rcuvector/rcuvector_test.cpp | 53 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/growstrategy.h | 21 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/util/rcuvector.hpp | 5 |
3 files changed, 45 insertions, 34 deletions
diff --git a/vespalib/src/tests/util/rcuvector/rcuvector_test.cpp b/vespalib/src/tests/util/rcuvector/rcuvector_test.cpp index 0190d59edfb..eb2b00f9e20 100644 --- a/vespalib/src/tests/util/rcuvector/rcuvector_test.cpp +++ b/vespalib/src/tests/util/rcuvector/rcuvector_test.cpp @@ -31,10 +31,15 @@ assertUsage(const MemoryUsage & exp, const MemoryUsage & act) return retval; } +GrowStrategy +growStrategy(size_t initial, float factor, size_t delta, size_t minimal = 0) { + return GrowStrategy(initial, factor, delta, minimal); +} + TEST(RcuVectorTest, basic) { { // insert - RcuVector<int32_t> v(GrowStrategy(4, 0, 4)); + RcuVector<int32_t> v(growStrategy(4, 0, 4)); for (int32_t i = 0; i < 100; ++i) { v.push_back(i); EXPECT_EQ(i, v[i]); @@ -53,7 +58,7 @@ TEST(RcuVectorTest, basic) TEST(RcuVectorTest, resize) { { // resize percent - RcuVector<int32_t> v(GrowStrategy(2, 0.50, 0)); + RcuVector<int32_t> v(growStrategy(2, 0.50, 0)); EXPECT_EQ(2u, v.capacity()); v.push_back(0); EXPECT_EQ(2u, v.capacity()); @@ -65,7 +70,7 @@ TEST(RcuVectorTest, resize) EXPECT_TRUE(v.isFull()); } { // resize delta - RcuVector<int32_t> v(GrowStrategy(1, 0, 3)); + RcuVector<int32_t> v(growStrategy(1, 0, 3)); EXPECT_EQ(1u, v.capacity()); v.push_back(0); EXPECT_EQ(1u, v.capacity()); @@ -75,7 +80,7 @@ TEST(RcuVectorTest, resize) EXPECT_TRUE(!v.isFull()); } { // resize both - RcuVector<int32_t> v(GrowStrategy(2, 2.0, 3)); + RcuVector<int32_t> v(growStrategy(2, 2.0, 3)); EXPECT_EQ(2u, v.capacity()); v.push_back(0); EXPECT_EQ(2u, v.capacity()); @@ -87,14 +92,14 @@ TEST(RcuVectorTest, resize) EXPECT_TRUE(!v.isFull()); } { // reserve - RcuVector<int32_t> v(GrowStrategy(2, 0, 0)); + RcuVector<int32_t> v(growStrategy(2, 0, 0)); EXPECT_EQ(2u, v.capacity()); v.unsafe_reserve(8); EXPECT_EQ(8u, v.capacity()); } { // explicit resize GenerationHolder g; - RcuVectorBase<int8_t> v(GrowStrategy(16, 1.0, 0), g); + RcuVectorBase<int8_t> v(growStrategy(16, 1.0, 0), g); v.push_back(1); v.push_back(2); g.transferHoldLists(0); @@ -120,7 +125,7 @@ TEST(RcuVectorTest, resize) TEST(RcuVectorTest, generation_handling) { - RcuVector<int32_t> v(GrowStrategy(2, 0, 2)); + RcuVector<int32_t> v(growStrategy(2, 0, 2)); v.push_back(0); v.push_back(10); EXPECT_EQ(0u, v.getMemoryUsage().allocatedBytesOnHold()); @@ -143,7 +148,7 @@ TEST(RcuVectorTest, generation_handling) TEST(RcuVectorTest, reserve) { - RcuVector<int32_t> v(GrowStrategy(2, 0, 2)); + RcuVector<int32_t> v(growStrategy(2, 0, 2)); EXPECT_EQ(2u, v.capacity()); EXPECT_EQ(0u, v.size()); v.push_back(0); @@ -167,7 +172,7 @@ TEST(RcuVectorTest, reserve) TEST(RcuVectorTest, memory_usage) { - RcuVector<int8_t> v(GrowStrategy(2, 0, 2)); + RcuVector<int8_t> v(growStrategy(2, 0, 2)); EXPECT_TRUE(assertUsage(MemoryUsage(2,0,0,0), v.getMemoryUsage())); v.push_back(0); EXPECT_TRUE(assertUsage(MemoryUsage(2,1,0,0), v.getMemoryUsage())); @@ -183,10 +188,11 @@ TEST(RcuVectorTest, memory_usage) EXPECT_TRUE(assertUsage(MemoryUsage(6,5,0,0), v.getMemoryUsage())); } -TEST(RcuVectorTest, shrink_with_buffer_copying) -{ +void verify_shrink_with_buffer_copying(size_t initial_size, size_t absolute_minimum) { + const size_t minimal_capacity = std::max(4ul, absolute_minimum); + const size_t initial_capacity = std::max(initial_size, minimal_capacity); GenerationHolder g; - RcuVectorBase<int8_t> v(GrowStrategy(16, 1.0, 0), g); + RcuVectorBase<int8_t> v(growStrategy(initial_size, 1.0, 0, absolute_minimum), g); v.push_back(1); v.push_back(2); v.push_back(3); @@ -196,9 +202,9 @@ TEST(RcuVectorTest, shrink_with_buffer_copying) MemoryUsage mu; mu = v.getMemoryUsage(); mu.incAllocatedBytesOnHold(g.getHeldBytes()); - EXPECT_TRUE(assertUsage(MemoryUsage(16, 4, 0, 0), mu)); + EXPECT_TRUE(assertUsage(MemoryUsage(initial_capacity, 4, 0, 0), mu)); EXPECT_EQ(4u, v.size()); - EXPECT_EQ(16u, v.capacity()); + EXPECT_EQ(initial_capacity, v.capacity()); EXPECT_EQ(1, v[0]); EXPECT_EQ(2, v[1]); EXPECT_EQ(3, v[2]); @@ -207,7 +213,7 @@ TEST(RcuVectorTest, shrink_with_buffer_copying) v.shrink(2); g.transferHoldLists(1); EXPECT_EQ(2u, v.size()); - EXPECT_EQ(4u, v.capacity()); + EXPECT_EQ(minimal_capacity, v.capacity()); EXPECT_EQ(1, v[0]); EXPECT_EQ(2, v[1]); EXPECT_EQ(1, old[0]); @@ -217,7 +223,14 @@ TEST(RcuVectorTest, shrink_with_buffer_copying) EXPECT_EQ(2, v[1]); mu = v.getMemoryUsage(); mu.incAllocatedBytesOnHold(g.getHeldBytes()); - EXPECT_TRUE(assertUsage(MemoryUsage(4, 2, 0, 0), mu)); + EXPECT_TRUE(assertUsage(MemoryUsage(minimal_capacity, 2, 0, 0), mu)); +} + +TEST(RcuVectorTest, shrink_with_buffer_copying) +{ + verify_shrink_with_buffer_copying(16, 8); + verify_shrink_with_buffer_copying(0, 8); + verify_shrink_with_buffer_copying(0, 0); } struct ShrinkFixture { @@ -229,7 +242,7 @@ struct ShrinkFixture { ShrinkFixture() : g(), initial_capacity(4 * page_ints()), initial_size(initial_capacity / 1024 * 1000), - vec(GrowStrategy(initial_capacity, 0.50, 0), g, alloc::Alloc::allocMMap()), oldPtr() + vec(growStrategy(initial_capacity, 0.50, 0), g, alloc::Alloc::allocMMap()), oldPtr() { for (size_t i = 0; i < initial_size; ++i) { vec.push_back(7); @@ -272,7 +285,7 @@ TEST(RcuVectorTest, shrink_can_shrink_mmap_allocation) TEST(RcuVectorTest, small_expand) { GenerationHolder g; - RcuVectorBase<int8_t> v(GrowStrategy(1, 0.50, 0), g); + RcuVectorBase<int8_t> v(growStrategy(1, 0.50, 0), g); EXPECT_EQ(1u, v.capacity()); EXPECT_EQ(0u, v.size()); v.push_back(1); @@ -321,7 +334,7 @@ struct Fixture : public FixtureBase { Fixture::Fixture() : FixtureBase(), - arr(GrowStrategy(16, 1.0, 0), g, initial_alloc) + arr(growStrategy(16, 1.0, 0), g, initial_alloc) { arr.reserve(100); } @@ -403,7 +416,7 @@ struct StressFixture : public FixtureBase { StressFixture::StressFixture() : FixtureBase(), - arr(GrowStrategy(16, 1.0, 0), g, initial_alloc), + arr(growStrategy(16, 1.0, 0), g, initial_alloc), stop_read(false), read_area(1000), generation_handler(), diff --git a/vespalib/src/vespa/vespalib/util/growstrategy.h b/vespalib/src/vespa/vespalib/util/growstrategy.h index dad83a5f704..efac26ce19d 100644 --- a/vespalib/src/vespa/vespalib/util/growstrategy.h +++ b/vespalib/src/vespa/vespalib/util/growstrategy.h @@ -9,32 +9,29 @@ namespace vespalib { class GrowStrategy { private: size_t _initialCapacity; - float _growFactor; + size_t _minimumCapacity; size_t _growDelta; + float _growFactor; public: GrowStrategy() noexcept - : GrowStrategy(1024, 0.5, 0) + : GrowStrategy(1024, 0.5, 0, 0) {} - GrowStrategy(size_t initialCapacity, float growPercent, size_t growDelta) noexcept + GrowStrategy(size_t initialCapacity, float growPercent, size_t growDelta, size_t minimumCapacity) noexcept : _initialCapacity(initialCapacity), - _growFactor(growPercent), - _growDelta(growDelta) + _minimumCapacity(minimumCapacity), + _growDelta(growDelta), + _growFactor(growPercent) { } - static GrowStrategy make(size_t initialCapacity, float growFactor, size_t growDelta) noexcept { - return GrowStrategy(initialCapacity, growFactor, growDelta); - } - + size_t getMinimumCapacity() const noexcept { return _minimumCapacity; } size_t getInitialCapacity() const noexcept { return _initialCapacity; } - size_t getGrowPercent() const noexcept { return _growFactor*100; } float getGrowFactor() const noexcept { return _growFactor; } size_t getGrowDelta() const noexcept { return _growDelta; } - void setInitialCapacity(size_t v) noexcept { _initialCapacity = v; } - void setGrowDelta(size_t v) noexcept { _growDelta = v; } bool operator==(const GrowStrategy & rhs) const noexcept { return (_initialCapacity == rhs._initialCapacity && + _minimumCapacity == rhs._minimumCapacity && _growFactor == rhs._growFactor && _growDelta == rhs._growDelta); } diff --git a/vespalib/src/vespa/vespalib/util/rcuvector.hpp b/vespalib/src/vespa/vespalib/util/rcuvector.hpp index 3c76ed22471..35a5fda81e4 100644 --- a/vespalib/src/vespa/vespalib/util/rcuvector.hpp +++ b/vespalib/src/vespa/vespalib/util/rcuvector.hpp @@ -20,7 +20,8 @@ RcuVectorHeld<T>::~RcuVectorHeld() = default; template <typename T> size_t RcuVectorBase<T>::calcNewSize(size_t baseSize) const { size_t delta = (baseSize * _growStrategy.getGrowFactor()) + _growStrategy.getGrowDelta(); - return baseSize + std::max(delta, static_cast<size_t>(1)); + size_t newSize = baseSize + std::max(delta, static_cast<size_t>(1)); + return std::max(newSize, _growStrategy.getMinimumCapacity()); } template <typename T> size_t RcuVectorBase<T>::calcNewSize() const { @@ -166,7 +167,7 @@ RcuVector<T>::onReallocation() { template <typename T> RcuVector<T>::RcuVector() - : RcuVectorBase<T>(GrowStrategy(16, 1.0, 0), _genHolderStore), + : RcuVectorBase<T>(GrowStrategy(16, 1.0, 0, 0), _genHolderStore), _generation(0), _genHolderStore() { } |