Sign in to follow this  
pachanga

Unity Multithreading: locks in World entities

Recommended Posts

(a small preamble first, I started somewhat a related topic in Multiplayer and Network Programming but I feel it's a more appropriate place for such discussions so I'm posting a more general version here as well) Guys, I'm developing a multiplayer game application with C++ and currently in the process of choosing an appropriate multithreading architecture for it. The core of the application is the endless loop which essentially updates each frame all entities of the game World. Currently this World loop is singlethreaded. It's working just fine but I'd really like to make it more scalable on multicores. Since all World entities exist in Locations, as follows: - Location - WorldEntity - WorldEntity - ... - Location - WorldEntity ...I was thinking about running each Location(and its updating logic) in a separate thread. This means I need to synchronize properly the World entities. And this is what I really don't want to to do since, I believe, explicit locking in domain classes methods is wrong and it makes the development, maintaining and debugging much-much more difficult. At first I was thinking about isolating Location entities from entities in different Locations by forbidding any calls between them. What are possible ways to achieve this? Store entities of each Location in a thread local storage so that they are not accessible from outside? Or maybe instead of a thread per Location use processes instead?(but that's going to complicate everything a lot). However even if Location entities are nicely isolated there another problem - persistence. I already have some sort of a simple generic persistence service which is running in a separate thread. It can be used in async mode, it accepts an object to be saved and returns a special future object which can be used to track the persistence process. I would love to use this service, however since it's running in a separate thread I again need to properly synchronize access to domain classes. In this case the possible option could be to implement proper cloning of domain objects so that persistence service would accept a copy of the object to be saved and no explicit locking would be needed... Hence the question, is all said above worth it? Or maybe I should simply add explicit synchronizing logic into all domain classes and be done with it? Or maybe there is some better option I'm not aware of? Thanks in advance [Edited by - pachanga on November 8, 2009 3:13:31 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by pachanga
At first I was thinking about isolating Location entities from entities in different Locations by forbidding any calls between them.
This solution sounds ok -- your game will scale to N cores, where N is the number of locations to be processed.
If you have 4 locations, you game will scale up to a quad core CPU (but won't scale any more than that).
Quote:
What are possible ways to achieve this?
Just simply don't create any links (pointers, references, etc) between entities in different locations!

You'll also need a thread safe messaging system if locations need to be able to communicate with each other. You can use a lock-free queue to pass messages from one thread to another safely.

You don't need to go putting each location in it's own process, just use discipline (and add debugging code to check you haven't made any mistakes).

You could have debugging code like:
//Thread local global variable to tell which location is being processed on this thread:
threadlocal int g_CurrentLocation;

void Location::Update()
{
g_CurrentLocation = this->ID;

for each this->entities as e
e->Update();

g_CurrentLocation = 0;
}

void Entity::Update()
{
//make sure this entity is being updated by the correct thread
assert( g_CurrentLocation == parentLocation->ID )

//...
}

Entity* Location::GetEntityByName( const std::string& name )
{
//if someone is trying to get a link to one of this location's entities
//make sure they are also being processed by this location
assert( g_CurrentLocation == this->ID );

return this->entities.find( name );
}
Quote:
Or maybe I should simply add explicit synchronising logic into all domain classes and be done with it?
If you choose this option, I'd recommend using lock-hierarchies to ensure you don't get any deadlocks.
Quote:
Or maybe there is some better option I'm not aware of?
There's no "right" way to do concurrency... but IMO, mutex-based concurrency is outdated, and will become ever more outdated with more and more cores becoming available to us. Everything should be based on "do work, memory fence, publish work". If possible you should wait for an existing memory fence rather than adding a new one for each piece of work.
Some links:
http://www.insomniacgames.com/research_dev/articles/2009/1500943
http://www.ddj.com/hpc-high-performance-computing/210604448

In my system, every game entity can potentially be running on a separate thread without any locks/mutexes.
I use the message passing / actor model of concurrency, where all function calls between entities are converted into "messages", which are executed at a safe point in time (not immediately). Return values from messages are returned as futures.
The system runs in cycles (each cycle is a memory fence). Each cycle all entities with pending messages execute their messages (each entity in parallel). Processing a message may generate new messages, which are added to a wait-free queue. At the end of the cycle, this queue is divided up among the worker threads and a new cycle begins.
If there is no work to do in a cycle (the queue is empty), then that means it's the end of the frame, and I increment the frame counter / time variables.

[Edited by - Hodgman on November 8, 2009 9:56:14 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
Some links:
http://www.insomniacgames.com/research_dev/articles/2009/1500943
http://www.ddj.com/hpc-high-performance-computing/210604448


Thanks, I'll have a look

Quote:

In my system, every game entity can potentially be running on a separate thread without any locks/mutexes.
I use the message passing / actor model of concurrency, where all function calls between entities are converted into "messages", which are executed at a safe point in time (not immediately). Return values from messages are returned as href="http://en.wikipedia.org/wiki/Futures_and_promises">futures.


Yep, the idea with futures is great, boost::future by Anthony Williams is a very nice implementation of this idea. BTW, I wonder what are the messages actually in your system? Are they just functors which are queued into a mail box of the recipient? E.g something like this:


PlayerPtr player = getPlayer(...);
SomeFuture future = player->queue(boost::bind(&Player::doSomeThing, player, arg1, arg2));


Quote:

The system runs in cycles (each cycle is a memory fence). Each cycle all entities with pending messages execute their messages (each entity in parallel). Processing a message may generate new messages, which are added to a wait-free queue. At the end of the cycle, this queue is divided up among the worker threads and a new cycle begins.
If there is no work to do in a cycle (the queue is empty), then that means it's the end of the frame, and I increment the frame counter / time variables.


Sounds interesting, thanks for sharing.

It's also interesting to know whether your objects are safely cloneable/copyable.

Share this post


Link to post
Share on other sites
Quote:
Original post by pachanga
Yep, the idea with futures is great, boost::future by Anthony Williams is a very nice implementation of this idea. BTW, I wonder what are the messages actually in your system? Are they just functors which are queued into a mail box of the recipient? E.g something like this:
PlayerPtr player = getPlayer(...);
SomeFuture future = player->queue(boost::bind(&Player::doSomeThing, player, arg1, arg2));
Yeah that's pretty much it (store the function address, this-pointer and arguments in a struct and put it in a queue), but I use some macros of my own instead of boost::bind, so the syntax I use is:
class Foo
{
public:
Method2( int, doSomething, int, arg1, int, arg2 );
};
int Foo::doSomething_( int arg1, int arg2 )
{
return arg1 + arg2;
}

Foo* pFoo = ...;
TFuture<int> four = pFoo->doSomething( 2, 2 );
An important consideration here is the memory allocator used to manage these structs/queues. My current implementation is over 100 times faster than my first proof-of-concept because I use thread-local temporary memory stores (most structs are only needed for a single cycle, simplifying allocation routines a lot) whereas my first attempt just used the default new/delete.

I haven't actually looked at boost::future, but one thing that my macros do is accept 'future' arguments as well as regular values, so you can write:
pFoo->doSomething( 2, pFoo->doSomething(1,1) );
The macro detects at compile time whether any of the arguments are futures and knows how many cycles it has to delay execution of the doSomething_ function.
With no futures passed in, there is a 1 cycle delay. With a plain future passed in there is a 2 cycle delay.
In the above case, the return value is a TFuture<int,2>, meaning the result won't be known for 2 cycles. If this value was passed to a 'message function' the macros would know to delay execution for 3 cycles, etc...

Quote:
It's also interesting to know whether your objects are safely cloneable/copyable.
I haven't needed this yet, but you could return a copy as a future.

As well as futures, objects can pass their own address to a function, e.g.
class Foo
{
public:
Method1( void, SendMeAClone, CloneReceiver*, arg1 );
};
void Foo::SendMeAClone_( CloneReceiver* pRec )
{
Foo temp = *this;
pRec->HereIsYourClone( temp );
}

Share this post


Link to post
Share on other sites
Well for one I have to use my ugly macros, e.g. this:
  Method2( int, doSomething, int, arg1, int, arg2 );

instead of:
  int doSomething( int arg1, int  arg2 );


Secondly, as I said, you've got to be careful how you handle the memory allocation for the "queued function objects" (the struct that holds the args + function pointer), as you'll be doing one of these allocations per function call.
By default that will be a ridiculous amount of overhead. You need a low-overhead constant-time allocator (and usually optimising memory allocation *speed* means that you waste memory *space*).

Also, the queue itself that you put the data into should be based on a wait-free algorithm, and care must be taken to avoid false sharing.

Third, using message passing for everything is a *general purpose* solution to concurrency. If you study a particular problem, you might be able to come up with a *specific* solution that is better for that single case.

Lastly, you've got to keep in mind that parallel logic doesn't always happen in the same order. If you've got a "game replay" function, it might break because the threading system could execute messages in a different order each time you run it.

e.g. If a player is on 10 health and gets 3 messages "at the same time" (i.e. during a single cycle):
TakeDamage(5)
TakeDamage(5)
GiveHealth(5)

If the order of these messages are executed in the above order, the players health will drop to 0 and they'll die.
But if they were executed in the below order, the player would survive:
TakeDamage(5)
GiveHealth(5)
TakeDamage(5)

I get around this by assigning each message a "priority" -- so when writing the game logic, I might give all "GiveHealth" messages higher priority than "TakeDamage" messages.
Each cycle, every entity sorts their current message queue by priority before executing them, in order to stop these "random threading bugs" from occurring.


What I like about it though is that it just makes things automatically concurrent without having to worry much about it (besides the priority thing!). You can be a user of a message passing system without being a threading expert.
There's no dead-locks, and as long as you assign the right priorities, there's no race conditions either, and you never have to use a mutex (in the game-logic code).

Share this post


Link to post
Share on other sites
On windows, I use the Interlocked family of functions.

On any x86 platform though (Windows/Linux/etc) you can use the LOCK prefix with the XCHG/CMPXCHG/etc instructions. The Windows interlocked functions compile down to these instructions.


Windows also provides _ReadWriteBarrier (and _ReadBarrier/_WriteBarrier), which on x86 are equivalent to calling any Interlocked function on a temporary variable.

On other platforms these functions may be more efficient -- x86 only has "full barriers" (i.e. _ReadBarrier/_WriteBarrier will do the exact same thing as _ReadWriteBarrier on x86), but other CPUs support "partial barriers", making _ReadBarrier/_WriteBarrier more efficient.

Share this post


Link to post
Share on other sites

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  

  • Partner Spotlight

  • Forum Statistics

    • Total Topics
      627658
    • Total Posts
      2978474
  • Similar Content

    • By Jcyshadow97
      Hi,guys.I m working on a Fantasy RPG.Currently i m work alone on the project.I really need someone can make UI stuff.If someone can handle it please feel free to contact me on email: 270514974@libero.it.
      Thank you guys and sorry for my english.
       
       



    • By STRATUM the Game
      Hey, everyone! This is my first post here.
      I would like to know what you think about my project called STRATUM. It's a 2D platformer that is heavily based on storytelling and boss fighting while trekking through the world.

      Everything in STRATUM takes place in the first century AD, in a world that wraps our own universe, called  The Stratum. A parallel Universe that is the home of the Christian deities . In this game you will play as a Dacian warrior, unfamiliar with everything in this world, you’ll get to know and understand The Stratum together with him.
      The main thing that I want with STRATUM is to reinvent the known lore and history of the Christian deities and realms. 
      The story is unconventional, it plays down a lot of the mysticism of Hell or Heaven and it gives it a more rational view while keeping the fantastic in it. What do I mean by that? Well, think about Hell. What do you know about it? It's a bad place where bad people go, right? Well, that's not the case in STRATUM. I don't want to describe such a world. In STRATUM, there is a reason for everything, especially for the way Hell is what it is in the game. "Hell" is called The Black Stratum in the game.
      This world is not very different from Earth, but it is governed by different natural laws.
      The story will also involve the reason why this world entered in touch with ours.

       
      What do you think about all that I said? Would you be interested in such a game? I have to say that everything is just a work of fiction made with my imagination. I do not want to offend anyone's beliefs.
      I want this to be a one man game. I have been working alone on it (this was my decision from the beginning) from art to effects to programming to music to sound effects to everything.
      I also have a youtube video HERE if you want to see the way the game moves and the way my music sounds.
      Please, any kind of feedback will be highly appreciated. If you have something bad to say, do it, don't keep it for yourself only. I want to hear anything that you don't like about my project.
       
    • By LimeJuice
      Hi, it's my first post on this forum and I would like to share the game I am working on at the moment.
      Graphics have been made with Blender3D using Cycle as a renderer and I am using Unity3D. It's a 2D game, one touch side-scrolling game for iOS and Android.
      Here some pictures, and you can have a look to the gameplay on this video :
      Feedbacks ?
      And if you want to try it, send me your email and I will add you to the beta tester list!
       
       








    • By Kirill Kot
      An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits. Active gameplay will appeal to players found of interactivity, especially lovers of quests and investigations.
      Available on:
      Gameroom (just open the web page and relax)
      AppStore
      GooglePlay
      WindowsPhone

    • By Kirill Kot
      Big Quest: Bequest. An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits.
      Mobile game, now available on Gameroom. Just open the web page and relax.
  • Popular Now