View Issue Details
| ID | Project | Category | Date Submitted | Last Update | |
|---|---|---|---|---|---|
| 0002237 | AI War 1 / Classic | Bug - Other | Jan 3, 2011 11:01 am | Jan 5, 2011 9:11 pm | |
| Reporter | Penguin21 | Assigned To | Chris_McElligottPark | ||
| Status | resolved | Resolution | fixed | ||
| Product Version | 4.059 | ||||
| Fixed in Version | 4.060 | ||||
| Summary | 0002237: Game Slows a ton during battles with FRD on | ||||
| Description | When I defend a planet from about 3000-4000 enemies using free roaming defender mode on my own units, the game slows down to about 1 FPS. I adjust the speed on the STAT page to the lowest setting, but it still says it is running very slowly, with a second in game passing in about 5 real seconds. I am running a computer with an overclocked i7 to 3.2 GHz with 12 GB RAB and a GTX 285 graphics card. My performance monitor says the game is only using about 18 % of the CPU, so not even 100% of one of the CPUs. I don't know if anything can be done to speed up these deffenses but it would be greatly appreciated. Any other information you need I will update this with. | ||||
| Tags | No tags attached. | ||||
| Internal Weight | |||||
|
|
If you can post the save that would help give us a test case we can inspect to see what exactly is taking so much processing time. Roughly how many of your own ships were there, btw? But in general FRD is CPU-intensive when the value of "number of my FRD ships" multiplied by "number of enemy ships" is very high. 1000 x 1000 is 1 million. 4000 x 4000 is _16_ million, so things can get bad pretty fast up there. |
|
|
As for your computer not reporting even 1 full core being occupied, that seems odd. My experience is that most of the cpu-usage metrics are not fully trustworthy particularly when there's a lot of cores. |
|
|
That's been what I've seen with regard to multiple cores, too. |
|
|
|
|
|
The file I attached is of a save game right before a medium sized battle. I've definitely had larger ones with worse choppiness, but this one is bad enough to be a good example with 1000 ships on my side and about 3500 on the AI's side. Would reducing unit caps and changing from epic battles to normal battles help minimize the intensity and length of the slowdowns? Thank you guys for quickly replying to these reports. No other company I've dealt with really gets back in the first week even. |
|
|
"Epic" is a game-speed setting, and switching it to normal just makes ships move faster and combat go faster (due to higher dps). Or do you mean you have ship caps set to high? If so setting it to normal or low is definitely a huge boon to reducing stress on cpu and memory :) |
|
|
I did mean ship caps set to high. I'll try maybe playing on normal ship caps to see if that makes the world of difference. But also with the epic question I meant that if combat took less time, any problematic lag that occurred would last for less time, and be less of a bother. |
|
|
Again, I have to ask. Is there a mass targeting algorithm that does better than O(n*m)? EDIT: I just realized that this statement could be interpreted as condescending. I don't mean it like that. I'm just wondering if there is a better algorithm that could solve these issues, or if this is fundamentally a super-linear problem. |
|
|
Penguin21, having combat go faster will help somewhat, yes, but I don't think it would significantly affect the likelihood or frequency of cpu or memory overconsumption. The combat-style setting is much more a matter of what the player prefers. TechSY730, the autotargetting algorithm is actually in theory: O(n*m*m+m*n*n) where n = number of friendly units and where m = number of enemy units Because for each friendly unit in n it has to not only check each enemy unit in m for "can I shoot this" and other such eligibility checks but also has to sort m that fall into that eligible set, and the sort is itself roughly linear in complexity (closer to logarithmic due to using quicksort). And then it has to do it for each enemy unit in m with respect to each friendly unit in n. Thankfully we massively cut this down by: 1) Aggressively paring down the "eligible" set before the sort; notably if enough targets are currently in range it doesn't even consider targets currently out of range. 2) Aggregating targeting data; if there are 100 fighter MkIs relatively close together, it will generally only compute the targeting data for one of them and the others will copy that data. This of course has its own cost but it's way tamer than the actual get-target-list operation. 3) Throttling both the get-target-list and update-from-aggregate-datasource (and related) operations to only allow so much of that to be done per simulation cycle. It does a decent job of deducting a number of "points" from the throttle corresponding to the actual size of the data sets, so that 3000 FRD ships all doing target checks on a set of 3 enemy ships is understood to be way less intensive than if the enemy set were 100 or 1000. It also splits the throttles by player number, to be fair. And in general we optimize the stuffing out of critical-path code like this :) |
|
|
Oh, I should add that the actual comparison used in the sort is of non-trivial complexity, it's not just an integer compare or anything like that. Though at one point I did try to pack all the relevant flags and values into a couple Int64's and let the ALU handle the compare ;) That proved to be a very brittle and surprisingly low-gain approach, however, particularly with the time spent packing data. |
|
|
Very nice optimization tricks, but they still don't lower the "worst case" algorithmic complexity do they? Also O(n^2*m + n*m^2) is a complexity I don't think I have ever seen before. EDIT: And I guess this also means this is a fundamentally super-linear problem, thus you will always stumble across degenerate cases sometimes? |
|
|
Not the theoretical worst case, no, but you'd have to either have a trivially small number of ships or somehow have all ships of a given type spread out as to be all out of aggregating range of each other (I think it's attack-range / 4), and the throttling causes the total cost to be spread out over several cycles if it is large, thus protecting actual game simulation rate. And normally you won't see a plus sign in a big-o expression, as it's only supposed to show the factor with the highest exponent/significance, however in this case it is not knowable ahead of time which of the two pieces will be more significant, and they have the same exponents. |
|
|
Well, its good to know you managed to get the worst case to be quite rare. :) |
|
|
I think if someone manages to get a worst-case autotargeting-time scenario with a fleet of at least 1000 ships versus at least 1000 ships, it should unlock an achievement :P |
|
|
Maybe like ZOMG, THE LOOPS!!! or something. |
|
|
In a lot of cases, the High ship caps really aren't supportable except possibly on the world's beefiest machines, as it's noted in the lobby tooltips. We knew some folks would be really mad if we cut down the global ship caps, but fact is that with an algorithm with logarithmic (or near) increases in CPU cost, the simplest way to optimize is to cut down on the number of inputs. That's why we recommend Normal so heartily -- it also has many RAM benefits, too, and you still get thousands of ships (and 30-60k ships in the galaxy is still routine even there). To some extent, I guess what I'm saying is that the High ship cap setting is kind of the wild west in terms of performance. It is very, very possible to shoot yourself (or your CPU) in the foot on High, especially depending on your computer specs. With an i7, and overclocked to boot, you're obviously at the top of the totem pole anyhow hardware-wise, but it's still a case where that logarithmic complexity can kick in. Optimizing those algorithms, as Keith noted, has been the chief optimization problem of AI War. But, in the end, it simply has an enormous amount of complexity no matter how you cut it. There are literally over a hundred decision points that have to be evaluated against potentially thousands of targets, by thousands of targeters. There are a lot of early-outs, but when you have ships in FRD mode that gets rid of one of the biggest ones: ignoring stuff that is obviously out of range. When stuff is maybe-in-range, there is a whole other set of math that has to be run through with regard to ships doing distance checks, etc. You know what, though... a FRD-and-sniper-specific possible optimization just occurred to me, that might help this some... |
|
|
I wouldn't worry a ton about the snipers, as all sniper ships of a given type for a given player all aggregate as one :) But FRD is another story. |
|
|
Coming up: * Put in a new CPU-efficiency-improving shift in the targeting logic for ships in FRD mode: while in FRD mode (and always for ships that are snipers), a much-less-accurate but much-faster-to-calculate range value is now used. Normally accurate ranges are important in battle, because ships have to know if they are in range to hit their target, etc. However, for ships in FRD mode, they can move to hit their target, so they only need to get a rougher idea of which ships are vaguely closest. ** The main side effect of this change, aside from the speed boost, is that ships in FRD mode will choose more poorly between targets that are close together and also at a diagonal from the targeting ship. There may be some other unintended side effects, though, so we'll have to keep an eye on that. In my tests with that logic, it was notably faster after the change. There's one other big change I have in mind, which should help with RAM use and actually with game load speed, etc, too. |
|
|
Well, when 4.060 comes out tomorrow, if you can test again and see how it does for you, that would be great. There's a limit to how much more we can do at this particular point in time if that doesn't happen to help, but in my testing it seems to help a fair bit. If you wind up with a save that better shows the truly awful performance, that would be easier for us to look at for inefficiencies, but again we've been hammering on this for about a year and a half now, and there's only so much blood you can squeeze from a given stone. ;) |
|
|
I'll definitely try and get a stress test from 4.060. Thank you both for your help with this topic. It has made me very glad I've purchased AI War. I'll post back with any update to the performance improvements I get. |
|
|
Many thanks in return for your understanding, assistance, and support! |
|
|
So: has 4.060 helped appreciably? |
|
|
Actually yes. To a startlingly large degree. I opened the same file I added in this one, where before it was taking several real seconds to pass in game. Now, with FRD on and nearly 4000 guys attacking it runs at nearly 100% game speed. It does skip slightly and cannot go any faster than 100% even when I put it in +10 speed, but that is a significant improvement from 20%. Awesome improvement! |
|
|
... Wow :) |
|
|
Awesome! I had seen something similar, although I didn't have a test case where it ever got that low before on my machine, so the result was a less notable improvement for me. I'm glad that it did so well, though! :D |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| Jan 3, 2011 11:01 am | Penguin21 | New Issue | |
| Jan 3, 2011 11:07 am | keith.lamothe | Note Added: 0007355 | |
| Jan 3, 2011 11:09 am | keith.lamothe | Note Added: 0007356 | |
| Jan 3, 2011 11:32 am | Chris_McElligottPark | Note Added: 0007358 | |
| Jan 3, 2011 8:37 pm | Penguin21 | File Added: Slows Down 001.sav | |
| Jan 3, 2011 8:40 pm | Penguin21 | Note Added: 0007402 | |
| Jan 3, 2011 8:41 pm | Penguin21 | Note Edited: 0007402 | |
| Jan 3, 2011 8:44 pm | keith.lamothe | Note Added: 0007403 | |
| Jan 3, 2011 8:52 pm | Penguin21 | Note Added: 0007405 | |
| Jan 3, 2011 8:58 pm | TechSY730 | Note Added: 0007406 | |
| Jan 3, 2011 9:01 pm | TechSY730 | Note Edited: 0007406 | |
| Jan 3, 2011 9:13 pm | keith.lamothe | Note Added: 0007408 | |
| Jan 3, 2011 9:16 pm | keith.lamothe | Note Added: 0007409 | |
| Jan 3, 2011 9:21 pm | TechSY730 | Note Added: 0007412 | |
| Jan 3, 2011 9:23 pm | TechSY730 | Note Edited: 0007412 | |
| Jan 3, 2011 9:25 pm | keith.lamothe | Note Added: 0007415 | |
| Jan 3, 2011 9:27 pm | TechSY730 | Note Added: 0007416 | |
| Jan 3, 2011 9:29 pm | keith.lamothe | Note Added: 0007417 | |
| Jan 3, 2011 9:30 pm | TechSY730 | Note Added: 0007418 | |
| Jan 3, 2011 9:45 pm | Chris_McElligottPark | Note Added: 0007419 | |
| Jan 3, 2011 9:46 pm | Chris_McElligottPark | Assigned To | => Chris_McElligottPark |
| Jan 3, 2011 9:46 pm | Chris_McElligottPark | Status | new => confirmed |
| Jan 3, 2011 10:08 pm | keith.lamothe | Note Added: 0007420 | |
| Jan 3, 2011 10:10 pm | Chris_McElligottPark | Note Added: 0007421 | |
| Jan 3, 2011 11:31 pm | Chris_McElligottPark | Note Added: 0007422 | |
| Jan 3, 2011 11:31 pm | Chris_McElligottPark | Status | confirmed => feedback |
| Jan 3, 2011 11:49 pm | Penguin21 | Note Added: 0007425 | |
| Jan 3, 2011 11:49 pm | Penguin21 | Status | feedback => assigned |
| Jan 3, 2011 11:50 pm | Chris_McElligottPark | Note Added: 0007426 | |
| Jan 5, 2011 1:08 am | Chris_McElligottPark | Note Added: 0007519 | |
| Jan 5, 2011 1:08 am | Chris_McElligottPark | Status | assigned => feedback |
| Jan 5, 2011 9:05 pm | Penguin21 | Note Added: 0007562 | |
| Jan 5, 2011 9:05 pm | Penguin21 | Status | feedback => assigned |
| Jan 5, 2011 9:10 pm | keith.lamothe | Note Added: 0007563 | |
| Jan 5, 2011 9:11 pm | Chris_McElligottPark | Note Added: 0007564 | |
| Jan 5, 2011 9:11 pm | Chris_McElligottPark | Status | assigned => resolved |
| Jan 5, 2011 9:11 pm | Chris_McElligottPark | Fixed in Version | => 4.060 |
| Jan 5, 2011 9:11 pm | Chris_McElligottPark | Resolution | open => fixed |
