Node::add_child is extremely inefficient when running inside the editor

[0x0ACB]

Godot version

3.x and 4.x maybe all

System information

Windows 10, Ubuntu 20.4 LTS

Issue description

I was having some issues importing scenes with a semi large amount of (direct child) Nodes (4000). Using Visual Studio profiling I found that the function costing 96.7% of that time was Node::add_child which I found extremely curious since I was constructing whole meshes before that which only took up 0.5% of the time. Digging a bit deeper the issue stems from Node::_generate_serial_child_name which will ALWAYS iterate over ALL children at least once! In the case there is already a child with the name assigned to the Node this may happen even more often.

An easy fix for this would be to use a Set with all child names for the current Node; reducing the amount of lookups needed. I would submit a pull request for this but I am not sure for which branch I should do this (this affects at least 3.x and 4.x and I would like to see this fixed in the version that can be downloaded directly from the godot Website [3.3.4]).

Steps to reproduce

Generate a lot of direct child nodes in an editor (import) script.

Minimal reproduction project

No response

[YuriSizov]

An easy fix for this would be to use a Set with all child names for the current Node; reducing the amount of lookups needed.

This may not be a good idea, because the parent then needs to sync that up on every rename and possibly reorder. Usually it's not a great idea to keep multiple connected sets of data in sync in parallel as it's easy to get them out of sync, especially for future maintainers and contributors who may not know first hand that such system is in place.

However, a solution to disable renames for bulk additions can be created, as that would directly address your problem.

See also the discussion on godotengine/godot-proposals#3165.

I am not sure for which branch I should do this (this affects at least 3.x and 4.x and I would like to see this fixed in the version that can be downloaded directly from the godot Website [3.3.4]).

Most PRs must be made against the master branch regardless, unless it's a fix for something specific to a 3.x version. Then the changes can be backported to the 3.x branch and maybe the appropriate branch for a stable version. However, a change like this is unlikely to be a part of a patch release (3.3.5, 3.4.1) and it missed the window for the next minor release (3.4). So even if submitted now, it will have to wait to at least 3.5. But also, depending on the implementation, we may not want risk breaking compatibility with existing 3.x projects at all.

[0x0ACB]

This may not be a good idea, because the parent then needs to sync that up on every rename and possibly reorder. Usually it's not a great idea to keep multiple connected sets of data in sync in parallel as it's easy to get them out of sync, especially for future maintainers and contributors who may not know first hand that such system is in place.

Im not quite sure why the parent would need to sync with the child. The function only looks at direct children of the current node. So each node would just need to maintain that set individually. A different approach would be to just store all nodes in a map in the first place. But that would probably be a larger change overall.

[YuriSizov]

Im not quite sure why the parent would need to sync with the child. The function only looks at direct children of the current node. So each node would just need to maintain that set individually.

This is not what I was talking about. Children can be renamed by anything. They can name themselves, they can be renamed from user scripts. As such, parent needs to keep its internal list in sync with the actual state of the node tree; something that we don't need to do now when we live fetch all the nodes.

[sehoffmann]

Isn't it well-defined what functions change the node tree of a parent and what functions are invoked on name changes? From a purely conceptual understanding, the proposed change doesn't sound too unreasonable to me. Using a majority of CPU time on string lookups seems unreasonable for a game engine to me though. Especially since this behavior is completely unexpected and opaque from the outside without profiling and knowing the codebase.

The issue causes major performance degradation for our import script, pushing the total required time up to minutes. For comparisons, if the mentioned check was deactivated, the same process would only take mere seconds.

While I understand your concerns about maintainability to some degree, a proposed "bulk_add" method requires end-users to know about these (internal) specifics. Most likely, many would intuitively use add_node() first. Leaving poorly performing code in such a crucial core function such as add_node() feels wrong to me either.

[YuriSizov]

@sehoffmann Again, my point wasn't that it's unknown when the rename happens (the node fires a signal on rename after all). My point was that keeping a separate list in sync is an added cost and a point of breakage if you are not careful. It's a pattern that can lead to errors in the engine when someone forgets to account for that second list.

As for method discoverability, that's moot. That's what documentation is for and if one doesn't read it, we cannot help them. And in the docs, we can cross link everything and add notes. Plus, it's not a common case to add thousands of nodes, this is specific enough that if you understand that's a problem, you likely know that reading docs is useful.

[sehoffmann]

@pycbouh I understand your point, and as I said, I understand your concerns to some degree as well. To clarify my point though: If its well-defined when renames happen, or when the tree gets modified, then you simply have to incorporate the change at these few key points. There are only two ways how somebody can potentially break this then:

1. He modifies the code at these key points.
2. He modifies the contract of these key points, i.e. they don't get called anymore for instance.

In case 1) he directly stumbles upon the code, reads it, and any additional comments. If he manages to break it regardless, then nothing in the world would have been able to prevent him from doing so IMO and who knows what else he might be capable of breaking as well.

Case 2) is obviously trickier, since he might not be directly aware of what side effects his change might introduce. But any developer changing a contract, especially in such a big public library, should be aware that this has a major impact. Firstly you don't do so without an important reason, and secondly, if you do, you are extra careful and rigorous about it.

In the end, the decision is yours. but my opinion is that you are too defensive about this. Having a core method with O(n) complexity (or O(N^2) for adding N nodes) when you could easily have O(1) seems odd to me. Just wanted to clarify my point, and I won't further stress this issue.

[YuriSizov]

Well, decision isn't mine, we don't use authority to decide, only rationale :) I'm just voicing my concerns as well over the naive approach. I'm all for improvements here, it would likely speed up even such basic things like loading scenes in the editor. My suggestion is just that, a suggestion.

[reduz]

I think there is some misunderstanding of what is going on here, most likely due to the OP lacking context. Adding children nodes in common cases should be extremely fast because:

• PackedScene assumes the tree has been validated, so it uses a fast path and does not perform validation when loading the scene.
• Adding children (without the requirement of legible unique name) in run-time is also very fast because it always generates a unique name without having to check the other children nodes.

So, in practice for games this is not a problem. The specific problem here is when creating the scene for the first time or creating it from the editor (because when doing it from the editor, proper unique names are always created). In other words, this is a very corner case that will happen in the editor.

My suggestion here is most likely that we look for a specific solution to this problem, probably a way to add a large amount of children in bulk by passing an array of nodes.

[akien-mga]

I can't reproduce the issue with this script:

func _ready():
	for i in range(40000):
		var node = Node.new()
		add_child(node)

Adds 40000 instances in less than a second.

Are you calling add_child(node, true), i.e. enabling the legible_unique_name which is specifically meant to generate a unique, human-readable name, which is indeed inefficient, which is why it's off by default?

[0x0ACB]

I can't reproduce the issue with this script:

func _ready():
	for i in range(40000):
		var node = Node.new()
		add_child(node)

Adds 40000 instances in less than a second.

Are you calling add_child(node, true), i.e. enabling the legible_unique_name which is specifically meant to generate a unique, human-readable name, which is indeed inefficient, which is why it's off by default?

No and this is only true if running in editor. In editor godot forces human readable names for all nodes as @reduz pointed out above.

[reduz]

@0x0ACB I took the liberty to fix the issue name so it's clearer where the problem happens.

So I think in short I would advocate for a function that lets you add a lot of children nodes in bulk (and they require legible unique names). That should make validation much faster as a hashmap or similar can be used to validate everything together.

[Zireael07]

What does 'in editor' mean here? Tool scripts? Plugins?

[0x0ACB]

What does 'in editor' mean here? Tool scripts? Plugins?

All code that is running inside the editor so yes. Tools and Editor Plugins for example

[reduz]

Maybe a:

add_children(TypedArray<Node> p_children,bool p_legible_unique_names=false) 

might be good? Documentation can be explicit on this being faster when adding large number of nodes, specially when they lack names and legible unique names is specified, or when they come with names and they need to be validated.

[0x0ACB]

Yes that sounds like a good alternative

[KoBeWi]

So I think the problem here is node_hrcr variable that forces the "legible unique names" globally in the editor. It should be resolved by #54072 (didn't read the whole discussion though)