This is an automated email from the ASF dual-hosted git repository. mzhu pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/mesos.git
commit 5108f076e6a5c275cae6b124bbcb110bc6785f94 Author: Meng Zhu <[email protected]> AuthorDate: Wed Apr 24 11:32:38 2019 -0700 Avoided some recalculation in the random sorter. This patch keeps the sorting related information in the memory and accompanies a dirty bit with it. This helps to avoid unnecessary recalculation of this info in `sort()`. Review: https://reviews.apache.org/r/70430 --- src/master/allocator/sorter/random/sorter.cpp | 22 ++++++++++++++++++++-- src/master/allocator/sorter/random/sorter.hpp | 10 ++++++---- 2 files changed, 26 insertions(+), 6 deletions(-) diff --git a/src/master/allocator/sorter/random/sorter.cpp b/src/master/allocator/sorter/random/sorter.cpp index 8cf01e3..f4132bb 100644 --- a/src/master/allocator/sorter/random/sorter.cpp +++ b/src/master/allocator/sorter/random/sorter.cpp @@ -47,13 +47,13 @@ namespace allocator { RandomSorter::RandomSorter() - : root(new Node("", Node::INTERNAL, nullptr)) {} + : sortInfo(this), root(new Node("", Node::INTERNAL, nullptr)) {} RandomSorter::RandomSorter( const UPID& allocator, const string& metricsPrefix) - : root(new Node("", Node::INTERNAL, nullptr)) {} + : sortInfo(this), root(new Node("", Node::INTERNAL, nullptr)) {} RandomSorter::~RandomSorter() @@ -70,6 +70,8 @@ void RandomSorter::add(const string& clientPath) { CHECK(!clients.contains(clientPath)) << clientPath; + sortInfo.dirty = true; + // Adding a client is a two phase algorithm: // // root @@ -160,6 +162,8 @@ void RandomSorter::add(const string& clientPath) void RandomSorter::remove(const string& clientPath) { + sortInfo.dirty = true; + Node* current = CHECK_NOTNULL(find(clientPath)); // Save a copy of the leaf node's allocated resources, because we @@ -237,6 +241,8 @@ void RandomSorter::remove(const string& clientPath) void RandomSorter::activate(const string& clientPath) { + sortInfo.dirty = true; + Node* client = CHECK_NOTNULL(find(clientPath)); if (client->kind == Node::INACTIVE_LEAF) { @@ -254,6 +260,8 @@ void RandomSorter::activate(const string& clientPath) void RandomSorter::deactivate(const string& clientPath) { + sortInfo.dirty = true; + Node* client = CHECK_NOTNULL(find(clientPath)); if (client->kind == Node::ACTIVE_LEAF) { @@ -271,6 +279,8 @@ void RandomSorter::deactivate(const string& clientPath) void RandomSorter::updateWeight(const string& path, double weight) { + sortInfo.dirty = true; + weights[path] = weight; // Update the weight of the corresponding internal node, @@ -562,6 +572,10 @@ RandomSorter::SortInfo::getClientsAndWeights() void RandomSorter::SortInfo::updateRelativeWeights() { + if (!dirty) { + return; + } + hashset<Node*> activeInternalNodes = sorter->activeInternalNodes(); auto isActive = [&activeInternalNodes](Node* node) { @@ -569,6 +583,8 @@ void RandomSorter::SortInfo::updateRelativeWeights() activeInternalNodes.contains(node); }; + // Note, though we reserve here, the size of the vector will always + // grow (as we add more roles). clients.reserve(sorter->clients.size()); weights.reserve(sorter->clients.size()); @@ -612,6 +628,8 @@ void RandomSorter::SortInfo::updateRelativeWeights() }; calculateRelativeWeights(sorter->root, 0.0, 1.0); + + dirty = false; } } // namespace allocator { diff --git a/src/master/allocator/sorter/random/sorter.hpp b/src/master/allocator/sorter/random/sorter.hpp index 15bc75c..55e22d7 100644 --- a/src/master/allocator/sorter/random/sorter.hpp +++ b/src/master/allocator/sorter/random/sorter.hpp @@ -134,18 +134,20 @@ private: Node* find(const std::string& clientPath) const; // Sorting related info are kept in memory to avoid recalculations. - // - // TODO(mzhu): Keep this in the memory to avoid recalculations. struct SortInfo { public: - SortInfo(const RandomSorter* sorter_) : sorter(sorter_) {} + SortInfo(const RandomSorter* sorter_) : dirty(true), sorter(sorter_) {} // Returns a pair of vectors which are active clients and // their corresponding relative weights. std::pair<std::vector<std::string>, std::vector<double>> getClientsAndWeights(); + // A dirty bit indicates whether the info is up-to-date + // and requires recalculation. + bool dirty; + private: void updateRelativeWeights(); @@ -160,7 +162,7 @@ private: std::vector<double> weights; const RandomSorter* sorter; - }; + } sortInfo; // Used for random number generation. std::mt19937 generator;
