Multi-core CPUs are not very well utilized for large fleets of ships.

[TheSilverHammer]

I have a quad core CPU.  I notice at some point the game will really slow down when I get a lot of ships.  At 2200 ships everything is fine, however by 2700 ships the game starts chugging (I have 12 gigs of ram, so this is not an issue).   I then go to task manager and notice the CPU utilization for AIWar is pegged at 25% and there are 23 threads going.  I have all the CPU's checked for affinity. 

I am guessing that there is a single thread that handling all the ship movements (or something related to ships I control).  Whatever this is, it needs to be parallelized to spread its work over more cores.

I know it is limited (so far ) to MY ships.  I can be on a screen with 3000 AI ships and there is no slowdown.  So it is not a rendering issue, or an AI Fleet movement issue.  It is strictly an issue of MY ships once I get to many.

[keith.lamothe]

Thank you for the suggestion but the simulation cannot be multithreaded in a way that:
a) is more efficient
b) still produces correct results
c) wouldn't require months of recoding (even with that, I don't know that a and b could be satisfied)

FYI, the AI decision making runs in its own thread, as it only has a few points of contact (in terms of shared data).

This is a very common problem, not unique to AI War by any stretch, but hopefully in 5-10 years there will be better techniques available for generalizing distributed computing of this sort of thing.

[keith.lamothe]

Oh, and if you could post the save file where you're having performance problem I could take a look and make sure it isn't any genuinely buggy behavior that's slogging it down.  Also, what version are you running?

The AI planets with no human contact will typically be pretty lightweight, due to a cold storage technique that basically ignores most AI ships that are just guarding some post somewhere away from the humans.

Thanks!
Keith

[TheSilverHammer]

Ill have to get the save when I am home.  I am running the 3.0 version from Steam.   However the slowdown doesn't happen with smaller fleets against large AI fleets.  When engaging the AI on their worlds with their large fleets, as soon as enough of my fleet dies, the slowdowns go away.

I am not sure I have a ready save with this, but next time it comes up, Ill make a special save and post it here.

I do realize the challenge of parallelizing certain algorithms, and yes, I know many other games suffer from this.  It would be an interesting algorithmic problem to crack, wouldn't it?  I do not know what kind of logic you are using that is causing this issue, but it would definitely be an fun puzzle to play with.

[keith.lamothe]

Ill have to get the save when I am home.  I am running the 3.0 version from Steam.

If you'd like you can try the latest prerelease version, we've changed quite a lot from 3.0, including a number of performance boosts.

But from what you're saying about when the problem happens, it could be some kind of buggy behavior causing it to churn on player ships.  That may have been fixed since 3.0.

I do realize the challenge of parallelizing certain algorithms, and yes, I know many other games suffer from this.  It would be an interesting algorithmic problem to crack, wouldn't it?  I do not know what kind of logic you are using that is causing this issue, but it would definitely be an fun puzzle to play with.

Depending on how general and efficient the solution was, the "cracking" of that one could be the most significant advance in computer science thus far in the century.

In our case it's just the typical requirements that a vast majority of modifications to the game state need to be atomic, and the synchronization necessary to guarantee that would have a significant performance overhead (among other costs) and would prevent most parallel processing (if only one thread can be modifying the combat statistics of a ship, for example).  So basically, yes, we could synchronize everything, but it wouldn't actually gain us anything

[keith.lamothe]

Moving this to the general forum since it's not a bug per se (though I'll check out that save if you can make one).

[XRsyst]

I too have notice performance issues when giving a fleet of 6000+ ships a move order.  And to the comment of "that's a lot" I point you to the bullet on the features page:

30,000+ ships at a time on 10-120 simultaneous planetary battlefields.

which says to me 6k ships is normal.

But back to the issue, when a blob of ships are given a move order the game freezes for about 5 seconds or so while those computations are made.  Here are some suggestions from someone who has no clue about the underlying representation or implementation

* Create a multi-threaded pathfinding service that you call out to that will do this pathfinding work for you.  It keeps the threads running so you don't incur the startup/shutdown cost.
* Treat the blob of ships as a logically fewer number of ships, then apply the general solution to the blob as a whole rather than all the ships individually. Or if the ships need to maintain perfect individuality maybe you can solve the general case then use a sort of recursive hierarchical segmenting technique on the blob until you get down to the individual ship level.
* Look at the code again and try to make it do less work   I'm always surprised at what I can find by taking a break for a day and coming back to something
* Tell me I'm off my rocker and to mind my own business

[TheSilverHammer]

I do not think that solving parallelizing problems would be ground breaking.  For example taking an exponential problem, like the Traveling Sales Person problem and making an O^2 version would be Nobel prize material, however making the same TSP take advantage of N cores is not.  It still would be exponential, but just run simultaneously on more cores.

I do not know what the bottleneck algorithm is, but whatever it is, should be convertible to handle N smaller slices in N threads rather than a single thread handling it all.   For example, remember our old friend, the Bubble Sort?  How would you write that to take advantage of N cores?  The answer is the Odd-even sort.  Same sort, but one is for multi-processing systems.   That is the kind of thing I am talking about. 

Ill grant you this might be difficult, but it is not impossible and certainly not like cracking the big NP Complete problem that would make you a billionaire.  Anyway, you just might not have the time or even given the solution it might not integrate into your code base easily.  I know it can be very problematic to take a classic single threaded rendering pipeline and parallelize that, even if you have the answer right in front of you.  That can be a major structural change, which might not be in the cards.

[keith.lamothe]

I do not think that solving parallelizing problems would be ground breaking.  For example taking an exponential problem, like the Traveling Sales Person problem and making an O^2 version would be Nobel prize material, however making the same TSP take advantage of N cores is not.  It still would be exponential, but just run simultaneously on more cores.

I meant that a general solution to "Take Program P that runs in X time units on N threads and produce Program P' with the exact same semantics but runs in significantly less time on N+1 threads" would be groundbreaking.  An O^2 TSP solution would be another class entirely, of course.

[keith.lamothe]

And I'm not sure I was clear earlier: we know *how* the simulation could be split across multiple threads.  For example, rather than the game loop looping over each planet, doing some stuff, then looping over each foreground-object on that planet and doing some more stuff, then going to the next planet it could fork off each planet to its own thread (or split the planets between 2 or 3 or whatever threads).  The problem is that we would then have to synchronize access to TONS of shared data (or create tons of non-authoritative copies for local use that has to be reconciled at the join, likely some combination of the two) to the extent that the simulation would be slower than it is now.  Add to that the exponential increase in the difficulty of finding bugs due to race conditions, the complexity of the code... it's just not worth it when there are so many other areas of performance gain to be had that apply to the entire customer base.

[RCIX]

30,000+ ships at a time on 10-120 simultaneous planetary battlefields.

Ok, follow me here. with 10 battlefields, and 30k ships split evenly across them, that would only be a thousand per planet (and this is the best case). Granted, ships are not always evenly distributed across planets, but that would still only make probably an estimated 6k ships total between you and the AI over 1 planet. The game's only designed to handle a couple-3 thousand ships per person per planet. Now, if you DO have enough power (like a Core i7 or something) then you can run a game with as many as 200k ships, but that's really on the highest end processor you can buy.

[Captain Cake]

30,000+ ships at a time on 10-120 simultaneous planetary battlefields.

Ok, follow me here. with 10 battlefields, and 30k ships split evenly across them, that would only be a thousand per planet (and this is the best case). Granted, ships are not always evenly distributed across planets, but that would still only make probably an estimated 6k ships total between you and the AI over 1 planet. The game's only designed to handle a couple-3 thousand ships per person per planet. Now, if you DO have enough power (like a Core i7 or something) then you can run a game with as many as 200k ships, but that's really on the highest end processor you can buy.

You have to admit that it is a little misleading though. I've got an i7 and I get the same issues when there's about 3-4000 ships, so its got nothing to do with that. Its a lack of full support for quad core processors, and I doubt it will ever support my 8 cores. The slow downs with large fleets don't ruin the game for me exactly, just makes me sigh a little sigh when they happen. This happens a lot to me as I mostly play with my friend and we really only have one or two threatened systems so the ship count skyrockets pretty frequently, the unbalanced CPAs when having multiple players definitely contributed to this as well. Unfortunatly my friend starts running into slow downs at about 2-3000 ships and hes got a quad core processor as well (not an i7 tho).

I don't really expect this game to get proper quad core support (I imagine a whole bunch of stuff would need to be redesigned and recoded) so I'm not going to hold my breath. But man... I remember back when Quake 4 came out and it originally didn't support dual core processors properly, and when it finally did there was an 84% increase in performance. So abstracted that would over double number of ships an i7 should be able to run without slow downs. Oh well, thems the brakes.

[XRsyst]

30,000+ ships at a time on 10-120 simultaneous planetary battlefields.

Ok, follow me here. with 10 battlefields, and 30k ships split evenly across them, that would only be a thousand per planet (and this is the best case). Granted, ships are not always evenly distributed across planets, but that would still only make probably an estimated 6k ships total between you and the AI over 1 planet. The game's only designed to handle a couple-3 thousand ships per person per planet. Now, if you DO have enough power (like a Core i7 or something) then you can run a game with as many as 200k ships, but that's really on the highest end processor you can buy.

Well the features list doesn't stipulate that the 30k only works if evenly distributed.

I'm a programmer and what I get told when I tell people stuff is hard is: "Don't drag me into your technical hell, I'm just here to tell you how it's supposed to work".

[RCIX]

30,000+ ships at a time on 10-120 simultaneous planetary battlefields.

Ok, follow me here. with 10 battlefields, and 30k ships split evenly across them, that would only be a thousand per planet (and this is the best case). Granted, ships are not always evenly distributed across planets, but that would still only make probably an estimated 6k ships total between you and the AI over 1 planet. The game's only designed to handle a couple-3 thousand ships per person per planet. Now, if you DO have enough power (like a Core i7 or something) then you can run a game with as many as 200k ships, but that's really on the highest end processor you can buy.

Well the features list doesn't stipulate that the 30k only works if evenly distributed.

I'm a programmer and what I get told when I tell people stuff is hard is: "Don't drag me into your technical hell, I'm just here to tell you how it's supposed to work".

So you know how X and Keith feel, right?

[keith.lamothe]

Yea, maybe we should amend that to say "Oh, we're sorry, you'll generally have to content yourself with 2000 vs. 2000 in actual on-screen fights."  With a picture of 2000 footmen vs. 2000 grunts in Warcraft 2 strategically positioned nearby