So who here is thinking of using Grand Central Dispatch?

Member
Posts: 35
Joined: 2009.10
Post: #1
This wouldn't apply to those targeting pre-Snow Leopard platforms or the iPhone. But for those who aren't, anyone thinking of using Grand Central Dispatch?

As far as I can tell, GCD doesn't so much make it easier to parallelize an app (you still have to figure out what chunks of code can be run concurrently, what shared resources there are, etc.) as it makes it easier to actually write the concurrency code. So I still have some decisions to make about how to structure my game if I want GCD.

The parts of my game I've identified are Update input (get what keys the player is pressing), Update AI (determine what actions each AI will take), Update logic (perform player action, perform AI action, run physics...), and Render (draw stuff). Render depends on Update logic and Update logic depends on both Update input and Update AI, so it seems only Update input and Update AI are truly independent of each other. However, I could parallelize things inside each task. For example, Update AI could have have an asynchronous task for each AI, assuming AIs are independent of one another.

As I think about it I'll post some ideas later.
Quote this message in a reply
Member
Posts: 46
Joined: 2008.10
Post: #2
I could see myself using it when I actually get to a point where thread control is important. In the mean time, while I'm making more simple games and developing smaller tools, probably not.

"Who's John Galt?"
Quote this message in a reply
Moderator
Posts: 3,573
Joined: 2003.06
Post: #3
TythosEternal Wrote:I could see myself using it when I actually get to a point where thread control is important. In the mean time, while I'm making more simple games and developing smaller tools, probably not.

That is a very reasonable view of it IMHO. Threading can be a big win, but games are notoriously hard to parallelize, not to mention just dealing with all the other myriad details first for even the most modest of games. I don't immediately see any areas where GCD can intrinsically make things easier for parallelizing games, although I think it looks like a really neat technology.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #4
I've converted one app of mine to use GCD (+blocks) some time ago, and it does make threading a whole lot simpler, as it gives you better synchronization primitives than pthreads.
Quote this message in a reply
Member
Posts: 35
Joined: 2009.10
Post: #5
DoG Wrote:it does make threading a whole lot simpler, as it gives you better synchronization primitives than pthreads.

Definitely. I haven't actually made anything that uses GCD yet, but looking at the examples I get the impression that it makes the implementation of threading easier.

That still leaves us to decide what to thread exactly though. Wacko

TythosEternal Wrote:I could see myself using it when I actually get to a point where thread control is important. In the mean time, while I'm making more simple games and developing smaller tools, probably not.

Yeah, concurrency probably doesn't matter for a smaller project. However, I am hoping to put together my first "big" project, and concurrency seems to be one of those things where it's not a good idea to just tack on in the middle of a project.

One idea I had was having an input update loop that just updates the currently pressed keys, and have the rest of the game in a second loop. The "main" game loop would grab the currently pressed keys every cycle without interrupting the the input loop itself. The effect I hope that would have is that the player never has to wait between key presses; he just presses keys whenever and the game just goes merrily along its way.
Quote this message in a reply
Member
Posts: 283
Joined: 2006.05
Post: #6
I know hardly anything about threading, but with a few extra lines of code I was able to make one of my game-related tools run asynchronously using GCD. It started using both processors, and there was a reasonable speed increase (1.25x-1.5x), so I was pleased with that.

I'd have to understand a lot more about what was going on though if I were to use CGD in a shipping product.
Quote this message in a reply
⌘-R in Chief
Posts: 1,256
Joined: 2002.05
Post: #7
Coyote Wrote:The effect I hope that would have is that the player never has to wait between key presses; he just presses keys whenever and the game just goes merrily along its way.

For what purpose? Accepting input certainly isn't going to be the most burdensome section of code; I can't imagine any performance benefit from that at all.

And, at best, within a single frame it'd lead to inconsistency. If your AI, for instance, is constantly reading from the actual current key "source" variables which are changing mid-frame, then you could easily have multiple NPCs responding to multiple sets of input. They'd "see" the player differently and respond differently at the same time.

And what's the benefit of updating input at 120 hz if the response to that input is occurring at 30hz? What human can notice 1/30th of a second of input lag anyway? Also, input isn't likely to change that fast anyway so trying to handle it faster when it's not changing is rather pointless.


-

As for GCD, something as simple as polling input is not really in the realm of intended purpose. You'd be far better off trying to chunk up your AI logic and process it in parallel -- if your AI has sufficient compute requirements to overcome the overhead of simply using GCD.

Where GCD shines is taking a number of discrete non-trivial tasks and executing them in parallel efficiently. If you have a thousand NPCs to update and it takes 50 ms to update them all, then splitting them up into a couple batches and processing the batches in parallel could be a big benefit. Enqueueing each NPC as an individual task, though, might be horrible because the overhead for managing each task can add as much or more time than you're saving.

I'm rambling Wacko, but the main point is: find the part of code that's actually taking a large amount of time which you should split up, rather than think about what you can split up, and figure out how to do it.
Quote this message in a reply
Member
Posts: 46
Joined: 2008.10
Post: #8
Applications (including games) that have significant AI and physics demands are good candidates for multithreading, and as such should benefit from GCD. The main two burdens in multithreading are:
- Distributing and executing processes across threads
- Ensuring that different processes lock and synch data properly

GCD makes the first item trivial, but you still have a lot of work to do to get the second to work properly, as far as I understand.

I suspect the first few applications I use GCD for will be CFD projects and neural network experiments. I don't expect to use GCD in games until I'm feeling very, very comfortable with the second point from above. I don't have enough experience with multi-threading to expect more any time soon, and I suspect most IDevGamers are in the same situation.

"Who's John Galt?"
Quote this message in a reply
Moderator
Posts: 3,573
Joined: 2003.06
Post: #9
Physics simulation is not a given to be better with multi-threading. It really can be super-complicated to deal with collision detection/response, depending upon how you go about it. Threading can make that even more complicated, and in some instances impossible to resolve.

That said, yeah, if you can do it in your physics, great!
Quote this message in a reply
Member
Posts: 46
Joined: 2008.10
Post: #10
True, if by "physics" you mean "collision detection" (which is often the case in games, of course). My background is science and engineering, though, so when I talk about parallelizing physics calculations, I'm most talking about iterating finite difference equations for motion, fluids, gravity, electric and magnetic forces, etc. Multi-threading is a marvelous way to reduce complexity of N-body problems like these (particular with the fast multipole method!)

That being said, I'm surprised that collision detection doesn't benefit from multi-threading. I'd love to learn more; can you share your sources?

"Who's John Galt?"
Quote this message in a reply
Moderator
Posts: 3,573
Joined: 2003.06
Post: #11
Yeah, yeah, the integration step you're talking about can easily be parallelized. Integration is by far the easiest phase (it also happens to be the fun part). Coarse collision detection can probably be parallelized too (assuming your collision detection system as a whole is conducive to it). Where everything goes to hell in a hand-basket is when you get into contact resolution and fine collision detection (that is, we already know two bodies are close enough to potentially be in contact and we need to calculate the details to know for sure). Particularly, the contact resolution phase is the bugger. (I am specifically talking about 3D here, BTW) It can be done several different ways, but what usually winds up happening is an iterative approach. Once a body has contacted another, the resolution can shift it and rotate it to where it is in contact with another in that finite period of time. How are you going to parallelize that? I mean, one object's fate intrinsically depends on the fate of the other object's motion within that slice of time. If the first object's resolution affects the second object's contact status, this can go back and forth. This contact resolution part of the physics engine takes the most amount of calculations and can be *incredibly* complicated. I've tried it. I can do it with boxes and spheres, but anything more than that and I flat-out gave up. There are some really smart guys out there who've already worked this out. Studying it gave me a *huge* appreciation for just how advanced and impressive physics engines out there like Bullet and ODE are.

I don't have any web references off-hand, but there are a few well-known physics books for game programmers you can find at Amazon. I have a few of them and have studied them to varying degrees, and one of them I studied fully. After all that, it's my assessment that physics just isn't guaranteed to be easily parallelized, as I said, particularly when it comes to contact resolution, and that's where the main performance hit is.
Quote this message in a reply
Moderator
Posts: 3,573
Joined: 2003.06
Post: #12
Thinking a little further, I completely ignored particle physics, where you don't care about collision detection (e.g. sparks (that you will allow to fall through objects), smoke, fireworks, etc.). Now that kind of physics would most definitely benefit from threading if you had a lot of particles.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #13
Actually, I long believed that Chipmunk would be very difficult to thread. It actually turned out to be trivial after realizing that locking wasn't very important in an iterative solver anyway.

Iterative solvers (nearly everybody uses them for rigid body physics) work by solving pairs of objects individually and looping over the solutions for all objects several times. Basically you are letting the constraints all fight it out. If the collision between A and B pushes B to the right and the collision between B and C pushes B to the left, it seem counter productive as they are just undoing each other's work. Over a few iterations the amount that B gets pushed around converges to a stable amount however. Surprisingly, it's far cheaper to approximate the forces this way that to construct a large linear equation and solve it. For large clusters of interacting objects, you would have to solve a very large linear equation as each object can interact with every other object to some extent through their common neighbors.

The interesting observation I saw once was that the constraints were basically overwriting each other's solutions, so why not let threads do the same thing? Instead of spending time on locking, just let the threads clobber each other's solutions. It's going to happen rarely when you have a lot of objects, and when you have 10 to 20 iterations it's very unlikely to have more than one or two of it's solutions overwritten.

Using OpenMP's parallel for loops, I was able to try this out in like 5 minutes on the Chipmunk demos. While it no longer ran deterministically, the simulation still looked fine and ran faster. My opinion on physics in games is that you should optimize for visual plausibility rather than 100% accuracy. From a game design point of view, a ball should roll down a hill and bump off a rock, but a ball should not roll down a hill bump off a rock and land perfectly balanced on the edge of wine glass. Floating point errors between different CPU architectures already prevent specific and reliable behavior like that.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Moderator
Posts: 3,573
Joined: 2003.06
Post: #14
Skorche Wrote:The interesting observation I saw once was that the constraints were basically overwriting each other's solutions, so why not let threads do the same thing? Instead of spending time on locking, just let the threads clobber each other's solutions. It's going to happen rarely when you have a lot of objects, and when you have 10 to 20 iterations it's very unlikely to have more than one or two of it's solutions overwritten.

I'm not sure I completely understand what you're describing, but I think that's where things get really hard for me to understand how threading could help. I can't imagine letting interpenetrations of various objects screw with other contact resolutions, in-progress. I am certain my engine would explode if I allowed that (like a stiff spring gone awry). For me, it has to be done one at a time or something bad will likely happen at some point, but I have heard of other techniques, so again, that's not to say it can't be done.

What I could imagine is having contact "groups" which are spatially separated enough that there would be little chance of a large velocity affecting an object in another group. I could definitely imagine threading per-group like that, and I'm sure it'd help in certain situations.

I totally agree with the notion that game physics needs to be done to the level of plausibility, not accuracy. There's practically no way to do it with full accuracy on today's hardware anyway. Again though, with the way I did it just to the level of plausibility, the poor thing is barely hanging onto stability by a whisker it seems -- unlocked threading would surely spell disaster.
Quote this message in a reply
Apprentice
Posts: 6
Joined: 2009.05
Post: #15
I use threads for background loading of assets and streaming data. Physics certainly is a candidate but I think the sound system is even lower hanging fruit.

I would highly recommend considering threads and laying the framework for non-synchronous operations sooner rather than later no matter what you plan to use it for. It is much harder to go back and refactor single-threaded code than it is to make the up front investment (even if it is minimal) for concurrent operations. Bite the bullet early and it will make your life a lot easier if you plan on growing a common code base to consider this feature in the beginning. Even on single cores, it's a nice way to think about parsing jobs and dividing up work for systems.
Quote this message in a reply
Post Reply