diff options
author | Arnstein Ressem <aressem@gmail.com> | 2020-06-26 00:19:39 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-06-26 00:19:39 +0200 |
commit | 41ef8c7bc65222d92839aa2ea65c07ef67db9679 (patch) | |
tree | 7ad165e86f57fd69f1ed8b6e6d5c69b859122427 /vdslib | |
parent | c997017dc89cd6ce7d16b6afee718cfcf99f2d80 (diff) |
Revert "Only sort once during ideal group calculations"
Diffstat (limited to 'vdslib')
-rw-r--r-- | vdslib/src/tests/distribution/distributiontest.cpp | 54 | ||||
-rw-r--r-- | vdslib/src/vespa/vdslib/distribution/distribution.cpp | 45 |
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); |