Coding with threads

This list of 33 articles is more applicable to general programming than game-engines specifically, but it's a good starting point:
http://herbsutter.co...ead-of-a-mutex/


"Thread safe" is a horrible term that's too vague to mean anything. If someone tells me that their library is "thread safe" without going into details, I automatically assume that they don't know what they're on about and that their library is probably slow and buggy...

Yes, the STL is thread-safe, in that many threads can read from a structure concurrently without adverse effects.
No, the STL is not thread-safe, in that if any thread can make modifications, then no other thread may read the structure concurrently.
Yes, the STL is thread-safe, in that different threads can be using different parts of the library, or different instances of it's objects concurrently.
No, the STL is not thread-safe, because there's many different implementations which have subtle differences...

Are there ways to make code threadsafe besides using mutexes around critical sections?[/quote]Yes. Mutexes are the wrong default for concurrent programming -- mutexes imply a "shared memory" concurrency model (where different threads must synchronise to operate on the same data) whereas the correct default programming model is based on message passing (threads are isolated except for communication via asynchronous messages).

To take this to it's extreme, you can use the Actor Model to implement regular object-oriented code in such a way where every function call becomes an asynchronous message, and everything becomes concurrent (without mutexes of any sort).

I of course want to avoid having too many locks all over the place or else I won't even be getting any advantage from threading.[/quote]Exactly, locks are bad. They're a form of forced synchronisation, which in the best case merely cause stalling and in the worst case cause dead-locks (surprisingly easily, too).

My plan is to rewrite my game engine to use threads for different processes.[/quote]I would seriously reconsider. Chances are, the result will be slower and have more bugs...

Reading is threadsafe, but if a write is happening, only that thread should have access. That makes sense. So how do you lock something like that? How would my writing thread try to get a lock on some data when there are 3 other threads reading from it?[/quote]Create a mutex to be paired with the structure. Before accessing the structure, lock the mutex. Then only 1 thread can access the structure at a time.struct SafeQueue {
void Push(const T& v) {
mutex.Lock();
queue.Push(v);
mutex.Unlock();
}
private:
CriticalSection mutex;
Queue queue;
};However, as mentioned above, programming with locks is a bad idea at all but the lowest-level systems. Higher level code should be using higher-level concurrency primitives, like messages.

A lot of current-gen game engines are built around a "job-based model", where tasks that need to be run are broken up into small functions that operate on a small amount of data (e.g. 128 KiB). Each of these function/data pairs is called a job, which can be put into a queue for execution by any idle thread:void ThreadMain( SafeQueue<Job>& jobs )
{
while( !quit )
{
Job* job;
if( jobs.Pop(&job) )
quit = job->Run();
}
}To solve the scheduling/synchronisation problem, jobs can be dependant on other jobs, so you can submit [font="Lucida Console"]Job X[/font] with the condition that [font="Lucida Console"]Job Y[/font] and [font="Lucida Console"]Job Z[/font] must first complete before [font="Lucida Console"]Job X[/font] begins.


In my current engine, I use a SPMD-style paradigm based around "task sections", which looks like:struct Game
{
TaskSection fooTask;
Foo foos[1024];
};
void RunGame(Game* g)//called each frame by each thread
{
ENTER_TASK_SECTION( g->fooTask );
{
int begin,end = DISTRIBUTE_TASK( g->fooTask );//this returns different results depending on which thread called it.
// e.g. with 4 threads, T0 will get (0,256), T1 gets (256,512), T2 gets (512,768) and T3 gets (768,1024), assuming no load-balancing.
for( int i=begin; i!=end; ++i )
g->foos.Update();
}
EXIT_TASK_SECTION( g->fooTask );//this records that this thread has finished it's distribution of the total workload

//... run some other tasks here

//if any threads are still working on the foo task (unlikely, as we put several other tasks in-between then and now)
//then this will wait for them to finish. While waiting, jobs from the job queue will be processed.
WAIT_FOR_TASK( g->fooTask );
int baz = g->foo[42].baz;//it's now guaranteed that all threads have finished the foo section, so it's safe to read the foo values.
}

I found this article, which was also some heavy reading... Heh I also read some of the 33 articles.

Designing the framework of a parallel game engine

The ideas there are MUCH better than what I had in mind and is more inline with what you are saying. It's also really crazy how much of my engine is already similar to how they describe so if I try to do something along these lines it won't be too hard at this point.

The task manager that comes with PhysX should be perfect.

I'm still trying to figure it out more or less though. Before I would have an entity's update method where it would do everything including AI if it was a character. With tasks, is every entity's update method call an individual task? I have the concept of entities being inactive and not having their update methods called if it's some object at rest doing nothing, so I could have only active entities be added to the task list.

Sometimes the update method on an entity is very simple. Something like a box moving left. It might not be worth using an entire thread for a one line update function, or is it fine since there's a thread pool and the overhead isn't really that high?

What if I'm recording a replay or playing over the network? How do things stay deterministic? The engine basically has things update at irregular time intervals due to variations in performance and all that. How would I know things synch up properly at each step?

One thing that might happen is the AI character thinks a target is at position (0, 1, 5) during the current step and acts accordingly. Then by the next step that target is at position (0, 1, 10).
What if I now play the replay on a faster computer with twice the frame rate and the target's position is synched up twice as fast? The AI is now making its decision at the same game time it made it last game, but now the target is at (0, 1, 7) and this leads the AI to desync a bit.

I'm going to throw in a couple more links in here.
http://www.1024cores.net/ is awesome for the lock-free stuff alone, but there's also a lot of other gems on the site.
If you consider using a pipeline processing model, check out http://calvados.di.u...namespace:about which is best in class.
If you like barrier type synchronization but think it needed to be improved with a fully dynamic 21st century approach, can't go wrong with hierarchical phasers: http://www.cs.rice.edu/~vs3/PDF/Shirako-Sarkar-IPDPS-2010.pdf which I think are one of the most exciting developments in parallel programming