Change shrink() to shrink underlying memory allocation if possible (without copying data).

Take grow factor into consideration when calculating wanted capacity in shrink().

3 files changed, 92 insertions, 37 deletions

diff --git a/searchlib/src/tests/common/rcuvector/rcuvector_test.cpp b/searchlib/src/tests/common/rcuvector/rcuvector_test.cpp
index 78332d7e3b3..f8a18d13192 100644
--- a/searchlib/src/tests/common/rcuvector/rcuvector_test.cpp
+++ b/searchlib/src/tests/common/rcuvector/rcuvector_test.cpp
@@ -7,6 +7,7 @@ LOG_SETUP("rcuvector_test");
 
 using namespace search::attribute;
 using search::MemoryUsage;
+using vespalib::alloc::Alloc;
 using vespalib::GenerationHandler;
 using vespalib::GenerationHolder;
 using vespalib::GenerationHeldBase;
@@ -183,10 +184,10 @@ TEST("test memory usage")
     EXPECT_TRUE(assertUsage(MemoryUsage(6,5,0,0), v.getMemoryUsage()));
 }
 
-TEST("test shrink")
+TEST("test shrink() with buffer copying")
 {
     GenerationHolder g;
-    RcuVectorBase<int8_t> v(g);
+    RcuVectorBase<int8_t> v(16, 100, 0, g);
     v.push_back(1);
     v.push_back(2);
     v.push_back(3);
@@ -198,7 +199,7 @@ TEST("test shrink")
     mu.incAllocatedBytesOnHold(g.getHeldBytes());
     EXPECT_TRUE(assertUsage(MemoryUsage(16, 4, 0, 0), mu));
     EXPECT_EQUAL(4u, v.size());
-    EXPECT_TRUE(v.capacity() >= 4u);
+    EXPECT_EQUAL(16u, v.capacity());
     EXPECT_EQUAL(1, v[0]);
     EXPECT_EQUAL(2, v[1]);
     EXPECT_EQUAL(3, v[2]);
@@ -207,7 +208,7 @@ TEST("test shrink")
     v.shrink(2);
     g.transferHoldLists(1);
     EXPECT_EQUAL(2u, v.size());
-    EXPECT_EQUAL(2u, v.capacity());
+    EXPECT_EQUAL(4u, v.capacity());
     EXPECT_EQUAL(1, v[0]);
     EXPECT_EQUAL(2, v[1]);
     EXPECT_EQUAL(1, old[0]);
@@ -217,7 +218,47 @@ TEST("test shrink")
     EXPECT_EQUAL(2, v[1]);
     mu = v.getMemoryUsage();
     mu.incAllocatedBytesOnHold(g.getHeldBytes());
-    EXPECT_TRUE(assertUsage(MemoryUsage(2, 2, 0, 0), mu));
+    EXPECT_TRUE(assertUsage(MemoryUsage(4, 2, 0, 0), mu));
+}
+
+struct ShrinkFixture {
+    GenerationHolder g;
+    RcuVectorBase<int> vec;
+    int *oldPtr;
+    ShrinkFixture() : g(), vec(4096, 50, 0, g, Alloc::allocMMap()), oldPtr()
+    {
+        for (size_t i = 0; i < 4000; ++i) {
+            vec.push_back(7);
+        }
+        EXPECT_EQUAL(4000u, vec.size());
+        EXPECT_EQUAL(4096u, vec.capacity());
+        assertEmptyHoldList();
+        oldPtr = &vec[0];
+    }
+    void assertOldEqualNewBuffer() {
+        EXPECT_EQUAL(oldPtr, &vec[0]);
+    }
+    void assertEmptyHoldList() {
+        EXPECT_EQUAL(0u, g.getHeldBytes());
+    }
+};
+
+TEST_F("require that shrink() does not increase allocated memory", ShrinkFixture)
+{
+    f.vec.shrink(2732);
+    EXPECT_EQUAL(2732u, f.vec.size());
+    EXPECT_EQUAL(4096u, f.vec.capacity());
+    TEST_DO(f.assertOldEqualNewBuffer());
+    TEST_DO(f.assertEmptyHoldList());
+}
+
+TEST_F("require that shrink() can shrink mmap allocation", ShrinkFixture)
+{
+    f.vec.shrink(2048);
+    EXPECT_EQUAL(2048, f.vec.size());
+    EXPECT_EQUAL(3072, f.vec.capacity());
+    TEST_DO(f.assertOldEqualNewBuffer());
+    TEST_DO(f.assertEmptyHoldList());
 }
 
 TEST("test small expand")
diff --git a/searchlib/src/vespa/searchlib/common/rcuvector.h b/searchlib/src/vespa/searchlib/common/rcuvector.h
index f9d8cf209c6..32dd1d99f7a 100644
--- a/searchlib/src/vespa/searchlib/common/rcuvector.h
+++ b/searchlib/src/vespa/searchlib/common/rcuvector.h
@@ -5,6 +5,7 @@
 #include <vespa/vespalib/util/generationholder.h>
 #include <vespa/searchlib/util/memoryusage.h>
 #include <vespa/searchcommon/common/growstrategy.h>
+#include <vespa/vespalib/util/alloc.h>
 #include <vespa/vespalib/util/array.h>
 
 namespace search {
@@ -37,9 +38,10 @@ class RcuVectorBase
                   "Value type must be trivially destructible");
 
 protected:
-    typedef vespalib::Array<T> Array;
-    typedef vespalib::GenerationHandler::generation_t generation_t;
-    typedef vespalib::GenerationHolder GenerationHolder;
+    using Array = vespalib::Array<T>;
+    using Alloc = vespalib::alloc::Alloc;
+    using generation_t = vespalib::GenerationHandler::generation_t;
+    using GenerationHolder = vespalib::GenerationHolder;
     Array              _data;
     size_t             _growPercent;
     size_t             _growDelta;
@@ -61,7 +63,8 @@ protected:
 
 public:
     using ValueType = T;
-    RcuVectorBase(GenerationHolder &genHolder);
+    RcuVectorBase(GenerationHolder &genHolder,
+                  const Alloc &initialAlloc = Alloc::alloc());
 
     /**
      * Construct a new vector with the given initial capacity and grow
@@ -70,9 +73,13 @@ public:
      * New capacity is calculated based on old capacity and grow parameters:
      * nc = oc + (oc * growPercent / 100) + growDelta.
      **/
-    RcuVectorBase(size_t initialCapacity, size_t growPercent, size_t growDelta, GenerationHolder &genHolder);
+    RcuVectorBase(size_t initialCapacity, size_t growPercent, size_t growDelta,
+                  GenerationHolder &genHolder,
+                  const Alloc &initialAlloc = Alloc::alloc());
 
-    RcuVectorBase(GrowStrategy growStrategy, GenerationHolder &genHolder);
+    RcuVectorBase(GrowStrategy growStrategy,
+                  GenerationHolder &genHolder,
+                  const Alloc &initialAlloc = Alloc::alloc());
 
     ~RcuVectorBase();
 
diff --git a/searchlib/src/vespa/searchlib/common/rcuvector.hpp b/searchlib/src/vespa/searchlib/common/rcuvector.hpp
index 920c0292435..6d1934a2148 100644
--- a/searchlib/src/vespa/searchlib/common/rcuvector.hpp
+++ b/searchlib/src/vespa/searchlib/common/rcuvector.hpp
@@ -49,12 +49,6 @@ RcuVectorBase<T>::reset() {
 }
 
 template <typename T>
-RcuVectorBase<T>::RcuVectorBase(GrowStrategy growStrategy, GenerationHolder &genHolder)
-    : RcuVectorBase(growStrategy.getDocsInitialCapacity(), growStrategy.getDocsGrowPercent(),
-                    growStrategy.getDocsGrowDelta(), genHolder)
-{ }
-
-template <typename T>
 RcuVectorBase<T>::~RcuVectorBase() { }
 
 template <typename T>
@@ -79,33 +73,36 @@ RcuVectorBase<T>::expandAndInsert(const T & v)
     _data.push_back(v);
 }
 
-
 template <typename T>
 void
 RcuVectorBase<T>::shrink(size_t newSize)
 {
-    // TODO: Extend Array class to support more optimial shrink when
-    // backing store is memory mapped.
     assert(newSize <= _data.size());
-    std::unique_ptr<Array> tmpData(new Array());
-    tmpData->reserve(newSize);
-    tmpData->resize(newSize);
-    for (uint32_t i = 0; i < newSize; ++i) {
-        (*tmpData)[i] = _data[i];
+    _data.resize(newSize);
+    size_t wantedCapacity = calcSize(newSize);
+    if (wantedCapacity >= _data.capacity()) {
+        return;
+    }
+    if (!_data.try_unreserve(wantedCapacity)) {
+        std::unique_ptr <Array> tmpData(new Array());
+        tmpData->reserve(wantedCapacity);
+        tmpData->resize(newSize);
+        for (uint32_t i = 0; i < newSize; ++i) {
+            (*tmpData)[i] = _data[i];
+        }
+        // Users of RCU vector must ensure that no readers use old size
+        // after swap.  Attribute vectors uses _committedDocIdLimit for this.
+        tmpData->swap(_data); // atomic switch of underlying data
+        size_t holdSize = tmpData->capacity() * sizeof(T);
+        vespalib::GenerationHeldBase::UP hold(new RcuVectorHeld<Array>(holdSize, std::move(tmpData)));
+        _genHolder.hold(std::move(hold));
     }
-    // Users of RCU vector must ensure that no readers use old size
-    // after swap.  Attribute vectors uses _committedDocIdLimit for this.
-    tmpData->swap(_data); // atomic switch of underlying data
-    // Use capacity() instead of size() ?
-    size_t holdSize = tmpData->size() * sizeof(T);
-    vespalib::GenerationHeldBase::UP hold(new RcuVectorHeld<Array>(holdSize, std::move(tmpData)));
-    _genHolder.hold(std::move(hold));
 }
 
-
 template <typename T>
-RcuVectorBase<T>::RcuVectorBase(GenerationHolder &genHolder)
-    : _data(),
+RcuVectorBase<T>::RcuVectorBase(GenerationHolder &genHolder,
+                                const Alloc &initialAlloc)
+    : _data(initialAlloc),
       _growPercent(100),
       _growDelta(0),
       _genHolder(genHolder)
@@ -117,8 +114,9 @@ template <typename T>
 RcuVectorBase<T>::RcuVectorBase(size_t initialCapacity,
                                 size_t growPercent,
                                 size_t growDelta,
-                                GenerationHolder &genHolder)
-    : _data(),
+                                GenerationHolder &genHolder,
+                                const Alloc &initialAlloc)
+    : _data(initialAlloc),
       _growPercent(growPercent),
       _growDelta(growDelta),
       _genHolder(genHolder)
@@ -127,6 +125,15 @@ RcuVectorBase<T>::RcuVectorBase(size_t initialCapacity,
 }
 
 template <typename T>
+RcuVectorBase<T>::RcuVectorBase(GrowStrategy growStrategy,
+                                GenerationHolder &genHolder,
+                                const Alloc &initialAlloc)
+    : RcuVectorBase(growStrategy.getDocsInitialCapacity(), growStrategy.getDocsGrowPercent(),
+                    growStrategy.getDocsGrowDelta(), genHolder, initialAlloc)
+{
+}
+
+template <typename T>
 MemoryUsage
 RcuVectorBase<T>::getMemoryUsage() const
 {