Jump to content
  • Advertisement
Sign in to follow this  
Numsgil

Threadsafe game data

This topic is 4033 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!