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 Tue, 24 Jul 2018 05:29:07 GMT

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

(Updated July 23, 2018, 10:29 p.m.)


Review request for mesos, Benjamin Mahler, Gastón Kleiman, and Vinod Kone.


Changes
-------

- Refactored the code for better readability;
- Added tests for subtracting the empty case;
- Added changes to v1 as well.


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 (updated)
-----

  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/

Changes: https://reviews.apache.org/r/67965/diff/1-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