{"action":"created","comment":{"url":"https://api.github.com/repos/freeorion/freeorion/pulls/comments/72218811","id":72218811,"diff_hunk":"@@ -2778,57 +2781,147 @@ void MapWnd::ClearSystemRenderingBuffers() {\n     m_star_circle_vertices.clear();\n }\n \n-std::vector<int> MapWnd::GetLeastJumps(int start_sys_it, int end_sys_it, const std::set<int>& resGroup,\n-                                       const std::set<std::pair<int, int> >& supplylanes,\n-                                       const ObjectMap& objMap)\n-{\n-    //std::map<int,bool> sysChecked;\n-    std::map<int,int> ancestor;\n-    std::deque<int> tryNext;\n-    std::vector<int> path;\n-    path.push_back(start_sys_it);\n-    if (start_sys_it==end_sys_it)\n-        return path;\n-\n-    for (std::set<int>::const_iterator sysIt = resGroup.begin(); sysIt!=resGroup.end(); sysIt++)\n-        ancestor[*sysIt] = -1;\n-    ancestor[start_sys_it] = start_sys_it;\n-    tryNext.push_back(start_sys_it);\n-\n-    while (!tryNext.empty() ) {\n-        int sysID = tryNext.front();\n-\n-        TemporaryPtr<const System> system = objMap.Object<const System>(sysID);\n-        if (!system)\n-            continue;\n-        const std::map<int, bool>& lanes = system->StarlanesWormholes();\n-        for (std::map<int, bool>::const_iterator laneIt = lanes.begin();\n-             laneIt != lanes.end(); ++laneIt)\n-        {\n-            int newSys = laneIt->first;\n-            std::pair<int, int> lane_forward = std::make_pair(sysID, newSys);\n-            std::pair<int, int> lane_backward = std::make_pair(newSys, sysID);\n-            // see if this lane exists in this empire's supply propegation lanes set.  either direction accepted. if not, skip this lane\n-            if (supplylanes.find(lane_forward) == supplylanes.end() && supplylanes.find(lane_backward) == supplylanes.end())\n-                continue;\n-            if (!laneIt->second && ( ancestor[newSys] == -1 )) { //is a starlane, and not yet visited newSys //TODO: should allow wormholes here?\n-                ancestor[newSys] = sysID;\n-                if (newSys==end_sys_it) {\n-                    int iSys = newSys;\n-                    while ((ancestor[iSys] !=-1)&&( ancestor[iSys] != iSys )) {\n-                        path.push_back(iSys);\n-                        iSys = ancestor[iSys];\n+namespace {\n+    // SupplyLaneMap map keyed by system containing all system","path":"UI/MapWnd.cpp","position":55,"original_position":55,"commit_id":"7b037310c2100c5ac306e55ee8c6407881d50d7b","original_commit_id":"7b037310c2100c5ac306e55ee8c6407881d50d7b","user":{"login":"geoffthemedio","id":11386908,"avatar_url":"https://avatars.githubusercontent.com/u/11386908?v=3","gravatar_id":"","url":"https://api.github.com/users/geoffthemedio","html_url":"https://github.com/geoffthemedio","followers_url":"https://api.github.com/users/geoffthemedio/followers","following_url":"https://api.github.com/users/geoffthemedio/following{/other_user}","gists_url":"https://api.github.com/users/geoffthemedio/gists{/gist_id}","starred_url":"https://api.github.com/users/geoffthemedio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/geoffthemedio/subscriptions","organizations_url":"https://api.github.com/users/geoffthemedio/orgs","repos_url":"https://api.github.com/users/geoffthemedio/repos","events_url":"https://api.github.com/users/geoffthemedio/events{/privacy}","received_events_url":"https://api.github.com/users/geoffthemedio/received_events","type":"User","site_admin":false},"body":"systemS ?","created_at":"2016-07-26T09:47:57Z","updated_at":"2016-07-26T09:47:57Z","html_url":"https://github.com/freeorion/freeorion/pull/797#discussion_r72218811","pull_request_url":"https://api.github.com/repos/freeorion/freeorion/pulls/797","_links":{"self":{"href":"https://api.github.com/repos/freeorion/freeorion/pulls/comments/72218811"},"html":{"href":"https://github.com/freeorion/freeorion/pull/797#discussion_r72218811"},"pull_request":{"href":"https://api.github.com/repos/freeorion/freeorion/pulls/797"}}},"pull_request":{"url":"https://api.github.com/repos/freeorion/freeorion/pulls/797","id":78754781,"html_url":"https://github.com/freeorion/freeorion/pull/797","diff_url":"https://github.com/freeorion/freeorion/pull/797.diff","patch_url":"https://github.com/freeorion/freeorion/pull/797.patch","issue_url":"https://api.github.com/repos/freeorion/freeorion/issues/797","number":797,"state":"open","locked":false,"title":"Improve mapwnd supply propagation performance","user":{"login":"LGM-Doyle","id":17235966,"avatar_url":"https://avatars.githubusercontent.com/u/17235966?v=3","gravatar_id":"","url":"https://api.github.com/users/LGM-Doyle","html_url":"https://github.com/LGM-Doyle","followers_url":"https://api.github.com/users/LGM-Doyle/followers","following_url":"https://api.github.com/users/LGM-Doyle/following{/other_user}","gists_url":"https://api.github.com/users/LGM-Doyle/gists{/gist_id}","starred_url":"https://api.github.com/users/LGM-Doyle/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/LGM-Doyle/subscriptions","organizations_url":"https://api.github.com/users/LGM-Doyle/orgs","repos_url":"https://api.github.com/users/LGM-Doyle/repos","events_url":"https://api.github.com/users/LGM-Doyle/events{/privacy}","received_events_url":"https://api.github.com/users/LGM-Doyle/received_events","type":"User","site_admin":false},"body":"tl:dr  This PR changes `MapWnd::InitStarlaneRenderingBuffers()` from a O(N^3) algorithm to a O(N) algorithm.\r\n\r\nThis PR refactors `MapWnd::InitStarlaneRenderingBuffers()` to improve performance.  \r\n\r\n`MapWnd::InitStarlaneRenderingBuffers()` calculates which systems and starlanes to display with wide lines in the map window to to indicate being part of a supply network.\r\n\r\n`MapWnd::InitStarlaneRenderingBuffers()` is the principle source of lag in the map window when the supply network of systems is large.  I determined this by profiling with `perf`.  \r\n\r\nThe problem is obvious when updating the production queue with a large number of systems in any empire's supply network.  freeorion It briefly freezes.\r\n\r\n\"Large\" number of systems is a fuzzy number dependent on each machine.  It might be 100 systems on a slow machine or 500 on a fast one.\r\n\r\n**Algorithm Comparison.**\r\n\r\nGiven N resource systems, M supply network systems and P average starlanes per system.\r\n    \r\nThe old method was roughly:\r\n    \r\n    `from N resources systems\r\n       to each of N resource systems\r\n          calculate the shortest path with P average starlanes\r\n          using a breadth first search of M supply network systems.`\r\n    \r\nThe old method was O(N^2*M*P).  In the late game P << N and N ~ M, so this reduces to O(N^3).\r\n    \r\nThe new method is roughly:\r\n    \r\n    `do a single breadth first search from all N resource systems to any of N\r\n    resource systems through M network systems with P average starlanes.`\r\n    \r\nThe new method is O((N+M)*P).  The new method handles each system once.  In the late game this reduces to O(N). \r\n\r\n**Performance Testing:**\r\nYou can easily verify the performance difference in the algorithms by checking the log for the string `MapWnd::InitStarlaneRenderingBuffers time: `.  The changes are save game compatible, so pick a late game save where the production window is obviously laggy and load the game, record some of the times, compile this PR, reload the game and compare the times.\r\n\r\nThe more systems in the supply network the bigger the difference in performance.  In the test case I used to develop the PR my improvement was 4400 ms vs 10 ms.  \r\n\r\n**Behavioral change:**\r\n  There is one user visible change in the behavior of the algorithms.  The old algorithm only displayed the shortest path between every resource to every other resource.  If two path were the same length it chose the path with the lower numbered system ids.  \r\n\r\nThe new algorithm shows all redundant supply paths as part of the supply network.\r\n\r\nThere is debug code in the PR to visualize the change. I removed the testing code in the last commit.  To visualize the change checkout https://github.com/freeorion/freeorion/commit/d09f01088e5822993fe7afe67e371b779010bbec `Clarify comments in MapWnd::InitStarlaneRenderingBuffers.` and load a saved game.  It will display the systems that are added to the rendered supply network with the new algorithm with big orange triangles.  \r\n\r\nNote, this does not change how the server handles the supply network, just how it is rendered in `MapWnd`.\r\n\r\n@Vezzra I'm assuming that you will ask the perennial question, should this go into 0.4.6?  \r\n- It addresses the regular forum complaint about late game slowness.  \r\n- It does not make any rules changes.  \r\n- It is \"tested\" code to the extent that any code in freeorion is tested. The aforementioned commit compares the new method directly with the old method.  \r\n\r\nI think it should go in.\r\n\r\n\r\n\r\n\r\n\r\n\r\n","created_at":"2016-07-25T21:23:46Z","updated_at":"2016-07-26T09:47:57Z","closed_at":null,"merged_at":null,"merge_commit_sha":"dcddf9ca112ca213b3876c7075465d665cdcf41b","assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/freeorion/freeorion/milestones/15","html_url":"https://github.com/freeorion/freeorion/milestones/Release%20v0.4.6","labels_url":"https://api.github.com/repos/freeorion/freeorion/milestones/15/labels","id":1226316,"number":15,"title":"Release v0.4.6","description":"Bugs, features and pull requests that should be fixed/finalized for the 0.4.6 release.","creator":{"login":"adrianbroher","id":84891,"avatar_url":"https://avatars.githubusercontent.com/u/84891?v=3","gravatar_id":"","url":"https://api.github.com/users/adrianbroher","html_url":"https://github.com/adrianbroher","followers_url":"https://api.github.com/users/adrianbroher/followers","following_url":"https://api.github.com/users/adrianbroher/following{/other_user}","gists_url":"https://api.github.com/users/adrianbroher/gists{/gist_id}","starred_url":"https://api.github.com/users/adrianbroher/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/adrianbroher/subscriptions","organizations_url":"https://api.github.com/users/adrianbroher/orgs","repos_url":"https://api.github.com/users/adrianbroher/repos","events_url":"https://api.github.com/users/adrianbroher/events{/privacy}","received_events_url":"https://api.github.com/users/adrianbroher/received_events","type":"User","site_admin":false},"open_issues":15,"closed_issues":389,"state":"open","created_at":"2015-07-26T16:21:09Z","updated_at":"2016-07-26T09:40:35Z","due_on":null,"closed_at":null},"commits_url":"https://api.github.com/repos/freeorion/freeorion/pulls/797/commits","review_comments_url":"https://api.github.com/repos/freeorion/freeorion/pulls/797/comments","review_comment_url":"https://api.github.com/repos/freeorion/freeorion/pulls/comments{/number}","comments_url":"https://api.github.com/repos/freeorion/freeorion/issues/797/comments","statuses_url":"https://api.github.com/repos/freeorion/freeorion/statuses/7b037310c2100c5ac306e55ee8c6407881d50d7b","head":{"label":"LGM-Doyle:improve_mapwnd_supply_propagation_performance","ref":"improve_mapwnd_supply_propagation_performance","sha":"7b037310c2100c5ac306e55ee8c6407881d50d7b","user":{"login":"LGM-Doyle","id":17235966,"avatar_url":"https://avatars.githubusercontent.com/u/17235966?v=3","gravatar_id":"","url":"https://api.github.com/users/LGM-Doyle","html_url":"https://github.com/LGM-Doyle","followers_url":"https://api.github.com/users/LGM-Doyle/followers","following_url":"https://api.github.com/users/LGM-Doyle/following{/other_user}","gists_url":"https://api.github.com/users/LGM-Doyle/gists{/gist_id}","starred_url":"https://api.github.com/users/LGM-Doyle/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/LGM-Doyle/subscriptions","organizations_url":"https://api.github.com/users/LGM-Doyle/orgs","repos_url":"https://api.github.com/users/LGM-Doyle/repos","events_url":"https://api.github.com/users/LGM-Doyle/events{/privacy}","received_events_url":"https://api.github.com/users/LGM-Doyle/received_events","type":"User","site_admin":false},"repo":{"id":51704490,"name":"freeorion","full_name":"LGM-Doyle/freeorion","owner":{"login":"LGM-Doyle","id":17235966,"avatar_url":"https://avatars.githubusercontent.com/u/17235966?v=3","gravatar_id":"","url":"https://api.github.com/users/LGM-Doyle","html_url":"https://github.com/LGM-Doyle","followers_url":"https://api.github.com/users/LGM-Doyle/followers","following_url":"https://api.github.com/users/LGM-Doyle/following{/other_user}","gists_url":"https://api.github.com/users/LGM-Doyle/gists{/gist_id}","starred_url":"https://api.github.com/users/LGM-Doyle/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/LGM-Doyle/subscriptions","organizations_url":"https://api.github.com/users/LGM-Doyle/orgs","repos_url":"https://api.github.com/users/LGM-Doyle/repos","events_url":"https://api.github.com/users/LGM-Doyle/events{/privacy}","received_events_url":"https://api.github.com/users/LGM-Doyle/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/LGM-Doyle/freeorion","description":"Source code repository of the FreeOrion project.","fork":true,"url":"https://api.github.com/repos/LGM-Doyle/freeorion","forks_url":"https://api.github.com/repos/LGM-Doyle/freeorion/forks","keys_url":"https://api.github.com/repos/LGM-Doyle/freeorion/keys{/key_id}","collaborators_url":"https://api.github.com/repos/LGM-Doyle/freeorion/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/LGM-Doyle/freeorion/teams","hooks_url":"https://api.github.com/repos/LGM-Doyle/freeorion/hooks","issue_events_url":"https://api.github.com/repos/LGM-Doyle/freeorion/issues/events{/number}","events_url":"https://api.github.com/repos/LGM-Doyle/freeorion/events","assignees_url":"https://api.github.com/repos/LGM-Doyle/freeorion/assignees{/user}","branches_url":"https://api.github.com/repos/LGM-Doyle/freeorion/branches{/branch}","tags_url":"https://api.github.com/repos/LGM-Doyle/freeorion/tags","blobs_url":"https://api.github.com/repos/LGM-Doyle/freeorion/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/LGM-Doyle/freeorion/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/LGM-Doyle/freeorion/git/refs{/sha}","trees_url":"https://api.github.com/repos/LGM-Doyle/freeorion/git/trees{/sha}","statuses_url":"https://api.github.com/repos/LGM-Doyle/freeorion/statuses/{sha}","languages_url":"https://api.github.com/repos/LGM-Doyle/freeorion/languages","stargazers_url":"https://api.github.com/repos/LGM-Doyle/freeorion/stargazers","contributors_url":"https://api.github.com/repos/LGM-Doyle/freeorion/contributors","subscribers_url":"https://api.github.com/repos/LGM-Doyle/freeorion/subscribers","subscription_url":"https://api.github.com/repos/LGM-Doyle/freeorion/subscription","commits_url":"https://api.github.com/repos/LGM-Doyle/freeorion/commits{/sha}","git_commits_url":"https://api.github.com/repos/LGM-Doyle/freeorion/git/commits{/sha}","comments_url":"https://api.github.com/repos/LGM-Doyle/freeorion/comments{/number}","issue_comment_url":"https://api.github.com/repos/LGM-Doyle/freeorion/issues/comments{/number}","contents_url":"https://api.github.com/repos/LGM-Doyle/freeorion/contents/{+path}","compare_url":"https://api.github.com/repos/LGM-Doyle/freeorion/compare/{base}...{head}","merges_url":"https://api.github.com/repos/LGM-Doyle/freeorion/merges","archive_url":"https://api.github.com/repos/LGM-Doyle/freeorion/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/LGM-Doyle/freeorion/downloads","issues_url":"https://api.github.com/repos/LGM-Doyle/freeorion/issues{/number}","pulls_url":"https://api.github.com/repos/LGM-Doyle/freeorion/pulls{/number}","milestones_url":"https://api.github.com/repos/LGM-Doyle/freeorion/milestones{/number}","notifications_url":"https://api.github.com/repos/LGM-Doyle/freeorion/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/LGM-Doyle/freeorion/labels{/name}","releases_url":"https://api.github.com/repos/LGM-Doyle/freeorion/releases{/id}","deployments_url":"https://api.github.com/repos/LGM-Doyle/freeorion/deployments","created_at":"2016-02-14T17:21:56Z","updated_at":"2016-02-14T17:22:02Z","pushed_at":"2016-07-25T21:25:59Z","git_url":"git://github.com/LGM-Doyle/freeorion.git","ssh_url":"git@github.com:LGM-Doyle/freeorion.git","clone_url":"https://github.com/LGM-Doyle/freeorion.git","svn_url":"https://github.com/LGM-Doyle/freeorion","homepage":"http://www.freeorion.org/","size":518153,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"freeorion:master","ref":"master","sha":"6a53621d1265622a25f70aa3989c6be68fbc6e78","user":{"login":"freeorion","id":1025550,"avatar_url":"https://avatars.githubusercontent.com/u/1025550?v=3","gravatar_id":"","url":"https://api.github.com/users/freeorion","html_url":"https://github.com/freeorion","followers_url":"https://api.github.com/users/freeorion/followers","following_url":"https://api.github.com/users/freeorion/following{/other_user}","gists_url":"https://api.github.com/users/freeorion/gists{/gist_id}","starred_url":"https://api.github.com/users/freeorion/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/freeorion/subscriptions","organizations_url":"https://api.github.com/users/freeorion/orgs","repos_url":"https://api.github.com/users/freeorion/repos","events_url":"https://api.github.com/users/freeorion/events{/privacy}","received_events_url":"https://api.github.com/users/freeorion/received_events","type":"Organization","site_admin":false},"repo":{"id":33066062,"name":"freeorion","full_name":"freeorion/freeorion","owner":{"login":"freeorion","id":1025550,"avatar_url":"https://avatars.githubusercontent.com/u/1025550?v=3","gravatar_id":"","url":"https://api.github.com/users/freeorion","html_url":"https://github.com/freeorion","followers_url":"https://api.github.com/users/freeorion/followers","following_url":"https://api.github.com/users/freeorion/following{/other_user}","gists_url":"https://api.github.com/users/freeorion/gists{/gist_id}","starred_url":"https://api.github.com/users/freeorion/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/freeorion/subscriptions","organizations_url":"https://api.github.com/users/freeorion/orgs","repos_url":"https://api.github.com/users/freeorion/repos","events_url":"https://api.github.com/users/freeorion/events{/privacy}","received_events_url":"https://api.github.com/users/freeorion/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/freeorion/freeorion","description":"Source code repository of the FreeOrion project.","fork":false,"url":"https://api.github.com/repos/freeorion/freeorion","forks_url":"https://api.github.com/repos/freeorion/freeorion/forks","keys_url":"https://api.github.com/repos/freeorion/freeorion/keys{/key_id}","collaborators_url":"https://api.github.com/repos/freeorion/freeorion/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/freeorion/freeorion/teams","hooks_url":"https://api.github.com/repos/freeorion/freeorion/hooks","issue_events_url":"https://api.github.com/repos/freeorion/freeorion/issues/events{/number}","events_url":"https://api.github.com/repos/freeorion/freeorion/events","assignees_url":"https://api.github.com/repos/freeorion/freeorion/assignees{/user}","branches_url":"https://api.github.com/repos/freeorion/freeorion/branches{/branch}","tags_url":"https://api.github.com/repos/freeorion/freeorion/tags","blobs_url":"https://api.github.com/repos/freeorion/freeorion/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/freeorion/freeorion/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/freeorion/freeorion/git/refs{/sha}","trees_url":"https://api.github.com/repos/freeorion/freeorion/git/trees{/sha}","statuses_url":"https://api.github.com/repos/freeorion/freeorion/statuses/{sha}","languages_url":"https://api.github.com/repos/freeorion/freeorion/languages","stargazers_url":"https://api.github.com/repos/freeorion/freeorion/stargazers","contributors_url":"https://api.github.com/repos/freeorion/freeorion/contributors","subscribers_url":"https://api.github.com/repos/freeorion/freeorion/subscribers","subscription_url":"https://api.github.com/repos/freeorion/freeorion/subscription","commits_url":"https://api.github.com/repos/freeorion/freeorion/commits{/sha}","git_commits_url":"https://api.github.com/repos/freeorion/freeorion/git/commits{/sha}","comments_url":"https://api.github.com/repos/freeorion/freeorion/comments{/number}","issue_comment_url":"https://api.github.com/repos/freeorion/freeorion/issues/comments{/number}","contents_url":"https://api.github.com/repos/freeorion/freeorion/contents/{+path}","compare_url":"https://api.github.com/repos/freeorion/freeorion/compare/{base}...{head}","merges_url":"https://api.github.com/repos/freeorion/freeorion/merges","archive_url":"https://api.github.com/repos/freeorion/freeorion/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/freeorion/freeorion/downloads","issues_url":"https://api.github.com/repos/freeorion/freeorion/issues{/number}","pulls_url":"https://api.github.com/repos/freeorion/freeorion/pulls{/number}","milestones_url":"https://api.github.com/repos/freeorion/freeorion/milestones{/number}","notifications_url":"https://api.github.com/repos/freeorion/freeorion/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/freeorion/freeorion/labels{/name}","releases_url":"https://api.github.com/repos/freeorion/freeorion/releases{/id}","deployments_url":"https://api.github.com/repos/freeorion/freeorion/deployments","created_at":"2015-03-29T08:22:20Z","updated_at":"2016-07-25T16:58:40Z","pushed_at":"2016-07-26T09:40:36Z","git_url":"git://github.com/freeorion/freeorion.git","ssh_url":"git@github.com:freeorion/freeorion.git","clone_url":"https://github.com/freeorion/freeorion.git","svn_url":"https://github.com/freeorion/freeorion","homepage":"http://www.freeorion.org/","size":536498,"stargazers_count":155,"watchers_count":155,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":60,"mirror_url":null,"open_issues_count":83,"forks":60,"open_issues":83,"watchers":155,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/freeorion/freeorion/pulls/797"},"html":{"href":"https://github.com/freeorion/freeorion/pull/797"},"issue":{"href":"https://api.github.com/repos/freeorion/freeorion/issues/797"},"comments":{"href":"https://api.github.com/repos/freeorion/freeorion/issues/797/comments"},"review_comments":{"href":"https://api.github.com/repos/freeorion/freeorion/pulls/797/comments"},"review_comment":{"href":"https://api.github.com/repos/freeorion/freeorion/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/freeorion/freeorion/pulls/797/commits"},"statuses":{"href":"https://api.github.com/repos/freeorion/freeorion/statuses/7b037310c2100c5ac306e55ee8c6407881d50d7b"}}}}
{"actor":{"display_login":"geoffthemedio"}}