Background
Following Optimize performance of AnimationGroup.Parse, the benchmark also shows that in AssetContainer.addToScene, getNodes takes most of CPU time.
It called scene.getNodes() for every nodes added.
And scene.getNodes() allocates a giant array of all nodes in scene.
So here both the time and space complexity should be O(n^2) here, and allocating transient arrays makes great pressure to GC.
Proposed change
This should reduce both time and space complexity from O(n^2) to O(n) here.
diff --git a/packages/dev/core/src/assetContainer.ts b/packages/dev/core/src/assetContainer.ts
index 8a1e44b6b1..f8499c1287 100644
--- a/packages/dev/core/src/assetContainer.ts
+++ b/packages/dev/core/src/assetContainer.ts
@@ -816,9 +816,25 @@ export class AssetContainer extends AbstractAssetContainer {
this.scene.addReflectionProbe(o);
}
+ // No more nodes added to scene after this line, so it's safe to make a "snapshot" of nodes
+ const nodeSet = new Set<Node>(this.scene.meshes);
+ for (const light of this.scene.lights) {
+ nodeSet.add(light);
+ }
+ for (const camera of this.scene.cameras) {
+ nodeSet.add(camera);
+ }
+ for (const transformNode of this.scene.transformNodes) {
+ nodeSet.add(transformNode);
+ }
+ for (const skeleton of this.skeletons) {
+ for (const bone of skeleton.bones) {
+ nodeSet.add(bone);
+ }
+ }
for (const addedNode of addedNodes) {
// If node was added to the scene, but parent is not in the scene, break the relationship
- if (addedNode.parent && this.scene.getNodes().indexOf(addedNode.parent) === -1) {
+ if (addedNode.parent && !nodeSet.has(addedNode.parent)) {
// Use setParent to keep transform if possible
if ((addedNode as TransformNode).setParent) {
(addedNode as TransformNode).setParent(null);
Alternatives
- Use array instead of
nodeSet, this makes best browser compatibility, butarray.indexOfis stillO(n)in time complexity, so the final time complexity is stillO(n^2), and space complexity isO(n) - Use uniqueId lookup with Map or plain object. This makes
O(n)for both time and space complexity, but falls in case of malformed data with collisions in uniqueId. - Optimize
scene.getNodes()to have some kind of cache, but it’s hard to “watch” changes of nodes. - Iterate all node arrays directly in the loop, no memory allocation,
O(n^2)in time complexity, a lot more code.
