I'm looking for implementations of this because I'm having an especially hard time understanding how data is usually handled. As I understand it, simply using critical sections and locking code regions where modification of shared resources happens is a no-go, because locking and unlocking imposes quite severe performance penalties on the program.

So another approach would be to simply copy all relevant data when I create the task and pass it to a thread and overwrite the original data at the end or at the beginning of the following frame with whatever the worker thread returns to me... which results in the problem that if two tasks modify the same resource... it's unclear to me how to meaningfully resolve that "result collision".

I guess it's theoretically possible to apply only deltas of incoming changes: Let's say each entity, at the beginning of a frame, checks the messaging system for modifications to itself. If there are n modifications to the entities component e, then the new e would probably just be the old e plus the sum of all "old_e - new_e" for each n. But that seems kind of ugly and I'm not sure if it even works for things which are not just simple changes to single numbers.

Are there any open source examples which implement this system that I could actually look at?


"Result collisions", as you put it, need to be handled with some type of synchronization. That can be locks, it can be atomics where possible (a good choice for simple things like adding up numbers, since there's often hardware support for atomic memory operations), or it can be some type of transactional approach. But no matter which solution you use, if you have high contention (many tasks needing to update the same memory), you will run into performance problems.

The short answer to dealing with contention is: don't do things that cause contention. :) Task-parallel systems need to be designed not to have result collisions at all, as much as possible.

For example, in some cases it's possible to switch to a gather model rather than a scatter one, where you have exactly one task for each result item and it pulls in whatever input data it needs. GPU shaders work this way, for instance; you have one shader thread for each output vertex, pixel, etc. and the shader reads buffers, samples textures etc. to get its inputs.

Another possibility, when all the output data really does need to end up merged together in one container, is to use the map-reduce pattern. You run independent "map" tasks, each of which has its own separate output buffer that it writes its results into. Then you run a collection of "reduce" tasks, whose job is to merge together two or more of those individual output buffers into a larger one. By structuring the reduce tasks as a tree, you can run several of them in parallel as well, merging larger result sets together at each step until you get down to just one. An example of this is mipmap generation.

All this was rather abstract, but for a look at a real task-parallel system, you might check out Fabian Giesen's Optimizing Software Occlusion Culling series, particularly the two "Care and feeding of worker threads" articles. This is about a software rasterizer, which you probably don't have in your game, but the principles apply in general.

  • \$\begingroup\$ Are atomic operations constructs like std::atomic dream constructs (at least for basic built in types like int and float) that have barely measurable performance impact or do I need to be careful when using them? Also regarding avoiding situations with lots of shared data: Sometimes this is unavoidable, no? For example if you deal with entities that interact a lot... I figure it's really to avoid that in those cases. Also that link looks interesting and somewhat relevant... I wrote a software rasterizer for fun a couple of weeks ago and wanted to use it to practice optimization a little bit. \$\endgroup\$ – TravisG Aug 5 '13 at 0:19
  • \$\begingroup\$ @TravisG Atomics are pretty fast as long as you don't have too many and don't have too much contention. They sure beat the lock-update-unlock cycle, anyway, which is why "lock-free" data structures (i.e. based on atomics) are so popular. As with anything performance-related, YMMV and it's never too soon to profile. \$\endgroup\$ – Nathan Reed Aug 5 '13 at 1:16
  • \$\begingroup\$ Thanks. As for the task manager in such a task based system... do you maybe have any pointers on implementation details of those? I've tried it now and it's an awful mess of locking and unlocking. I haven't tried just doing active waiting instead of passive waiting yet though. \$\endgroup\$ – TravisG Aug 5 '13 at 17:08
  • \$\begingroup\$ You could use some middleware like the open-source threadpool or Intel's TBB. However if rolling your own, I'd probably start with a lock-free queue of jobs, with worker threads atomically picking off the next queue item when they want to do more work, and sleeping when the queue is empty; add work from the main thread and fire an event to wake them. \$\endgroup\$ – Nathan Reed Aug 5 '13 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.