Deleting / detaching / moving large numbers of child nodes can be excessively slow

[lawnjelly]

Godot version

3.5 current (3.5 RC 3), earlier versions presumably

System information

N/A

Issue description

While benchmarking something else, I noticed that the time taken to queue_delete() a large number of MeshInstance children seemed to grow exponentially with the number of siblings of the parent. This is unlikely to come up that often outside of benchmarks / extreme cases, but is still a concern.

On discussion with @akien-mga there were two suspect areas, the ordered remove and possibly notifications sent as a result of the moving of the children. Testing revealed that the slowdown didn't occur when removing children in back to front order, which confirmed the suspicions.

A very similar problem can also occur when detaching / attaching / moving nodes.

I've also profiled the slow situation:

Steps to reproduce

• Add a large number of children to a node (5000+)
• Call queue_delete() in the order of get_child()

Minimal reproduction project

QueueDeleteSlow.zip

• Run the MRP, takes ~5 seconds to add 10,000 boxes and queue delete.
• Comment out the queue_free() line 14, takes 250ms.

If you queue free in reverse order:

	var num_children = $Boxes.get_child_count()
	for n in range (num_children):
		$Boxes.get_child(num_children - 1 - n).queue_free()

It takes 730ms - still curiously slower than adding, but a lot faster than before.

Update
Make the box invisible to eliminate the BVH from the bottlenecks, this shows the real difference from the PR linked.

Discussion

It is possible we can modify the deletion code to prevent this situation occurring, perhaps by guaranteeing reverse ordering:

• sorting the deletion list
• searching in reverse order through children for queued_for_deletion flags when deleting nodes

Additionally, if there is a notification on re-ordering, perhaps it can be sent once (after all deletes) instead of after each deletion.

[lawnjelly]

Related:
Recent profiling indicates this problem also unsurprisingly occurs with detaching nodes, with a similar exponential increase in time taken as the number of children increases, due to notifications.

[Zylann]

I just noticed this problem too in Godot 4, as I was removing about 500 3D nodes from a list of a few thousand siblings. It resulted in hiccups where framerate slowed down to 180ms.

The main culprit in my case was the NOTIFICATION_MOVED_IN_PARENT notification. It is sent to every node following the removed one. But sadly, it turns out none of the nodes care about that notification anyways, only 2D nodes are using it, so it's just wasted.
Removing the notification code made the removal fast enough to not cause hiccups anymore.

Possible workarounds:

• Make container "bucket" nodes, where each can have up to 10 children, in order to artificially reduce the number of siblings. This however require some management and creates extra nodes.
• Stop using nodes altogether and use servers. However that may affect usability, in my case I chose to use nodes because they are collision objects, which users can raycast and get an individual result from.
• Reduce numbers. That makes sense, but given what the real bottleneck is, I'd prefer other options first.

Possible solution:

• Make NOTIFICATION_MOVED_IN_PARENT opt-in. If only a specific family of nodes is using it, that's probably better (Node2D, Skeleton2D, Control, CanvasItem or CanvasLayer). Node has no clue on what it sends the notification on, so it could be a flag, maybe packed in a bitfield, so it would be fast to check and would cost no extra space. I tested this solution and it got rid of the issue as well.
• More specific to nodes using NOTIFICATION_MOVED_IN_PARENT: defer the notification. It is likely the removal of many nodes would make some siblings receive many times the same notification, which could be addressed in [3.x] Add deferred notifications #65581. Although it would still be nice if we could avoid sending such notifications in the first place when they arent needed. Besides, pushing a deferred notification and checking if it has been sent already has a cost in itself, and breaks compat...

Other solutions for 2D nodes could depend on how that notification is actually used. Maybe it could be changed to some lazy evaluation or polling (node index is updated faster than sending the notification). A virtual function could be used, though I dont know how fast it would be.

[lawnjelly]

This issue (deletion) is mostly solved by a combination of #62444 (particularly where large percentage of siblings are deleted) and #65581 (prevents more than 1 notification). I discussed the use of bitflags, observer pattern etc in #65581 (comment) in the "additional methods".

As I say there, registering an interest and observer pattern is potentially the most efficient mechanism, but the problem of backward compatibility is important (especially in 3.x), and also weighing up the complexity / efficiency of maintaining observer lists versus simpler, less perfect solutions. For NOTIFICATION_MOVED_IN_PARENT you also have to do something like sort the observer list, or go through it each time to determine which nodes are ahead of the changed child, because the notification is only sent to children later in the child list, not earlier. So you may exchange a bottleneck in one place, for a bottleneck in another.

I'm happy to do an observer lists PR, but really am waiting for these existing PRs to either be merged or get further review from @reduz . Otherwise it could be a waste of time. Observer lists is also very compat breaking so is more likely to be refused, so would be better to discuss first.

An additional technique I considered but didn't write about before is maintaining the ID within the child list of a node that all others are considered dirty, and flushing this list for NOTIFICATION_MOVED_IN_PARENT in a single step on a tick, rather than checking each Node individually for an existing deferred notification. This would work for the particular case of MOVED_IN_PARENT, but isn't very generic.

[Zylann]

and also weighing up the complexity / efficiency of maintaining observer lists

you also have to do something like sort the observer list

There is no observer list to maintain in my solution. The change is only a few lines. Also, I did it in Godot 4.

[lawnjelly]

Sorry, I was not clear - in that quoted paragraph I'm discussing only observer lists. 🙂

[akien-mga]

Fixed by #62444 for 3.6.

Still relevant for master, as #62446 hasn't been merged yet (@reduz wants to explore an alternative solution, likely after the 4.0 release).

[eimfach]

Fixed by #62444 for 3.6.

Still relevant for master, as #62446 hasn't been merged yet (@reduz wants to explore an alternative solution, likely after the 4.0 release).

Milestone 3.6 was removed, does that mean it won't get into 3.6 ?

[akien-mga]

It's fixed in 3.6 as I wrote above. But it's not fixed in 4.0, which is why this issue is still open - and since it's now a 4.x specific bug, the 3.6 milestone isn't accurate.

[wareya]

Is there going to be a way to allow nodes to opt into NOTIFICATION_MOVED_IN_PARENT in 4.x in the future?

I'm making a container node that uses NOTIFICATION_MOVED_IN_PARENT to refresh its background. It draws the background with VisualServer and needs to make it a non-child of the container node to prevent it from being clipped by the container's bounds, with the draw index based on the index of the container node in its parent. I need to use this notification because otherwise moving other nodes around the container causes the background to draw at the wrong sort level, resulting in situations like this:

2023-08-12_06-48-49.mp4