[MESOS-9325] Optimize `Resources::filter` operation.

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.7.1
• Labels: mesosphere performance
• Epic Link: Allocator performance improvement.
• Sprint: Mesosphere RI-6 Sprint 2018-31
• Story Points: 1
• Assignee: Meng Zhu
• Reporter: Meng Zhu
• Created: 16/Oct/18 23:12
• Updated: 23/Oct/18 20:05
• Resolved: 19/Oct/18 23:43

Description

`Resources::filter()` is a heavily used function. Currently it is O(n^2) due to the `add()` operation for each `Resource`:

Resources Resources::filter(
    const lambda::function<bool(const Resource&)>& predicate) const
{
  Resources result;
  foreach (
      const Resource_Unsafe& resource_,
      resourcesNoMutationWithoutExclusiveOwnership) {
    if (predicate(resource_->resource)) {
      result.add(resource_);
    }
  }
  return result;
}

`add()` is O( n ). This is not necessary. `filter()` operation should only remove `Resource` entries. We should be able to `push_back` the resource to the vector without scanning, making the `filter()` O( n ).