Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Exponentially slow quitting time with dependencies between (gdscript) scripts #85435

Closed
eldidou opened this issue Nov 27, 2023 · 2 comments · Fixed by #85603
Closed

Exponentially slow quitting time with dependencies between (gdscript) scripts #85435

eldidou opened this issue Nov 27, 2023 · 2 comments · Fixed by #85603
Assignees
@adamscott
Labels
bug performance topic:gdscript
Milestone
4.3

Comments

@eldidou
Copy link
Contributor

eldidou commented Nov 27, 2023

Godot version

Godot v4.2.rc2

System information

Godot v4.2.rc2 - Ubuntu 22.04.3 LTS 22.04 - X11 - Vulkan (Forward+) - integrated Intel(R) UHD Graphics (CML GT2) () - Intel(R) Core(TM) i7-10850H CPU @ 2.70GHz (12 Threads)

Issue description

When there is a lot of dependencies between types defined with class_name or class, the quitting time for game (and editor) grows exponentially.

With a "real" project (nb of scripts: 97, nb lignes of code: 11638, nb dependencies between script: 336) the quitting time is ~8.0s.
I could manage to reduce it to ~5.0s just by moving an inner class from one file to another.

On a "toy" project, with N scripts doing nothing except depending on each others, the quitting time seems exponential:

  • 40 scripts : 1.5s
  • 50 scripts : 2.5s
  • 60 scripts : 4.5s
  • 70 scripts : 8.4s
  • 80 scripts : 15.7s
  • 90 scripts : 27.1s
  • 100 scripts : 46.8s

Adding the dependencies as a type check (if my_var is MyType) triggers the issue.
Adding the dependencies as a type creation (MyType.new()) triggers the issue.
Adding the dependencies as type hinting (var my_var : MyType) doesn't triggers the issue.

Adding inner (unused) classes inside these script increases a lot the time.

The dependencies being cyclical or not doesn't seems to change the behavior.

Same issue with 4.1.2-stable.

Steps to reproduce

  1. Create N scripts, each depending on each others

for example for script0.gd:

class_name Script0

static func some_func():
    print(Script0.new())
    print(Script1.new())
    print(Script2.new())
    print(Script3.new())
    ...

  1. in the script of the main scene, add a dependency to one of the N inter-depending scripts, for example with print(null is Script0)

  2. then quit directly the scene, with get_tree().quit()

  3. launch the main scene

If N is high enough (>50), it will start to quit directly, but the quitting time will be long.

  1. quit the editor.

The quitting time will also be quite long.

note: a python script has been provided in the minimal project to create all the N inter-depending gdscript scripts of step 1.

Minimal reproduction project

quitting_time_dependencies.zip
@eldidou
Copy link
Contributor Author

eldidou commented Nov 29, 2023

Here is a stack trace if I try to attach to the process when it's seems stuck trying to quit:

    at ./core/templates/rb_set.h:293
#1  RBSet<GDScript*, Comparator<GDScript*>, DefaultAllocator>::find (p_value=<optimized out>, this=0x7fff7dc10480) at ./core/templates/rb_set.h:574
#2  RBSet<GDScript*, Comparator<GDScript*>, DefaultAllocator>::has (p_value=<optimized out>, this=0x7fff7dc10480) at ./core/templates/rb_set.h:595
#3  GDScript::_get_dependencies (this=0x55585c376970, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1269
#4  0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2c71d0, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#5  0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2c6ac0, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#6  0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2bda60, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#7  0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2b9130, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#8  0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2b8a20, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#9  0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2af9c0, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#10 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2aaa70, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#11 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2a6140, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#12 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2a5940, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#13 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c29c8e0, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#14 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c297fb0, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#15 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c2978a0, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#16 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c292b20, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#17 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c28c8b0, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#18 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585c28bb40, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#19 0x00005558500179eb in GDScript::_get_dependencies (this=0x55585a66ad60, p_dependencies=..., p_except=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#20 0x00005558500179eb in GDScript::_get_dependencies (this=this@entry=0x55585c3e1eb0, p_dependencies=..., p_except=p_except@entry=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1281
#21 0x000055585001c808 in GDScript::_get_dependencies (p_except=<optimized out>, p_dependencies=..., this=<optimized out>) at modules/gdscript/gdscript.cpp:1269
#22 GDScript::get_dependencies (this=0x55585c3e1eb0) at modules/gdscript/gdscript.cpp:1153
#23 0x000055585001c9c4 in GDScript::get_inverted_dependencies (this=0x55585c335fa0) at modules/gdscript/gdscript.cpp:1178
#24 0x000055585001cc71 in GDScript::get_must_clear_dependencies (this=this@entry=0x55585c414030) at modules/gdscript/gdscript.cpp:1193
#25 0x000055585002119e in GDScript::clear (this=this@entry=0x55585c414030, p_clear_data=p_clear_data@entry=0x0) at modules/gdscript/gdscript.cpp:1487
#26 0x000055585002314a in GDScript::clear (p_clear_data=0x0, this=0x55585c414030) at modules/gdscript/gdscript.cpp:1443
#27 GDScriptLanguage::finish (this=<optimized out>) at modules/gdscript/gdscript.cpp:2208
#28 0x0000555853ee8262 in ScriptServer::finish_languages () at core/object/script_language.cpp:259
#29 0x000055584fe48330 in Main::cleanup (p_force=p_force@entry=false) at main/main.cpp:3783
#30 0x000055584fdcf6a3 in main (argc=<optimized out>, argv=0x7fff7dc10dc8) at platform/linuxbsd/godot_linuxbsd.cpp:76

@eldidou
Copy link
Contributor Author

eldidou commented Nov 29, 2023

After further investigation, it seems that indeed all of the time is spent in GDScript::get_must_clear_dependencies.
With N scripts, get_must_clear_dependencies is called N times, and it calls get_inverted_dependencies up to N times, which calls get_dependencies N times, which lists up to N scripts...
There are RBSet operations in get_dependencies and those are in log(N).
So overall the time spent here grows with N^4*log(N) of the number of scripts.

Looking at the code it seems doable to reduce it to at least N^3*log(N), possibly N^2*log(N).
What is does is to list of dependencies (direct or not) for which nothing else depends on.

@eldidou eldidou mentioned this issue Dec 1, 2023
Merged
@akien-mga akien-mga added this to the 4.3 milestone Dec 1, 2023
@adamscott adamscott self-assigned this Dec 4, 2023
YuriSizov pushed a commit to YuriSizov/godot that referenced this issue Jan 25, 2024
@eldidou @YuriSizov
Speed up GDScript::get_must_clear_dependencies()
b34af3a 
get_must_clear_dependencies() has a N^3*log(N) time complexity, and this can very quickly slow down the quitting process as more gdscripts are added in a project.
This change improves it to N^2*log(N).
Instead of using all the inverted dependencies, we do the same with all (non-inverted) dependencies, which is N times faster.

Fixes godotengine#85435

(cherry picked from commit 0d77c3e)
GuybrushThreepwood-GitHub pushed a commit to GuybrushThreepwood-GitHub/godot that referenced this issue Jan 27, 2024
@eldidou @GuybrushThreepwood-GitHub
Speed up GDScript::get_must_clear_dependencies()
8d5bd54 
get_must_clear_dependencies() has a N^3*log(N) time complexity, and this can very quickly slow down the quitting process as more gdscripts are added in a project.
This change improves it to N^2*log(N).
Instead of using all the inverted dependencies, we do the same with all (non-inverted) dependencies, which is N times faster.

Fixes godotengine#85435
@mihe mihe mentioned this issue Jul 18, 2024
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@adamscott adamscott

Labels
bug performance topic:gdscript
Projects
None yet
Milestone
4.3
Development

Successfully merging a pull request may close this issue.

Speed up GDScript::get_must_clear_dependencies() eldidou/godot
4 participants
@adamscott @akien-mga @eldidou @AThousandShips