godot icon indicating copy to clipboard operation
godot copied to clipboard

Improve `Tree` performance

Open aaronp64 opened this issue 7 months ago • 4 comments

Added TreeItem::last_child to avoid needing to iterate through all children to get to the end. This mainly helps in cases where one TreeItem has many children (1000s), and new children are added to the end, as each add had to iterate through all previously added children.

Gdscript example to compare creating TreeItems, time reduced from 1640ms to 66ms:

func _ready() -> void:
	var root = $Tree.create_item()
	root.set_text(0, "Root")
	var start_time = Time.get_ticks_msec()
	for i in 20000:
		var item = $Tree.create_item()
		item.set_text(0, "Item " + str(i))
	var end_time = Time.get_ticks_msec()
	print("Time: %dms" % (end_time - start_time))

This also impacts SceneTreeEditor. I created a Node2D scene with 10,000 empty Node2D children to test with. Opening this scene took 4.28 seconds before this change, 1.55 seconds after. At 20,000 children, time was reduced from 16 seconds to 2.65 seconds.

EditorDebuggerTree has similar slowness in adding items, but also is repeatedly updated when running game from the editor. Using the gdscript below to create 30,000 Node2Ds at runtime, the editor is significantly more responsive when using the remote scene tree while the parent node stays collapsed. Once the parent node is expanded, more time is spent handling the tree's text/heights, which gets pretty slow, but is still faster than before.

func _ready() -> void:
	for i in 30000:
		add_child(Node2D.new())

Also added some unit tests. All tests pass with both old and new code, except for the Clear items test, which failed on old code due to children_cache not being cleared in clear_children(). Looks like we avoided needing to use the cache in existing code where clear_children() is called, so this hasn't been an issue.

aaronp64 avatar Jul 25 '24 18:07 aaronp64