You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@mesos.apache.org by Meng Zhu <mz...@mesosphere.io> on 2018/07/18 18:29:33 UTC
Review Request 67965: Optimized ranges subtraction operation.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/67965/
-----------------------------------------------------------
Review request for mesos and Benjamin Mahler.
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
Diff: https://reviews.apache.org/r/67965/diff/1/
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