SdfPath: inconsistent hash in versions > 21.11

[cpichard]

Description of Issue

Hi,
The following code show a case where a SdfPath object belonging to a proxy instance returns different hashes during the life of the application. This behaviour seems to have been introduced in version > 21.11. I believe this is a bug as, if it is not, it would mean we can't rely on hashes for sdfpath. In the test case, there is a game loop, for each frame a SdfPath object is copied and stored in a vector then destroyed. The hash is different even if the string representation of the path is the same.

Steps to Reproduce

The following code exposes the behaviour:

//cmake_minimum_required (VERSION 3.14)
//project(sdfpathbug)
//set(CMAKE_CXX_STANDARD 14)
//find_package(pxr REQUIRED)
//add_executable(sdfpathbug main.cpp) 
//target_compile_definitions(sdfpathbug PRIVATE NOMINMAX)
//target_link_libraries(sdfpathbug ${PXR_LIBRARIES})
//target_include_directories(sdfpathbug PRIVATE ${PXR_INCLUDE_DIRS})

#include <iostream>
#include <string>
#include <unordered_map>

#include <pxr/usd/usd/primRange.h>
#include <pxr/usd/usd/stage.h>

PXR_NAMESPACE_USING_DIRECTIVE

const std::string scene = R""(#usda 1.0

def "Prototype" (
    active = false
)
{
    def Xform "Points" (
        instanceable = true
    )
    {
        uniform token[] xformOpOrder = ["xformOp:translate"]

        def PointInstancer "pointInstancer"
        {
            quath[] orientations = [(0, 0, 0, 1)]
            point3f[] positions = [(0, 0, 0)]
            color3f[] primvars:displayColor = [(0, 0, 1)]
            int[] protoIndices = [0]
            add rel prototypes = </Prototype/Points/pointInstancer/prototype>

            def Mesh "prototype"
            {
                float3[] extent = [(-1, 0, -1), (1, 2, 1)]
                int[] faceVertexCounts = [4, 3, 3, 3, 3]
                int[] faceVertexIndices = [0, 1, 2, 3, 1, 0, 4, 2, 1, 4, 3, 2, 4, 0, 3, 4]
                float3[] points = [(1, 0, 1), (-1, 0, 1), (-1, 0, -1), (1, 0, -1), (0, 2, 0)]
            }
        }
    }
}

def Xform "Points1" (
    append references = </Prototype/Points>
)
{
}

def Xform "Points2" (
    append references = </Prototype/Points>
)
{
    double3 xformOp:translate = (0, 0, 1)
}

)"";

constexpr int maxTry = 5000;

int main(int argc, const char **argv) {
  // Used to store the sdfpath hash per path (represented in string)
  std::unordered_map<std::string, size_t> hashes;

  // Load stage from string
  auto rootLayer = SdfLayer::CreateNew("delete_me.usd");
  rootLayer->ImportFromString(scene);
  auto stage = UsdStage::Open(rootLayer);

  for (int i = 0; i < maxTry; ++i) { // Simulate game loop
    std::vector<SdfPath> paths;
    auto range = UsdPrimRange::Stage( // Iterate on the stage
        stage, UsdTraverseInstanceProxies(UsdPrimAllPrimsPredicate));
    for (auto iter = range.begin(); iter != range.end(); ++iter) {
      const auto path = iter->GetPath();
      paths.push_back(path); // Store the path in a vector
    }
    for (const auto &path : paths) { // Iterate on the stored paths
      auto it = hashes.find(path.GetAsString());
      if (it != hashes.end()) {
        if (it->second != path.GetHash()) {
          std::cout << "Error, hash changed for " << it->first << std::endl;
          break;
        }
      } else {
        hashes[path.GetAsString()] = path.GetHash();
      }
    }
  }
  return 0;
}

System Information (OS, Hardware)

Compiled on windows 10 21H2 19044.1766
Microsoft Visual Studio Community 2019 Version 16.11.12
Intel(R) Core(TM) i7 CPU 960 @ 3.20GHz 3.20 GHz

Package Versions

USD 22.05a, USD 22.03 and USD 21.11

Build Flags

I used cmake to create the project. The cmake recipe is in the comment at the top of the code. The behaviour was visible in RelWithDebInfo and built with
cmake --build . --config RelWithDebInfo

Thanks a lot for any help with this issue.

Cyril

[gitamohr]

The hash values associated with SdfPath objects are intended for use with runtime hash tables. Think std::unordered_map keyed by SdfPath. They are not guaranteed to be unique, and the hash code for a given SdfPath instance is only guaranteed to be stable so long as there exists at least one instance of that SdfPath. The path's string representation is not relevant to this hash code, and an SdfPath's hash code cannot be used as a unique identifier.

In your particular example, the problem most likely arises due to traversal with instance proxies. UsdStage does hold onto SdfPaths for its prims, but for instancing it only holds one "subtree" of paths under each prototype. Instance proxies dynamically expand the specific subtree paths for each instance as you traverse, in order to present a view of the stage "as if" it wasn't instanced. That is if you have /foo and /bar that are instances of a single prototype, then the instance proxies traversal will only create the paths /foo/child1..N and /bar/child1..N while serving up those specific instance proxies. After the traversal is complete, nothing holds those /foo/child1..N and /bar/child1..N paths, so the next time around their hash codes may be different.

Instead of holding hash codes for SdfPaths, can you hold the SdfPath instances themselves?

IMHO it's highly unfortunate that we use the term "hashing" to mean two radically different things: 1) hashing for hash tables where collisions are expected and gracefully handled and where hash codes are not meant to have any kind of long-term stability, and 2) content-based hashing for fingerprinting / identification, where collisions are assumed to never happen and long-term stability and repeatability is important. The hash functions for SdfPath (like for many other C++ objects) is firmly in the first category.

[cpichard]

Hi Alex, Thanks a lot for the clear and detailed explanations. I wasn't sure if once created a SdfPath would live until the end of the application or until his last holder dies, I have my answer now, thanks. I was guessing the lifetime might have been the problem and ended up storing the paths of the proxy instances to workaround this issue, which worked but is not ideal in my case. The hashes are ultimately used in a bespoke hash map which takes integers for keys and stores ui data for different types of elements, so I need to store the SdfPath in an external structure. This behaviour wasn't visible on version <=21.11, was something holding on to instance proxies before or was it just luck ? Would you know it there is already some code to efficiently fingerprint/identify a SdfPath ? at least more efficient than creating and hashing a string ? Thanks again for the help, Cyril

[gitamohr]

Hi Cyril -- is it possible to store the SdfPath in the mapped_type of your hash table? e.g. unordered_map<uint64_t, type_that_includes_the_SdfPath> ? At least that way you don't have a sidecar structure to maintain and you're guaranteed that the hash code will always be valid. Note, though, that you would still have a lurking bug here because the hash codes do not uniquely identify paths so you will eventually have a collision.

I don't know of any specific reason offhand why 21.11 would begin to exhibit this problem for you. I do suspect you were just getting lucky before.

We don't, to my knowledge, have a way to produce a fingerprint/identity style hash code short of running such a hash on the string representation. We don't have much of a need for that, since we use the SdfPath object as the identifier in-process; that's its purpose. We use its text representation as the identifier in persistent storage (or over a wire).

[gitamohr]

Oh also, I wanted to say thank you for the clear and concise example!

[drwave]

What a lovely, instructive thread this has been!

…

On Jun 27, 2022, at 2:09 PM, Alex Mohr ***@***.***> wrote: Oh also, I wanted to say thank you for the clear and concise example! — Reply to this email directly, view it on GitHub <#1922 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAM2AOR46C75M25EAASJGE3VRIJ7VANCNFSM5Z5472DA>. You are receiving this because you are subscribed to this thread.

[cpichard]

Hi Alex, thanks a lot ! Unfortunately I can't store the SdfPath in the mapped type without some substantial developments. It would have been ideal though. The hash map in question is the one imgui uses to keep the UI elements state, and, as a note, it is already unsafe to collisions. In my application the SdfPath hash is used as the identifier of the tree node element at that location. Before, I used to let imgui hashes the text representation of the SdfPath, but it turned out that GetHash was way faster, not surprisingly, and the speedups were visible on medium size scene (~10000 prims). I'll probably keep the current workaround, it seems like the best trade-off so far. Thanks again for all your answers, they were really helpful. Best, Cyril On Tue, Jun 28, 2022 at 3:28 AM Michael B. Johnson ***@***.***> wrote:

…

What a lovely, instructive thread this has been! > On Jun 27, 2022, at 2:09 PM, Alex Mohr ***@***.***> wrote: > > > Oh also, I wanted to say thank you for the clear and concise example! > > — > Reply to this email directly, view it on GitHub < #1922 (comment)>, or unsubscribe < https://github.com/notifications/unsubscribe-auth/AAM2AOR46C75M25EAASJGE3VRIJ7VANCNFSM5Z5472DA >. > You are receiving this because you are subscribed to this thread. > — Reply to this email directly, view it on GitHub <#1922 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AACJJU56QS37NJ2OZWVAUZTVRJPMHANCNFSM5Z5472DA> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[meshula]

@cpichard FWIW, for performance reasons, and to avoid collisions, and to solve the problem in an unobtrusive way, maybe Dear ImGui's PushId(const void*); stuff(); PopId(); pattern would help? If you have a stable pointer associated one to one with the elements in your UI, you can use that pointer instead ~ it'll be unique as the pointer you use as an id, and Dear ImGui won't spend time processing a string, so it should be at least as fast as SdfPath's Gethash(). There is also PushId(int id); for the case that you have a unique integer value available.

[sunyab]

Filed as internal issue #USD-7459

[sunyab]

I'm going to close this one out as resolved, thank you all for the discussion!

[cpichard]

Thanks @sunyab !

I had sent this reply by mail few days ago, and realising it didn't go through, so I am posting it back here.

Hi @meshula ,
thanks for the idea ! I can investigate how the PushId(void*) PopId can be leveraged in the code this week-end, my issue is to keep a stable pointer somehow. Imgui doesn't have a notion of UI objects that can be kept in memory, like qt, so I can't rely on imgui for this pointer. In a way, keeping the SdfPath of the proxy instances in a structure allows to keep the SdfPath internal memory stable, producing a stable pointer used by GetHash. I feel it gives the best bang for the buck for the side project I am working on for now.
Regarding the hash collision in imgui, it seems to be a known potential risk, as there is no collision resolution, but it looks like it has been a non issue so far, I found a thread here: ocornut/imgui#4612
Thanks again for the help,
Cyril