{"action":"created","issue":{"url":"https://api.github.com/repos/OpenRA/OpenRA/issues/8770","labels_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/8770/labels{/name}","comments_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/8770/comments","events_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/8770/events","html_url":"https://github.com/OpenRA/OpenRA/pull/8770","id":97155316,"number":8770,"title":"Throttle AI order speed to prevent lag spikes","user":{"login":"RoosterDragon","id":3399086,"avatar_url":"https://avatars.githubusercontent.com/u/3399086?v=3","gravatar_id":"","url":"https://api.github.com/users/RoosterDragon","html_url":"https://github.com/RoosterDragon","followers_url":"https://api.github.com/users/RoosterDragon/followers","following_url":"https://api.github.com/users/RoosterDragon/following{/other_user}","gists_url":"https://api.github.com/users/RoosterDragon/gists{/gist_id}","starred_url":"https://api.github.com/users/RoosterDragon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/RoosterDragon/subscriptions","organizations_url":"https://api.github.com/users/RoosterDragon/orgs","repos_url":"https://api.github.com/users/RoosterDragon/repos","events_url":"https://api.github.com/users/RoosterDragon/events{/privacy}","received_events_url":"https://api.github.com/users/RoosterDragon/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/OpenRA/OpenRA/labels/PR:%20Needs%20+2","name":"PR: Needs +2","color":"009800"}],"state":"closed","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/OpenRA/OpenRA/milestones/15","html_url":"https://github.com/OpenRA/OpenRA/milestones/Next%20release","labels_url":"https://api.github.com/repos/OpenRA/OpenRA/milestones/15/labels","id":1127295,"number":15,"title":"Next release","description":"","creator":{"login":"obrakmann","id":4331210,"avatar_url":"https://avatars.githubusercontent.com/u/4331210?v=3","gravatar_id":"","url":"https://api.github.com/users/obrakmann","html_url":"https://github.com/obrakmann","followers_url":"https://api.github.com/users/obrakmann/followers","following_url":"https://api.github.com/users/obrakmann/following{/other_user}","gists_url":"https://api.github.com/users/obrakmann/gists{/gist_id}","starred_url":"https://api.github.com/users/obrakmann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/obrakmann/subscriptions","organizations_url":"https://api.github.com/users/obrakmann/orgs","repos_url":"https://api.github.com/users/obrakmann/repos","events_url":"https://api.github.com/users/obrakmann/events{/privacy}","received_events_url":"https://api.github.com/users/obrakmann/received_events","type":"User","site_admin":false},"open_issues":8,"closed_issues":32,"state":"open","created_at":"2015-05-24T08:30:48Z","updated_at":"2015-07-27T05:37:01Z","due_on":null,"closed_at":null},"comments":10,"created_at":"2015-07-24T21:56:39Z","updated_at":"2015-07-27T05:38:26Z","closed_at":"2015-07-27T05:37:01Z","pull_request":{"url":"https://api.github.com/repos/OpenRA/OpenRA/pulls/8770","html_url":"https://github.com/OpenRA/OpenRA/pull/8770","diff_url":"https://github.com/OpenRA/OpenRA/pull/8770.diff","patch_url":"https://github.com/OpenRA/OpenRA/pull/8770.patch"},"body":"Fixes #8466\r\nFixes #8384\r\nFixes #4584\r\n\r\n## Issue\r\nIn games with AI, as the game progresses there will start to be lag spikes every ~1 second. The spikes get worse with more AI.\r\n\r\n## Cause\r\nAIs re-evaluate their current state at set intervals. For example [assigning of roles](https://github.com/OpenRA/OpenRA/blob/7d56209f3b772ea847cc8c9decb4c33cc4210e7d/OpenRA.Mods.Common/AI/HackyAI.cs#L40-L41) and [updating of squads](https://github.com/OpenRA/OpenRA/blob/7d56209f3b772ea847cc8c9decb4c33cc4210e7d/OpenRA.Mods.Common/AI/HackyAI.cs#L46-L47). You'll notice both of these are 20/30 ticks - which are both roughly 1 second.\r\n\r\nLuckily, evaluating AI state is fast.\r\n\r\nWhat happens then is that the AIs issue new orders to be carried out. In a typical case they might issue say 10 orders to one of the squads to attack.\r\n\r\nLuckily, issuing orders is fast.\r\n\r\n[These orders are processed during the tick by the order manager](https://github.com/OpenRA/OpenRA/blob/7d56209f3b772ea847cc8c9decb4c33cc4210e7d/OpenRA.Game/Network/OrderManager.cs#L212).\r\n\r\nLuckily, processing orders is fast.\r\n\r\n[Each time an order is processed, a hash of the world state must be generated for sync purposes](https://github.com/OpenRA/OpenRA/blob/7d56209f3b772ea847cc8c9decb4c33cc4210e7d/OpenRA.Game/Network/OrderManager.cs#L213). This allows clients to identify the order responsible in the event of a desync.\r\n\r\nUnluckily, hashing the world state is extremely slow.\r\n\r\nIn games with several AI, a few AI will decide to send orders to their squads, each squad needing maybe a dozen orders. They do this all at the exact same tick. This results in a flood of orders (say about 50 orders instead of the more usual 0-5) to be processed in a single tick. Hashing the world state so many times as a result of processing the orders is the reason for the lag spike.\r\n\r\n## The Fix\r\nI address this issue by limiting the ability of the AI to generate a flood of orders in a single tick. Instead, I spread out the orders over several ticks.\r\n\r\nThe first commit makes each AI in the game operate on different ticks. In games with lots of AI, this prevents them teaming up to make one tick very slow.\r\n\r\nThe second limits the number of orders an AI can issue per tick. Extra orders are queued up and processed on subsequent ticks. This prevents spikes from issuing orders to entire squads at once by forcing the AI to order each unit on separate ticks.\r\n\r\nThis throttling means that orders might be outdated by the time they are issued. This seems to work in my testing but somebody who knows how orders work better than I do should confirm I'm not introducing a massive chance for crashes and/or desyncs.\r\n\r\n## Results\r\nPerf graphs before and after (we care about the teal line representing tick_time)\r\n\r\n![Perf Graph Comparion](http://i.imgur.com/SU5a0Lo.png)\r\n\r\nYou can check this yourself by just spectating a game with a large number of AI. Wait a few minutes until they start attacking each other and the lag spikes should appear. With this PR they should be prevented.\r\n"},"comment":{"url":"https://api.github.com/repos/OpenRA/OpenRA/issues/comments/125092435","html_url":"https://github.com/OpenRA/OpenRA/pull/8770#issuecomment-125092435","issue_url":"https://api.github.com/repos/OpenRA/OpenRA/issues/8770","id":125092435,"user":{"login":"Mailaender","id":756669,"avatar_url":"https://avatars.githubusercontent.com/u/756669?v=3","gravatar_id":"","url":"https://api.github.com/users/Mailaender","html_url":"https://github.com/Mailaender","followers_url":"https://api.github.com/users/Mailaender/followers","following_url":"https://api.github.com/users/Mailaender/following{/other_user}","gists_url":"https://api.github.com/users/Mailaender/gists{/gist_id}","starred_url":"https://api.github.com/users/Mailaender/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Mailaender/subscriptions","organizations_url":"https://api.github.com/users/Mailaender/orgs","repos_url":"https://api.github.com/users/Mailaender/repos","events_url":"https://api.github.com/users/Mailaender/events{/privacy}","received_events_url":"https://api.github.com/users/Mailaender/received_events","type":"User","site_admin":false},"created_at":"2015-07-27T05:38:26Z","updated_at":"2015-07-27T05:38:26Z","body":"[Changelog](https://github.com/OpenRA/OpenRA/wiki/Changelog-(bleed)/_compare/8e6edb08a71aa67ebf46eb07a246517d847ae84f...29c0bbfc83d4d7a62269e8d2603dd440e3b40cde)"}}