Threading question

Why is this working fine?

This way of handling threading is dangerous. It will work most of the time, but sometimes something unexpected occurres. The real difficulty is to analyse the unexpected bug.

Is it safe for me to continue doing this?

Yes,no, maybe...

In other words, there is only a small time window when one thread writes data and one thread read this data. An unexpected bug occurred whenever these two windows overlaps, which might happen really seldomly.

There are some ways to ease this kind of stuff.

1. Using system synchronisation: This is often the worst case to handle multithreading in games. Whenever you use or read shared data, you ensure that your thread is the only one who read/manipulate the data by using some kind of system supported syncronisation (mutex,semaphore etc.). The issue is, that your other threads will get blocked for some time (=wasted time).

2. Atomic operations: This is pretty cool. Atomic operations ensure that there's no real blocking of threads. Check CAS operations, these are really useful for lockless lists/queues .

3. Synchronisation by contract (no official term): This is more like what you have done. You ensure, that if multiple threads read only from a shared data, that no other thread will manipulate it concurrently and if one thread manipulates shared data, no other thread read from or write to it. This in combination of a few sync points (see 1. and 2.) will ensure that your threads can work concurrently most of the time without utilising explicit sync mechanism.

One example:

10 threads animate the skeletons of a pool of entities (pulled from a list by using atomic CAS), writing the animation data to buffer B.

while 1 thread renders all animated entities from data buffer A.

After all threads has finished, swap data buffer A and B (synchroinsation point).

In this example, you use double buffering, some CAS operation and a short synchronisation phase at the end.

I see. I also understand why those windows never overlap, as you put it, because Game::updateGame() is called when Ogre3D fires its frameRenderingQueued() event, which is right after Ogre has shovelled all of the data to the GPU and has nothing else to do. This works fine if there aren't many objects to draw, but if I understand this correctly, some synchronisation problems could occur if the rendering frame rate ever drops to the rate of game loop updates.

How do I mutually exclude e.sceneNode?

Simply put, having one thread read from data at the same time as another is writing from it without synchronization is undefined behavior. The bad kind that does what you expect 99% of the time, and leaves impossible to trace errors the last 1%.

The simplest way to synchronize a large chunck of data is to a acquire a mutex when ever accessing that chunk of shared data. You always want to hold the mutex for as short an interval as possible.

Are there any common patterns for handling synchronization in games? It feels like having to grab a mutex every time I want to modify some data will quickly turn my multi-threaded game engine into an effectively single-threaded one, as all other threads will be blocked. How do you balance the need for thread-safety with the desire to not block other threads from running?

It feels like having to grab a mutex every time I want to modify some data will quickly turn my multi-threaded game engine into an effectively single-threaded one, as all other threads will be blocked.

Yep, therefor you should avoid this as much as possible. This is somewhat special about game-development, sometimes an application developer will rejoice when a process finishes after just below 200ms, whereas a game developer will break down once a process needs more then 2ms. And synchronisation is one of the fastes ways to surpass the 2ms

This works fine if there aren't many objects to draw, but if I understand this correctly, some synchronisation problems could occur if the rendering frame rate ever drops to the rate of game loop updates.

How do you balance the need for thread-safety

You dont need to balance thread-safety, because your code must be thread-safe period. It is just the matter how hard it is to ensure thread-safety. If you use mutex/semaphores/critical sections etc. it is quite easy, but potentially slow. If you use lock-less sync by contract, you are at a much higher risk of including bugs, but it is much faster.

On the other hand, maximum CPU usage is not always needed, and modern, powerful CPUs remove the burden of hobby/indie developer of squezzing out the last drop of performance. So, as long as you don't try to invent the next block-buster AAA engine, I would sugguest to use a good mix of manageable code and block-less concurrrency behavior, which feels comfortable. Just remember, the best, fastest code is worth nothing, if you can't handle it over a long period.

I know Ogre3D is using boost.thread in the background for rendering, so it is asynchronously reading from scene nodes, but I'm not synchronising when writing to the scenenodes. Why is this working fine? Is it safe for me to continue doing this?

Normally, if you put a bunch of jobs into a thread pool, you then wait for them to finish somewhere. If updateGame is the safe time to update game entities, you would wait for all those pooled updates to finish right after scheduling them, if your game has nothing else it can do before waiting.

However, as your game gets more complex, I'd expect "doFancyMovementCode" to need to read data from other entities. How are you planning on dealing with that?

However, as your game gets more complex, I'd expect "doFancyMovementCode" to need to read data from other entities. How are you planning on dealing with that?

I've been reading about different types of locks (boost synchronization chapter), and I think the most efficient way to approach that problem is to use read/write locks (shared_lock). As I understand it, multiple threads are allowed to read the same data without having to lock. The lock is only acquired if a thread tries to write to data being read.

Not quite. A reader/writer lock is still a lock. It is typically cheaper to take a read lock than a write lock, but it's still a lock.

Here's why:

- Thread A begins reading data from 0xf00
- Thread B locks 0xf00
- Thread B begins a series of writes to 0xf00
- Thread A resumes and sees partially written data
- Thread B unlocks
- Thread A is now in bogus state

If by contrast a read lock is treated like a lock:

- Thread A locks 0xf00 for read
- Thread B blocks waiting for write-lock on 0xf00
- Thread A completes its stuff and unlocks
- Thread B resumes and safely takes the write-lock and updates 0xf00
- Thread A cannot interrupt this because the read lock will block the thread until B unlocks

The main advantage to reader/writer locks is that you can cheaply read from many threads, but you still need to lock, so it isn't free. It's also much easier to introduce nasty bugs than with simple mutual exclusion. I generally recommend against R/W locks unless there is hard evidence that they can reduce threat contention, for that very reason.

Here's a (basic) implementation of a rw-spinlock: http://jfdube.wordpress.com/2014/01/03/implementing-a-recursive-read-write-spinlock

Would making the member variables of the components atomic also be an option?

I hope you appreciate this, a mandatory introduction into C++ in regards to its memory model:

http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2

I strongly recommend you spend the time watching it. I can not emphasize it enough: MT is not the land where you can just try what works and what does not - you need to understand what is going on (ie. the hows and whys). The linked talk is a good start i would say.

You can also establish a thread to perform a synchronous blocking Listen or Read from a socket, this will couse no CPU usage from the thread while the thread is sitting on the blocking function. You then from other thread can issue data to this socket so the pending thread will start working, and you can peek for result on a non blocking socket from the issuing thread for data being happend to be delivered. This is simply having no shared memory, but instead swap contacting data between workers, what allows for non-blocking, performant fullfillment of issued command on a spare thread. If you happen to have a lot of data being in a shared state, you can narrow down the contacting, keeping only synchronization between the thread's internal copies of data.

Having a graph of scene/game objects with individual locks on them is bad juju. It leads to a completely non-deterministic game loop where individual systems are operating data from this frame and the previous frame, as they all fight for locks and update your spaghetti mess of data at random intervals. Atomic members is even worse, as class invariants that affect more than one member can no longer be enforced, and individual objects can now be in a half updated/half stale state.

You shouldn't use locks or atomic variables, except in the core guts of the threading system of your engine where absolutely needed.

Most engines are based instead around data-flows.
e.g. Take some code:

A = Task()
B = Task2(A)
C = Task3(A)
D = Task4(B,C)

you can look at the input regions and output regions of these tasks, and their dependencies between each other.
Task1 has no dependencies, and treats data block A as an output. Task2 depends on Task1's output as it's input. Task4 depends on the outputs of Task2 and Task3.
Once the dependencies are known, you can arrange the tasks into a Directed Acyclic Graph, and can use a topological sort to generate a linear schedule that the tasks can be executed in.
Each task might be made up of a list of parallel jobs.
In this example, all engine threads can execute the list of Task1 jobs, then sync to ensure the whole list is completed, then they can execute all of the Task2 and Task3 jobs, then sync again, then execute the Task4 jobs.
No locking. No atomic members in high level code. Just scheduling of execution.
The high level game code remains completely deterministic. You scale across any number of CPU cores. There's no deadlocks or race conditions possible. It's more efficient due to a tiny number of sync points / atomic memory accesses (compared to one in every lock).
There's a reason that job pools have become the defacto standard way to scale across multiple cores in game engines. If you're touching locks, you're doing it wrong! :D

Would making the member variables of the components atomic also be an option?

In short, no. Atomic would make access to those variables incredibly slow and disable a lot of valid optimizations the compiler could otherwise do. Not to mention that your code using these variables is going to want to modify more then one, or make changes based on the state of multiple variables and you're right back to where you started, except that instead of seeing corrupted variable data you'd see corrupted class/struct data.

Would making the member variables of the components atomic also be an option?

No. Atomics are an optimization over locks for small types. But if you have several related fields in an object, those fields need to modified together so that they stay consistent. To ensure that happens with atomics you would need to make the whole class one atomic unit, which it most cases makes it not be a small type. Using atomics with any type, means you can't access individual members, but rather must read or write the whole object at once, which can make even small structs inefficient as atomics when you really do only need one member.

Atomics are an option when you're only sharing a small result, finding the average of a bunch of integers.