mesos-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Vinod Kone <vinodk...@apache.org>
Subject Re: Review Request 67965: Optimized ranges subtraction operation.
Date Tue, 24 Jul 2018 21:06:21 GMT

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




src/common/values.cpp
Line 231 (original), 231 (patched)
<https://reviews.apache.org/r/67965/#comment289353>

    extra blank line.



src/common/values.cpp
Lines 239 (patched)
<https://reviews.apache.org/r/67965/#comment289354>

    `ranges`



src/common/values.cpp
Lines 263 (patched)
<https://reviews.apache.org/r/67965/#comment289355>

    either use `iteratorLeft` and `iteratorRight` or `itLeft` and `itRight`. i've looked around
and I don't think we use `itr*` anywhere.



src/common/values.cpp
Lines 265 (patched)
<https://reviews.apache.org/r/67965/#comment289356>

    don't think you need the comment here. it's pretty clear?



src/common/values.cpp
Lines 290-311 (patched)
<https://reviews.apache.org/r/67965/#comment289368>

    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.



src/common/values.cpp
Lines 313 (patched)
<https://reviews.apache.org/r/67965/#comment289369>

    I like that you moved this outside the loop!



src/common/values.cpp
Line 371 (original), 464 (patched)
<https://reviews.apache.org/r/67965/#comment289370>

    Can you add a TODO here to make this consistent with how we do subtraction?



src/v1/values.cpp
Lines 233 (patched)
<https://reviews.apache.org/r/67965/#comment289371>

    See below.


- Vinod Kone


On July 24, 2018, 5:29 a.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:29 a.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/2/
> 
> 
> 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