Revert "Only sort once during ideal group calculations"

2 files changed, 24 insertions, 75 deletions

diff --git a/vdslib/src/tests/distribution/distributiontest.cpp b/vdslib/src/tests/distribution/distributiontest.cpp
index 387146accfc..f0b48faebef 100644
--- a/vdslib/src/tests/distribution/distributiontest.cpp
+++ b/vdslib/src/tests/distribution/distributiontest.cpp
@@ -13,7 +13,6 @@
 #include <vespa/vespalib/io/fileutil.h>
 #include <vespa/vespalib/stllike/lexical_cast.h>
 #include <vespa/vespalib/text/stringtokenizer.h>
-#include <vespa/vespalib/util/benchmark_timer.h>
 #include <chrono>
 #include <thread>
 #include <fstream>
@@ -1144,57 +1143,4 @@ TEST(DistributionTest, test_hierarchical_distribute_less_than_redundancy)
     }
 }
 
-namespace {
-
-std::string generate_config_with_n_1node_groups(int n_groups) {
-    std::ostringstream config_os;
-    std::ostringstream partition_os;
-    for (int i = 0; i < n_groups - 1; ++i) {
-        partition_os << "1|";
-    }
-    partition_os << '*';
-    config_os << "redundancy " << n_groups << "\n"
-              << "initial_redundancy " << n_groups << "\n"
-              << "ensure_primary_persisted true\n"
-              << "ready_copies " << n_groups << "\n"
-              << "active_per_leaf_group true\n"
-              << "distributor_auto_ownership_transfer_on_whole_group_down true\n"
-              << "group[0].index \"invalid\"\n"
-              << "group[0].name \"invalid\"\n"
-              << "group[0].capacity " << n_groups << "\n"
-              << "group[0].partitions \"" << partition_os.str() << "\"\n";
-
-    for (int i = 0; i < n_groups; ++i) {
-        int g = i + 1;
-        config_os << "group[" << g << "].index \"" << i << "\"\n"
-                  << "group[" << g << "].name \"group" << g << "\"\n"
-                  << "group[" << g << "].capacity 1\n"
-                  << "group[" << g << "].partitions \"\"\n"
-                  << "group[" << g << "].nodes[0].index \"" << i << "\"\n"
-                  << "group[" << g << "].nodes[0].retired false\n";
-    }
-    return config_os.str();
-}
-
-std::string generate_state_with_n_nodes_up(int n_nodes) {
-    std::ostringstream state_os;
-    state_os << "version:1 bits:8 distributor:" << n_nodes << " storage:" << n_nodes;
-    return state_os.str();
-}
-
-}
-
-TEST(DistributionTest, DISABLED_benchmark_ideal_state_for_many_groups) {
-    const int n_groups = 150;
-    Distribution distr(generate_config_with_n_1node_groups(n_groups));
-    ClusterState state(generate_state_with_n_nodes_up(n_groups));
-
-    std::vector<uint16_t> actual;
-    uint32_t bucket = 0;
-    auto min_time = vespalib::BenchmarkTimer::benchmark([&]{
-        distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, (bucket++ & 0xffffU)), actual);
-    }, 5.0);
-    fprintf(stderr, "%.10f seconds\n", min_time);
-}
-
 }
diff --git a/vdslib/src/vespa/vdslib/distribution/distribution.cpp b/vdslib/src/vespa/vdslib/distribution/distribution.cpp
index 3bdee0447c0..52d523071e6 100644
--- a/vdslib/src/vespa/vdslib/distribution/distribution.cpp
+++ b/vdslib/src/vespa/vdslib/distribution/distribution.cpp
@@ -345,7 +345,6 @@ namespace {
         const Group* _group;
         double _score;
 
-        ScoredGroup() : _group(nullptr), _score(0) {}
         ScoredGroup(const Group* group, double score)
             : _group(group), _score(score) {}
 
@@ -425,36 +424,40 @@ Distribution::getIdealGroups(const document::BucketId& bucket,
                              std::vector<ResultGroup>& results) const
 {
     if (parent.isLeafGroup()) {
-        results.emplace_back(parent, redundancy);
+        results.push_back(ResultGroup(parent, redundancy));
         return;
     }
-    const Group::Distribution& redundancyArray = parent.getDistribution(redundancy);
-    std::vector<ScoredGroup> tmpResults;
-    tmpResults.reserve(redundancyArray.size());
-    uint32_t seed = getGroupSeed(bucket, clusterState, parent);
+    const Group::Distribution& redundancyArray(
+            parent.getDistribution(redundancy));
+    std::vector<ScoredGroup> tmpResults(redundancyArray.size(),
+                                        ScoredGroup(0, 0));
+    uint32_t seed(getGroupSeed(bucket, clusterState, parent));
     RandomGen random(seed);
     uint32_t currentIndex = 0;
-    const auto& subGroups = parent.getSubGroups();
-    for (const auto& g : subGroups) {
-        while (g.first < currentIndex++) {
-            random.nextDouble();
-        }
+    const std::map<uint16_t, Group*>& subGroups(parent.getSubGroups());
+    for (std::map<uint16_t, Group*>::const_iterator it = subGroups.begin();
+         it != subGroups.end(); ++it)
+    {
+        while (it->first < currentIndex++) random.nextDouble();
         double score = random.nextDouble();
-        if (g.second->getCapacity() != 1) {
-            // Capacity shouldn't possibly be 0.
-            // Verified in Group::setCapacity()
-            score = std::pow(score, 1.0 / g.second->getCapacity().getValue());
+        if (it->second->getCapacity() != 1) {
+                // Capacity shouldn't possibly be 0.
+                // Verified in Group::setCapacity()
+            score = std::pow(score, 1.0 / it->second->getCapacity().getValue());
+        }
+        if (score > tmpResults.back()._score) {
+            tmpResults.push_back(ScoredGroup(it->second, score));
+            std::sort(tmpResults.begin(), tmpResults.end());
+            tmpResults.pop_back();
         }
-        tmpResults.emplace_back(g.second, score);
     }
-    std::sort(tmpResults.begin(), tmpResults.end());
-    if (tmpResults.size() > redundancy) {
-        tmpResults.resize(redundancy);
+    while (tmpResults.back()._group == nullptr) {
+        tmpResults.pop_back();
     }
     for (uint32_t i=0, n=tmpResults.size(); i<n; ++i) {
         ScoredGroup& group(tmpResults[i]);
-        // This should never happen. Config should verify that each group
-        // has enough groups beneath them.
+            // This should never happen. Config should verify that each group
+            // has enough groups beneath them.
         assert(group._group != nullptr);
         getIdealGroups(bucket, clusterState, *group._group,
                        redundancyArray[i], results);