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

[Bug]: Poor performance opening "Check Online Content" window due to O(N^3) behaviour #9535

Closed
JGRennison opened this issue Sep 3, 2021 · 0 comments
Labels

Comments

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Sep 3, 2021

Version of OpenTTD

master (9c74dc2), however this is not a new bug

Expected result

Blazing fast, silky smooth, positive adjectives performance when opening the check online content window

Actual result

Frame rate decreases dramatically when the list is being populated.
Screenshot_2021-09-03_17-13-37-trim

The performance problem seems to be created in ClientNetworkContentSocketHandler::ReverseLookupDependency via ClientNetworkContentSocketHandler::CheckDependencyState.
This seems to be because each received content item calls CheckDependencyState on each previously received item, which calls ReverseLookupDependency which again iterates all previously received items, leading overall to O(N^3) behaviour in the number of content items. See below for approximate measurements.
Screenshot_2021-09-03_17-25-28

Steps to reproduce

  1. Open the "Check Online Content" window from the main menu (not when in a game).
@TrueBrain TrueBrain added the bug label Sep 3, 2021
JGRennison added a commit to JGRennison/OpenTTD-patches that referenced this issue Sep 4, 2021
Fixes performance issues with dependency lookup

See: OpenTTD/OpenTTD#9535
JGRennison added a commit to JGRennison/Upstream-OpenTTD that referenced this issue Sep 4, 2021
Fixes performance issues with dependency lookup when retrieving
content list from the content server.
JGRennison added a commit to JGRennison/Upstream-OpenTTD that referenced this issue Sep 7, 2021
Fixes performance issues with dependency lookup when retrieving
content list from the content server.
@TrueBrain TrueBrain closed this in 6e3d023 Sep 9, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants