UsdImagingDelegate::PopulateSelection doesn't have good scalability

[williamkrick]

Description of Issue

UsdView doesn't support marquee selection. A user selects things by picking a single rprim in the viewport, or by picking a prim in the hierarchy view. That single selected prim is that passed into UsdImagingDelegate::PopulateSelection, which then marks that prim & all of its children selected.

In Maya and MayaUSD I support a selection list with multiple prims selected. I have marquee selection to easily put things into the selection list. In order to populate the Usd selection I call UsdImagingDelegate::PopulateSelection once per prim in the selection list. If I marquee select everything in the USD scene, then my selection list has one entry per drawable prim in the scene.

The problem is when the scene has a large number of select-able prims (100k prims or more) and I marquee select all of them, I spend around half an hour making UsdImagingDelegate::PopulateSelection calls!

What is happening is inside PopulateSelection there is a call to _GatherDependencies. This code is trying to find all the prims which are children of the selected prim. _GatherDependencies finds all the children using _dependencyInfo, a sorted list of all the prims. First _GatherDependencies finds the first prim whose path starts with the selected path (std::multimap::lower_bound). Then _GatherDependencies searches for the last prim whose path starts with the given path (std::upper_bound because a custom comparison method is necessary). This binary search is slow, I think because std::multimap iterator is not a LegacyRandomAccessIterator which makes std::upper_bound take O(N) iterator increments. So selecting everything in the scene is O(N^2) iterator increments (and O(N log N) HasPrefix calls).

I have some code changes which give a 13,000x performance improvement to my particular case where what is selected is primarily leaf nodes without children. The change works by checking to see if there are any children before beginning the binary search. I will upload to a pull request after I log this issue to discuss that particular solution. That is just a suggestion for a solution, I would take any solution that scales.

Steps to Reproduce

In MayaUSD

1. Load a suitably complex scene. Something with lots of mesh prims (100k) and relatively deep hierarchies of xforms above those meshes (~10) should reproduce the issue easily.
2. marquee select all the objects in the scene.
3. Wait 20 to 30 minutes for Maya to become responsive again.

In UsdView I wasn't able to reproduce this issue, but I think it is there. When I followed the steps below I seem to have run into a different scalability issue converting the selection of everything in the hierarchy view into a selection list. I am not sure exactly what is going on but it is also not scalable.

1. Load a suitably complex scene. Something with lots of mesh prims (100k) and relatively deep hierarchies of xforms above those meshes (~10) should reproduce the issue easily.
2. In the hierarchy view choose show->expand all
3. Find the last expanded rpirm and select it, the shift-select the first expanded rprim. This will select each rprim individually.
4. Wait 1 hour and UsdView is still not responsive.

Internal issue MAYA-114875.

System Information (OS, Hardware)

Windows 10

Package Versions

USD 21.08 or 21.11 (earlier versions not tested), MayaUSD v0.14.0 (earlier versions should have the same issue), Maya PR 130 (I think 2022.x will all have the same issue as well).

Build Flags

[jilliene]

Filed as internal issue #USD-7036

[spiffmon]

Thanks, @williamkrick ! In usdview, whenever we have a multi-prim selection, we check to see if an ancestor of any selected leaf is also selected, in which case we remove all descendants from the set. I haven't looked at that code in awhile, but it could be NLogN or possibly even quadratic, so that may explain the extra pathology you're seeing there.

[sunyab]

Closing out old issue, the fix in PR #1691 was merged and released in v22.03 earlier this year. Thanks!