Poor performance of 2D Tree View with many items

[Developer-Alexander]

Godot version

v4.0.beta10.mono.official

System information

Windows 11, Intel UHD Graphics 770

Issue description

When many items (10000+) are added to a 2D Tree view the performance decreases drastically until the windows freezes completely. It starts with very low slow scrolling and ends up with a complete freeze for some minutes. The mouse wheel is practically unusable. When maximizing the windows it freezes instantly.

I would expect that the UI would run smoothly even with a large number of nodes added to a Tree View.

Steps to reproduce

Add a 2D Tree View to an empty scene. Add a simple script to a large number of nodes to the Tree View.

Minimal reproduction project

tree_bench.zip

[Calinou]

This is expected if you don't use a recycling system ("virtual scrolling") to display only the part of the tree that is currently relevant. The current lack of 2D batching in the Vulkan renderer doesn't help either (#70415). As a result, this particular test case may perform better in 3.x or with the Compatibility backend (which uses OpenGL and features batching).

In the meantime, I recommend implementing a pagination system for your tree display.

[ConteZero]

Could be related to #56199

[AThousandShips]

From my own experience this is specifically when adding the items right? This is because the shaping of each item takes a while and blocks, there might be ways we can make it not shape items that aren't visible (though I'm not familiar with the details of that code) or similarly avoid the performance hit, but does this problem go away if you add the items gradually? If the items are nested you can also improve the performance by folding some of them.

[Developer-Alexander]

As a result, this particular test case may perform better in 3.x or with the Compatibility backend (which uses OpenGL and features batching)

I did try it with OpenGL Backend and the performance was noticeably better. But maximizing the window freezes the App all the time.

In the meantime, I recommend implementing a pagination system for your tree display.

Unfortunately the usecase does not work well with pagination. It is more like a giant tree, that loads and unfolds just the nodes as they are requested by the user. But in the end the number of nodes can become very large.

[Developer-Alexander]

Is there a chance for a more fluid experience in a near future?
Especially the freezing windows when maximizing or changing the size of the window is a big problem from my point of view.

[Calinou]

Is there a chance for a more fluid experience in a near future? Especially the freezing windows when maximizing or changing the size of the window is a big problem from my point of view.

Despite looking simple, this is a difficult thing to optimize. It won't be done for 4.0, and is dependent on the willingness of contributors to look into this issue.

I would recommend you recreate the same benchmark in 3.5.1 to see if there's a significant performance regression. You can also try forcing the use of the fallback TextServer to see if the advanced TextServer is the cause of the lower shaping performance. To do so, you'd need to compile Godot from source (as the fallback text driver isn't compiled by default, since the advanced text driver can do everything the fallback text driver does). Pass the module_text_server_fb_enabled=yes option to SCons when compiling, then set the text driver to Fallback in the advanced Project Settings.

[lawnjelly]

I noticed this happening in my own music app when displaying too many notes in a scrollable window. I'll probably end up making a "virtual window" as @Calinou suggested above, but ideally this kind of thing would be handled by the engine automatically (at least for the main core controls).

I was also getting errors due to the command queue being overfilled. This suggests part of the problem is a design issue in Godot 2D (also relevant in 3D, but there don't tend to be as many items):

Global transforms are sent individually to the VisualServer per canvas item if the parent item (or scrollbar) is moved.

This in itself is a bottleneck. Ideally for a scene tree we should be sending just one changed transform across the thread boundary (client code to VisualServer) and letting the VisualServer recalculate according to the parent. But because of Godot design philosophy (making it work even without a scene tree) the emphasis has been on treating each item individually, rather than part of a scene graph.

Of course there are several components to this overall problem and different ways of making it more efficient with the least amount of recomputation.

There are several component problems (with some overlap):

• The problem of rendering efficiently when scrolling
• The problem of recalculating transforms when a small part of the entire tree is modified (can we reuse existing structure above and below the modification?)
• The problem of input, collide detecting through a large tree.

Some kind of virtual window handled client side might be a straightforward approach to work within the existing Godot design. It might not work in every scenario, but for situations where content can easily be split up into "lines" it makes sense.

The idea would be to either pre-create or create on the fly the lines needed for the entire control or the virtual window in the client code, then either:

• Only activate the lines that are currently in view in the VisualServer
• Create / destroy canvas items on the fly (or use a pool) to get the lines to show up in the VisualServer

The second approach is particularly important if you have a lot of data, for instance you want to display a text file that is several megabytes.

Calculating a virtual window for a simple list is easier than for a 2D Tree View, but even the tree view should be acceleratable.

[Developer-Alexander]

Thank you for that great explanation. If you have an good example for an implementation of a virtual window please let me know.

The problem of rendering efficiently when scrolling

I found out that every scroll event triggers TreeItem *Tree::_find_item_at_pos() that triggers int Tree::get_column_minimum_width() which does a scan trough all items of the tree to figure out the size of the colum.

I think this is an information that could be cached easily and updated only when a TreeItem changes.

Setting set_column_clip_content(0, true) in GDScript brought a massive performance boost since the iteration of all TreeItems is skipped. It results in a much more fluent scrolling experience. But it still consumes a lot of CPU time. There might be even mor space for optimization. (e.g. cache item hight of TreeItems children)

[Developer-Alexander]

TreeView has another performance issue: When adding many child nodes to a node the worst case time complexity becomes O(n²).

Reason for this is that in the worst case all current children are walked through to find the postion where to place the new child.

This becomes a problem for example when you want to perform a bulk insert.