[Bug]: Poor performance opening "Check Online Content" window due to O(N^3) behaviour #9535
Labels
bug
Something isn't working
Comments
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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
The performance problem seems to be created in
ClientNetworkContentSocketHandler::ReverseLookupDependencyviaClientNetworkContentSocketHandler::CheckDependencyState.This seems to be because each received content item calls
CheckDependencyStateon each previously received item, which callsReverseLookupDependencywhich again iterates all previously received items, leading overall to O(N^3) behaviour in the number of content items. See below for approximate measurements.Steps to reproduce
The text was updated successfully, but these errors were encountered: