mesos-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Joerg Schad (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MESOS-3051) performance issues with port ranges comparison
Date Tue, 08 Sep 2015 14:26:45 GMT

    [ https://issues.apache.org/jira/browse/MESOS-3051?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14734878#comment-14734878
] 

Joerg Schad commented on MESOS-3051:
------------------------------------

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)

Mime
View raw message