Reduce and prevent unnecessary random-access to `List`

[AThousandShips]

Random-access access to List when iterating is O(n^2) (O(n) when accessing a single element)

• Removed subscript operator, in favor of a more explicit get
• Added conversion from Iterator to ConstIterator
• Remade existing operations into other solutions when applicable

Didn't (generally) replace uses of List with other structures except a few cases where it avoided a lot of code weirdness, it takes a lot more detailed evaluation of uses to handle that side, better left for other PRs by area maintainers

[fire]

I’ curious since this is an optimization there should be profiles that show faster performance.

[AThousandShips]

It's hard to establish exactly, and don't have performance testing setup on my machine, but the basic code can't not be faster simply due to the fundamental logic, unsure how much it would be though and what paths would be critical

[fire]

Anyways I would recommend getting a profile to confirm. Profiling can be unintuitive. This seems clearcut so it might be a good intro to setting up profiling for ourselves.

[AThousandShips]

Agreed, I don't have profiling set up, nor am I sure what parts would be useful to profile directly

[fire]

@Calinou made a benchmark server, we may be able to check total runtime on some of the benchmark tests to see improvement.

[AThousandShips]

Ran benchmark tests and there weren't any reliable benchmark differences either direction, I suspect this won't have direct measurable performance effects on the engine itself but represents a better methodology performance wise at the core, but since List is used so sparingly it likely won't affect things generally, though it might affect areas like GDScript compilation etc.

Since the aim is to use a better method and enforce it generally I'd call the aim performance, but can remove the label if the requirement itself is to produce measurable improvements on the running, but the changes themselves matter just as a matter of appropriate use of the data type

[jsjtxietian]

IMHO there are two types of performace related programming, one is write performant code and one is optimization.

Benchmark is more for the second one, in this case, we do know that access a list can not be faster than access continuous array due to cache effect and it's generally a good advice to do so, we do not need a benchmark to know that. Thousands of small un-optimized code may add up in the future to make it hard for maintainers to do "optimizion" since it may be hard for us to findout any hot spots.

I will take https://github.com/godotengine/godot/issues/76144 as an example, the performace slowdown will be more obvious when the scale is large, and yes we can do the optimization when user report this, but IMHO it would be much better if we can prevent this from happening by apply some simple rules like this pr did. It's not like other optimizations that would require a lot of work, the cost of this pr is relatively low.

[lawnjelly]

Overall this looks great.

I'd be tempted to take the plunge and use local variables (e.g. reference) in a few cases where multiple front()->get() etc are used, just in order to reduce the verbosity.

These weren't there originally granted, so I understand being wary of introducing bugs via duplicate variable names or something. Or could be left to another PR.

[AThousandShips]

Fixed the unnecessary referencing in main, but left most of the other cases alone, as it's a bit of a larger careful refactor, and can do those in a follow-up

[Calinou]

I've tried to compare results between master and this PR on https://github.com/godotengine/godot-benchmarks, but the benchmarks where it would be the most relevant tend to have high runtime variations.

Either way, I've gotten this from hyperfine by running all its GDScript benchmarks:

❯ hyperfine 'bin/godot.linuxbsd.editor.x86_64.master --path ~/Documents/Git/godotengine/godot-benchmarks -- --run-benchmarks --include-benchmarks="*gdscript*"' 'bin/godot.linuxbsd.editor.x86_64 --path ~/Documents/Git/godotengine/godot-benchmarks -- --run-benchmarks --include-benchmarks="*gdscript*"'              
Benchmark 1: bin/godot.linuxbsd.editor.x86_64.master --path ~/Documents/Git/godotengine/godot-benchmarks -- --run-benchmarks --include-benchmarks="*gdscript*"
  Time (mean ± σ):     41.086 s ±  0.164 s    [User: 39.285 s, System: 0.795 s]
  Range (min … max):   40.770 s … 41.294 s    10 runs
 
Benchmark 2: bin/godot.linuxbsd.editor.x86_64 --path ~/Documents/Git/godotengine/godot-benchmarks -- --run-benchmarks --include-benchmarks="*gdscript*"
  Time (mean ± σ):     41.053 s ±  0.176 s    [User: 39.270 s, System: 0.777 s]
  Range (min … max):   40.801 s … 41.325 s    10 runs
 
Summary
  bin/godot.linuxbsd.editor.x86_64 --path ~/Documents/Git/godotengine/godot-benchmarks -- --run-benchmarks --include-benchmarks="*gdscript*" ran
    1.00 ± 0.01 times faster than bin/godot.linuxbsd.editor.x86_64.master --path ~/Documents/Git/godotengine/godot-benchmarks -- --run-benchmarks --include-benchmarks="*gdscript*"

This PR seems to provide a tiny overall speedup (in terms of overall runtime, including startup + shutdown) across an average of 10 runs for each. Standard deviation is still quite high so take it with a grain of salt, but at least we can be assured this change doesn't harm performance.

[lawnjelly]

This PR seems to provide a tiny overall speedup (in terms of overall runtime, including startup + shutdown) across an average of 10 runs for each. Standard deviation is still quite high so take it with a grain of salt, but at least we can be assured this change doesn't harm performance.

It is good to confirm there is no slowdown. :+1: In terms of performance increases though, bear in mind the primary intended effect here is protective.

Existing common path performance sapping cases will (hopefully) mostly already have been fixed. The aim here is to make it more difficult to inadvertently introduce performance hotspots in the future, which then need extra work to identify and fix.

There's a number of other data structures which tend to be more appropriate if elements are heavy, there is random insertions / deletions / moves, and indexed access is required, which is why indexed access to linked list is usually a bit of a "code smell".

[akien-mga]

Thanks!

[AThousandShips]

Thank you!

If you or anyone come across things related to this just point me that direction if any help is needed for adjusting to these changes

[AThousandShips]

In terms of performance increases though, bear in mind the primary intended effect here is protective.

Exactly, thank you

I am going to add a few follow-up improvements, like replacements with LocalVector, also gonna open a PR with a get_front/back now that this is merged, but some areas are more appropriate for area maintainers to look at for replacements, but they'll be much easier to identify now given the dedicated syntax

[AThousandShips]

I'll open a Godot-cpp PR to add the get methods to there as well to make it compatible with the syntax

[aaronfranke]

Removed subscript operator, in favor of a more explicit get

What is the replacement for setting at a given index?

[AThousandShips]

Using foo.get(i) = x;, I chose not to add an explicit set for clutter, can do if it's needed for clarity, but the method is a drop in replacement for the operator

Bur you likely shouldn't be using List if you need to do this

[aaronfranke]

I'm passing data to OS::get_singleton()->execute, which uses List. I have to use List because this is Godot's API.

[AThousandShips]

I think editing the elements in this way isn't necessary, adding and removing from the end, or creating a new list might be better