View Issue Details

IDProjectCategoryLast Update
0002956AI War 1 / ClassicBug - OtherMar 23, 2011 8:28 pm
ReporterFunnyMan Assigned ToChris_McElligottPark  
Status resolvedResolutionfixed 
Product Version5.000 
Fixed in Version5.007 
Summary0002956: Removing a large number of ships from a control group causes massive network lag
DescriptionI, 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.
TagsNo tags attached.
Internal Weight

Relationships

related to 0003171 new Severe lag when sending many units through a wormhole simultaneously 

Activities

Draco18s

Feb 25, 2011 4:53 pm

developer   ~0010756

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.

FunnyMan

Mar 20, 2011 7:40 pm

reporter   ~0011181

This may not be network-related at all. The game seems to grind to a halt in single-player under similar conditions.

FunnyMan

Mar 22, 2011 3:50 pm

reporter   ~0011223

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.

Draco18s

Mar 22, 2011 3:55 pm

developer   ~0011224

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).

TechSY730

Mar 22, 2011 5:07 pm

reporter   ~0011229

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.

Draco18s

Mar 22, 2011 6:43 pm

developer   ~0011253

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() ).

TechSY730

Mar 22, 2011 6:54 pm

reporter   ~0011254

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

Draco18s

Mar 22, 2011 7:46 pm

developer   ~0011256

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

TechSY730

Mar 22, 2011 7:56 pm

reporter   ~0011257

Last edited: Mar 22, 2011 7:59 pm

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.

Draco18s

Mar 22, 2011 7:59 pm

developer   ~0011258

Quite.
There's no way to get O(1) seek times and O(1) insertion/deletion (arbitrary location) times.

TechSY730

Mar 22, 2011 8:01 pm

reporter   ~0011259

Exactly.

And you apparently missed my "joke" that acknowledged this impossibility by calling such a data structure with those properties the "Magic data structure".

Draco18s

Mar 22, 2011 8:02 pm

developer   ~0011260

No, I know it would be magic, I got the joke. :)

FunnyMan

Mar 22, 2011 9:42 pm

reporter   ~0011276

"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.

Draco18s

Mar 22, 2011 10:39 pm

developer   ~0011293

Hash tables have O(k) insertion and seek times, based on how often collisions happen.

Chris_McElligottPark

Mar 23, 2011 8:28 pm

administrator   ~0011389

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.

Issue History

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