[mesos] 03/10: Added a ScalarResourceQuantities type to improve sorters performance.

[bm...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

bmahler pushed a commit to branch 1.7.x
in repository https://gitbox.apache.org/repos/asf/mesos.git

commit c3f32c5a45aa6b326328f77a1ae546ee7fd18a93
Author: Benjamin Mahler <bm...@apache.org>
AuthorDate: Sun Sep 16 16:37:38 2018 -0700

    Added a ScalarResourceQuantities type to improve sorters performance.
    
    This type replaces the use of hashmaps keyed by resource names in
    favor of storing vectors of `pair<string,Value::Scalar>`, in order
    to avoid the performance penalty of using hashmaps.
    
    Running *HierarchicalAllocator_BENCHMARK_Test.DeclineOffers/21 shows
    the following improvement:
    
    Using 10000 agents and 1000 frameworks
    Added 1000 frameworks in 42.49ms -> 42.85ms (no change)
    Added 10000 agents in 7.69secs -> 4.89secs (normalized: 1 -> 0.64)
    round 0 allocate() took 5.42secs -> 3.53secs (nomralized: 1 -> 0.65)
    
    Review: https://reviews.apache.org/r/68731
---
 src/master/allocator/sorter/drf/sorter.hpp    | 26 ++++-----
 src/master/allocator/sorter/random/sorter.hpp | 26 ++++-----
 src/master/allocator/sorter/sorter.hpp        | 84 +++++++++++++++++++++++++++
 3 files changed, 108 insertions(+), 28 deletions(-)

diff --git a/src/master/allocator/sorter/drf/sorter.hpp b/src/master/allocator/sorter/drf/sorter.hpp
index 71352c8..2957a2e 100644
--- a/src/master/allocator/sorter/drf/sorter.hpp
+++ b/src/master/allocator/sorter/drf/sorter.hpp
@@ -169,14 +169,13 @@ private:
     // identities of resources and not quantities.
     Resources scalarQuantities;
 
-    // We also store a map version of `scalarQuantities`, mapping
-    // the `Resource::name` to aggregated scalar. This improves the
-    // performance of calculating shares. See MESOS-4694.
+    // To improve the performance of calculating shares, we store
+    // a redundant but more efficient version of `scalarQuantities`.
+    // See MESOS-4694.
     //
-    // TODO(bmahler): Ideally we do not store `scalarQuantities`
-    // redundantly here, investigate performance improvements to
-    // `Resources` to make this unnecessary.
-    hashmap<std::string, Value::Scalar> totals;
+    // TODO(bmahler): Can we remove `scalarQuantities` in favor of
+    // using this type whenever scalar quantities are needed?
+    ScalarResourceQuantities totals;
   } total_;
 
   // Metrics are optionally exposed by the sorter.
@@ -430,14 +429,13 @@ struct DRFSorter::Node
     // the corresponding resource. See notes above.
     Resources scalarQuantities;
 
-    // We also store a map version of `scalarQuantities`, mapping
-    // the `Resource::name` to aggregated scalar. This improves the
-    // performance of calculating shares. See MESOS-4694.
+    // To improve the performance of calculating shares, we store
+    // a redundant but more efficient version of `scalarQuantities`.
+    // See MESOS-4694.
     //
-    // TODO(bmahler): Ideally we do not store `scalarQuantities`
-    // redundantly here, investigate performance improvements to
-    // `Resources` to make this unnecessary.
-    hashmap<std::string, Value::Scalar> totals;
+    // TODO(bmahler): Can we remove `scalarQuantities` in favor of
+    // using this type whenever scalar quantities are needed?
+    ScalarResourceQuantities totals;
   } allocation;
 
   // Compares two nodes according to DRF share.
diff --git a/src/master/allocator/sorter/random/sorter.hpp b/src/master/allocator/sorter/random/sorter.hpp
index 6bfeda0..825c158 100644
--- a/src/master/allocator/sorter/random/sorter.hpp
+++ b/src/master/allocator/sorter/random/sorter.hpp
@@ -167,14 +167,13 @@ private:
     // identities of resources and not quantities.
     Resources scalarQuantities;
 
-    // We also store a map version of `scalarQuantities`, mapping
-    // the `Resource::name` to aggregated scalar. This improves the
-    // performance of calculating shares. See MESOS-4694.
+    // To improve the performance of calculating shares, we store
+    // a redundant but more efficient version of `scalarQuantities`.
+    // See MESOS-4694.
     //
-    // TODO(bmahler): Ideally we do not store `scalarQuantities`
-    // redundantly here, investigate performance improvements to
-    // `Resources` to make this unnecessary.
-    hashmap<std::string, Value::Scalar> totals;
+    // TODO(bmahler): Can we remove `scalarQuantities` in favor of
+    // using this type whenever scalar quantities are needed?
+    ScalarResourceQuantities totals;
   } total_;
 };
 
@@ -406,14 +405,13 @@ struct RandomSorter::Node
     // the corresponding resource. See notes above.
     Resources scalarQuantities;
 
-    // We also store a map version of `scalarQuantities`, mapping
-    // the `Resource::name` to aggregated scalar. This improves the
-    // performance of calculating shares. See MESOS-4694.
+    // To improve the performance of calculating shares, we store
+    // a redundant but more efficient version of `scalarQuantities`.
+    // See MESOS-4694.
     //
-    // TODO(bmahler): Ideally we do not store `scalarQuantities`
-    // redundantly here, investigate performance improvements to
-    // `Resources` to make this unnecessary.
-    hashmap<std::string, Value::Scalar> totals;
+    // TODO(bmahler): Can we remove `scalarQuantities` in favor of
+    // using this type whenever scalar quantities are needed?
+    ScalarResourceQuantities totals;
   } allocation;
 };
 
diff --git a/src/master/allocator/sorter/sorter.hpp b/src/master/allocator/sorter/sorter.hpp
index 432ccfe..68cf698 100644
--- a/src/master/allocator/sorter/sorter.hpp
+++ b/src/master/allocator/sorter/sorter.hpp
@@ -19,6 +19,7 @@
 
 #include <functional>
 #include <string>
+#include <utility>
 #include <vector>
 
 #include <mesos/resources.hpp>
@@ -148,6 +149,89 @@ public:
   virtual size_t count() const = 0;
 };
 
+// Efficient type for scalar resource quantities that avoids
+// the overhead of using `Resources`.
+//
+// TODO(bmahler): This was originally added to replace a
+// `hashmap<string, Scalar>` and hence the interface was
+// tailored to the particular usage of the map. In order
+// to move this up as a replacement of all quantities
+// (e.g. `Resources::createStrippedScalarQuantity()`),
+// this will need more functionality to do so (e.g.
+// arithmetic operators, containment check, etc).
+class ScalarResourceQuantities
+{
+public:
+  ScalarResourceQuantities()
+  {
+    // Pre-reserve space for first-class scalars.
+    quantities.reserve(4u);  // [cpus, disk, gpus, mem]
+  }
+
+  // Returns true if there is a non-zero amount of
+  // the specified resource.
+  bool contains(const std::string& name) const
+  {
+    // Don't bother binary searching since we don't expect
+    // a large number of quantities.
+    foreach (auto& quantity, quantities) {
+      if (quantity.first == name) {
+        return quantity.second.value() > 0.0;
+      }
+    }
+
+    return false;
+  }
+
+  const Value::Scalar& at(const std::string& name) const
+  {
+    // Don't bother binary searching since we don't expect
+    // a large number of quantities.
+    foreach (auto& quantity, quantities) {
+      if (quantity.first == name) {
+        return quantity.second;
+      }
+    }
+
+    // TODO(bmahler): Print out the vector, need to add
+    // a `stringify(const pair<T1, T2>& p)` overload.
+    LOG(FATAL) << "Failed to find '" << name << "'";
+  }
+
+  Value::Scalar& operator[](const std::string& name)
+  {
+    // Find the location to insert while maintaining
+    // alphabetical ordering. Don't bother binary searching
+    // since we don't expect a large number of quantities.
+    auto it = quantities.begin();
+    for (; it != quantities.end(); ++it) {
+      if (it->first == name) {
+        return it->second;
+      }
+
+      if (it->first > name) {
+        break;
+      }
+    }
+
+    it = quantities.insert(it, std::make_pair(name, Value::Scalar()));
+
+    return it->second;
+  }
+
+  typedef std::vector<std::pair<std::string, Value::Scalar>>::const_iterator
+    const_iterator;
+
+  const_iterator begin() const { return quantities.begin(); }
+  const_iterator   end() const { return quantities.end(); }
+
+private:
+  // List of scalar resources sorted by resource name.
+  // Arithmetic operations benefit from this sorting.
+  std::vector<std::pair<std::string, Value::Scalar>> quantities;
+};
+
+
 } // namespace allocator {
 } // namespace master {
 } // namespace internal {