Godot-proposals: Add a way to remove all children from a node quickly

[Shadowblitz16]

Describe the project you are working on:
a game in which I am generating a ton of nodes

Describe the problem or limitation you are having in your project:
I am trying to generate a 16x16 plane of objects however everytime I edit the width and height of the grid it needs to be cleared and updated

doing so by looping through all nodes is too slow in gdscript and there needs to be a way to clear a branch all at once.
possibly through pointers

Describe the feature / enhancement and how it helps to overcome the problem or limitation:
I suggest remove_children() be added as a work around.
this would be a fast way of clearing all the children of a node

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:
node.remove_children()

If this enhancement will not be used often, can it be worked around with a few lines of script?:
idk if it would be used often but we already had a merge request here but was shut down

Is there a reason why this should be core and not an add-on in the asset library?:
because its a simple way to manage nodes without slowing down godot

[Xrayez]

I've been using godotengine/godot#8337 without issues so far. I work with images and use a grid container for color palettes, spawning random objects given random seed and whatnot.

If the issue that some children are actually essential for correct functionality of a node (quite a bunch of the GUI nodes), these kind of nodes should be made internal as suggested in godotengine/godot#30391.

[groud]

doing so by looping through all nodes is too slow in gdscript and there needs to be a way to clear a branch all at once.

What do you mean it is too slow ? Do you have some numbers ? Are you sure this comes from gdscript ? Because I highly doubt your bottleneck come from gdscript, the simple removal and re-instanciation of a node is a demanding task, whether or not the call to remove_child() is made in gdscript or in native code will likely make no significant difference.

[Xrayez]

Providing some GDScript methods:

extends Node

static func queue_free_children(node: Node) -> void:
    for idx in node.get_child_count():
        node.queue_free()

static func free_children(node: Node) -> void:
    for idx in node.get_child_count():
        node.free()

# Usage
func _ready():
    queue_free_children(self)
    free_children(self)

propagate_call("queue_free") doesn't work because we actually need to save parent... 😄

By the way, if Godot really tries to be simplistic, we can remove Node.get_children() because it can be easily done via script similarly:

static func get_children(node):
    var children = []
    for idx in node.get_child_count():
        children.push_back(node.get_child(idx))
    return children

But I guess it's used more often which justifies it being in core...

[groud]

But I guess it's used more often which justifies it being in core...

Yes, that the difference actually. Iterating over nodes is really common.

Removing all nodes, and very likely re-instanciating them afterwards as OP does, is a really bad practice. Re-instanciating nodes instead of updating them is significantly more resource demanding, so encouraging such practices by simplifying the API for doing so is not really a great idea.

[RabbitB]

Maybe I'm misunderstanding the issue, but if removing all children from a node is a common task in your program, couldn't you streamline the process by removing the parent and instancing it again? Or if that's not feasible, create a child under the current parent, that will contain all the nodes that will regularly need to be cleared, so you can remove the single child instead of looping through all of them?

queue_free also frees any children when called on a Node, so it sounds like what you're trying to accomplish is already easily done. It just requires a slightly different solution than what you were already attempting.

[Shadowblitz16]

@groud I tried to generate a 16x16x1 grid of spatial nodes and it took like 3 seconds for 1 loop
I even added a yield to make it not lock up the editor
@RabbitB I would then have to make packed scene for it and even then its children would be instanced again

I don't see why making a engine side function that does

for n in get_children(): remove_child(n) 

would be a big issue the only difference would be that it would be faster

[groud]

@groud I tried to generate a 16x16x1 grid of spatial nodes and it took like 3 seconds for 1 loop

Once again, this still does not mean that moving the loop to native code is going to make the code significantly faster. If your code spends 99% of its time inside the removing and instantiating code, which is very likely the case, optimizing the loop will only give you a 1% speed increase.

And we won't optimize an API just to win a 1% speed increase, especially if it encourages bad practices (as I said earlier, fully replacing nodes is significantly heavier than updating them).

[Xrayez]

fully replacing nodes is significantly heavier than updating them

While I have to agree with this statement, in some cases it's important to have reproducible results. Yeah you could allocate some maximum number of nodes and update them manually, but that comes with the cost of potential inconsistent results between successive iterations/generation of a game level. Some other aspects to keep track of like ensuring node's signals are also re-connected to callbacks on the next generation. This is all handled by the queue_free.

The way I see it, it's not necessarily about speed, but about consistent results, QoL, and additional performance gain which comes from not using GDScript for loop-related heavy computations.

queue_free also frees any children when called on a Node, so it sounds like what you're trying to accomplish is already easily done. It just requires a slightly different solution than what you were already attempting.

That's a good workaround, but again we're talking about usability of the engine achieved out-of-the-box, with additional benefit of a slight increase in performance, every bit counts. 🙂

[groud]

every bit counts

Not at the price of a bloated API.

[Xrayez]

every bit counts

Not at the price of a bloated API.

Little things make big things happen. 😛

I actually have a counter proposal.

Currently propagate_call() works by calling methods on the children and the caller itself. What about adding an option to exclude the caller (which would prevent the caller from being freed)?

I mean something like:

propagate_call_children("queue_free")

Not only this would be useful for this particular proposal, but many other use cases where we want to exclude the parent by propagating calls like that.

Adding another boolean option to exclude parent would still be a bloat to API, nor adding a new method like this though.

Isn't every new addition is actually a bloat?

[Shadowblitz16]

@groud I can garentee you 1000% that it would be alot more 1% I would say at least 50% if not more

I don't need to bench mark gdscript to tell you how slow it is.
people have already done it and its and least 10 times slower then C#

[groud]

I don't need to bench mark gdscript to tell you how slow it is.

This is your assertion, which, once again, has to be proven true. Please do a benchmark.

It's simple to do, make the same loop without the function call (or eventually with a dummy call to a function), and you will see how little time it take to iterate over 16 x 16 objects... Then compare the time to the same loops with queue_free(), and the difference will be the time spent in the call to queue_free().

GDscript is slower than c++, it does not make it unable to rapidly go over 256 object...

[groud]

Alright, so I made the benchmark myself anyway (I added a button to run the _on_Button_pressed function) :

extends Node

func _ready():
    for i in range(16):
        for j in range(16):
            var node = Node3D.new()
            add_child(node)

func _on_Button_pressed():
    var time_before = OS.get_ticks_usec()
    for child in get_children():
        child.queue_free()
    var time_after = OS.get_ticks_usec() 

    print(str(time_after - time_before) + "us")

This prints:

So it takes 495us (microseconds) to call queue_free on 256 nodes in gdscript... There is absolutely no way your bottleneck is here. Let's imagine your target fps is 60fps, so a frame duration is 16ms, and you could divide those 495us by 10. In the end you would end up with an improvement of (0.495 * 9/10) / 16 = 2.8%. And this would be if you absolutely wanted to do this every frame, which in not advised at all.

In your case where the whole deletion takes 3seconds, the improvement would be around (0.495 * 9/10) / 3000 = 0.015%. So, as I said, far less than 1% of the time it takes to actually remove the nodes.

And in fact, this is perfectly understandable, as queue_free() delays the freeing of the nodes at the end of the frame, so it does not do much directly. So in the end, optimizing this part of the code in C++ would make absolutely no sense.

[RabbitB]

@groud Even if queue_free was dog-slow, like I mentioned before, there's already a native optimized version of it that frees tons of nodes together. It's called queue_free. It does it automatically even.

If @Shadowblitz16 thinks queue_free is the source of his issue, and still thinks so after your post, then he can do a simple reorganization of his nodes. Wherever he's instantiating his nodes now, just add a singular node there and make all the nodes he wants to free, a child of that instead. Then he can easily call queue_free on that single node and it will handle everything in native code.

[Shadowblitz16]

@groud @RabbitB and what are you comparing it to? groud didn't do a C++ or C# test.

I think 3 seconds is way to long to free up 256 nodes.

I don't think there would need to be a reason to write sandbox generation code like this in gdnative if groud was actually correct.

if its true that its not the loop and is actually the node deletion at the end of the frame then that should be optimized.

and even so I don't still don't think having a way to queue_free a nodes children would be bad.
since it would be looping c++ side it could also do some memory tricks to optimize it.

[mhilbrunner]

I think 3 seconds is way to long to free up 256 nodes.

Please provide an example where freeing 256 nodes takes 3 seconds.

The only one who provided any specific data so far was groud, who claims

So it takes 495us (microseconds) to call queue_free on 256 nodes in gdscript

Please provide your code where it takes 3 seconds. :) Maybe you're running into a bug.

since it would be looping c++ side it could also do some memory tricks to optimize it.

Like what tricks?

[RabbitB]

and even so I don't still don't think having a way to queue_free a nodes children would be bad.
since it would be looping c++ side it could also do some memory tricks to optimize it.

I don't think I understand what you're asking at this point, because queue_free already operates on all children of a node, and does so within C++. In fact, here's all the relevant code for it!

/* node.cpp */

// line 2879
ClassDB::bind_method(D_METHOD("queue_free"), &Node::queue_delete);

// line 2687
void Node::queue_delete() {

    if (is_inside_tree()) {
        get_tree()->queue_delete(this);
    } else {
        SceneTree::get_singleton()->queue_delete(this);
    }
}

// line 53
void Node::_notification(int p_notification) {
    // ... line 159
    case NOTIFICATION_PREDELETE: {

        set_owner(nullptr);

        while (data.owned.size()) {

            data.owned.front()->get()->set_owner(nullptr);
        }

        if (data.parent) {

            data.parent->remove_child(this);
        }

        // kill children as cleanly as possible
        while (data.children.size()) {

            Node *child = data.children[data.children.size() - 1]; //begin from the end because its faster and more consistent with creation
            remove_child(child);
            memdelete(child);
        }
    // ...

/* scene_tree.cpp */

// line 1016
void SceneTree::queue_delete(Object *p_object) {

    _THREAD_SAFE_METHOD_
    ERR_FAIL_NULL(p_object);
    p_object->_is_queued_for_deletion = true;
    delete_queue.push_back(p_object->get_instance_id());
}

// line 1002
// _flush_delete_queue is called on the next idle frame.
void SceneTree::_flush_delete_queue() {

    _THREAD_SAFE_METHOD_

    while (delete_queue.size()) {

        Object *obj = ObjectDB::get_instance(delete_queue.front()->get());
        if (obj) {
            memdelete(obj);
        }
        delete_queue.pop_front();
    }
}

This is actually pretty simple to follow, except that freeing children is separated from the actual object freeing code. When you call queue_free in GDScript, it's bound to queue_delete in the Node class. queue_delete gets the SceneTree and calls its own queue_delete. The queue_delete in the SceneTree just marks the node as queued for deletion and pushes it onto the object delete queue. At the end of each idle frame, every object in the delete queue gets freed using memdelete.

I didn't post it here, but all memdelete does is call any deconstructors or special predelete handling code defined for an object, and then frees the memory of that object. This is where that NOTIFICATION_PREDELETE section comes in. Immediately before a Node is freed in memory, it destroys all of its children by calling memdelete on them as well. This cascades the deletions, which removes all children of the originally deleted Node, all of their children, etc. until nothing is left to be freed.

Suffice to say, this happens fast. In fact, the only thing that really takes any time is the actual freeing of memory, which is performance limited by the OS and not Godot.

P.S. This is why Godot is so freakin' awesome. If you have any questions about how something works or exactly what it does, you can dig into the source yourself and trace the entire process.

[mhilbrunner]

@RabbitB I think the difference is that queue_free deletes the node and it's children, not only the children?

[RabbitB]

I think the difference is that queue_free deletes the node and it's children, not only the children?

It does, but if @Shadowblitz16 needs the ability to delete all children at once, queue_free already provides it. You just need to reparent the children under a separate node, and then make that node a child of your original node you don't want to delete.

I do understand that's not exactly what @Shadowblitz16 wants, but game development has always been a huge long list of what we want and what we can do. For practical reasons, this is the most straightforward solution.

All that said, freeing the memory is still the most expensive part of queue_free, so without actual testing, I'd dare make the assumption that there's negligible difference between freeing everything at once, or iterating through every child and calling queue_free individually. If it's too slow, it's because of a game design issue, not an engine issue. Which isn't that surprising, considering that minimizing memory allocations and deletions has always been one of the biggest factors in directing game development.

[mhilbrunner]

You just need to reparent the children under a separate node, and then make that node a child of your original node you don't want to delete.

Thats a lot more cumbersome than calling a hypothehical free_all_children(), though.

I'd dare make the assumption that there's negligible difference between freeing everything at once, or iterating through every child and calling queue_free individually

That seems to be the case, yes. Still, maybe having a free_all_children() shortcut may be worth it, as its shorter and more clear, if this use case crops up often enough.

[Duroxxigar]

So I got curious and I repeated the test that @groud did. My results were a little faster however. The before pic won't have anything printed because well...it hasn't been ran yet. The after will have the time printed.

BEFORE

AFTER

Still hungry for the coveted 3 second amount with this test, I tried 2500 nodes. This resulted in about 1500us

I then cranked it up some more. Up to 4900 nodes. This resulted in about 2900us

I then wanted to see what would happen if I had a child on each of THOSE nodes. This is about 9800 nodes in total.

After running that one, it was only a marginal increase for essentially double the amount of nodes. 3301us

Personally - I would really like to see your project getting hung up on freeing 256 nodes. (Not saying it is impossible).

[Shadowblitz16]

@Duroxxigar I am a bit busy today if I find time to make a reproduction project I will.

I am also using it on 3d meshes which and nested mesh children to make up a turret instead of 2d or ui nodes.

[Jummit]

Here is the "official" potential implementation:
https://github.com/godotengine/godot/blob/49a1e3db12a5543ab9e512ad04c478d9d5ef77c7/scene/main/node.cpp#L173-L179

// kill children as cleanly as possible
while (data.children.size()) {


    Node *child = data.children[data.children.size() - 1]; //begin from the end because its faster and more consistent with creation
    remove_child(child);
    memdelete(child);
}

[Xrayez]

That seems to be the case, yes. Still, maybe having a free_all_children() shortcut may be worth it, as its shorter and more clear, if this use case crops up often enough.

Found an occurrence recently: https://github.com/Strangemother/godot-simple-floorplan-generator/blob/b4c1d0ae298170bd32cf05333ccaec4f02b55517/scripts/Space.gd#L54-L57.

Again, procedural generation topic. 😛

As for me, it's not really about performance, but convenience. If this could provide some performance boost (and it will), that's just a nice byproduct.

I don't understand why this even needs a discussion, makes perfect sense for something like this to be in core, dang...

[Xrayez]

See API of other software/frameworks:

1. https://docs.microsoft.com/en-us/dotnet/api/documentformat.openxml.openxmlelement.removeallchildren?view=openxml-2.8.1

2. https://developer.apple.com/documentation/spritekit/sknode/1483040-removeallchildren?language=objc

3. https://apireference.aspose.com/words/net/aspose.words/compositenode/methods/removeallchildren

4. https://flex.apache.org/flexunit/asdoc/flexunit/org/fluint/uiImpersonation/VisualTestEnvironment.html

5. http://www.cs.umd.edu/hcil/jazz/learn/piccolo.net/doc-1.2/api/UMD.HCIL.Piccolo.PNode.RemoveAllChildren.html

[Xrayez]

Found some occurrences in Godot's editor for clearing children:

https://github.com/godotengine/godot/blob/1dd2cf79140644913f50283a32ba7cd07f5e48aa/editor/editor_properties_array_dict.cpp#L314-L318
https://github.com/godotengine/godot/blob/1dd2cf79140644913f50283a32ba7cd07f5e48aa/editor/find_in_files.cpp#L430-L432

[Xrayez]

I propose to add Node.clear_children():

Removes all children from the scene tree and frees them with [method queue_free]. If you need to delete children immediately, free them manually in a [code]for[/code] loop instead.

[udit]

I propose to add Node.clear_children():

If someone uses this on root it will delete singletons also, right? I think documentation should also include a warning about that. Someone might use this as a part of generic custom scene switcher to change sub-scenes as well as current scene.

[Xrayez]

@udit likely yes, it's always possible to break the system if you need. 🙂

Someone might use this as a part of generic custom scene switcher to change sub-scenes as well as current scene.

I think this would be a wrong method to choose for scene switching.

---

Also, I think it might be actually better to make Node.clear_children() to free children immediately. This is because you can always call Node.call_deferred("clear_children") to simulate the behavior of queue_free(), otherwise you'd be limited to just queue_free by default (without introducing another method like Node.queue_clear_children(), which would be already quite inconsistent with queue_free name).