View Issue Details
| ID | Project | Category | Date Submitted | Last Update | |
|---|---|---|---|---|---|
| 0002956 | AI War 1 / Classic | Bug - Other | Feb 25, 2011 4:14 pm | Mar 23, 2011 8:28 pm | |
| Reporter | FunnyMan | Assigned To | Chris_McElligottPark | ||
| Status | resolved | Resolution | fixed | ||
| Product Version | 5.000 | ||||
| Fixed in Version | 5.007 | ||||
| Summary | 0002956: Removing a large number of ships from a control group causes massive network lag | ||||
| Description | I, the non-host player, am attempting to subdivide a large ball of my ships into 16 transports. The overall strategy for this is to create a control group, divide the selection in half, create a second control group, subtract the second group from the first one, and so on, recycling control groups as the smallest ones are shoved into transports. The original ball contains 2,688 ships, in control group 1. Half are added to control group 2, then Ctrl+Alt+1 is pressed to remove those ships from control group 1. At this point, an apparent network desync happens, with both players seeing Waiting For Players. If I reconnect, the last action does not happen, and repeating it repeats the "desync". If we wait for several minutes (as when I started typing this bug report), it does eventually sync up, with control group 1 shrunk appropriately. We have a save that reproduces this reliably, if it's needed. | ||||
| Tags | No tags attached. | ||||
| Internal Weight | |||||
| related to | 0003171 | new | Severe lag when sending many units through a wormhole simultaneously |
|
|
This reminds me that if you try to make a control group of a selection of 0 ships (essentially removing the control group) by ctrl-X (where X is the control group number) all the game does is select that control group. |
|
|
This may not be network-related at all. The game seems to grind to a halt in single-player under similar conditions. |
|
|
This is a pure shot in the dark, but does this operation take n^2 time? It doesn't seem linear with the number of ships removed, and the naïve implementation would be to remove each ship from the list individually, meaning that removing the first 100 ships would cause each of the remaining ones to be shifted in memory 100 times. |
|
|
That's an interesting thought. I know that Array.splice() isn't the most efficient function in the world. If that is being used, a quick optimization would be to swap the element-to-be-removed with the [i]last[/i] element in the array, then truncate the array (with --Array.length which AFAIK is the fastest method; certainly faster than splice() on the last element and faster than pop() which needs to return that unit. It's a tossup between --length and length--, depending on source language and implementation). |
|
|
Should there be some sort of cutoff where if more than a certain percentage of ships are being removed from a control group, it will instead scrap the array and rebuild the control group's array from the selected ships from a freshly allocated array? This way, you get whichever algorithm will "hurt the least" for that case. It will of course take some nifty math to figure out the optimal cutoff point. It will depend very much on how the control groups are stored and how the current selection list is stored. |
|
|
If you want to get fancy: loop through the array a, if a[j] needs to be removed, swap to [e] where e = a.length-1, decrement e, decrement j (assuming j starts at 0, otherwise increment), and continue. If you swap two things, you need to check if the element swapped in also needs to move (hence decrementing j). e keeps track of your "end" index so that you can fill the end of the array with to-be-removed items. Then just chop off the end of the array (a.length = e). It'll be faster in all other solutions, with two exceptions: Removing all units from the array (clear the control group) Removing more than half of the units (I make special note of the first condition, as it's very fast to execute) in which case, you do the same thing as above, but instead create a temporary array and push into it all elements that need to be kept, kill the original (a.length = 0), then copy back (a = temp.concat() ). |
|
|
If only someone could invent a data structure that is constant time in all modification operations, including removing and preserving contiguousness (instead of filling the deleted spot with null or something), and constant time reads even during random accesses. (Note: True constant time, not amortized constant time or average constant time) I'd call it, the "Magic Data Structure". :D |
|
|
It's called a linked list. :) Indexing is O(n) and there's wasted space (RAM usage). But insertion and deletion times are faster. http://en.wikipedia.org/wiki/Linked_list#Tradeoffs |
|
|
Ah, but it doesn't have constant time random access retrievals, as you mentioned. That is one of the major things that keeps it from being used for every list data structure need. O(n) (worst case) lookups is pretty nasty once you start storing a large number of things. |
|
|
Quite. There's no way to get O(1) seek times and O(1) insertion/deletion (arbitrary location) times. |
|
|
Exactly. And you apparently missed my "joke" that acknowledged this impossibility by calling such a data structure with those properties the "Magic data structure". |
|
|
No, I know it would be magic, I got the joke. :) |
|
|
"There's no way to get O(1) seek times and O(1) insertion/deletion (arbitrary location) times." A hash table comes close enough in most cases. It'd certainly be sufficient for a mere few thousand elements. |
|
|
Hash tables have O(k) insertion and seek times, based on how often collisions happen. |
|
|
Really nice catch! * Previously, adding and removing ships to control groups was way slower than it should have been. In terms of bulk add/removes, it was way, WAY slower than it should have been. This was a past optimization that was not fully optimized -- it had one critical flaw, mainly. This is now fixed, and it has a couple of major effects: ** Obviously, when editing control groups in bulk, it's hugely improving the speed of that (it could cause "Waiting For Players" messages, before). ** Unexpectedly, it also makes savegames load in less than half the time they used to. As it turns out, there was a lot of "take this ship out of the control group it already wasn't in" going on in there, and that was just eating performance. |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| Feb 25, 2011 4:14 pm | FunnyMan | New Issue | |
| Feb 25, 2011 4:53 pm | Draco18s | Note Added: 0010756 | |
| Mar 20, 2011 7:40 pm | FunnyMan | Note Added: 0011181 | |
| Mar 22, 2011 3:50 pm | FunnyMan | Note Added: 0011223 | |
| Mar 22, 2011 3:55 pm | Draco18s | Note Added: 0011224 | |
| Mar 22, 2011 5:07 pm | TechSY730 | Note Added: 0011229 | |
| Mar 22, 2011 6:43 pm | Draco18s | Note Added: 0011253 | |
| Mar 22, 2011 6:54 pm | TechSY730 | Note Added: 0011254 | |
| Mar 22, 2011 7:46 pm | Draco18s | Note Added: 0011256 | |
| Mar 22, 2011 7:56 pm | TechSY730 | Note Added: 0011257 | |
| Mar 22, 2011 7:56 pm | TechSY730 | Note Edited: 0011257 | |
| Mar 22, 2011 7:59 pm | Draco18s | Note Added: 0011258 | |
| Mar 22, 2011 7:59 pm | TechSY730 | Note Edited: 0011257 | |
| Mar 22, 2011 8:01 pm | TechSY730 | Note Added: 0011259 | |
| Mar 22, 2011 8:02 pm | Draco18s | Note Added: 0011260 | |
| Mar 22, 2011 9:42 pm | FunnyMan | Note Added: 0011276 | |
| Mar 22, 2011 10:39 pm | Draco18s | Note Added: 0011293 | |
| Mar 23, 2011 8:28 pm | Chris_McElligottPark | Note Added: 0011389 | |
| Mar 23, 2011 8:28 pm | Chris_McElligottPark | Status | new => resolved |
| Mar 23, 2011 8:28 pm | Chris_McElligottPark | Fixed in Version | => 5.007 |
| Mar 23, 2011 8:28 pm | Chris_McElligottPark | Resolution | open => fixed |
| Mar 23, 2011 8:28 pm | Chris_McElligottPark | Assigned To | => Chris_McElligottPark |
| Apr 1, 2011 9:32 pm | FunnyMan | Relationship added | related to 0003171 |
