Comments on threading library

It might help if you could show how it would be used to solve a real-world problem, or a reduced form of such a problem.

It might help if you could show how it would be used to solve a real-world problem, or a reduced form of such a problem.

Ah, okies. I'll try to find some suitable examples.

I had a very quick look on your lib and noticed that you are using locks for message queue and thread pool classes. Usually these are implemented as lock-free structures for sake of performance.

Cheers, Jarkko

I had a very quick look on your lib and noticed that you are using locks for message queue and thread pool classes. Usually these are implemented as lock-free structures for sake of performance.

Cheers, Jarkko

Thanks for the tip, I heard that implementing lock-free containers can be a real pain so I'm leaving that for the future at the moment until I've tested the current version enough to see that the rest of the library works.

EDIT:
It occured to me to actually look if somebody else has written something along these lines. So far I've mostly found 1 writer-N readers, I need N-N since my messageclients can send and receive messages. I'll look into this more, if there's something ready and stable there's no reason not to use it.

I have implemented a lock-free job queue as part of Spin-X Platform if you want to have a look. I don't have a message queue implementation though, but that should be pretty trivial to implement with lock-free lifo/fifo classes. These all work in multiple producer/consumer cases.

Cheers, Jarkko

I've begun working on a threading library and I think it's got to the point that I'm considering actually telling people it exists (the horror...). It's task and message-based, i.e. you start tasks and the tasks can communicate through thread-safe messages.
If anybody got a minute to spare I'd appreciate suggestions on things I could improve, or if you want a threading library and use it it'd be even better.

The library, it's open source, can be found at http://github.com/dutt/trassel.

I'm not sure if this is the right forum for this, I considered "Alternative game libraries" or "Help wanted", if a mod think it's better in another forum please move it.

My primary question would be what is the use case you are targetting with this? Given messaging and what is in effect a thread pool, I'm not sure what problem this solves. As someone pointed out, examples would be good. But, I'll take a stab and say you are probably targetting a game system in which case I tend to suggest doing things quite a bit differently. My problem with thread pools in games is that they don't help with solving the places where threading is extremely complicated and performance sensitive, the AI/Object code portions of the game and everything they interact with. I'll just use a couple very simple examples of problems which a thread pool does not help solve:

Object 1 gets a list of Objects 2-5 and looks at their positions.
Object 1 will need to lock the data for objects 2-5 in order to safely read the positions and work on them.
Object 1 has no expectation that objects 2-5 have or have not been updated for the latest game frame.
Object 1 is going to incur 3 mutex locks/unlocks while processing, if other objects are doing the same this gets VERY expensive.

Object 1 sends "take damage" to object 3.
If object 3 dies from the damage, when do you schedule it's destruction in such a threading model? After the thread pool completes processing?

Object 1 sends message to Object 2 which sends message back to Object 1 etc, circular.
In the threaded systems this can be entertaining (sarcasm) to deal with since things happen without order.

Those are just a couple of the fun items you run into with such a solution. Did you have any thoughts on how you would deal with the above? I never got a performant solution from the thread pool style of processing and went a completely different direction, pretty much like general purpose GPU stream computing just done on the CPU for game objects.

I have implemented a lock-free job queue as part of Spin-X Platform if you want to have a look. I don't have a message queue implementation though, but that should be pretty trivial to implement with lock-free lifo/fifo classes. These all work in multiple producer/consumer cases.

Cheers, Jarkko

Thanks I'll try to have a peek when I get a free moment then.

[quote name='dutt' timestamp='1312015437' post='4842456']
snip

My primary question would be what is the use case you are targetting with this? Given messaging and what is in effect a thread pool, I'm not sure what problem this solves. As someone pointed out, examples would be good. But, I'll take a stab and say you are probably targetting a game system in which case I tend to suggest doing things quite a bit differently. My problem with thread pools in games is that they don't help with solving the places where threading is extremely complicated and performance sensitive, the AI/Object code portions of the game and everything they interact with. I'll just use a couple very simple examples of problems which a thread pool does not help solve:
[/quote]

My current target is my little hobby project I'm working on at home, so yes I'm targeting games but I might use this in other small tools too. I'll try to write some proper samples some time in the near future to make it clearer.

The other reason I wrote it was for learning, so comments/questions like yours and Jarkkos are a great help and so far I've learnt a lot during development.

Object 1 gets a list of Objects 2-5 and looks at their positions.
Object 1 will need to lock the data for objects 2-5 in order to safely read the positions and work on them.
Object 1 has no expectation that objects 2-5 have or have not been updated for the latest game frame.
Object 1 is going to incur 3 mutex locks/unlocks while processing, if other objects are doing the same this gets VERY expensive.

My plan is to use upgradeable locks in my world model(not the graphics kind of model), that way several people can read at once. Regards to writing I'm debating whether to use write-locks or a write-queue that get processed every tick. I might go with write locks at first and a write-queue if there's a lot of waiting around to write.

Object 1 sends "take damage" to object 3.
If object 3 dies from the damage, when do you schedule it's destruction in such a threading model? After the thread pool completes processing?

Hm...this I hadn't thougth about. I will probably implement a removal queue that is hanled after each tick before the next batch of processing begins.

Object 1 sends message to Object 2 which sends message back to Object 1 etc, circular.
In the threaded systems this can be entertaining (sarcasm) to deal with since things happen without order.

I don't think I should get any deadlocks but I'm not sure, I've tried to outline my thoughts on how things "should" run a bit further down.

Those are just a couple of the fun items you run into with such a solution. Did you have any thoughts on how you would deal with the above? I never got a performant solution from the thread pool style of processing and went a completely different direction, pretty much like general purpose GPU stream computing just done on the CPU for game objects.

Could you elaborate what you meant by that second part of the last sentence, "pretty much like general purpose GPU stream computing just done on the CPU for game objects"? I'm not in the business so I'm not too up to date.

I'll try to outline my rough plan; I don't have a thread per creature instead I'm using creature context runners that take a message and a creature and then let the creature handle the message
1 world runner, sending one tick() message to each creature every turn and then doing some cleanup and so on after they're all done.
N creature context runners, these handle the creature messages. Only having N creatures concurrently active should reduce the number of concurrent waiting at locks a fair amount. On a 1 or 2 core system this will probably not give much benefit but I'm runing 4 cores with HT, giving 8 threads, at home which could make it interesting since I can easily increase N if the application run on a system more cores.

I basically consider the creatures jobs and this whole thing becomes one big job queue processing plant. I think the threads will run something like this, for simplicity I'm assuming four free cores. Due to when things are sent it'll be partially ordered.
1) core 1: world sends out tick() messages.
2) core 2: receives message and runs tick() on object 1. object 1 sends a message to object 2 and then the handler is done, freeing this context runner for the next message to be handled by a creature.
2) core 3: receeves message and runs tick() on object 2. object 2 sends a message to object 1.
3) core 4: receives message from object 1 or 2 and runs handleMessage() on the target, sending the reply.
3) core n: receives message from object 1 or 2 that wasn't handled in the step above and runs handleMessage() on the target, sending the reply.
4) core n: receives a reply and run handleMessage() on the sender.
4) core n: receives the other reply and run handleMessage() on the sender.

Thoughts? I'm not sure how I naive I'm being this this is my first big foray into the scary world of threads.

Those are just a couple of the fun items you run into with such a solution. Did you have any thoughts on how you would deal with the above? I never got a performant solution from the thread pool style of processing and went a completely different direction, pretty much like general purpose GPU stream computing just done on the CPU for game objects.

I think all mutations to data which is shared between multiple threads should be delayed after the frame sync point. Flushing the mutations in the end of the frame should be rather quick operation.

Cheers, Jarkko

Could you elaborate what you meant by that second part of the last sentence, "pretty much like general purpose GPU stream computing just done on the CPU for game objects"? I'm not in the business so I'm not too up to date.

Basically I use no locking within my engine (beyond some very basic stuff) due to having reworked the various pieces of code to behave like a stream processing system. So, what that means is I can run a function over all objects without worry as long as it follows some basic rules. The primary rule is that if you read something you can not also write to it. I.e. say I am writing a flocking behavior, the update function can look at it's own position and velocity and those of all the objects around it but because the function reads that data, it can not also update it's position within the given function. It has to either store intermediate data in a stream or save it in some manner for a later update function to actually apply. So, you have to break the update into two functions:


Update_GatherInfluences( Threading::Buffer& out )
look at other objects and myself, generate a velocity change vector value.
store a pointer to myself and the new vector in the transient output buffer.

Update_ApplyNewVelocity( Threading::Buffer& in )
Extract the pointer and velocity.
Apply it


From the usage side of things:


struct temp
{
Go::Object* mpObject;
Math::Vector3f mNewVelocity;
};
threadSystem.StreamBuffer().Reserve( sizeof( temp ) * World.Objects().size() );
threadSystem.Apply( &Update_GatherInfluences, World.Objects() );
threadSystem.Barrier();
threadSystem.Apply( &Update_ApplyNewVelocity, threadSystem.StreamBuffer().Read< temp >() )
threadSystem.Barrier();
// Do more work


Basically the above code is a dirty outline of the idea. What it does is makes sure that the output buffer is large enough, it asks a bunch of threads to apply a function to all the objects in the world, and then makes sure all the work completes (a semaphore wait) and then applies the calculated data to the objects. At the cost of a little memory bandwidth you have no locking required except the two Barrier calls which just make sure all worker threads have finished the application function before moving to the next apply call. It's just turning the problem on it's side and looking at it from a different perspective.

I'll try to outline my rough plan; I don't have a thread per creature instead I'm using creature context runners that take a message and a creature and then let the creature handle the message
1 world runner, sending one tick() message to each creature every turn and then doing some cleanup and so on after they're all done.
N creature context runners, these handle the creature messages. Only having N creatures concurrently active should reduce the number of concurrent waiting at locks a fair amount. On a 1 or 2 core system this will probably not give much benefit but I'm runing 4 cores with HT, giving 8 threads, at home which could make it interesting since I can easily increase N if the application run on a system more cores.

I basically consider the creatures jobs and this whole thing becomes one big job queue processing plant. I think the threads will run something like this, for simplicity I'm assuming four free cores. Due to when things are sent it'll be partially ordered.
1) core 1: world sends out tick() messages.
2) core 2: receives message and runs tick() on object 1. object 1 sends a message to object 2 and then the handler is done, freeing this context runner for the next message to be handled by a creature.
2) core 3: receeves message and runs tick() on object 2. object 2 sends a message to object 1.
3) core 4: receives message from object 1 or 2 and runs handleMessage() on the target, sending the reply.
3) core n: receives message from object 1 or 2 that wasn't handled in the step above and runs handleMessage() on the target, sending the reply.
4) core n: receives a reply and run handleMessage() on the sender.
4) core n: receives the other reply and run handleMessage() on the sender.

Thoughts? I'm not sure how I naive I'm being this this is my first big foray into the scary world of threads.

It's not a bad starting point but it is a difficult one due to the locking and complications caused by unordered updates. You can make it work and you'll definately learn a lot in the process but it probably won't perform as well as you expect.

[quote name='JarkkoL' timestamp='1312287244' post='4843529']
I had a very quick look on your lib and noticed that you are using locks for message queue and thread pool classes. Usually these are implemented as lock-free structures for sake of performance.

Cheers, Jarkko

Thanks for the tip, I heard that implementing lock-free containers can be a real pain so I'm leaving that for the future at the moment until I've tested the current version enough to see that the rest of the library works.
[/quote]

You have heard correctly. I'm not a fan of blanket statements or I'd tell you to stay away from lockless programming. So instead I'll say this: Lockless programming is incredibly difficult to do correctly (especially across multiple platforms). Please do not underestimate it and spend ample time educating yourself about the topic. The idea behind it is simple, but when dealing with CPU and compiler re-ordering is where it becomes a nightmare. Proceed with caution.

[quote name='dutt' timestamp='1312443764' post='4844379']
Could you elaborate what you meant by that second part of the last sentence, "pretty much like general purpose GPU stream computing just done on the CPU for game objects"? I'm not in the business so I'm not too up to date.

Basically I use no locking within my engine (beyond some very basic stuff) due to having reworked the various pieces of code to behave like a stream processing system. So, what that means is I can run a function over all objects without worry as long as it follows some basic rules. The primary rule is that if you read something you can not also write to it. I.e. say I am writing a flocking behavior, the update function can look at it's own position and velocity and those of all the objects around it but because the function reads that data, it can not also update it's position within the given function. It has to either store intermediate data in a stream or save it in some manner for a later update function to actually apply. So, you have to break the update into two functions:


Update_GatherInfluences( Threading::Buffer& out )
look at other objects and myself, generate a velocity change vector value.
store a pointer to myself and the new vector in the transient output buffer.

Update_ApplyNewVelocity( Threading::Buffer& in )
Extract the pointer and velocity.
Apply it


From the usage side of things:


struct temp
{
Go::Object* mpObject;
Math::Vector3f mNewVelocity;
};
threadSystem.StreamBuffer().Reserve( sizeof( temp ) * World.Objects().size() );
threadSystem.Apply( &Update_GatherInfluences, World.Objects() );
threadSystem.Barrier();
threadSystem.Apply( &Update_ApplyNewVelocity, threadSystem.StreamBuffer().Read< temp >() )
threadSystem.Barrier();
// Do more work


Basically the above code is a dirty outline of the idea. What it does is makes sure that the output buffer is large enough, it asks a bunch of threads to apply a function to all the objects in the world, and then makes sure all the work completes (a semaphore wait) and then applies the calculated data to the objects. At the cost of a little memory bandwidth you have no locking required except the two Barrier calls which just make sure all worker threads have finished the application function before moving to the next apply call. It's just turning the problem on it's side and looking at it from a different perspective.
[/quote]

I thought a bit about doing something like that when it comes to the writing of data. Thanks a lot for the example code though, always helps to have something a bit more concrete and not just a bunch of abstract thoughts bouncing around. Interesting rule too, "read xor write", I hadn't thought about that. But what's stopping something from writing to a more complex object at the same time something else is reading from it?

[quote name='dutt' timestamp='1312443764' post='4844379']
I'll try to outline my rough plan;
...
Thoughts? I'm not sure how I naive I'm being this this is my first big foray into the scary world of threads.

It's not a bad starting point but it is a difficult one due to the locking and complications caused by unordered updates. You can make it work and you'll definately learn a lot in the process but it probably won't perform as well as you expect.
[/quote]

If that's all I get from this I'm happy Then I can create the next complete rewrite and perhaps get some performance as well.

[quote name='dutt' timestamp='1312360467' post='4843960']
[quote name='JarkkoL' timestamp='1312287244' post='4843529']
I had a very quick look on your lib and noticed that you are using locks for message queue and thread pool classes. Usually these are implemented as lock-free structures for sake of performance.

Cheers, Jarkko

Thanks for the tip, I heard that implementing lock-free containers can be a real pain so I'm leaving that for the future at the moment until I've tested the current version enough to see that the rest of the library works.
[/quote]

You have heard correctly. I'm not a fan of blanket statements or I'd tell you to stay away from lockless programming. So instead I'll say this: Lockless programming is incredibly difficult to do correctly (especially across multiple platforms). Please do not underestimate it and spend ample time educating yourself about the topic. The idea behind it is simple, but when dealing with CPU and compiler re-ordering is where it becomes a nightmare. Proceed with caution.
[/quote]

Yes that's what I heard. Making it work on one platform with one architecture can be done without too much hassle, but supporting different platforms and different architectures(primarily 32bit vs 64bit) can be a real pain. If I get the time I'll probably take a shot at it though, it's always worth a try

Yes that's what I heard. Making it work on one platform with one architecture can be done without too much hassle, but supporting different platforms and different architectures(primarily 32bit vs 64bit) can be a real pain. If I get the time I'll probably take a shot at it though, it's always worth a try

Getting it to work is the easy part.

It's trying to fix the bugs that is hard. Or when it can't be done at all.


But lockless isn't answer to "fast".

1) High contention + high operation count = pressure on cache synchronization over entire CPU (undesirable, scales poorly and affects entire system)
2) Low contention + high operation count = batch operations will work better
3) High contention + low operation count = regular critical sections work just as well (~20 cycles per lock or so)
4) Low contention + low operation count = anything

Lock-free or wait-free (terminology here is a mess) is considerably more important from design perspective. By allowing at least some part of the system to progress they prevent deadlocks, even at expense of efficiency. Such design becomes important with large heterogenous systems and may simplify or prevent certain dead-lock scenarios. There are other benefits in specific scenarios where determinism may be traded for eventual consistency.

They do not solve problems with contention. If some data is heavily read-write contested, lock-free structures will likely result in poorer performance or hang the process entirely on single-core machine.

Perhaps the best and optimal case is single-reader-single-writer, such as streaming buffers. it's also one of the earliest real-world uses in audio streaming where benefits were clear.


But in general, lock-free algorithms, especially as replacement for traditional data structures are simply not worth the cost benefit.

Even in above case of staged or batched simulation updates, regular primitives would work just fine with orders of magnitude less unknowns.

It's task and message-based, i.e. you start tasks and the tasks can communicate through thread-safe messages.

I haven't looked at the code, but this is definitely a good idea. (I know, because this is my own preferred architecture :)

So far I've mostly found 1 writer-N readers, I need N-N since my messageclients can send and receive messages. I'll look into this more, if there's something ready and stable there's no reason not to use it.

Personally I usually handle this with client callbacks. That is, the readers (sinks) will store one or more callback function pointers through which they are able to communicate back to the writer(s).

[quote name='dutt' timestamp='1312360467' post='4843960']So far I've mostly found 1 writer-N readers, I need N-N since my messageclients can send and receive messages. I'll look into this more, if there's something ready and stable there's no reason not to use it.

Personally I usually handle this with client callbacks. That is, the readers (sinks) will store one or more callback function pointers through which they are able to communicate back to the writer(s).
[/quote]

n-by-n communication is commonly handled by map/reduce these days.

One implementation comes with TBB.

Most important reason is it avoid deadlocks and subscription problems, such as which thread the callbacks are executed on (OGL might need same thread).

[quote name='dutt' timestamp='1312621097' post='4845360']
Yes that's what I heard. Making it work on one platform with one architecture can be done without too much hassle, but supporting different platforms and different architectures(primarily 32bit vs 64bit) can be a real pain. If I get the time I'll probably take a shot at it though, it's always worth a try

Getting it to work is the easy part.

It's trying to fix the bugs that is hard. Or when it can't be done at all.
[/quote]
...I included fixing bugs in "making it work" But yes I imagine the bugs can be a nightmare.

But lockless isn't answer to "fast".

1) High contention + high operation count = pressure on cache synchronization over entire CPU (undesirable, scales poorly and affects entire system)
2) Low contention + high operation count = batch operations will work better
3) High contention + low operation count = regular critical sections work just as well (~20 cycles per lock or so)
4) Low contention + low operation count = anything

Lock-free or wait-free (terminology here is a mess) is considerably more important from design perspective. By allowing at least some part of the system to progress they prevent deadlocks, even at expense of efficiency. Such design becomes important with large heterogenous systems and may simplify or prevent certain dead-lock scenarios. There are other benefits in specific scenarios where determinism may be traded for eventual consistency.

They do not solve problems with contention. If some data is heavily read-write contested, lock-free structures will likely result in poorer performance or hang the process entirely on single-core machine.

Perhaps the best and optimal case is single-reader-single-writer, such as streaming buffers. it's also one of the earliest real-world uses in audio streaming where benefits were clear.

But in general, lock-free algorithms, especially as replacement for traditional data structures are simply not worth the cost benefit.

Even in above case of staged or batched simulation updates, regular primitives would work just fine with orders of magnitude less unknowns.

Big thanks for the overview Do you have any tips on easily finding the contention/op-count factor or is it mainly run a profiler and see how much time is spent at the lock()-calls waiting?
By "high operation count" do you mean a lot of processing is done on each item retrieved from the threadsafe storage, or a lot is done before release() is calld.

[quote name='Dragonion' timestamp='1312673466' post='4845602']
[quote name='dutt' timestamp='1312360467' post='4843960']So far I've mostly found 1 writer-N readers, I need N-N since my messageclients can send and receive messages. I'll look into this more, if there's something ready and stable there's no reason not to use it.

Personally I usually handle this with client callbacks. That is, the readers (sinks) will store one or more callback function pointers through which they are able to communicate back to the writer(s).
[/quote]

n-by-n communication is commonly handled by map/reduce these days.

One implementation comes with TBB.

Most important reason is it avoid deadlocks and subscription problems, such as which thread the callbacks are executed on (OGL might need same thread).
[/quote]

Huh, I had not heard of map/reduce before, I'll look into that. I assume it's this you're referring to?

Making sure a task is always run on the same thread is an interesting challenge, I'll add that to the todo-list.

By "high operation count" do you mean a lot of processing is done on each item retrieved from the threadsafe storage, or a lot is done before release() is calld.

It depends on context. If using a message queue, it would be the number of messages posted and received. The higher the number vs. some reference frame (time slice, processing, ...), the more benefit one might get from batching. At same time it introduces the problem of over and under subscription since larger batches may lead to uneven load.

Huh, I had not heard of map/reduce before, I'll look into that. I assume it's this you're referring to?[/quote]

That or fork/join, scatter/gather... Problem is: how to most efficiently distribute n workloads over m workers.

Making sure a task is always run on the same thread is an interesting challenge, [/quote]
It's not as much important as it is crucial. UIs, IO, many APIs almost always require either execution on same thread, specific thread or both.

I'll add that to the todo-list.[/quote]
There is boost::asio which solves this problem using strands. It also covers various forms of cross-thread messaging.


IMHO, writing a thread library isn't necessary. thread is part of new C++, there is pthreads, boost::thread, OMP and all of these cover the abstractions.

Almost everything in this discussion has to do with how to correctly partition the problem and those are the hard problems to solve. But they require understanding the problem and no library can help with that. Once the problem is broken down into pieces that can be run either concurrently or in parallel, then libraries mentioned above already provide the building blocks to implement them.