Replace the use of std::list with std::vector. This avoids a lof of new/delete.

The number of elements that are moved around is small and significantly less than
the gain by more efficient memory management.

1 files changed, 16 insertions, 28 deletions

diff --git a/vdslib/src/vespa/vdslib/distribution/distribution.cpp b/vdslib/src/vespa/vdslib/distribution/distribution.cpp
index ac085ea5cbe..897c0a0ae8e 100644
--- a/vdslib/src/vespa/vdslib/distribution/distribution.cpp
+++ b/vdslib/src/vespa/vdslib/distribution/distribution.cpp
@@ -70,6 +70,7 @@ Distribution::Distribution(const Distribution& d)
 Distribution::ConfigWrapper::ConfigWrapper(std::unique_ptr<DistributionConfig> cfg) :
     _cfg(std::move(cfg))
 { }
+
 Distribution::ConfigWrapper::~ConfigWrapper() = default;
 
 Distribution::Distribution(const ConfigWrapper & config) :
@@ -227,7 +228,7 @@ namespace {
         ScoredGroup(const Group* group, double score) noexcept
             : _group(group), _score(score) {}
 
-        bool operator<(const ScoredGroup& other) const {
+        bool operator<(const ScoredGroup& other) const noexcept {
             return (_score > other._score);
         }
     };
@@ -238,37 +239,24 @@ namespace {
         uint16_t _reliability;
         double _score;
 
-        ScoredNode(uint16_t index, uint16_t reliability, double score)
+        ScoredNode(uint16_t index, uint16_t reliability, double score) noexcept
             : _index(index), _reliability(reliability), _score(score) {}
 
-        bool operator<(const ScoredNode& other) const {
+        bool operator<(const ScoredNode& other) const noexcept {
             return (_score < other._score);
         }
     };
 
-    struct IndexSorter {
-        const std::vector<ScoredGroup>& _groups;
-
-        IndexSorter(const std::vector<ScoredGroup>& groups) : _groups(groups) {}
-
-        bool operator()(uint16_t a, uint16_t b) {
-            return (_groups[a]._group->getIndex()
-                        < _groups[b]._group->getIndex());
-        }
-    };
-
     /**
      * Throw away last entries until throwing away another would
      * decrease redundancy below total reliability. If redundancy !=
      * total reliability, see if non-last entries can be removed.
      */
-    void trimResult(std::list<ScoredNode>& nodes, uint16_t redundancy) {
+    void trimResult(std::vector<ScoredNode>& nodes, uint16_t redundancy) {
             // Initially record total reliability and use the first elements
             // until satisfied.
         uint32_t totalReliability = 0;
-        for (std::list<ScoredNode>::iterator it = nodes.begin();
-             it != nodes.end(); ++it)
-        {
+        for (auto it = nodes.begin(); it != nodes.end(); ++it) {
             if (totalReliability >= redundancy || it->_reliability == 0) {
                 nodes.erase(it, nodes.end());
                 break;
@@ -278,12 +266,10 @@ namespace {
             // If we have too high reliability, see if we can remove something
             // else
         if (totalReliability > redundancy) {
-            for (std::list<ScoredNode>::reverse_iterator it = nodes.rbegin();
-                    it != nodes.rend();)
-            {
+            for (auto it = nodes.rbegin(); it != nodes.rend();) {
                 if (it->_reliability <= (totalReliability - redundancy)) {
                     totalReliability -= it->_reliability;
-                    std::list<ScoredNode>::iterator deleteIt(it.base());
+                    auto deleteIt(it.base());
                     ++it;
                     nodes.erase(--deleteIt);
                     if (totalReliability == redundancy) break;
@@ -443,7 +429,7 @@ Distribution::getIdealNodes(const NodeType& nodeType,
         // Create temporary place to hold results. Use double linked list
         // for cheap access to back(). Stuff in redundancy fake entries to
         // avoid needing to check size during iteration.
-        std::list<ScoredNode> tmpResults(groupRedundancy, ScoredNode(0, 0, 0));
+        std::vector<ScoredNode> tmpResults(groupRedundancy, ScoredNode(0, 0, 0));
         for (uint32_t j=0, m=nodes.size(); j<m; ++j) {
             // Verify that the node is legal target before starting to grab
             // random number. Helps worst case of having to start new random
@@ -469,15 +455,17 @@ Distribution::getIdealNodes(const NodeType& nodeType,
                 score = std::pow(score, 1.0 / nodeState.getCapacity().getValue());
             }
             if (score > tmpResults.back()._score) {
-                for (std::list<ScoredNode>::iterator it = tmpResults.begin();
-                     it != tmpResults.end(); ++it)
-                {
+                tmpResults.pop_back();
+                auto it = tmpResults.begin();
+                for (; it != tmpResults.end(); ++it) {
                     if (score > it->_score) {
                         tmpResults.insert(it, ScoredNode(nodes[j], nodeState.getReliability(), score));
                         break;
                     }
                 }
-                tmpResults.pop_back();
+                if (it == tmpResults.end()) {
+                    tmpResults.emplace_back(nodes[j], nodeState.getReliability(), score);
+                }
             }
         }
         trimResult(tmpResults, groupRedundancy);
@@ -491,7 +479,7 @@ Distribution::getIdealNodes(const NodeType& nodeType,
 Distribution::ConfigWrapper
 Distribution::getDefaultDistributionConfig(uint16_t redundancy, uint16_t nodeCount)
 {
-    std::unique_ptr<vespa::config::content::StorDistributionConfigBuilder> config(new vespa::config::content::StorDistributionConfigBuilder());
+    auto config = std::make_unique<vespa::config::content::StorDistributionConfigBuilder>();
     config->redundancy = redundancy;
     config->group.resize(1);
     config->group[0].index = "invalid";