[
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)
