mesos-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Meng Zhu <m...@mesosphere.io>
Subject Re: Review Request 67965: Optimized ranges subtraction operation.
Date Wed, 25 Jul 2018 00:24:24 GMT


> On July 24, 2018, 2:06 p.m., Vinod Kone wrote:
> > src/common/values.cpp
> > Lines 290-311 (patched)
> > <https://reviews.apache.org/r/67965/diff/2/?file=2063376#file2063376line290>
> >
> >     This part is a bit hard to follow. Can you break it down into 4 cases
> >     
> >     1) left is subsumed in right
> >     2) right is subsumed in left
> >     3) left overlaps right but left's start is smaller
> >     4) left overlaps right but right's start is smaller
> >     
> >     
> >     Even if some of these cases ends up with same resulting code, I think it's worth
duplicating for readability.

I think it is actually more complicated if we separate into the said four cases, there will
be more corner cases concerning equal signs. I think while the separation makes it easy to
reason the logic of the individual case, it makes it relatively difficult to be confident
that the code has covered all the individual corner cases (or a single case is only covered
once).


- Meng


-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/67965/#review206414
-----------------------------------------------------------


On July 24, 2018, 5:23 p.m., Meng Zhu wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/67965/
> -----------------------------------------------------------
> 
> (Updated July 24, 2018, 5:23 p.m.)
> 
> 
> Review request for mesos, Benjamin Mahler, Gastón Kleiman, and Vinod Kone.
> 
> 
> Bugs: MESOS-9086
>     https://issues.apache.org/jira/browse/MESOS-9086
> 
> 
> Repository: mesos
> 
> 
> Description
> -------
> 
> The current ranges subtraction uses boost IntervalSet.
> Based on the profiling result of MESOS-8989, the ranges
> subtraction operation is about 2~3 times more expensive
> than that of addition. The conversion cost from Ranges
> to IntervalSet may be the culprit.
> 
> This patch optimizes the ranges subtraction operation by
> converting Ranges to a vector of internal sub-ranges, sorting
> the vector based on sub-range start and then applying a
> one-pass algorithm similar to that of addition.
> 
> 
> Diffs
> -----
> 
>   src/common/values.cpp afe4137f82115dd4ec9967b5eba16a1dd15401c8 
>   src/tests/values_tests.cpp 2f5abedfd461c114d03f5e941d81ebe414188033 
>   src/v1/values.cpp d2c31f6c91998382dec1d8834b40613013716cdd 
> 
> 
> Diff: https://reviews.apache.org/r/67965/diff/3/
> 
> 
> Testing
> -------
> 
> make check
> 
> Benchmarking:
> 
> tl:dr: more than 80% performance improvment across board. Performance of subtraction
is now on par or better than the addition, especially when there are a large number of sub-ranges.
> 
> Build with -O2 optimization, ran on a multicore machine with peak frequency at 2.2GHz:
> 
> Took 1.617706ms to perform 1000 'a += b' operations on ports:[1-6, 11-16, 21-26...91-96]
and ports:[3-8, 13-18, 23-28..., 93-98] with 10 sub-ranges
> Took 1.607999ms to perform 1000 'a -= b' operations on ports:[1-6, 11-16, 21-26...91-96]
and ports:[3-8, 13-18, 23-28..., 93-98] with 10 sub-ranges
> Took 3.094113ms to perform 1000 'a + b' operations on ports:[1-6, 11-16, 21-26...91-96]
and ports:[3-8, 13-18, 23-28..., 93-98] with 10 sub-ranges
> Took 3.152291ms to perform 1000 'a - b' operations on ports:[1-6, 11-16, 21-26...91-96]
and ports:[3-8, 13-18, 23-28..., 93-98] with 10 sub-ranges
> 
> Took 14.908924ms to perform 1000 'a += b' operations on ports:[1-6, 11-16, 21-26...991-996]
and ports:[3-8, 13-18, 23-28..., 993-998] with 100 sub-ranges
> Took 13.564767ms to perform 1000 'a -= b' operations on ports:[1-6, 11-16, 21-26...991-996]
and ports:[3-8, 13-18, 23-28..., 993-998] with 100 sub-ranges
> Took 25.523443ms to perform 1000 'a + b' operations on ports:[1-6, 11-16, 21-26...991-996]
and ports:[3-8, 13-18, 23-28..., 993-998] with 100 sub-ranges
> Took 24.871216ms to perform 1000 'a - b' operations on ports:[1-6, 11-16, 21-26...991-996]
and ports:[3-8, 13-18, 23-28..., 993-998] with 100 sub-ranges
> 
> Took 234.22483ms to perform 1000 'a += b' operations on ports:[1-6, 11-16, 21-26...9991-9996]
and ports:[3-8, 13-18, 23-28..., 9993-9998] with 1000 sub-ranges
> Took 144.417381ms to perform 1000 'a -= b' operations on ports:[1-6, 11-16, 21-26...9991-9996]
and ports:[3-8, 13-18, 23-28..., 9993-9998] with 1000 sub-ranges
> Took 322.548021ms to perform 1000 'a + b' operations on ports:[1-6, 11-16, 21-26...9991-9996]
and ports:[3-8, 13-18, 23-28..., 9993-9998] with 1000 sub-ranges
> Took 227.835441ms to perform 1000 'a - b' operations on ports:[1-6, 11-16, 21-26...9991-9996]
and ports:[3-8, 13-18, 23-28..., 9993-9998] with 1000 sub-ranges
> 
> 
> Thanks,
> 
> Meng Zhu
> 
>


Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message