You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@mesos.apache.org by "Joerg Schad (JIRA)" <ji...@apache.org> on 2015/09/09 05:54:46 UTC
[jira] [Comment Edited] (MESOS-3051) performance issues with port
ranges comparison
[ https://issues.apache.org/jira/browse/MESOS-3051?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14734878#comment-14734878 ]
Joerg Schad edited comment on MESOS-3051 at 9/9/15 3:54 AM:
------------------------------------------------------------
The proposed approach is to reduce the number of new Ranges objects and try to reuse existing objects as much as possible to avoid the allocations/destructions seen above.
We add an optimized {code}coalesce(Value::Ranges* ranges){code} function.
Furthermore we try to add invariants to Ranges (or least the coalesce function(s)).
All coalesce functions now have the preconditions that their input range collection is sorted in ascending order of the begin value of each range. We feel this assumption is plausible as the coalesce is only called from values.cpp.
*void coalesce(Value::Ranges\* ranges)*
The algorithm is the following: For each range we try to merge it with the following ranges (due to the sort precondition we don't
have to check only until the first non-matching range). If ranges are overlapping/neighboring, we merge them and remove the merged ranges. If ranges are disjoint,
we stop and continue checking from the next range.
*void coalesce(Value::Ranges\* ranges, const Value::Range& range)*
The algorithm is the following: Recall that 'ranges' We try to to find the first range overlapping/neighboring with the added 'range' and merge both.
If this extends the range (i.e. new end) we check whether further ranges need to be merged.
was (Author: js84):
The proposed approach is to reduce the number of new Ranges objects and try to reuse existing objects as much as possible to avoid the allocations/destructions seen above.
We add an optimized {code}coalesce(Value::Ranges* ranges){code} function.
Furthermore we try to add invariants to Ranges (or least the coalesce function(s)).
All coalesce functions now have the preconditions that their input range collection is sorted in ascending order of the begin value of each range. This assumptions makes coalescing ranges more efficient (see below), but also has drawbacks (see alternative to deleteRange() below). We feel this assumption is plausible as the coalesce is only called from values.cpp.
*void coalesce(Value::Ranges\* ranges)*
The algorithm is the following: For each range we try to merge it with the following ranges (due to the sort precondition we don't
have to check only until the first non-matching range). If ranges are overlapping/neighboring, we merge them and remove the merged ranges. If ranges are disjoint,
we stop and continue checking from the next range.
*void coalesce(Value::Ranges\* ranges, const Value::Range& range)*
The algorithm is the following: Recall that 'ranges' We try to to find the first range overlapping/neighboring with the added 'range' and merge both.
If this extends the range (i.e. new end) we check whether further ranges need to be merged.
*Problematic DeleteSubrange()*
We use DeleteSubrange() when we need to remove Subranges. This has the problem that it will shift all further elements.
We could alternatively swap the to-be-deleted element to the end and remove the last one (would destroy sorting).
> performance issues with port ranges comparison
> ----------------------------------------------
>
> Key: MESOS-3051
> URL: https://issues.apache.org/jira/browse/MESOS-3051
> Project: Mesos
> Issue Type: Bug
> Components: allocation
> Affects Versions: 0.22.1
> Reporter: James Peach
> Assignee: Joerg Schad
> Labels: mesosphere
>
> Testing in an environment with lots of frameworks (>200), where the frameworks permanently decline resources they don't need. The allocator ends up spending a lot of time figuring out whether offers are refused (the code path through {{HierarchicalAllocatorProcess::isFiltered()}}.
> In profiling a synthetic benchmark, it turns out that comparing port ranges is very expensive, involving many temporary allocations. 61% of Resources::contains() run time is in operator -= (Resource). 35% of Resources::contains() run time is in Resources::_contains().
> The heaviest call chain through {{Resources::_contains}} is:
> {code}
> Running Time Self (ms) Symbol Name
> 7237.0ms 35.5% 4.0 mesos::Resources::_contains(mesos::Resource const&) const
> 7200.0ms 35.3% 1.0 mesos::contains(mesos::Resource const&, mesos::Resource const&)
> 7133.0ms 35.0% 121.0 mesos::operator<=(mesos::Value_Ranges const&, mesos::Value_Ranges const&)
> 6319.0ms 31.0% 7.0 mesos::coalesce(mesos::Value_Ranges*, mesos::Value_Ranges const&)
> 6240.0ms 30.6% 161.0 mesos::coalesce(mesos::Value_Ranges*, mesos::Value_Range const&)
> 1867.0ms 9.1% 25.0 mesos::Value_Ranges::add_range()
> 1694.0ms 8.3% 4.0 mesos::Value_Ranges::~Value_Ranges()
> 1495.0ms 7.3% 16.0 mesos::Value_Ranges::operator=(mesos::Value_Ranges const&)
> 445.0ms 2.1% 94.0 mesos::Value_Range::MergeFrom(mesos::Value_Range const&)
> 154.0ms 0.7% 24.0 mesos::Value_Ranges::range(int) const
> 103.0ms 0.5% 24.0 mesos::Value_Ranges::range_size() const
> 95.0ms 0.4% 2.0 mesos::Value_Range::Value_Range(mesos::Value_Range const&)
> 59.0ms 0.2% 4.0 mesos::Value_Ranges::Value_Ranges()
> 50.0ms 0.2% 50.0 mesos::Value_Range::begin() const
> 28.0ms 0.1% 28.0 mesos::Value_Range::end() const
> 26.0ms 0.1% 0.0 mesos::Value_Range::~Value_Range()
> {code}
> mesos::coalesce(Value_Ranges) gets done a lot and ends up being really expensive. The heaviest parts of the inverted call chain are:
> {code}
> Running Time Self (ms) Symbol Name
> 3209.0ms 15.7% 3209.0 mesos::Value_Range::~Value_Range()
> 3209.0ms 15.7% 0.0 google::protobuf::internal::GenericTypeHandler<mesos::Value_Range>::Delete(mesos::Value_Range*)
> 3209.0ms 15.7% 0.0 void google::protobuf::internal::RepeatedPtrFieldBase::Destroy<google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler>()
> 3209.0ms 15.7% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::~RepeatedPtrField()
> 3209.0ms 15.7% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::~RepeatedPtrField()
> 3209.0ms 15.7% 0.0 mesos::Value_Ranges::~Value_Ranges()
> 3209.0ms 15.7% 0.0 mesos::Value_Ranges::~Value_Ranges()
> 2441.0ms 11.9% 0.0 mesos::coalesce(mesos::Value_Ranges*, mesos::Value_Range const&)
> 452.0ms 2.2% 0.0 mesos::remove(mesos::Value_Ranges*, mesos::Value_Range const&)
> 169.0ms 0.8% 0.0 mesos::operator<=(mesos::Value_Ranges const&, mesos::Value_Ranges const&)
> 82.0ms 0.4% 0.0 mesos::operator-=(mesos::Value_Ranges&, mesos::Value_Ranges const&)
> 65.0ms 0.3% 0.0 mesos::Value_Ranges::~Value_Ranges()
> 2541.0ms 12.4% 2541.0 google::protobuf::internal::GenericTypeHandler<mesos::Value_Range>::New()
> 2541.0ms 12.4% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler::Type* google::protobuf::internal::RepeatedPtrFieldBase::Add<google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler>()
> 2305.0ms 11.3% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::Add()
> 2305.0ms 11.3% 0.0 mesos::Value_Ranges::add_range()
> 1962.0ms 9.6% 0.0 mesos::coalesce(mesos::Value_Ranges*, mesos::Value_Range const&)
> 343.0ms 1.6% 0.0 mesos::ranges::add(mesos::Value_Ranges*, long long, long long)
> 236.0ms 1.1% 0.0 void google::protobuf::internal::RepeatedPtrFieldBase::MergeFrom<google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler>(google::protobuf::internal::RepeatedPtrFieldBase const&)
> 1471.0ms 7.2% 1471.0 google::protobuf::internal::RepeatedPtrFieldBase::Reserve(int)
> 1333.0ms 6.5% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler::Type* google::protobuf::internal::RepeatedPtrFieldBase::Add<google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler>()
> 1333.0ms 6.5% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::Add()
> 1333.0ms 6.5% 0.0 mesos::Value_Ranges::add_range()
> 1086.0ms 5.3% 0.0 mesos::coalesce(mesos::Value_Ranges*, mesos::Value_Range const&)
> 247.0ms 1.2% 0.0 mesos::ranges::add(mesos::Value_Ranges*, long long, long long)
> 107.0ms 0.5% 0.0 void google::protobuf::internal::RepeatedPtrFieldBase::MergeFrom<google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler>(google::protobuf::internal::RepeatedPtrFieldBase const&)
> 107.0ms 0.5% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::MergeFrom(google::protobuf::RepeatedPtrField<mesos::Value_Range> const&)
> 107.0ms 0.5% 0.0 mesos::Value_Ranges::MergeFrom(mesos::Value_Ranges const&)
> 105.0ms 0.5% 0.0 mesos::Value_Ranges::CopyFrom(mesos::Value_Ranges const&)
> 105.0ms 0.5% 0.0 mesos::Value_Ranges::operator=(mesos::Value_Ranges const&)
> 104.0ms 0.5% 0.0 mesos::coalesce(mesos::Value_Ranges*, mesos::Value_Range const&)
> 1.0ms 0.0% 0.0 mesos::remove(mesos::Value_Ranges*, mesos::Value_Range const&)
> 2.0ms 0.0% 0.0 mesos::Resource::MergeFrom(mesos::Resource const&)
> 2.0ms 0.0% 0.0 google::protobuf::internal::GenericTypeHandler<mesos::Resource>::Merge(mesos::Resource const&, mesos::Resource*)
> 2.0ms 0.0% 0.0 void google::protobuf::internal::RepeatedPtrFieldBase::MergeFrom<google::protobuf::RepeatedPtrField<mesos::Resource>::TypeHandler>(google::protobuf::internal::RepeatedPtrFieldBase const&)
> 29.0ms 0.1% 0.0 void google::protobuf::internal::RepeatedPtrFieldBase::MergeFrom<google::protobuf::RepeatedPtrField<mesos::Resource>::TypeHandler>(google::protobuf::internal::RepeatedPtrFieldBase const&)
> 898.0ms 4.4% 898.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler::Type* google::protobuf::internal::RepeatedPtrFieldBase::Add<google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler>()
> 517.0ms 2.5% 0.0 google::protobuf::RepeatedPtrField<mesos::Value_Range>::Add()
> 517.0ms 2.5% 0.0 mesos::Value_Ranges::add_range()
> 429.0ms 2.1% 0.0 mesos::coalesce(mesos::Value_Ranges*, mesos::Value_Range const&)
> 88.0ms 0.4% 0.0 mesos::ranges::add(mesos::Value_Ranges*, long long, long long)
> 379.0ms 1.8% 0.0 void google::protobuf::internal::RepeatedPtrFieldBase::MergeFrom<google::protobuf::RepeatedPtrField<mesos::Value_Range>::TypeHandler>(google::protobuf::internal::RepeatedPtrFieldBase const&)
> {code}
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)