This was a great read, thanks for sharing.

That improvement sounds great. Any chance that’s up as a PR to blender?

I didn't submit the PR yet, but opened an issue which has not been picked up. Maybe most of the USD files used in Blender do not trigger the O(N^2) behavior.

Possibly. Do you have a link to the PR handy?

I don't think a PR is ready. My solution does not fully solve the problem. It requires more thoughts. Thanks.

Excited to see this potentially integrated into FreeCAD. It is already very good at utilizing assets from other applications like Blender, and producing assets that can be used in other applications.

It would really help smooth out some wrinkles in the building industry if we could freely interoperate with each other while using different applications. I can't afford (stomach) anything but FreeCAD for my building projects. All the engineers I work with use autocad.

Interesting. Since the list is sorted, is the insertion still a linear search (O(N)) or now a binary search (O(log(N))? Or did I misunderstand something? Also, why is it not a hash table (almost O(1))?

Good point, I have the same doubt. Even if it is sorted, you still cannot do binary search on it unless using some skip list ideas. In fact, the code right now is doing linear search to find the ID given a name.

TBH, I don't fully understand how the ID linked list is utilized in Blender and why it needs to sorted by names. It seems some other data structure could also work, unless I missed something.

Oh is it an actual linked list and not an array?

Yes, actually it is a doubly linked list.

Wow, thanks!