tree 719ffca21bb871dee9ece45729a5e849a7fbec33
parent d4afcd10b6535d91c5a6a544aed2f09af6201b46
author Andrei Sekretenko <asekretenko@apache.org> 1589386513 +0200
committer Andrei Sekretenko <asekretenko@apache.org> 1589487384 +0200

Fixed performance of tracking resource totals in allocator's roles tree.

Before this patch, the roles tree was tracking total resources
offered/allocated to a role as a single `Resources` objects.
In the case when each agent has a limited number of unique resources
(for example, a single persistent voulme), this resulted in poor
asymptotic complexity of allocation versus the number of agents
(O(N^2)) that was clearly observable in
`HierarchicalAllocations_BENCHMARK_Test.PersistentVolumes`.
In addition, the role tree code was violating the convention that
`Resources` belonging to different agents should never be added.

This patch implements per-agent tracking of `Resources` in the roles
tree, thus improving the performance of allocation (and getting rid of
the potentially problematic O(N^2) asymptotic) in the case of many
agents with a limited number of unique resources each.

Review: https://reviews.apache.org/r/72508