commit 754d8eb76c6fcd539fc2c32f0e2f90f6503b9f0c
Author: Eric Fried <email address hidden>
Date: Fri Feb 15 10:54:36 2019 -0600
Perf: Use dicts for ProviderTree roots
ProviderTree used to keep track of root providers in a list. Since we
don't yet have sharing providers, this would always be a list of one for
non-ironic deployments, or N for ironic deployments of N nodes.
To find a provider (by name or UUID), we would iterate over this list,
an O(N) operation. For large ironic deployments, this added up fast -
see the referenced bug.
With this change, we store roots in two dicts: one keyed by UUID, one
keyed by name. To find a provider, we first check these dicts. If the
provider we're looking for is a root, this is now O(1). (If it's a
child, it would still be O(N), because we iterate over all the roots
looking for a descendant that matches. But ironic deployments don't have
child providers (yet?) (right?) so that should be n/a. For non-ironic
deployments it's unchanged: O(M) where M is the number of descendants,
which should be very small for the time being.)
Test note: Existing tests in nova.tests.unit.compute.test_provider_tree
thoroughly cover all the affected code paths. There was one usage of
ProviderTree.roots that was untested and broken (even before this
change) which is now fixed.
Change-Id: Ibf430a8bc2a2af9353b8cdf875f8506377a1c9c2
Closes-Bug: #1816086
(cherry picked from commit 8c797450cbff5194fb6791cd0a07fa060dc8af72)
Reviewed: https:/ /review. opendev. org/670179 /git.openstack. org/cgit/ openstack/ nova/commit/ ?id=754d8eb76c6 fcd539fc2c32f0e 2f90f6503b9f0c
Committed: https:/
Submitter: Zuul
Branch: stable/stein
commit 754d8eb76c6fcd5 39fc2c32f0e2f90 f6503b9f0c
Author: Eric Fried <email address hidden>
Date: Fri Feb 15 10:54:36 2019 -0600
Perf: Use dicts for ProviderTree roots
ProviderTree used to keep track of root providers in a list. Since we
don't yet have sharing providers, this would always be a list of one for
non-ironic deployments, or N for ironic deployments of N nodes.
To find a provider (by name or UUID), we would iterate over this list,
an O(N) operation. For large ironic deployments, this added up fast -
see the referenced bug.
With this change, we store roots in two dicts: one keyed by UUID, one
keyed by name. To find a provider, we first check these dicts. If the
provider we're looking for is a root, this is now O(1). (If it's a
child, it would still be O(N), because we iterate over all the roots
looking for a descendant that matches. But ironic deployments don't have
child providers (yet?) (right?) so that should be n/a. For non-ironic
deployments it's unchanged: O(M) where M is the number of descendants,
which should be very small for the time being.)
Test note: Existing tests in nova.tests. unit.compute. test_provider_ tree e.roots that was untested and broken (even before this
thoroughly cover all the affected code paths. There was one usage of
ProviderTre
change) which is now fixed.
Change-Id: Ibf430a8bc2a2af 9353b8cdf875f85 06377a1c9c2 4fb6791cd0a07fa 060dc8af72)
Closes-Bug: #1816086
(cherry picked from commit 8c797450cbff519