GitLab

Currently this methods works as O(N*M), where
N = size of imported_resources_ in the provider
M = number of resources being received by the provider

That is because each received element is removed individually from the
imported_resources_ set, and each removal will cost O(N).

Instead, sort the incoming resources, then walk through the two
sets of resources in parallel, which is O(N+M). During this walk,
replace resources to be removed from imported_resources_ with resources
that we are keeping as we walk, which is O(1). Then erase the empty space
created by this process at the end of the loop, which is O(N). This
makes the complexity O(2N+M) = O(N+M).

This is similar to the std::remove_if() algorithm, except that we have
to write it ourselves to avoid O(M) work at each step, and instead walk
the received resources in parallel.

We also sort the returned M resources as a prelude, to ensure we can do
the walk in parallel. This costs O(MlogM), making the whole thing
O(N+MlogM).

Similarly, for ClientResourceProvider::ReleaseAllExportedResources()
stop removing elements individually. In this case we can use
base::EraseIf to iterate through the set, act on each element, and
return true if it should be erased.

R=piman@chromium.org

Bug: 881295
Cq-Include-Trybots: luci.chromium.try:android_optional_gpu_tests_rel
Change-Id: I94522eb07e2f09b20a10d8f254faa63fd2ab9d0e
Reviewed-on: https://chromium-review.googlesource.com/1211908
Commit-Queue: danakj <danakj@chromium.org>
Reviewed-by: Antoine Labour <piman@chromium.org>
Cr-Commit-Position: refs/heads/master@{#590347}