[mesos] 03/03: Avoided some recalculation in the random sorter.

[mz...@apache.org]

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 <mz...@mesosphere.io>
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;