From d18ee22daeab01118d8ec4c72bbcfa105f656b67 Mon Sep 17 00:00:00 2001
From: Henning Baldersheim <balder@yahoo-inc.com>
Date: Thu, 10 Aug 2023 16:56:19 +0000
Subject: When splitting a large number of nodes into their leaf groups you end
 up with many vectors with only a single node in them. Then it is more
 efficient to use a small_vector that keeps the 4 first entries within.
 Reduces # allocations and avoids indirection.

---
 .../src/vespa/storage/distributor/activecopy.cpp   | 39 ++++++++++++----------
 vdslib/src/tests/distribution/distributiontest.cpp |  4 +++
 .../src/vespa/vdslib/distribution/distribution.h   |  4 +--
 3 files changed, 27 insertions(+), 20 deletions(-)

diff --git a/storage/src/vespa/storage/distributor/activecopy.cpp b/storage/src/vespa/storage/distributor/activecopy.cpp
index ea194e1be21..5d59d1a838f 100644
--- a/storage/src/vespa/storage/distributor/activecopy.cpp
+++ b/storage/src/vespa/storage/distributor/activecopy.cpp
@@ -9,21 +9,25 @@
 #include <cassert>
 
 namespace std {
-    template<typename T>
-    std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
-        out << "[";
-        for (uint32_t i=0; i<v.size(); ++i) {
-            out << "\n  " << v[i];
-        }
-        if (!v.empty()) {
-            out << "\n";
-        }
-        return out << "]";
+
+template<typename T>
+std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
+    out << "[";
+    for (uint32_t i=0; i<v.size(); ++i) {
+        out << "\n  " << v[i];
     }
+    if (!v.empty()) {
+        out << "\n";
+    }
+    return out << "]";
+}
+
 }
 
 namespace storage::distributor {
 
+using IndexList = lib::Distribution::IndexList;
+
 ActiveCopy::ActiveCopy(uint16_t node, const BucketDatabase::Entry& e, const std::vector<uint16_t>& idealState)
     : _nodeIndex(node),
       _ideal(0xffff)
@@ -109,22 +113,21 @@ struct ActiveStateOrder {
     }
 };
 
-std::vector<uint16_t>
+IndexList
 buildValidNodeIndexList(BucketDatabase::Entry& e) {
-    std::vector<uint16_t> result;
+    IndexList result;
     result.reserve(e->getNodeCount());
     for (uint32_t i=0, n=e->getNodeCount(); i < n; ++i) {
         const BucketCopy& cp = e->getNodeRef(i);
-        if (!cp.valid()) {
-            continue;
+        if (cp.valid()) {
+            result.push_back(cp.getNode());
         }
-        result.push_back(cp.getNode());
     }
     return result;
 }
 
 std::vector<ActiveCopy>
-buildNodeList(BucketDatabase::Entry& e, const std::vector<uint16_t>& nodeIndexes, const std::vector<uint16_t>& idealState)
+buildNodeList(BucketDatabase::Entry& e,vespalib::ConstArrayRef<uint16_t> nodeIndexes, const std::vector<uint16_t>& idealState)
 {
     std::vector<ActiveCopy> result;
     result.reserve(nodeIndexes.size());
@@ -140,11 +143,11 @@ ActiveList
 ActiveCopy::calculate(const std::vector<uint16_t>& idealState, const lib::Distribution& distribution,
                       BucketDatabase::Entry& e, uint32_t max_activation_inhibited_out_of_sync_groups)
 {
-    std::vector<uint16_t> validNodesWithCopy = buildValidNodeIndexList(e);
+    IndexList validNodesWithCopy = buildValidNodeIndexList(e);
     if (validNodesWithCopy.empty()) {
         return ActiveList();
     }
-    std::vector<lib::Distribution::IndexList> groups;
+    std::vector<IndexList> groups;
     if (distribution.activePerGroup()) {
         groups = distribution.splitNodesIntoLeafGroups(validNodesWithCopy);
     } else {
diff --git a/vdslib/src/tests/distribution/distributiontest.cpp b/vdslib/src/tests/distribution/distributiontest.cpp
index 33a6d47b719..ec7c05fa7a2 100644
--- a/vdslib/src/tests/distribution/distributiontest.cpp
+++ b/vdslib/src/tests/distribution/distributiontest.cpp
@@ -1031,4 +1031,8 @@ TEST(DistributionTest, DISABLED_benchmark_ideal_state_for_many_groups) {
     fprintf(stderr, "%.10f seconds\n", min_time);
 }
 
+TEST(DistributionTest, control_size_of_IndexList) {
+    EXPECT_EQ(24u, sizeof(Distribution::IndexList));
+}
+
 }
diff --git a/vdslib/src/vespa/vdslib/distribution/distribution.h b/vdslib/src/vespa/vdslib/distribution/distribution.h
index b39afb17e15..8cf93b01630 100644
--- a/vdslib/src/vespa/vdslib/distribution/distribution.h
+++ b/vdslib/src/vespa/vdslib/distribution/distribution.h
@@ -12,7 +12,7 @@
 #include <vespa/document/bucket/bucketid.h>
 #include <vespa/vdslib/state/nodetype.h>
 #include <vespa/vespalib/util/exception.h>
-#include <vespa/vespalib/util/arrayref.h>
+#include <vespa/vespalib/util/small_vector.h>
 
 namespace vespa::config::content::internal {
     class InternalStorDistributionType;
@@ -148,7 +148,7 @@ public:
      * Utility function used by distributor to split copies into groups to
      * handle active per group feature.
      */
-    using IndexList = std::vector<uint16_t>;
+    using IndexList = vespalib::SmallVector<uint16_t, 4>;
     std::vector<IndexList> splitNodesIntoLeafGroups(vespalib::ConstArrayRef<uint16_t> nodes) const;
 
     static bool allDistributorsDown(const Group&, const ClusterState&);
-- 
cgit v1.2.3