----------------------------------------------------------- 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