Merge pull request #16015 from vespa-engine/balder/optimize-by-using-vector-over-list

Replace the use of std::list with std::vector. This avoids a lof of n…

10 files changed, 128 insertions, 158 deletions

diff --git a/vdslib/src/vespa/vdslib/distribution/distribution.cpp b/vdslib/src/vespa/vdslib/distribution/distribution.cpp
index ac085ea5cbe..e622d0fd0d9 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) :
@@ -220,55 +221,44 @@ namespace {
 
     /** Used to record scored groups during ideal groups calculation. */
     struct ScoredGroup {
+        double       _score;
         const Group* _group;
-        double _score;
 
-        ScoredGroup() : _group(nullptr), _score(0) {}
-        ScoredGroup(const Group* group, double score) noexcept
-            : _group(group), _score(score) {}
+        ScoredGroup() noexcept : _score(0), _group(nullptr) { }
+        ScoredGroup(double score, const Group* group) noexcept
+            : _score(score), _group(group) { }
 
-        bool operator<(const ScoredGroup& other) const {
+        bool operator<(const ScoredGroup& other) const noexcept {
             return (_score > other._score);
         }
     };
 
     /** Used to record scored nodes during ideal nodes calculation. */
     struct ScoredNode {
+        double _score;
         uint16_t _index;
         uint16_t _reliability;
-        double _score;
 
-        ScoredNode(uint16_t index, uint16_t reliability, double score)
-            : _index(index), _reliability(reliability), _score(score) {}
+        ScoredNode() noexcept : _score(0), _index(0), _reliability(0) {}
+        ScoredNode(double score, uint16_t index, uint16_t reliability) noexcept
+            : _score(score), _index(index), _reliability(reliability) {}
 
-        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 +268,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;
@@ -293,6 +281,19 @@ namespace {
             }
         }
     }
+
+    void
+    insertOrdered(std::vector<ScoredNode> & tmpResults, ScoredNode && scoredNode) {
+        tmpResults.pop_back();
+        auto it = tmpResults.begin();
+        for (; it != tmpResults.end(); ++it) {
+            if (*it < scoredNode) {
+                tmpResults.insert(it, scoredNode);
+                return;
+            }
+        }
+        tmpResults.emplace_back(scoredNode);
+    }
 }
 
 void
@@ -323,7 +324,7 @@ Distribution::getIdealGroups(const document::BucketId& bucket,
             // Verified in Group::setCapacity()
             score = std::pow(score, 1.0 / g.second->getCapacity().getValue());
         }
-        tmpResults.emplace_back(g.second, score);
+        tmpResults.emplace_back(score, g.second);
     }
     std::sort(tmpResults.begin(), tmpResults.end());
     if (tmpResults.size() > redundancyArray.size()) {
@@ -347,26 +348,24 @@ Distribution::getIdealDistributorGroup(const document::BucketId& bucket,
     if (parent.isLeafGroup()) {
         return &parent;
     }
-    ScoredGroup result(0, 0);
+    ScoredGroup result;
     uint32_t seed(getGroupSeed(bucket, clusterState, parent));
     RandomGen random(seed);
     uint32_t currentIndex = 0;
     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();
+    for (const auto & subGroup : subGroups) {
+        while (subGroup.first < currentIndex++) random.nextDouble();
         double score = random.nextDouble();
-        if (it->second->getCapacity() != 1) {
+        if (subGroup.second->getCapacity() != 1) {
             // Capacity shouldn't possibly be 0.
             // Verified in Group::setCapacity()
-            score = std::pow(score, 1.0 / it->second->getCapacity().getValue());
+            score = std::pow(score, 1.0 / subGroup.second->getCapacity().getValue());
         }
         if (score > result._score) {
             if (!_distributorAutoOwnershipTransferOnWholeGroupDown
-                || !allDistributorsDown(*it->second, clusterState))
+                || !allDistributorsDown(*subGroup.second, clusterState))
             {
-                result = ScoredGroup(it->second, score);
+                result = ScoredGroup(score, subGroup.second);
             }
         }
     }
@@ -381,17 +380,12 @@ Distribution::allDistributorsDown(const Group& g, const ClusterState& cs)
 {
     if (g.isLeafGroup()) {
         for (uint32_t i=0, n=g.getNodes().size(); i<n; ++i) {
-            const NodeState& ns(cs.getNodeState(
-                    Node(NodeType::DISTRIBUTOR, g.getNodes()[i])));
+            const NodeState& ns(cs.getNodeState(Node(NodeType::DISTRIBUTOR, g.getNodes()[i])));
             if (ns.getState().oneOf("ui")) return false;
         }
     } else {
-        typedef std::map<uint16_t, Group*> GroupMap;
-        const GroupMap& subGroups(g.getSubGroups());
-        for (GroupMap::const_iterator it = subGroups.begin();
-             it != subGroups.end(); ++it)
-        {
-            if (!allDistributorsDown(*it->second, cs)) return false;
+        for (const auto & subGroup : g.getSubGroups()) {
+            if (!allDistributorsDown(*subGroup.second, cs)) return false;
         }
     }
     return true;
@@ -437,14 +431,17 @@ Distribution::getIdealNodes(const NodeType& nodeType,
     }
     RandomGen random(seed);
     uint32_t randomIndex = 0;
+    std::vector<ScoredNode> tmpResults;
     for (uint32_t i=0, n=_groupDistribution.size(); i<n; ++i) {
         uint16_t groupRedundancy(_groupDistribution[i]._redundancy);
         const std::vector<uint16_t>& nodes(_groupDistribution[i]._group->getNodes());
-        // Create temporary place to hold results. Use double linked list
-        // for cheap access to back(). Stuff in redundancy fake entries to
+        // Create temporary place to hold results.
+        // Stuff in redundancy fake entries to
         // avoid needing to check size during iteration.
-        std::list<ScoredNode> tmpResults(groupRedundancy, ScoredNode(0, 0, 0));
-        for (uint32_t j=0, m=nodes.size(); j<m; ++j) {
+        tmpResults.reserve(groupRedundancy);
+        tmpResults.clear();
+        tmpResults.resize(groupRedundancy);
+        for (uint32_t j=0; j < nodes.size(); ++j) {
             // Verify that the node is legal target before starting to grab
             // random number. Helps worst case of having to start new random
             // seed if the node that is out of order is illegal anyways.
@@ -469,15 +466,7 @@ 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)
-                {
-                    if (score > it->_score) {
-                        tmpResults.insert(it, ScoredNode(nodes[j], nodeState.getReliability(), score));
-                        break;
-                    }
-                }
-                tmpResults.pop_back();
+                insertOrdered(tmpResults, ScoredNode(score, nodes[j], nodeState.getReliability()));
             }
         }
         trimResult(tmpResults, groupRedundancy);
@@ -491,7 +480,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";
diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h b/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h
index 6d207b51a53..d1be4a2229c 100644
--- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h
+++ b/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h
@@ -11,8 +11,7 @@
 #include <vespa/vdslib/distribution/distribution.h>
 #include <vespa/vdslib/state/nodetype.h>
 
-namespace storage {
-namespace lib {
+namespace storage::lib {
 
 /**
  * A list of ideal nodes, sorted in preferred order. Wraps a vector to hide
@@ -59,7 +58,7 @@ public:
         UP_STATE_COUNT
     };
 
-    virtual ~IdealNodeCalculator() {}
+    virtual ~IdealNodeCalculator() = default;
 
     virtual IdealNodeList getIdealNodes(const NodeType&,
                                         const document::BucketId&,
@@ -88,5 +87,4 @@ public:
     virtual void setClusterState(const ClusterState&) = 0;
 };
 
-} // lib
-} // storage
+}
diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.cpp b/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.cpp
index 79a025c0d6a..8379018d4d7 100644
--- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.cpp
+++ b/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.cpp
@@ -7,11 +7,8 @@
 
 namespace storage::lib {
 
-IdealNodeList::IdealNodeList() :
-    _idealNodes()
-{ }
-
-IdealNodeList::~IdealNodeList() { }
+IdealNodeList::IdealNodeList() = default;
+IdealNodeList::~IdealNodeList() = default;
 
 void
 IdealNodeList::print(std::ostream& out, bool , const std::string &) const
@@ -31,7 +28,7 @@ IdealNodeCalculatorImpl::IdealNodeCalculatorImpl()
     initUpStateMapping();
 }
 
-IdealNodeCalculatorImpl::~IdealNodeCalculatorImpl() { }
+IdealNodeCalculatorImpl::~IdealNodeCalculatorImpl() = default;
 
 void
 IdealNodeCalculatorImpl::setDistribution(const Distribution& d) {
diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.h b/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.h
index 67b50da2335..4b55a732aee 100644
--- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.h
+++ b/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.h
@@ -7,8 +7,7 @@
 
 #include "idealnodecalculator.h"
 
-namespace storage {
-namespace lib {
+namespace storage::lib {
 
 class IdealNodeCalculatorImpl : public IdealNodeCalculatorConfigurable {
     std::vector<const char*> _upStates;
@@ -29,5 +28,4 @@ private:
     void initUpStateMapping();
 };
 
-} // lib
-} // storage
+}
diff --git a/vdslib/src/vespa/vdslib/state/clusterstate.cpp b/vdslib/src/vespa/vdslib/state/clusterstate.cpp
index ff792517bf9..983018c2a21 100644
--- a/vdslib/src/vespa/vdslib/state/clusterstate.cpp
+++ b/vdslib/src/vespa/vdslib/state/clusterstate.cpp
@@ -280,34 +280,40 @@ ClusterState::getNodeCount(const NodeType& type) const
     return _nodeCount[type];
 }
 
+namespace {
+    NodeState _G_defaultSDState(NodeType::STORAGE, State::DOWN);
+    NodeState _G_defaultDDState(NodeType::DISTRIBUTOR, State::DOWN);
+    NodeState _G_defaultSUState(NodeType::STORAGE, State::UP);
+    NodeState _G_defaultDUState(NodeType::DISTRIBUTOR, State::UP);
+    [[noreturn]] void throwUnknownType(const Node & node) __attribute__((noinline));
+    void throwUnknownType(const Node & node) {
+        throw vespalib::IllegalStateException("Unknown node type " + node.getType().toString(), VESPA_STRLOC);
+    }
+}
+
 const NodeState&
 ClusterState::getNodeState(const Node& node) const
 {
-        // If beyond node count, the node is down.
-    if (node.getIndex() >= _nodeCount[node.getType()]) {
-        if (node.getType() == NodeType::STORAGE) {
-            static NodeState defaultSDState(NodeType::STORAGE, State::DOWN);
-            return defaultSDState;
-        } else if (node.getType() == NodeType::DISTRIBUTOR) {
-            static NodeState defaultDDState(NodeType::DISTRIBUTOR, State::DOWN);
-            return defaultDDState;
-        }
-        throw vespalib::IllegalStateException(
-                "Unknown node type " + node.getType().toString(), VESPA_STRLOC);
-    }
-        // If it actually has an entry in map, return that
+    // If it actually has an entry in map, return that
     std::map<Node, NodeState>::const_iterator it = _nodeStates.find(node);
     if (it != _nodeStates.end()) return it->second;
+
+    // If beyond node count, the node is down.
+    if (__builtin_expect(node.getIndex() >= _nodeCount[node.getType()], false)) {
+        if (node.getType().getType() == NodeType::Type::STORAGE) {
+            return _G_defaultSDState;
+        } else if (node.getType().getType() == NodeType::Type::DISTRIBUTOR) {
+            return _G_defaultDDState;
+        }
+    } else {
         // If not mentioned in map but within node count, the node is up
-    if (node.getType() == NodeType::STORAGE) {
-        static NodeState defaultSUState(NodeType::STORAGE, State::UP);
-        return defaultSUState;
-    } else if (node.getType() == NodeType::DISTRIBUTOR) {
-        static NodeState defaultDUState(NodeType::DISTRIBUTOR, State::UP);
-        return defaultDUState;
+        if (node.getType().getType() == NodeType::Type::STORAGE) {
+            return _G_defaultSUState;
+        } else if (node.getType().getType() == NodeType::Type::DISTRIBUTOR) {
+            return _G_defaultDUState;
+        }
     }
-    throw vespalib::IllegalStateException(
-            "Unknown node type " + node.getType().toString(), VESPA_STRLOC);
+    throwUnknownType(node);
 }
 
 void
diff --git a/vdslib/src/vespa/vdslib/state/clusterstate.h b/vdslib/src/vespa/vdslib/state/clusterstate.h
index d034b45c71d..723703a1aa5 100644
--- a/vdslib/src/vespa/vdslib/state/clusterstate.h
+++ b/vdslib/src/vespa/vdslib/state/clusterstate.h
@@ -57,12 +57,10 @@ public:
     uint16_t getDistributionBitCount() const { return _distributionBits; }
     const State& getClusterState() const { return *_clusterState; }
     const NodeState& getNodeState(const Node& node) const;
-    const vespalib::string& getDescription() const { return _description; }
 
     void setVersion(uint32_t version) { _version = version; }
     void setClusterState(const State& state);
     void setNodeState(const Node& node, const NodeState& state);
-    void setDescription(vespalib::stringref s) { _description = s; }
     void setDistributionBitCount(uint16_t count) { _distributionBits = count; }
 
     void print(std::ostream& out, bool verbose, const std::string& indent) const override;
diff --git a/vdslib/src/vespa/vdslib/state/node.cpp b/vdslib/src/vespa/vdslib/state/node.cpp
index fa1bab0e4b6..f52ebad605e 100644
--- a/vdslib/src/vespa/vdslib/state/node.cpp
+++ b/vdslib/src/vespa/vdslib/state/node.cpp
@@ -2,21 +2,20 @@
 
 #include "node.h"
 #include <vespa/vespalib/stllike/asciistream.h>
+#include <ostream>
 
-namespace storage {
-namespace lib {
+namespace storage::lib {
 
-Node::Node(const NodeType& type, uint16_t index)
-    : _type(&type),
-      _index(index)
+std::ostream &
+operator << (std::ostream & os, const Node & node)
 {
+    return os << node.getType() << '.' << node.getIndex();
 }
 
-void
-Node::print(vespalib::asciistream& as, const PrintProperties&) const
+vespalib::asciistream &
+operator << (vespalib::asciistream & os, const Node & node)
 {
-    as << *_type << '.' << _index;
+    return os << node.getType() << '.' << node.getIndex();
 }
 
-} // lib
-} // storage
+}
diff --git a/vdslib/src/vespa/vdslib/state/node.h b/vdslib/src/vespa/vdslib/state/node.h
index 4184bb5a05e..293ed8defa5 100644
--- a/vdslib/src/vespa/vdslib/state/node.h
+++ b/vdslib/src/vespa/vdslib/state/node.h
@@ -8,28 +8,27 @@
 #pragma once
 
 #include "nodetype.h"
-#include <vespa/vespalib/util/printable.h>
 
-namespace storage {
-namespace lib {
+namespace storage::lib {
 
-class Node : public vespalib::AsciiPrintable {
+class Node {
     const NodeType* _type;
     uint16_t _index;
 
 public:
-    Node() : _type(&NodeType::STORAGE), _index(0) {}
-    Node(const NodeType& type, uint16_t index);
+    Node() noexcept : _type(&NodeType::STORAGE), _index(0) { }
+    Node(const NodeType& type, uint16_t index) noexcept
+        : _type(&type), _index(index) { }
 
     const NodeType& getType() const { return *_type; }
     uint16_t getIndex() const { return _index; }
 
-    void print(vespalib::asciistream&, const PrintProperties&) const override;
-
-    bool operator==(const Node& other) const
-        { return (other._index == _index && *other._type == *_type); }
-    bool operator!=(const Node& other) const
-        { return (other._index != _index || *other._type != *_type); }
+    bool operator==(const Node& other) const {
+        return (other._index == _index && *other._type == *_type);
+    }
+    bool operator!=(const Node& other) const {
+        return (other._index != _index || *other._type != *_type);
+    }
 
     bool operator<(const Node& n) const {
         if (*_type != *n._type) return (*_type < *n._type);
@@ -37,5 +36,7 @@ public:
     }
 };
 
-} // lib
-} // storage
+std::ostream & operator << (std::ostream & os, const Node & n);
+vespalib::asciistream & operator << (vespalib::asciistream & os, const Node & n);
+
+}
diff --git a/vdslib/src/vespa/vdslib/state/state.cpp b/vdslib/src/vespa/vdslib/state/state.cpp
index 96829905c8a..03997470188 100644
--- a/vdslib/src/vespa/vdslib/state/state.cpp
+++ b/vdslib/src/vespa/vdslib/state/state.cpp
@@ -4,23 +4,15 @@
 
 #include <vespa/vespalib/util/exceptions.h>
 
-namespace storage {
-namespace lib {
+namespace storage::lib {
 
-const State State::UNKNOWN("Unknown", "-", 0,
-        true,  true,  false, false, false);
-const State State::MAINTENANCE("Maintenance", "m", 1,
-        false, false, true,  true,  false);
-const State State::DOWN("Down", "d", 2,
-        false, false, true,  true,  true);
-const State State::STOPPING("Stopping", "s", 3,
-        true,  true,  false, false, true);
-const State State::INITIALIZING("Initializing", "i", 4,
-        true,  true,  false, false, true);
-const State State::RETIRED("Retired", "r", 5,
-        false, false, true, true,  false);
-const State State::UP("Up", "u", 6,
-        true,  true,  true,  true,  true);
+const State State::UNKNOWN("Unknown", "-", 0, true,  true,  false, false, false);
+const State State::MAINTENANCE("Maintenance", "m", 1, false, false, true,  true,  false);
+const State State::DOWN("Down", "d", 2, false, false, true,  true,  true);
+const State State::STOPPING("Stopping", "s", 3, true,  true,  false, false, true);
+const State State::INITIALIZING("Initializing", "i", 4, true,  true,  false, false, true);
+const State State::RETIRED("Retired", "r", 5, false, false, true, true,  false);
+const State State::UP("Up", "u", 6, true,  true,  true,  true,  true);
 
 const State&
 State::get(vespalib::stringref serialized)
@@ -61,9 +53,7 @@ State::State(vespalib::stringref name, vespalib::stringref serialized,
     _validWantedNodeState[distributor] = validDistributorWanted;
 }
 
-State::~State()
-{
-}
+State::~State() = default;
 
 void
 State::print(std::ostream& out, bool verbose, const std::string& indent) const
@@ -72,14 +62,4 @@ State::print(std::ostream& out, bool verbose, const std::string& indent) const
     out << (verbose ? _name : _serialized);
 }
 
-bool
-State::oneOf(const char* states) const
-{
-    for (const char* c = states; *c != '\0'; ++c) {
-        if (*c == _serialized[0]) return true;
-    }
-    return false;
 }
-
-} // lib
-} // storage
diff --git a/vdslib/src/vespa/vdslib/state/state.h b/vdslib/src/vespa/vdslib/state/state.h
index 61747f5eed2..d49795dc22d 100644
--- a/vdslib/src/vespa/vdslib/state/state.h
+++ b/vdslib/src/vespa/vdslib/state/state.h
@@ -47,14 +47,13 @@ public:
     static const State& get(vespalib::stringref serialized);
     const vespalib::string& serialize() const { return _serialized; }
 
-    bool validReportedNodeState(const NodeType& node) const
-        { return _validReportedNodeState[node]; }
-    bool validWantedNodeState(const NodeType& node) const
-        { return _validWantedNodeState[node]; }
+    bool validReportedNodeState(const NodeType& node) const { return _validReportedNodeState[node]; }
+    bool validWantedNodeState(const NodeType& node) const { return _validWantedNodeState[node]; }
     bool validClusterState() const { return _validClusterState; }
 
-    bool maySetWantedStateForThisNodeState(const State& wantedState) const
-        { return (wantedState._rankValue <= _rankValue); }
+    bool maySetWantedStateForThisNodeState(const State& wantedState) const {
+        return (wantedState._rankValue <= _rankValue);
+    }
 
     /**
      * Get a string that represents a more human readable version of
@@ -76,7 +75,12 @@ public:
      * states, given as the single character they are serialized as.
      * For instance, "um" will check if this state is up or maintenance.
      */
-    bool oneOf(const char* states) const;
+    bool oneOf(const char* states) const {
+        for (const char* c = states; *c != '\0'; ++c) {
+            if (*c == _serialized[0]) return true;
+        }
+        return false;
+    }
 };
 
 }