Using the slowest data structure almost every time.

[vblanco20-1]

MODERATOR NOTE: This issue is over five years old and discusses a reality that no longer matches the status quo of the codebase. For more information, scroll to this comment.

--

I was reviewing the code of godot, and i`ve found complete disregard for any kind of cpu side performance, down to the core data structures. Its using List everywhere, when a linked list is the slowest data structure you can use on modern PCs. Almost any other data structure would be faster, specially on small sized structures. Its specially egregious on things like the light list or reflection captures in renderables, where you are storing 3 pointers every time, instead of just giving it a stack array of 8 max lights (for example) + an extra for the cases where it would be more than that.

Same thing with RID_Owner being a tree where it could be a hash map, or a slotmap. Also the Octree implementation for culling has the exact same issue.

I want to ask about the design intention behind that total and absolute overuse of linked lists and dreadful performance pointer heavy data structures everywhere in the code. Is that for a specific reason? In most of the cases a "chunked" linked list, where you do a linked list of arrays would automatically bring performance gains on the same code.

The use of these data structures also prevents any kind of "easy" parallelism in a good chunk of the code and completely trashes the cache.

I am working on making a proof of concept implementation of refactoring some of the internals to use better data structures. At this moment i am working on a rewrite of the culling code which bypasses the current octree and just uses a flat array with optional parallelism. Ill use the tps-demo as benchmark and come back with results, which in fact i have benchmarked to go 25 levels deep on that octree...

On another more happy note, i am very impressed with the code style quality, everything is easy to follow and understand, and quite well commented.

[mafiesto4]

Who needs performance?

Curious to see what you measure.

[Ranoller]

So this can explain why a simple Light2D node in Godot can burn your computer?

[CptPotato]

@Ranoller I don't think so. The bad lighting performance is most likely related to how Godot performs 2D lighting at the moment: Rendering every sprite n-times (with n being the number of lights that are affecting it).

Edit: see #23593

[vblanco20-1]

To clarify, this is about CPU side inefficiencies all over the code. This has nothing to do with godot features or godot GPU rendering itself.

[pgruenbacher]

@vblanco20-1 on a bit of a side-tangent, you and I had talked about the nodes being modeled as ECS entities instead. I wonder if the trick is to do a feature branch of godot with a new ent module that would gradually work side-by-side with the tree. like a get_tree() and get_registry(). the ent module would probably miss like 80% of the functionality of the tree/scene, but it could be useful for as a testbed, especially for stuff like composing large static levels with lots of objects (culling, streaming, batch rendering). Reduced functionality and flexibility but greater perfromance.

[vblanco20-1]

Before going full ECS (wich i might do) i want to work on some low hanging fruits as a experiment. I might try to go full data-oriented later down the line.

[vblanco20-1]

So, first updates:

update_dirty_instances : from 0.2-0.25 miliseconds to 0.1 milisecond
octree_cull (the main view): from 0.35 miliseconds to 0.1 milisecond

The fun part? the replacement for octree cull is not using any acceleration structure, it just iterates over a dumb array with all the AABBs.

The even funnier part? The new culling is 10 lines of code. If i wanted to have it parallel, it would be a single change to the line.

Ill continue with implementing my new culling with the lights, to see how much the speedup accumulates.

[pgruenbacher]

we should probably get a google benchmark directory going too on the master branch. That may help with validating so people don't have to argue about it.

[bojidar-bg]

There is the godotengine/godot-tests repository, but not many people are using it yet.

[vblanco20-1]

New update:

Ive implemented a fairly dumb spatial acceleration structure, with 2 levels. Im just generating it every frame Further improvement could make it better and update it dynamically instead of remaking it.

In the image, the different rows are different scopes, and each of the colored block is a task/chunk of code. In that capture, im doing both the octree cull and my cull side by side to have a direct comparaison

It demonstrates that recreating the entire acceleration structure is faster than a single old octree cull.
Also that further culls tend to be about half to one third of the current octree.

I havent found a single case where my dumb structure is slower than the current octree, other that the cost of the initial creation.

Another bonus is that its very multithread friendly, and can be scaled to whatever core count you want just with a parallel for.

It also checks the memory completely contigously, so it should be possible to make it do SIMD without much hassle.

Another important detail is that its vastly simpler than the current octree, with way less lines of code.

[Ranoller]

You are causing more hype that the end of game of thrones....