Threads?

[JonathanS]

I know that c++ doesn't support threads and you need an external library (is that the right buzz word?).

Looked up some but since there are so many I'd thought I'd ask you guys what you like the best and why?

[manasij7479]

I know that c++ doesn't support threads and you need an external library (is that the right buzz word?).

It does, nowadays.
std::thread - Cppreference

You can also try Boost's thread for a similar design to standard threads, or Intel's tbb library which is often praised.
Btw, if you are already familiar with gui toolkits like Qt , sfml or anything else, check out their own libraries, which will be easier to learn that foreign designs.

[MK27]

Yes that is a right buzz word.

The only one I've used is pthreads, because everything I do is on linux, and that is the native standard there, among other places. An issue is that threading library must work closely with the OS kernel, so, eg, there is a windows pthreads port, but it is just a wrapper for the native MS thread library. Pthreads I think works natively on OSX, but there is also a seperate Mac threading API, I dunno what the relationship is.

Boost has a thread lib that is probably worth checking out, since it is presumably cross-platform (it will use pthreads where appropriate, the MS lib on windows, etc).
Thread Management - Boost 1.35.0
It looks to me that the means of synchronizing threads is treated separately.
Synchronization - Boost 1.41.0
Which is fine -- while thread safe synchronization is probably pre-requisite to most threaded programming, they don't need to be part of the same API.

WRT the new C++11 std::thread manasij7479 mentions, I guess the parallel means of thread safe synchronization would be:
http://en.cppreference.com/w/cpp/atomic
but again, you could use any thread safe means -- just do not bother trying to make up your own; it is not possible without resorting to processor specific asm calls, I believe.

[MK27]

Boost has a thread lib that is probably worth checking out, since it is presumably cross-platform (it will use pthreads where appropriate, the MS lib on windows, etc).
Thread Management - Boost 1.35.0
It looks to me that the means of synchronizing threads is treated separately.
Synchronization - Boost 1.41.0

Oh, maybe I'm wrong, those are older references:
Chapter..28...Thread - Boost 1.49.0
Looks like an umbrella covering threads and mutexes.

If you don't get the distinction between thread management and thread synchronization that is something you should read up on soon.

[manasij7479]

It looks to me that the means of synchronizing threads is treated separately.

What is wrong with that ?
A thread safe class might not need to use threads internally.

[MK27]

What is wrong with that ?
A thread safe class might not need to use threads internally.

That's why I said:

Which is fine -- while thread safe synchronization is probably pre-requisite to most threaded programming, they don't need to be part of the same API.

[Elysia]

...just do not bother trying to make up your own; it is not possible without resorting to processor specific asm calls, I believe.

It is, actually. It just isn't pretty, and it's pretty limited and non-efficient.
It essentially required at least n boolean variables where there are n threads. But that's just the bare minimal; any algorithm implementing such primitives is bound to need more.

Anyway, pthreads are for C. Boost and TBB are for C++ and they are pretty good, as I have used them both. TBB is also aimed to be some kind of general parallelization library (that is, you create tasks, and TBB tries to manage the number of threads and the work they do for you), but other than that, they're pretty similar.

[MK27]

It is, actually. It just isn't pretty, and it's pretty limited and non-efficient.
It essentially required at least n boolean variables where there are n threads. But that's just the bare minimal; any algorithm implementing such primitives is bound to need more.

Unless the operations on the bools is atomic, I don't see how this is a thread safe design. Even if the bools are each only modified by one thread, they are useless for synchronization if the other threads cannot safely read them (which requires a thread safe, atomic operation).

[manasij7479]

Unless the operations on the bools is atomic,...

I thought it was .. unless you've got a Quantum Computer !

[Elysia]

Here is one such algorithm that requires no special instructions: Lamport's bakery algorithm - Wikipedia, the free encyclopedia

[Elysia]

I thought it was .. unless you've got a Quantum Computer !

It most definitely isn't. Computer architectures aren't exactly simple!

To do any kind of synchronization, you need at least a load, a conditional branch, at least one instruction to modify the value you've loaded into a register and finally write back.
But what happens if there's a context switch between the load and the store?

So while it is indeed atomic in the sense that it is only 1 byte (and hence will probably only take one clock to transfer over the bus), it won't necessarily be atomic with regard to the number of instructions.

[manasij7479]

It most definitely isn't. Computer architectures aren't exactly simple!

How 'complex' can a single bit be made ?

Edit: I see.

[Elysia]

First off, a bool isn't a single bit. It's one byte. Today's computer a byte-addressed, not bit addressed.
Secondly, consider what has to happen.

First we load the value. This involves the cpu having to put the address on the bus and somehow signal the memory (this is if we ignore cache). That's one cycle.
Then we have to wait until the memory is ready to transfer the bits to the cpu. This can take many cycles. Count on 10s of cycles.
Then the data has to arrive to the cpu over the bus.
Then we need to execute some conditional branch on the value, which can cause a branch misprediction (and probably will at least once). A branch probably takes one clock cycle, but a branch misprediction is expensive.
Then we need to update the data in the registers to reflect the new state we want to write back. One clock cycle.
Finally, we need to write back. This again implies that we need to wait for the memory to be ready, transfer the bits over the bus and wait for the memory to write the data.

Consider what happens if there is an instruction trying to reference the same position in memory at the same time. This is a very real scenario with multi-core processors.

[MK27]

Here is one such algorithm that requires no special instructions: Lamport's bakery algorithm - Wikipedia, the free encyclopedia

I wouldn't trust that:

 1  lock(integer i) {
 2      Entering[i] = true;
 3      Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);

The "max" call on line 3 involves a non-atomic read thru an array of integer sized variables. If one thread half sets a Number[i] and then another thread calls max() there, the value of Number[i] in the second thread will be set to an UB value. This makes the while condition on line 10 meaningless, since Number could end up filled with completely random junk:

10          while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {

[Elysia]

I cannot vouch for its correctness since I do not fully understand it myself. However, it has been proven correct (though it does require for prerequisites, such as no OOE).