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.

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

Linkgraph takes a very long time to recalculate on large save, causing hangs #7842

Open
Awizonosz opened this issue Nov 23, 2019 · 11 comments
Open
Labels

Comments

@Awizonosz
Copy link

@Awizonosz Awizonosz commented Nov 23, 2019

Can you do something with OpenTTD so j could again play on my save?

Save that crach in every version of OpenTTD.zip

Version of OpenTTD

Expected result

Actual result

Steps to reproduce

@LordAro
Copy link
Member

@LordAro LordAro commented Nov 23, 2019

We require some more details. Which versions have you tried? What are the symptoms of the crash? Can you upload all the associated crash.* files ?

@Awizonosz
Copy link
Author

@Awizonosz Awizonosz commented Nov 23, 2019

When j am doing anything like watching or creating new train line on that save approximately every 20 minutes it's crash like that how it is on screenshot.

Bug

@LordAro
Copy link
Member

@LordAro LordAro commented Nov 23, 2019

When running the save myself, the game actually deadlocks (hangs) at 20 May, a few ingame days after loading. This appears to be occurring inside the Linkgraph code.

If the game is actually crashing for you, that's a separate issue that we need those crash files to be able to diagnose. These will be in your "personal directory" - most likely C:\Users\<username>\Documents\OpenTTD, or next to openttd.exe

@Awizonosz
Copy link
Author

@Awizonosz Awizonosz commented Nov 23, 2019

J find that in C:\Users<username>\Documents\OpenTTD named as crash

crash.log

@LordAro
Copy link
Member

@LordAro LordAro commented Nov 23, 2019

OK, that's unrelated to this issue - that file is from 1.9.1. When you say the game crashes, what do you mean? Is the game hanging, or exiting to desktop?

@Awizonosz
Copy link
Author

@Awizonosz Awizonosz commented Nov 23, 2019

Its hanging for 3-7 minutes mostly

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Nov 24, 2019

Your save game is set to take 16 days to recalculate each the cargo distribution graph.
Your largest cargo distribution graph has 1516 stations, and as the time taken to recalculate each graph is roughly proportional to N² log(N) in the number of stations, it takes significantly more than 16 days to calculate.
As your network is heavily overloaded anyway, you should probably set the distribution accuracy setting to its minimum value (2), and drastically increase the values of the settings for how often the distribution graph is updated and how many days are taken for it to be recalculated, until it no longer hangs periodically. These are in "environment" -> "cargo distribution" in the settings window. You will need to set the settings category to "advanced" or "expert".

@LordAro LordAro changed the title Crash on one my save in every version of OpenTTD Linkgraph takes a very long time to recalculate on large save, causing hangs Nov 24, 2019
@James103
Copy link
Contributor

@James103 James103 commented Nov 24, 2019

Is it possible to optimize the link graph calculation so that it takes less than O(N² log(N)) time (N proportional to station count)? If so, what's the lowest amount of time you can optimize towards?

@Awizonosz
Copy link
Author

@Awizonosz Awizonosz commented Nov 24, 2019

Thanks

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Nov 24, 2019

Is it possible to optimize the link graph calculation so that it takes less than O(N² log(N)) time (N proportional to station count)? If so, what's the lowest amount of time you can optimize towards?

The existing algorithm can be optimised a bit to reduce the constants, but it doesn't make a huge difference. You still get O(N² log(N)) behaviour. It's more pragmatic to change the scheduler to be aware of the how long the recalculation is likely to take.

@James103
Copy link
Contributor

@James103 James103 commented Dec 16, 2019

For large networks and/or when fast-forwarding, I suggest the following for performance reasons:

  • "Take 60 days for recalculation of distribution graph"
  • "Update distribution graph every 14 days"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.