[MESOS-9086] Optimize range subtraction operation.

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.7.0
• Labels: mesosphere performance
• Target Version/s: 1.7.0
• Epic Link: Allocator performance improvement.
• Sprint: Mesosphere Sprint 2018-24, Mesosphere Sprint 2018-25
• Story Points: 3
• Assignee: Meng Zhu
• Reporter: Meng Zhu
• Shepherd: Vinod Kone
• Created: 18/Jul/18 17:57
• Updated: 27/Jul/18 17:28
• Resolved: 27/Jul/18 17:28

Description

Based on the profiling result of MESOS-8989, the range subtraction operation is about 2~3 times more expensive than that of addition. It's not obvious that this has to be the case.

The current range subtraction implementation relies on boost IntervalSet, the construction cost of the IntervalSet could be the culprit:
https://github.com/apache/mesos/blob/9147283171d761a4d38710f24ba654f8a96e325c/src/common/values.cpp#L378-L387

I think we could do better by writing a one-pass (with sorting) algorithm like that of addition.