Comment 6 for bug 1816086

Reviewed: https://review.opendev.org/670179
Committed: https://git.openstack.org/cgit/openstack/nova/commit/?id=754d8eb76c6fcd539fc2c32f0e2f90f6503b9f0c
Submitter: Zuul
Branch: stable/stein

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)