Creating nested variant sets becomes exponentially slower when adding more variant sets

[juergen3ds]

Description of Issue

The method SetVariantSelection becomes exponentially slower when I create a "package" variant set which switches other variant sets. Creating this "package" variant set takes ~1 sec for 100 variant sets in the package, ~8 sec for 200 variant sets and ~34 sec for 300 variant sets.

Steps to Reproduce

void perfTest()
{
    using namespace pxr;

    constexpr int numSets = 300;
    constexpr int numVars = 3;

    UsdStageRefPtr stage = pxr::UsdStage::CreateNew("C:\\temp\\test.usda");
    UsdPrim prim = stage->DefinePrim(pxr::SdfPath("/scene"));
    stage->SetDefaultPrim(prim);

    UsdVariantSets variantSets = prim.GetVariantSets();

    std::vector< UsdVariantSet > varSets;
    for (int i = 0; i < numSets; ++i)
    {
        varSets.push_back(variantSets.AddVariantSet("varSet_" + std::to_string(i)));
        for (int j = 0; j < numVars; ++j)
        {
            varSets[i].AddVariant("var_" + std::to_string(j));
        }
    }

    UsdVariantSet packageSet = variantSets.AddVariantSet("packageSet");
    for (int j = 0; j < numVars; ++j)
    {
        std::string name = "var_" + std::to_string(j);
        packageSet.AddVariant(name);
        packageSet.SetVariantSelection(name);
        {
            UsdEditContext context(packageSet.GetVariantEditContext() );
            for (int i = 0; i < numSets; ++i)
            {
                //this SetVariantSelection call is becoming exponentially slower, when number of variant sets is increased (numSets).
                varSets[i].SetVariantSelection(name);
            }
        }
    }

    stage->Save();
}

Package Versions

22.03

[spiffmon]

Very interesting setup! If I read that correctly, you're creating hundreds of variantSets on the same prim, and then creating a final, weakest variantSet whose every variant supplies selections for all the other variantSets - do I have that right?

Some things to note that may be contributing, here:

1. Each time you set a variant selection, it will recompose the entire prim, not just the variantSet whose variant is being specified.
2. "resolving" the variant selection as we compose each variantSet is more involved than the "simple" recursive algorithm described for LIVRPS, because we try hard to find a usable selection anywhere in the prim's composition graph, and by having so many variantSets (each one is basically an arc), there are alot of places to look, and for each of the 300 variantSets, we always find either a) no selection, after searching everywhere or b) as the last loop proceeds, a selection in the very last (weakest) place we look
3. You might see some improvement if it's acceptable to make the packageSet be the strongest/first variantSet instead of the last one? variantSets.AddVariantSet("packageSet", UsdListPositionFrontOfPrependList )
4. But, to really address the core problem of all the iterative recomposition that is happening, you'd need to become familiar with the Sdf-level authoring API's so that you can use an SdfChangeBlock to batch all your edits so that the prim only recomposes once (or a small number of times). Providing a "batch editing" API at the UsdStage-level is on our backlog, but not in the next six months roadmap.

[juergen3ds]

Yes, the package variant sets the selection for other variant sets.

Adding the packageSet at the front did not make any measurable difference.

Adding the SdfChangeBlock here to delay the notifications improves the performance a lot.

...
packageSet.SetVariantSelection(name);
{
    SdfChangeBlock changeBlock;
    UsdEditContext context(packageSet.GetVariantEditContext() );
    for (int i = 0; i < numSets; ++i)
    {
        varSets[i].SetVariantSelection(name);
    }
}

Thanks.

[spiffmon]

Hi @juergen3ds , I did not make it clear enough that API's in pxr/usd/usd (and higher in the software layering, so no schemas either) are unsafe to use while an SdfChangeBlock is active. You appear to be getting lucky in your use of UsdVariantSets, but in general it can lead to incorrect results, or even trigger errors or possibly even crashes. This is because the Usd API's often take advantage of the fact that the stage is recomposing after each micro-edit. Here is a version of your snippet that I have not tested, but suggests the necessary approach:

...
packageSet.SetVariantSelection(name);
{
    SdfChangeBlock changeBlock;
    UsdEditTarget target = packageSet.GetVariantEditTarget();
        SdfPrimSpecHandle variantPrim = target.GetPrimSpecForScenePath(prim.GetPath());
        // This test may be unnecessary, but I don't have time to verify whether creating 
        // the variantSet, as you have just done, above, guarantees that its child primSpec will be created
        if (!variantPrim) {
            variantPrim = Sdf.CreatePrimInLayer(target.GetLayer(), target.MapToSpecPath(prim.GetPath());
        }
    for (int i = 0; i < numSets; ++i)
    {
        variantPrim.SetVariantSelection(varSets[i].GetName(), name);
    }
}

It may also be a good idea, if it is likely that someone else will be learning from your code, that anywhere you use an SdfChangeBlock, you add a warning comment stating that you can only use Sdf-level authoring API's while it is active.

[juergen3ds]

Thanks, I adjusted my code accordingly.

In your example for the C++ API it should be SdfCreatePrimInLayer without dot and variantPrim->SetVariantSelection.

[sunyab]

Filed as internal issue #USD-7515

[ziriax]

Unfortunately it is not just the creation that becomes slower, it is the selection itself.

The more variant set "nesting" you have, the slower it becomes, exponentially.

This actually occurs with some commercial software USD variant exporters, it can take over 3 seconds in some scenes to set a single variant selection on my machine.

That software typically generates two variants per "option": on describing the changes, and off, which is just {}. Then it combines these options into a "package", picking on or off per option variant. And this is recursive, you can have bigger packages that toggle smaller packages.

These empty variants feel redundant? I wrote code to remove all these empty variants", and that makes it between 3 to 10 times faster, while at first sight (by comparing all the resolved values and relationships) gives the same output. But still way to slow for interactive usage.

You mentioned

because we try hard to find a usable selection anywhere in the prim's composition graph

Is it possible to disable this search, e.g. using a custom USD build, to see if that improves it?

[spiffmon]

@ziriax , we have not been able to schedule this work yet, and it will be at least Spring before we can. I can understand why removing empty "off" variants might make authoring faster, though I'm not sure why it would speed up composition while changing variant selections; it is reasonable and supported to have an empty/none variant selection, though while usdview supports "unsetting" a variant selection, I'm not sure all DCC's do?

No, it would not be straightforward to disable variant resolution, unfortunately.

The one alternate encoding you might try, which has its own issues, is to use expression variables inside references, using variables to specify whether each "feature" is present or not. It would take some creativity to encode packages in this way, and before exploring it you'd need to determine whether your target apps would support allowing users to set variables. I don't have the time to really explore it now, but for sure this route would be much much faster when scaling to hundreds or thousands of options.