Sign in to follow this  

Threadsafe game data

This topic is 3727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have two threads so far. One handles input and game logic, and is designed to run at a fairly consistant clock rate. The other is the graphics thread, with its sole mission being to churn out frames as fast as possible. I'd like to communicate between the two using a shared data model. Basically, all the game data is stored in a central repository, and the different threads and modules in the game communicate indirectly by reading and/or modifying the data (so called data-driven design). When the graphics thread goes to update, however, it needs to update itself based on a consistant game state. That is, it needs to wait for the logic thread to reach the end of whatever cycle it's currently working on. The two methods I can see to ensure this is to either block the logic thread whenever the graphics thread is ready to draw another frame (not really a good option since it totally serializes the program), or double buffer all the game data. Then, when the graphics thread signals its ready for another frame, the logic thread would flip the buffers when it finishes its current cycle. The buffers would only need to be flipped when the graphics thread is ready to render another frame, so as the FPS drops it won't effect the engine clock rate (or that's the goal anyway). not all of the game data is needed for every frame, though. Some of the much larger structures, such as the terrain heightmap, would be a pain to fully copy every frame. This leads to the idea of the graphics thread flagging what data it's going to need for the next frame, so there isn't any needless copying going on. The problem is that I don't see a clean way of doing all this in code (C#). It would be a mess of boolean flags and locks everywhere. I'm wondering if someone could point out a more elegant system. Ideally I'd like to be able to add new threads doing new tasks as the progress on the game develops, so I'm also looking for a solution that doesn't assume two threads.

Share this post


Link to post
Share on other sites
Oddly enough, you are doing EXACTLY what my engine does. I suppose great or somewhat ok minds think alike and all that.

So this is how I'm handling it. I'm going with the double buffered approach so far- unless its performance isn't up to snuff.

1) I have a large block of memory for visual objects, a struct/class of fixed size for each. I have two of those, one for editing and one for rendering. Every frame draw in the main thread, I lock the buffers mutexes and copy the edit buffer into the rendering buffer. Once the render thread has its copy of the data, its all good to go. Both threads can work on their own data freely.

2) I also have a status array and matching which contains status markers for each object. Literally, its like a library machine. When a thread wants to edit an object it reads it out, copying its 128 bytes (they are small) and marking that in the status array. When they are done, the bytes are copied back in to the array and the status marker is reset. This allows any thread to 'check out' any object at any time and return it when its done.

3) Threads that must complete their actions before the next frame can signal the engine with HoldFrame(), and then when they are done ReleaseFrame().

So this sounds quite similar to what you are doing. Things like a height map, which most likely are static anyway? (are they going to change a lot during the play) could best be handled as a resource individual from all the data copying.

I'm not sure I explained this well enough, so shoot away if you have questions.

Share this post


Link to post
Share on other sites
Having a "ready to draw" flag does serialize, possibly making your multi-threaded program slower than if it were single-threaded.

There are infinite options, and I have no idea what is right for your game. I'll just throw out some ideas that might help you get a better grasp on how to tackle this.

Data that cannot change is safe to use across threads without locks(*). Although there are a lot of requirements for this, often "level" data in games fall into this category.

Data can be segmented to allow independent operations, and then you can lock the operations. For example, you might have a character that cannot interact with large portions of your environment. You can safely render all those portions while updating the character, so you might have RenderEnvA and RenderEnvB, where RenderEnv2 can execute in parallel with UpdateCharacterPosition, but RenderEnv1 cannot.

These are the most generic things I could think of, so hopefully they help. Perhaps people can provide you better information if you provided details on the type of actions your game needs to support, as a board game is VERY different from a FPS that supports destructable environments.

Best of luck.


*: assuming a system where many reads to the same memory location are safe and fast.

Share this post


Link to post
Share on other sites
Quote:

I'm wondering if someone could point out a more elegant system.


In the general sense, we can't. The two methods you see are what are available to you (in the general case). Make a snapshot (or duplicate updates) so the two/many threads are using their own instance of the data, or lock the data to insure synchronization.

Share this post


Link to post
Share on other sites
Right, so let's say I want to pursue the idea of buffers. The game itself is a sim (most closely related to SimEarth), so it's very data heavy, and most of the data is mutable through the simulation (like erosion changing height data). Most of that data doesn't ever get rendered, but it could occasionally. Like the crime overlay in SimCity. For most scenes, the graphics thread just needs to positions and orientations of critters and the player (there's a 1st person exploratory mode, so it's not all looking down).

When buffers are swapped at the end of a cycle, the graphics thread will need to determine what information it wants to render. It will then need to block the logic thread while it copies the relevant buffers (which shouldn't take long at all).

The issue here is how to organize the buffers and the locks. There probably just needs to be one global lock that blocks access to the data repository. The graphics thread needs to wait until the logic thread(s) release the lock and signal that the cycle is computed. It then acquires an exclusive lock, and quickly copies the data it needs and releases the lock again. Not too bad, though the implementation can get tricky if there's alot of logic threads.

Some data gets copied every cycle, and so needs its own dedicated buffer. Some data, like the "surface temperature", only gets rendered in a very specific context (the player asks to see it), so it should only create the buffer when needed. It also may get updated at a much slower clockrate than the FPS, so it needs some sort of signal to show when the buffer it copied is out of date.

The question I have is where the control should lie. One way would have the graphics thread in charge of determining when to update data buffers, when they're out of date, etc. Another would have the data itself control when it gets buffered, signaling that a buffers out of date, etc. Maybe the buffers it passes have methods to invalidate them that the data can call using a stored reference. You could take it to the extreme and just have the graphics thread passively render whatever data its given, like OpenGL-- a big finite state machine.

I'd like some guidance on figuring out who should control what. Because there's alot of data, and I need the program to grow organically as new data is added to the simulation, I'm leaning towards having the data control itself, but not so far as having the graphics thread become a FSM. I'd have data inherit from a ThreadsafeData<Type> class, and pass out a ThreadsafeDataBuffer<Type> object when a thread asked for a buffer from it. The ThreadsafeData object could then signal through the ThreadsafeDataBuffer when the buffer's out of date, and the thread using it could control what to do in that situation (is this critical enough to update right now, or can we wait until later?) Different threads could have read-only access to the data without requesting a buffer, and the class itself could hide details of buffer creation, flipping, etc.

Is this the right track, or am I just making more trouble for myself?

Share this post


Link to post
Share on other sites
Some tips:

Try to reduce shared-state concurrency

If you have to then consider using software transactional memory (STM) (there are a few STM libraries for C# you can use).

If you can use lock-free containers (for some containers in C# you can check here).

Look for opportunities for data-parallization, good places to look are numerical computations on arrays, generally they are purely functional (referential transparency) and have no to very little dependencies.

Share this post


Link to post
Share on other sites
One thread only reads and displays the data, while the other thread produces the data. Related to the Producer/Consumer model, but less strict about products getting consumed. The only time any data gets locked is to make a copy at a time when the data's all consistant (at the end of an update cycle). In such a simple system like this, deadlock is extremely unlikely (unless there's a major programming snafu). It increases as the number of producer threads increases, obviously, but I'm not planning on 100s of game logic threads-- probably just one, but I might add one or two more for different "clock speeds" (run critter AI a little faster than erosion, for instance). I don't see the advantage of persuing more complex multithreading techniques.

Generally it seems to me that STM and the other things you pointed out are for large systems with hundreds of interacting threads. I don't see how it's applicable here.


To sum:
Quote:

Try to reduce shared-state concurrency


Why?

Share this post


Link to post
Share on other sites
I don't know if this can be applied to your engine as well, but I've spent a lot of time thinking about parallelization in my engine and the way it works right now is (almost) completely lock-free.
I have a thread-pool that manages any number of threads and that I access through a lock-free queue. So for example if I need to do the calculations for a particle system, do AI path finding, frustum culling, whatever... I add a new "job" to the queue. The job is basically an object that holds references to all the data it requires and has a method "run" that does the actual computation. Jobs never share state so no locking is required. Also, depending on the framerate and number of logical CPUs I process as many as four frames in advance. For this to work without too much CPU-overhead, I "clone" the necessary data structures at load time where necessary. In the case of a particle system for example, there's only one vertex buffer however there are as many as four objects for the particle system's state (each for a different frame). This produces some memory overhead but it's also much faster than duplicating data at runtime.
As soon as one frame is fully processed, it is then rendered by the render thread which also keeps a queue. In general, the queue is always filled and at least one frame is always available at any given time so synchronization is usually not necessary. However, I was afraid there could be "buffer underruns" so I decided that the thread pool should notify the renderer once all jobs for a frame have been processed. I do this using atomic operations so synchronization is also not required.

Share this post


Link to post
Share on other sites
Depending on how much of the data is used by the renderer, you might be able to seperate the data buffers and post updates for only a smaller subset of shared data (write by game mechanics/read by render). The updates could be done via events in a lockless FIFO (one generator/one consumer) Ex- position vector + movement vector/facing, animation state, special effect triggers. (They also only have to be posted if they change...)

The renderer could update its state (process the incoming events) between its render cycles (and even load level by reading only so much per cycle -- not critical if the frame rate is fast and any changes get added within some fraction of a second...)

Things like NavMeshes are often simplifications of the actual display meshes and so wont add much more memory. Animations usually have their own sequencing/control data which the AI/game mechanics care little about.

Share this post


Link to post
Share on other sites
Quote:
Original post by Numsgil
How do you signal the graphics thread that a frame is ready? Whos in charge of creating the message?


I keep track of how many job-objects belong to a frame and then keep a counter that is incremented whenever a job is completed. This can be done in an atomic fashion using some assembly (LOCK XADD). The jobs know which frame they belong to so in theory they could even be processed out-of-the-order (but they never are). Once the job counter equals the number of jobs originally pushed onto the queue, the main thread (which receives an asynchronous callback from the thread pool whenever a set of jobs is complete) notifies the render thread. This is done by setting a flag which the renderer checks whenever it has completed rendering a frame. In most cases, this flag should be pretty useless though because the renderer's frame-queue always contains the data for at least one complete frame.

Share this post


Link to post
Share on other sites
I too have started looking into this, and I'll share with you some thoughts I've had on the issue. Please note that nothing has been implemented just yet :).

We have 2 threads - the graphics thread (GT) and the world thread (WT). The GT is responsible for the scene graph and renderer (and other things, but they aren't important here) and the WT is responsible for the entities (game objects) and other things that do "stuff". For a game object to be visible, it creates it's own SceneObject class. There are many different types of SceneObject classes - vertex meshes, skeletal meshes, static meshes, simple shapes, etc. These objects encapsulate all the functionality needed for that type of object - model loading, texture/material loading, animation, etc. The SceneObject automatically registers itself with the scene graph the moment it is created (this currently requires a lock, but AFAIK there are lock-free list containers out there that would remove this).

As the end of each world update, the world engine locks the scene graph, and every game object updates the position/angle of it's graphics object. Any other logic is performed at the same time (animation updates, etc)*. The scene graph is then unlocked and the next cycle is started.

At the start of each frame (remember that world updates and frames are no longer linked together in a MT system), the graphics engine locks the scene graph, pulls the rendering details (texture id, model id, frame, position, etc) of all visible objects from it and passes it onto the renderer. The graphics engine then unlocks the scene graph, and tells the renderer to draw the data it has been sent. Once this is done, the cycle repeats.

So, that would be 1 lock per frame and 1 lock per game update. I can't think of any better way of doing this (if someone knows an atomic way of copying a 4x4 matrix I would love to hear it) without implementing some overcomplicated lock-free messaging system which would probably take up more overhead than is needed.

* The reason the SceneObject logic is performed in the world thread is because it will need to communicate animation events back to the game object that created it, and it's a hell of a lot easier to do this in the same thread as it removes another possibility of needing to lock objects.

Anyway, just some thoughts on the matter. Also, seriously offering cookies to the person that provides a lock-free 4x4 matrix copy function. It wouldn't solve the problem of the animated objects needing to communicate back to the game object, but for non-animated objects it would be a god-send.

Share this post


Link to post
Share on other sites
Sounds like the method you're running is almost serial... Lose the draw-every-gameworld-update idea. Have a single lock that allows the two threads access to the game data, and a flag.

If the flag is set to, say, true, the graphics thread needs to acquire that lock before it can refresh its self. The logic thread holds the lock until it finishes a whole gamelogic cycle, then releases it and sets the flag to true. It repeats the process by attempting to reacquire the lock. If the graphics thread manages to grab the lock, it'll set to the flag to false. This way you can run your graphics thread at pretty much any FPS you want independantly of the logic thread.

Share this post


Link to post
Share on other sites
Quote:
Original post by Numsgil
Sounds like the method you're running is almost serial... Lose the draw-every-gameworld-update idea. Have a single lock that allows the two threads access to the game data, and a flag.

If the flag is set to, say, true, the graphics thread needs to acquire that lock before it can refresh its self. The logic thread holds the lock until it finishes a whole gamelogic cycle, then releases it and sets the flag to true. It repeats the process by attempting to reacquire the lock. If the graphics thread manages to grab the lock, it'll set to the flag to false. This way you can run your graphics thread at pretty much any FPS you want independantly of the logic thread.


That's exactly what I said - at the end of every game object it locks the scene graph, updates the positions & data, relocks and and starts another update cycle. In the graphics thread, every frame it locks the scene graph, pulls a list of visible objects, unlocks it and then draws the objects. One thread could be running 200 times per second and the other 60 times per second - the only time they need to wait on each other is if one currently has the scene graph locked, and even then it is designed to minimise the amount of time spent locked.

Share this post


Link to post
Share on other sites
What happens when the graphics thread starts to lag and only manages to update, say, 10 times a second? Won't it pull the logic thread down with it?

[Edited by - Numsgil on October 1, 2007 2:04:23 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Numsgil
What happens when the graphics thread starts to lag and only manages to update, say, 10 times a second? Won't it pull the logic thread down with it?


No, because the only time the graphics thread locks the scene graph is when getting the list of visible objects. the scene graph is immediately unlocked afterwards. Then, the graphics thread does all the complicated sorting and the actual rendering in it's own time and the game thread is free to keep updating the scene graph with new values. The scene graph itself is only locked for a very short period of time.

The game engine can continue updating the scene graph at a faster rate than the graphics engine can draw it - all that happens is that some updates aren't drawn (which is a natural side-effect of putting the game and graphics into their own threads).

When the Game Thread is faster than Graphics Thread, updates performed that don't get drawn.
When the Game Thread is slower than Graphics Thread, the same frame is drawn multiple times.
When the Game Thread is the same speed as the Graphics Thread, each update is drawn to the screen exactly once.

Share this post


Link to post
Share on other sites
Ah yes, I see now. I thought that your scene graph and the render were tied together, so the graphics thread would need to stop rendering when it doesn't have access to it. You're doing basically the same thing I'm doing, then.

Share this post


Link to post
Share on other sites

This topic is 3727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this