Tuesday, October 13, 2009

Multithreaded gameplay

How do we multithread gameplay without driving gameplay programmers insane?

My current idea is:
  • Do all gameplay processing as events reacting to stuff (such as collide_with_pickup_object), not through a generic update() call.
  • Each event concerns a number of entities (e.g., [player, ammo_pack]). The processing function for an event is allowed to touch the entities it concerns freely, but not any other entities.
  • Each frame, consider all events. Let two entities being in the same event define an equivalence relation between those two entities. The corresponding equivalence classes then define "islands" of entities that can be processed safely on separate cores.
  • Assign each island to a core, process the events for that island one by one on the core.
  • Provide a thread-safe interface to any global entitites that the event processors may need to touch for effect spawning, sound play, etc. (Preferrably through a queue so that the global entities don't have to be touched directly from the event processors.)
Some concerns:
  • Will the islands become "too big". I.e., if almost everything interacts with the player, there is a risk that everything ends up in a single big "player island".
  • Will it be reasonable for gameplay programmers to write code that follows these restrictions.


  1. Another option is STM which effectively optimistically presumes that updates don't collide (I.e. they form islands). Collisions are detected, reverted and retried automatically. Not sure if there's a solution out there for STM using C++ though.

  2. All I've read about software transactional memory (which isn't that much) has been focused on very small, simple and contained examples (such as lock-free lists). I'm finding it pretty hard to picture how STM would even work for something as complex and sprawling as gameplay code.

  3. This comment has been removed by the author.

  4. I know this is long past, but I'm wondering, how do you approach frame-locked jobs? Given the latency of the average context switch, do you find yourself with a few threads in your worker pool that don't do any sleeping, just spinning for high response times? Also, do you find yourself doing mostly out of band tasks at the moment (can happen on any frame), or per-frame/per-system tick jobs?

  5. I'm not sure what frame-locked jobs mean.

    Yeah, we have a hack for dealing with the sleeping/spinning issue. You don't want to go to sleep immediately when you run out of things to do, because the context switch times will punish you brutally. But you don't want to spin lock aggressively either, because that's not nice to user's batteries and fans. So we wait for a "little while" to see if any new jobs arrive, and then we go to sleep.

    All of the jobs in this system are per-frame jobs. We don't have any jobs with the contract "deliver this in a few frames" (apart from async tasks like file and network reads).