Idea to make multithreading easier

[RCIX]

Feel free to shoot some holes in this plan, but:
In order to work on data that needs to interact with itself (like targeting for ships needing to access positions of other ships and junk, which it might not be able to since the position is being calculated on another thread), it uses data from after the last update to work.

[keith.lamothe]

Rather than discuss the details and start another one of "those" threads, I'll just say that there are huge, gaping, nasty holes in that approach for this game

That said, if for some reason we absolutely positively had to spread the main thread out across more cores, this would be a relatively promising approach.  Whether the game would actually be any faster with all that would entail, dunno.

But there are far better and far less costly gains to be had just by finding ways for the game to do less work, rather than spreading it out

[x4000]

What Keith said, forthe most part. Incidentally, what you describe is how the ai thread already works for the game. The ai is on a slight delay, and it doesn't even have even versioning between all the various ships. For it's purposes, it really doesn't matter, and it keeps performance possible. The largest challenge when splitting out the simulation itself across multiple threads is the multiplayer: there is no way to non-synchronously execute a deterministic algorithm that I know of. Certainly not one of this complexity.

But as Keith said, even if this were more likely to work, there's just not much of a compelling reason to try to get it to do so, because there are easier ways to accomplish the goal of lower performance.

[keith.lamothe]

there are easier ways to accomplish the goal of lower performance.

This is true, but probably not your point

[x4000]

Heh.

[zebramatt]

there are easier ways to accomplish the goal of lower performance.

This is true, but probably not your point

It's sad that my "everybody hates a smart Aleck" sense only just prevented me from posting exactly the same thing!

[x4000]

Keith and I have a special arrangement where I'm allowed to make iPhone typos if he's allowed to be a Smart Aleck about it.

[RCIX]

And i get to say "you're typing on an iphone aren't you" now and then

Anyway, i'm not that knowledgeable about multithreading, but if you had time to explain what the gaping holes in my idea is that would be awesome! I promise i won't turn it into one of "those" threads, and if posting it would, a PM would work just as well.

[keith.lamothe]

Well, Chris pointed out one of the biggest and least solvable ones: in a multiplayer game, each player machine must execute all simulation computations for a given cycle in the same order as the other machines, or they will not get the same results.  Desync = end of game.  If the simulation calculations are distributed across multiple threads, we have no way of making them happen in a specific order (short of a crazy amount of synchronization that would basically mean that there wasn't any parallel processing anyway).

The other more pedestrian issues are things like the additional memory consumption of the additional copies of the simulation data, and the cpu costs of making those copies.  Not deal-breakers (as Chris said, we do a loose form of this with the AI thread), but this would actually be adding a lot of work to the overall workload, and thus diminish if not totally overtake any performance gain from the division of workload.

And then there's the issue that it makes further extension of the game exponentially more difficult as we have a whole extra set of bugs to worry about as well as just more coding because every piece of sim data is stored in an additional way.  Speed of development is very important to us.

[RCIX]

Well, my idea is that you have the big master read-only copy of data globally accessable for read-only which contains the results from last update. And aside from dealing with things that use random numbers (which would be a problem now that i think about it), the processing can run in basically any order and the results will be the same.

So, do you guys use random numbers a lot?

[x4000]

And i get to say "you're typing on an iphone aren't you" now and then

 

Anyway, i'm not that knowledgeable about multithreading, but if you had time to explain what the gaping holes in my idea is that would be awesome! I promise i won't turn it into one of "those" threads, and if posting it would, a PM would work just as well.

No worries.  Basically, it's what I already said, along with what Keith noted.  But the other huge thing is that, going along with what Keith said, the amount of work that this adds is pretty substantial -- to the CPU, to the RAM load, to the processor bus, etc.  So, with at 32bit program, we'd hit RAM issues way, way faster.  

But even more critically, it would be doing vastly more work and thus make the single-core performance absolutely horrible unless we kept two enormous code branches, one for the multithreading and one for the single threading.  And those would have about a 0% chance of being synchronous with one another, giving deterministic results that was identical between the two, anyway.

It's one of those things that just gets exponentially, exponentially more complicated because everything is related.  In a game like a FPS or other action game, it's comparably easy to use multiple cores because all of the individual simulations are ALWAYS out of sync.  Half-Life isn't synchronous between player sessions, it has to constantly re-sync.  So that's why you see people sometimes leap forwards in a shooter game, and someone you "killed" pop right back to life -- or someone shooting you around a corner, depending on the game.  Those are all artifacts of desyncs being fixed.  Generally in a low-latency environment the sync is within 500ms of one another, so there's little of those artifacts, but when lag gets hit it gets worse.  Conversely, strategy games get choppy and slow instead, because they are relying on the sync rather than re-syncing because of the massive amounts of data there -- you can't sync hundreds of objects a second in realtime, let alone thousands or tens of thousands.  In most FPS games, it's 64 at the most, and they use a lot of tricky prediction and such to minimize the load.

Even if we had 6 coders instead of 2, it would be really an iffy thing to approach with 2 of them being devoted fulltime just to making multithreading work.

[RCIX]

Ah. Sort of a "threading gives you more than enough rope to hang yourself" (in terms of amount of work and difficulty) thing?

[x4000]

Well, my idea is that you have the big master read-only copy of data globally accessable for read-only which contains the results from last update.

That would require an absolute ton of locking and unlocking.  On the order of hundreds of millions per second.  You'd be lucky to have 1 frame every two or three seconds with that approach with a game the scale of AI War.  There are some variants of what you're talking about, but I've done profiling and experimenting with all of them before I settled on the threading model for AI War (and with past projects), and this is the only one that had anywhere remotely near the processing power we need.

And aside from dealing with things that use random numbers (which would be a problem now that i think about it), the processing can run in basically any order and the results will be the same.

Presuming that the original part above was feasible, then this might work aside from the randomization thing.  But you'd wind up spending so much time waiting for locks, and/or transferring data back and forth between all the states, that I just don't think it would work.  An individual ship in AI War has upwards of 500 data points about it, many of which are lists of object references, and such.  Copying that volume of data, and translating it in some meaningful way based on internal IDs, is absolutely murderous.  With the AI thread, we pare it down to a mere 40ish data points of primitive types to synchronize, and then the AI thread calculates another 40-50 data points on its side on its own.

So, do you guys use random numbers a lot?

Yes, several tens of thousand a second, at least.

[x4000]

Ah. Sort of a "threading gives you more than enough rope to hang yourself" (in terms of amount of work and difficulty) thing?

Well, used correctly, it's an amazing thing.  The reason that the AI runs so well in AI War compared to SupCom or similar is because of how well our threading model works.  But we rely very heavily on it being a non-synchronous second thread, running just on the game host, which is a key innovation that really pushes us ahead by letting us use a less-locky method.  As it stands, the synchronization with the AI thread eats a good 20-40ms per second, sometimes more when the ship caps get really insane, which is pretty huge. 

And that's with a really severe lag (1-2 seconds) in terms of the updatedness of that data, and with only syncing a really small portion of that data.  With an AI that is acting in a more high-level thinking capacity, the 1-2 seconds is nothing, but even there I had to augment that with sort of low-level AI on the main thread to prevent any "thinking... thinking..." type lapses.

Someday there will be better threading models all around, I'm convinced of it, but right now the tools just aren't there to do a synchronous multithreaded application that runs in realtime in this sort of fashion.

[RCIX]

That would require an absolute ton of locking and unlocking.  On the order of hundreds of millions per second.  You'd be lucky to have 1 frame every two or three seconds with that approach with a game the scale of AI War.  There are some variants of what you're talking about, but I've done profiling and experimenting with all of them before I settled on the threading model for AI War (and with past projects), and this is the only one that had anywhere remotely near the processing power we need.

I was under the impression that you needed to lock only when there was the possibility of someone else writing to that field while you're reading it; my idea would process everything at once by totally keeping the master data copy readonly (a little like get-only properties) then when it's all done update the master data copy by overwriting it. I'd also have to think of a way to keep memory use down though.

But other than that, you have good points