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 <[email protected]> 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 {
