C++:

			Control *ctrl = memnew(Control);
			add_child(ctrl);

			{
				const int count = 100000;
				const int internal_count = 50000;

				for (int i = 0; i < internal_count; i++) {
					ctrl->add_child(memnew(Control), false, INTERNAL_MODE_FRONT);
				}

				for (int i = 0; i < count; i++) {
					ctrl->add_child(memnew(Control));
				}

				for (int i = 0; i < internal_count; i++) {
					ctrl->add_child(memnew(Control), false, INTERNAL_MODE_BACK);
				}
				
				// Validate cache.
				int child_count = ctrl->get_children().size();
				print_line(vformat("Children count = %d", child_count));
			}

			{
				int time = Time::get_singleton()->get_ticks_msec();
				int count = ctrl->get_children().size();
				print_line(vformat("Before: get_children, internal=true: %d ms", Time::get_singleton()->get_ticks_msec() - time));
				print_line(vformat("Children count = %d", count));
			}

			{
				int time = Time::get_singleton()->get_ticks_msec();
				int count = ctrl->get_children_fast().size();
				print_line(vformat("After: get_children, internal=true: %d ms", Time::get_singleton()->get_ticks_msec() - time));
				print_line(vformat("Children count = %d", count));
			}

			{
				int time = Time::get_singleton()->get_ticks_msec();
				int count = ctrl->get_children(false).size();
				print_line(vformat("Before: get_children, internal=false: %d ms", Time::get_singleton()->get_ticks_msec() - time));
				print_line(vformat("Children count = %d", count));
			}

			{
				int time = Time::get_singleton()->get_ticks_msec();
				int count = ctrl->get_children_fast(false).size();
				print_line(vformat("After: get_children, internal=false: %d ms", Time::get_singleton()->get_ticks_msec() - time));
				print_line(vformat("Children count = %d", count));
			}

			remove_child(ctrl);
			memdelete(ctrl);

GDScript:

	var internal_count: int = 10000
	var count: int = 10000

	for i in internal_count:
		add_child(Control.new(), false, Node.INTERNAL_MODE_FRONT)

	for i in count:
		add_child(Control.new())

	for i in internal_count:
		add_child(Control.new(), false, Node.INTERNAL_MODE_BACK)

	# Validate cache.
	get_children()

	var time = Time.get_ticks_msec()
	get_children(true)
	prints("Before: include internal: ", Time.get_ticks_msec() - time)

	time = Time.get_ticks_msec()
	get_children_fast(true)
	prints("After: include internal: ", Time.get_ticks_msec() - time)

	time = Time.get_ticks_msec()
	get_children()
	prints("Before: exclude internal: ", Time.get_ticks_msec() - time)

	time = Time.get_ticks_msec()
	get_children_fast()
	prints("After: exclude internal: ", Time.get_ticks_msec() - time)

I'm guessing the bottleneck is the repeated get_child call, both because of the thread guard, but also because it does a lot of unnecessary checks.

The bottleneck was that _update_children_cache() was called when include_internal==true which results in two loops over all children instead of just one loop with the current implementation, you can see the difference when include_internal==false it's only faster by 2ms which was the cost of calling get_child.

The bottleneck was that _update_children_cache() was called when include_internal==true which results in two loops over all children instead of just one loop with the current implementation, you can see the difference when include_internal==false it's only faster by 2ms which was the cost of calling get_child.

Yes, but we expect children to update rarely. Updating the children cache is somewhat costly once, but iterating it afterwards is nearly free compared to iterating the HashMap.The reason being that the children cache has all elements in a contiguous array, while iterating the children HashMap can results in a lot of cache misses. It is important for the performance of Node to use the children cache wherever possible.

This follows up get_child_count implementation where we update the cache only to exclude internal children which results in faster return when include_internal == true.

int Node::get_child_count(bool p_include_internal) const {
	ERR_THREAD_GUARD_V(0);
	if (p_include_internal) {
		return data.children.size();
	}

	_update_children_cache();
	return data.children_cache.size() - data.internal_children_front_count_cache - data.internal_children_back_count_cache;
}

The implementation of get_child_count can exploit the fact that we do not need to iterate the children at all when p_include_internal is true. This makes for an obvious shortcut without trade-off.

However, get_children does need to iterate the children, and therefore it needs to use the children cache. If it weren't using the children cache, we'd be losing most of the performance to cache misses in cold access situations.

Yes, but we expect children to update rarely. Updating the children cache is somewhat costly once, but iterating it afterwards is nearly free compared to iterating the HashMap.The reason being that the children cache has all elements in a contiguous array, while iterating the children HashMap can results in a lot of cache misses. It is important for the performance of Node to use the children cache wherever possible.

_update_children_cache loops over the HashMap already and i just have saved this step, a better implementation may be to check if data.children_cache_dirty so we loop over the HashMap instead of resulting in two loops over all children, this is useful especially when we need to use methods that doesn't require updating the cache like remove_child.

	for (const KeyValue<StringName, Node *> &K : data.children) {
		data.children_cache[idx] = K.value;
		idx++;
	} 

a better implementation may be to check if data.children_cache_dirty so we loop over the HashMap instead of resulting in two loops over all children

Yes, this would be faster on first access (with the caveat that it would work for the scenario where p_include_internal is false).
However, we shouldn't be optimizing for the 'first access' case.

Like I mentioned above, in general we expect the children to be relatively constant over multiple calls. Even if they change once every few frames, there might be dozens of calls to get_children afterwards where the children cache can be exploited.
While you have benchmarked the improvement of performance on hot, initial access, your benchmark does not represent the case we expect to occur most often, which is cold, repeated access. For this case, the children cache is the best solution, even if it does incur a performance cost on the first call where the children cache needs to be created.

Useful use case where it doesn't need to update the children cache:

var children = get_children(true)
# Remove all non control nodes from children.
for child: Node in children:
    if child.get_class() != &"Control":
        remove_child(child)
        child.free()
print_tree_pretty() # Now the cache is updated, but only once instead of twice.

So we can update the cache if it's dirty inside the method when get_children(true) is called and the cache is dirty instead of looping twice over all children, it will remain fast and yet will update the cache if it's dirty.

So we can update the cache if it's dirty inside the method when get_children(true) is called and the cache is dirty instead of looping twice over all children, it will remain fast and yet will update the cache if it's dirty.

Feel free to benchmark it against my proposed solution! I suspect the second loop isn't a bottleneck, compared to the thread guards and extraneous checks that both my proposed solution and your proposed solution mitigate. After this optimization, I'm guessing the allocation and data copying to be the new bottleneck (and not a secondary loop).

Thank you for helping in optimizing it, it appeared that we can't relay on get_children(true) without validating cache or the order may be incorrect, I have only insured that get_child is never called which have added smaller optimization, also updated the code that i have used for testing and insured that i always validate the cache before the benchmarks which was why the first call was much slower than the others.

Thanks for being open about changing the implementation in this way.

You’re welcome! I always appreciate feedback, even when it’s critical. Thank you for your patience and for helping me improve and deepen my understanding of the source code.

For completion's sake, I'd be interested in a benchmark of the current version against master, just to make sure it's a substantial improvement still. But we can merge without it; I'm pretty confident get_child was the major bottleneck to solve here.

Children count = 200,000 (100,000 internal and 100,000 external)

Before: get_children, internal=true: 73 ms
 After: get_children, internal=true: 65 ms

Before: get_children, internal=false: 36 ms
 After: get_children, internal=false: 32 ms

I have made another benchmark against the current implementation and it appears that separating both loops results in faster execution since it has less calculations and uses constants.

TypedArray<Node> Node::get_children(bool p_include_internal) const {
	ERR_THREAD_GUARD_V(TypedArray<Node>());
	_update_children_cache();

	TypedArray<Node> children;

	if (p_include_internal) {
		const int size = data.children_cache.size();
		children.resize(size);

		for (int i = 0; i < size; i++) {
			children[i] = data.children_cache[i];
		}
	} else {
		const int size = data.children_cache.size() - data.internal_children_back_count_cache;
		children.resize(size - data.internal_children_front_count_cache);

		int idx = 0;
		for (int i = data.internal_children_front_count_cache; i < size; i++) {
			children[idx++] = data.children_cache[i];
		}
	}

	return children;
}

Before: get_children, internal=true: 70 ms
 After: get_children, internal=true: 65 ms

Before: get_children, internal=false: 35 ms
 After: get_children, internal=false: 31 ms

The performance improvement is very small (within margin of error possibly, as there's some variance).

I’ve updated the implementation, and I’m curious to see if it now shows a measurable improvement that justifies the effort we invested.

Thanks!