Threads?

[phantomotap]

Here is one such algorithm that requires no special instructions

The raw algorithm has been proven correct in an abstract machine that doesn't support concurrency the way it works on most machines in real life and assumes strictly ordered reads and writes.

Consider a machine with multiple real threads of execution that don't share real (hardware) cache: real thread one may cache the shared "ownership" array and mutates real cache which is distinct from the real cache owned by real thread two. Without memory barriers being thrown across the shared array the logic fails in any number of ways.

In other words, practical implementations in C and C++ for processors with multiple real threads will still need to use primitives that guarantee atomic operations across the real shared array. You can't do that without help from the hardware or operating system.

On the other hard, the raw algorithm works fine for systems with only one single instruction layer and one real thread of execution.

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 is true, but in practice the "i" is computed so as to be unique to a given thread.

Soma

[MK27]

However, it has been proven correct (though it does require for prerequisites, such as no OOE).

Hmmm....

The original proof shows that for overlapping reads and writes to the same storage cell only the write must be correct. The read operation can return an arbitrary number.

In that case, why use a read operation at all? Why not just use rand()? If a write operation uses a value derived from a read operation that can be arbitrary, how is it meaningful whether the write operation is then "correct"?

I'm not sure what the "Proof" proves either, but if the net result is access to a shared resource whereby a "read operation can return an arbitrary number" then this does not have any practical use value I can think of.

[phylene]

Hey, does tbb have anything over on pthreads? Is it like, better, easier to use, anything like that?

[MK27]

Hey, does tbb have anything over on pthreads? Is it like, better, easier to use, anything like that?

As Elysia points out, pthreads is a C API, if that makes a big difference to you.

TBB looks to me like something built as a higher level API on top of threads, and not a normative threading library, so it depends what you are trying to accomplish. If you want to learn about threading in a traditional sense, I would use something else. But if that doesn't matter and you just want something to provide you with some tools for concurrency, give it a try.

http://en.wikipedia.org/wiki/Intel_T...uilding_Blocks

[Elysia]

Hey, does tbb have anything over on pthreads? Is it like, better, easier to use, anything like that?

Of course it is! pthreads is for C, which means it cannot support C++ features.
tbb and boost takes advantage of C++ features to enable flexibility and control, and cleans up properly so you don't create memory leaks.