mesos-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Meng Zhu (JIRA)" <j...@apache.org>
Subject [jira] [Created] (MESOS-9325) Optimize `Resources::filter` operation.
Date Tue, 16 Oct 2018 23:13:00 GMT
Meng Zhu created MESOS-9325:
-------------------------------

             Summary: Optimize `Resources::filter` operation.
                 Key: MESOS-9325
                 URL: https://issues.apache.org/jira/browse/MESOS-9325
             Project: Mesos
          Issue Type: Bug
            Reporter: Meng Zhu
            Assignee: Meng Zhu


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

{code:java}
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;
}
{code}

`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).




--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

Mime
View raw message