Calling SDL functions from multiple threads via a linked list or queue

[steve9164]

Hi,

I really want to have a worker thread doing calculations and updating my game board, then sending things to a base function which can use SDL functions. This is because SDL functions can only be called from the original thread (see http://www.libsdl.org/docs/html/thread.html ).

I don't really mind what I use as long as it is not a few hundred lines long or has a list of dependencies that take ages to compile, I'm also not looking for the "must be absolutely thread safe" with lots of mutexes, just something simple maybe using C++11 atomic pointer?

So far I have come up with the idea of having a linked list like this:

struct Node
{
    (*pf)(Uint32); // pointer to function. Uint32 is a common SDL type
    /*data*/ // Variables for function parameters
    Node* next;
}

The biggest problem I can see with this is that some (EDIT: most) functions take different parameters, so the pointer to function won't work and the data variables change for each function. I could use a union in the struct and an enum to work out when to use which variables and pointer to function in a giant switch or void pointers with enum then cast again in a giant switch.

Any help would be greatly appreciated. I will try to reply to requests for clarification or explaining my problem in greater depth.

[Disch]

I'm also not looking for the "must be absolutely thread safe"

Code is either thread-safe or it isn't. If it's not, your program will be unstable and buggy, and it will be very hard to fix the bugs.

If you don't design your program with thread safety from the start, it's very difficult to work it in later.

"Lock-free" code is very likely to not work. Even code that people have written and posted on the internet is known to be broken when run on multicore machines. Synchronizing two or more threads absolutely must have a memory barrier around key variable accesses. There is no getting around that.

Any tutorial that tells you to use "volatile" to make your variables threadsafe is wrong and should not be trusted. Volatility has nothing to do with threadsafety in C++. (The exception is that some versions of MSVS [but not all] put memory barriers around volatile variable accesses, making them threadsafe, but other compilers don't do that, so you shouldn't rely on it).

There are a few ways to create a memory barrier. The most common is with a mutex. Another option is built into C++11's atomic class.


Example of bad code that will not work:

int data = 0;
bool dataready = false;

void altthread()
{
  // provide some data
  data = 5;
  // tell the main thread that the data is ready
  dataready = true;
}

void mainthread()
{
  while(!dataready);  // wait for data to be ready

  cout << data;  // BAD, 'data' may not actually be written yet.
    // might output 0, might output 5, might output something else entirely.
}

The question you really have to ask yourself is "Would making this game multithreaded really be an improvement?". It probably wouldn't be. Games tend to be linear in design, so one thread is usually all you need for the logic.

Adding more threads may not even give you a speed boost. I recently did an experiment where I tried to add multithreading to an emulator I was writing. Aside from having to spend days debugging to stop it from crashing at random times (issues with thread safety), it actually HURT performance a lot.

The numbers are here:
http://forums.nesdev.com/viewtopic.php?p=96069#p96069

("preemptive" = multithreaded as you know it
"cooperative" = using one thread to simulate many threads. For purposes of this illustraction, you can consider cooperative as being not multithreaded)

Now granted... emulators will have to "sync up" their threads more often than a normal game would. But As the numbers show I was only doing about 11 syncs per frame... and even with that low of a sync count, there was a performance decrease of ~34 FPS.

So unless you're just looking to experiment and get your feet wet with multithreading, I wouldn't bother.



EDIT:

That said... as for your actual problem... you could do this with a std::list and std::function (C++11) pairing:

#include <functional>
#include <list>

typedef std::list< std::function<void()> > calllist_t;
calllist_t  calllist;

void func1(int a);  // callback that takes 1 param
void func2(int a, int b);  // callback that takes 2 params

void producer_thread()
{
  // NOTE:  accesses to 'calllist' MUST be behind a mutex (not shown here)

  // we want the main thread to call func1(10);
  calllist.push_back( std::bind( func1, 10 ) );

  // then have it call func2( 3, 4 );
  calllist.push_back( std::bind( func2, 3, 4 ) );
}

// main thread
void consumer_thread()
{
  // NOTE:  accesses to 'calllist' MUST be behind a mutex (not shown here)

  while(!calllist.empty())
  {
    // call the function at the head of the list
    std::function<void()> func = calllist.front();
    calllist.pop_front();
    func();  // call the function
  }
}

[steve9164]

Wow, I looked into std::bind and std::function and they look like they would be very useful not only for this. I just wanted a bit of clarification about them.
The list you used was a list of void() std::functions. I understand that std::bind kind of does the same as creating a new function with your function arguments in it so that every function becomes the same type (as in you don't need to send arguments on the actual call)? I.e.

void doStuff(int, int, string, char);
std::function<void()> newFunc = std::bind(doStuff, 8, 9, "Hello", '\n');

is equivalent (or very similar to):

void newFunc()
{
    doStuff(8, 9, "Hello", '\n');
}

Please correct me if I am wrong

[steve9164]

Also you mentioned single thread work. How would I do this if I have an event loop constantly running and calling functions in new threads when a user clicks on things and calling those functions again while the first instance(s) have not yet returned if the user clicks somewhere else, as well as detecting closes and not having an interface that blocks?

[steve9164]

Then going back to the original linked list idea, I could create a new Node (which would have a Node* and std::function<void()>) do stuff to it like std::bind my function then atomically write to the Node* next. The main thread could wait (or just skip the part of the event loop which does SDL function calls until the next run) for the next pointer to not be a null pointer. This would then signify that it could go into this node and run the function. Would this create problems with multithreading.

Sorry to write three messages at once. To avoid confusion please write which message you are replying to (I.e. message 1, 2 or 3) in your replies.
Thanks

[Disch]

I understand that std::bind kind of does the same as creating a new function with your function arguments in it so that every function becomes the same type

Basically, yes. Although not all functions HAVE to be the same type. You can still pass parameters and return values (see std::placeholders::_1, etc).

std::bind is actually quite powerful, but also pretty complicated.

Also you mentioned single thread work. How would I do this if I have an event loop constantly running and calling functions in new threads when a user clicks on things and calling those functions again while the first instance(s) have not yet returned if the user clicks somewhere else, as well as detecting closes and not having an interface that blocks?

I'm curious as to what kind of program you're making where a single task takes so long that it does not return immediately.

There are ways around this, but if you really do have such time consuming functions, then multithreading might be the way to go.

Can you indulge my curiousity and give me an example of one such function that takes ~0.5 seconds or longer to complete?

Then going back to the original linked list idea

I'm not really sure why you're so determined to write your own linked list. std::list works just fine.

I mean you can if you want... it can certainly be fun to reinvent the wheel sometimes. I do it every now and then, too.

Would this create problems with multithreading.

Any situation where you have multiple threads accessing the same data can create problems with multithreading.

Memory accesses are pipelined so that they can be run much faster. This means that data can be read several lines of code before you actually try to read it. And data can be written several lines after, etc. The order of which these things actually happen is not as linear as you might think.

If thread A modifies a 'next' pointer to make it null, indicating there are no more nodes... thread B might have already started reading the 'next' pointer... even if it didn't get to that line of code yet (ie: it might still be spinning in a wait loop, waiting for thread A to tell it to go).

The only way to resolve these issues is to put up memory barriers. There is no way around it... you must do it. Memory barriers guarantee that all previous writes have completed, and no future reads have started.

The downside is that memory barriers disrupt the pipeline and thus are slow. So if you are doing a lot of them, they can really hit performance.


This is a very complicated topic... and it is very difficult to generate optimized approaches that actually work. Your best bet is to just guard accesses to shared objects with a mutex. It's simple and it works.

[steve9164]

Can writes be reordered?

I.e. In this example:

// Worker thread
nodeList->next = nullptr; // Linked list set to nullptr
... // Other code working out
Node* pNode = new Node;
pNode->data = // put whatever data into the node
nodeList->next = pNode; //next being an atomic Node* 

Could the write of pNode value to next be reordered to being before the data write?

[Disch]

Could the write of pNode value to next be reordered to being before the data write?

Yes.

There is no way around it -- you need a memory barrier.

EDIT:

It's not so much that the writes are reordered, so much as they're incomplete. Remember that modern architectures pipeline instructions well in advance, and it's already starting work on an instruction 3 steps away before it finishes the one it's currently working on.

This guy explains it pretty well. He even gives that exact same example you did and explains why it doesn't get around the problem:

http://cbloomrants.blogspot.ca/2009/01/01-25-09-low-level-threading-junk-part.html

[steve9164]

What about std::atomic<T*>? http://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync

And the reason that my threads take a while to return is that they also include delays for animations. Maybe I need to restructure my program, but when I was first writing it, I thought this was a good way. It is one of my first graphics programming tasks and is fairly simple (probably less than 1000 lines of code). How would you advise on restructuring without threads?

[Disch]

Stephen Davies wrote:

What about std::atomic<T*>

std::atomic has built in memory barrier functionality by default. So yes that will work

my original reply wrote:

Another option is built into C++11's atomic class.

;)

And the reason that my threads take a while to return is that they also include delays for animations. [snip]How would you advise on restructuring without threads?

Yes that is a very poor use of threads.

If this is for a game, you should be updating your game world every so often (like once per frame). When you're doing that, you can go through a list of active animations have call an "update" function for each of them.

Another option (if this isn't a game with regular updates), is to create timers, which basically fire off a message/event to the window handler every so often. Then once you get a timer message you can go through your animations and update them.

Something like this:

void Animation::Update( int milliseconds )
{
  // 'milliseconds' is the number of ms since the last call to update
  ms_until_next_frame -= milliseconds;

  while(milliseconds <= 0)
  {
    AdvanceAnimationToNextFrame();
    ms_until_next_frame += length_of_this_frame;
  }
}

[steve9164]

Thanks Disch. I will have a look into writing my game without threads and see how that works.