On 18 September 2013 07:19, Tim Blechmann wrote:

...

As I understood the reason semaphores were not included in c++11 was because they were too hard to use and the recommendation is to just use condition_variable instead.

i'm not sure about the rationale for not including semaphores, but tbo condition_variables are not exactly easy to use, either and i've seen a lot of code, which does not use them correctly. also the API is a bit crippled, as they do not allow to identify spurious wakeups ...

Why do you care if a wakeup is spurious? A condition_variable should be associated with some condition (the clue is in the name) and so when you wake up you re-check the condition. If the condition is true then you don't need to care whether you woke up because notified or you woke up spuriously but the condition happened to be true anyway (e.g. the condition was made true by another thread but you woke up just before it notified you.) If you're not checking some predicate then you're using it wrong.

On 18 September 2013 11:33, Tim Blechmann wrote:

also, checking the condition requires you to acquire a lock, which in

Right, to use a condition_variable you need the CV, a lock and a condition. If you don't have those three things you're using it wrong,

many use cases is not necessary. and locks are not free, as they involve memory barriers and atomic operations. and how many platforms implement PI mutexes?

Don't semaphores involve memory barriers and/or atomics too? POSIX semaphores do. (N.B. I'm not disputing that semaphores have less overhead than CVs.)

condition_variables have their use, but stating that other synchronization primitives are more error-prone to use is just wrong!

I didn't state that. I was only commenting on the assertion that the API is crippled by not detecting spurious wakeups. The claim that semaphores are error-prone comes from something called Boost.Threads, whatever that is, but it does at least give references: http://www.boost.org/doc/libs/1_31_0/libs/thread/doc/faq.html#question10

I think the semaphores are a good idea. When you work with low latency concurrent data structures, the mutex and condition variables are very slow. Even the spinlocks done with atomic variables are slow. In my library [countertree + suballocator] the suballocator spends 0.74 seconds in allocate 50000000 elements, the same code with a spinlock spends 3.5 seconds. I am agree with the critics to the standard, but my main critics to the standard is that many times they forget the "common people" language. I see when explain to my students. I must translate from the "expert" language to the "common people" language, and then they understand the use and functionality of the things. If they have problems for to understand, they will have problems when use it. I think this is a main part of the problems using the semaphores. I know it is not easy ( I know by experience), but spend time in this , save time of a lot of people. 2013/9/18 Tim Blechmann

...

...

many use cases is not necessary. and locks are not free, as they involve memory barriers and atomic operations. and how many platforms implement PI mutexes?

Don't semaphores involve memory barriers and/or atomics too? POSIX semaphores do.

(N.B. I'm not disputing that semaphores have less overhead than CVs.)

they do, but much less: according to some micro-benchmarks with much contention, dispatch semaphores on osx are about 80 times faster than CVs, while posix semaphores on linux are about 30 times faster.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

...

they do, but much less: according to some micro-benchmarks with much contention, dispatch semaphores on osx are about 80 times faster than CVs, while posix semaphores on linux are about 30 times faster.

Semaphores are ripe for people misusing them. There are good reasons their use isn't encouraged,

would you be willing to share the arguments *why* their use isn't recommended?

especially as it's extremely easy to roll your own with an atomic, a mutex and condvar which will be just as fast as any native implementation.

this is clearly wrong, but i'd be happy to be proven wrong by numbers or even better: code that i could run for benchmarking. because my numbers show the opposite.

I also might add that your figures might be good for an uncontended semaphore, but I'd bet you a top dollar semaphores perform terribly when contended whereas CVs will be less pathological (agreed this depends on the CPU in question).

as you can read in the post you quoted, by benchmarks show a factor of 30 or 80 in case of contention.

I would also be far more concerned with correctness than performance in any threading primitive. If the power users really need performance, they'll roll their own. Boost is no place for such brittle threading primitives with many caveats and/or architecture specific assumptions.

sorry, but i strongly disagree: i think that boost is the place for high-performance code, that power users can rely on. i don't know how many `power users' have to maintain abstractions for low-level primitives. regarding semaphores, can you please mention one operating system, that does not support them natively?

...

sorry, but i strongly disagree: i think that boost is the place for high-performance code, that power users can rely on. i don't know how many `power users' have to maintain abstractions for low-level primitives. regarding semaphores, can you please mention one operating system, that does not support them natively?

I agree. But we should also try to guess what memory order guarantees should a boost/standard semaphore offer. Interprocess currently uses full-fence operations on spin-semaphores (just like in other primivites, like mutexes, which is too strong for mutexes and maybe for semaphores).

To be used as a binary semaphore, I guess wait()/post() could be just acquire/release. But I don't know if this applies to counting semaphores (and specially get_value(). I can read an old thread on this:

https://groups.google.com/forum/#!topic/comp.programming.threads/HpUwUUjgLK8

i was also under the impression that wait/post should be acquire/release, both for semaphores and for events. get_value() may need some special care, but i'm not planning to add this to the sync::semaphore interface, because it is not widely supported: neither mach nor dispatch semaphores provide an API for accessing the semaphore count. cheers, tim

...

get_value() may need some special care, but i'm not planning to add this to the sync::semaphore interface, because it is not widely supported: neither mach nor dispatch semaphores provide an API for accessing the semaphore count.

Maybe support it conditionally, like mutex::native_handle()?

i'd rather keep the API simple and not expose the internal type, but this is just a gut feeling ... cheers, tim

i was also under the impression that wait/post should be acquire/release, both for semaphores and for events. get_value() may need some special care, but i'm not planning to add this to the sync::semaphore interface, because it is not widely supported: neither mach nor dispatch semaphores provide an API for accessing the semaphore count.

Ok, nice. In any case, if sem_getvalue or similar should synchronize with boty post() and wait() and read the most recent value, if the semaphore is emulated with an atomic emulation on an integer I think a Read-Modify-Write operation with memory_order_acq_rel be the answer (something like fetch_add with argument 0?) Reading the count while the mutex is hold shouldn't also work? Best, Ion

On 9/22/2013 9:30 AM, Quoth Niall Douglas:

On Intel, it's very tough to debug relaxed memory order code as Intel does very litle reordering relative to other CPUs.

ARM is better, but I believe it needs an Alpha to really get the bugs out.

There is, surely, some magic tool for LLVM somewhere which will output all programs doing all possible reordering combinations for some bit of code. That would reveal bugs even on Intel.

I used "Relacy Race Detector" a while back to test some lock-free algorithms. It does require a little bit of rewriting to instrument the code but it's pretty straightforward.

On 19 Sep 2013 at 20:27, Andrey Semashev wrote:

...

Semaphores are ripe for people misusing them.

...and blessing for those who manage to use them right. The same could be said about pretty much any component.

Of course, but I see more frequent race conditions in semaphore using code than other systems. For example, ASIO has a race condition on IOCP writes if you allow its completion port semaphore to be higher than one. Semaphores are the best tool for a limited set of use cases, but I'd use them as a last resort.

...

There are good reasons their use isn't encouraged, especially as it's extremely easy to roll your own with an atomic, a mutex and condvar which will be just as fast as any native implementation. I also might add that your figures might be good for an uncontended semaphore, but I'd bet you a top dollar semaphores perform terribly when contended whereas CVs will be less pathological (agreed this depends on the CPU in question).

Do you have numbers to prove your distrust for semaphores? Because my experience is quite different, and my use cases implied heavy contention, where semaphore and atomics allowed to avoid excessive context switches. My experience is mostly with Linux, though.

My main item of distrust is debugging race conditions caused by their use. Performance can be very good, but no better than alternatives in most cases. If by contention you mean the semaphore has a permit count of 20 and the average threads in flow is 25, then that's not what I mean by contention. By contention I mean a permit count of 1 and 1000 threads very rapidly getting through the protected code. In this situation a semaphore is no faster than a mutex in my experience.

...

I would also be far more concerned with correctness than performance in any threading primitive. If the power users really need performance, they'll roll their own. Boost is no place for such brittle threading primitives with many caveats and/or architecture specific assumptions.

I disagree. Designing and implementing such commonly used primitive as a semaphore or event, with proper porting to different platforms and testing, is a huge help for developers. Let alone potentially making it standard, if the design proves right.

As I mentioned, I'm soft for standardised win32 style events and would just love one present in the C standard. Here's a C11 proposed notifier object: https://github.com/ned14/ISO_POSIX_standards_stuff/tree/master/pthread s%20Notifer%20Object. As I mentioned, I got no interest from libc maintainers to add it, therefore POSIX couldn't get interested. A shame. Niall -- Currently unemployed and looking for work. Work Portfolio: http://careers.stackoverflow.com/nialldouglas/

On 19 Sep 2013 at 22:49, Andrey Semashev wrote:

...

Semaphores are the best tool for a limited set of use cases, but I'd use them as a last resort.

Right, semaphores are a tool with its use cases. It should be used carefully, but just as well as all threading primitives. Believe it or not, I spend much more time debugging incorrect use of mutexes and CVs than semaphores.

I think we might actually be more in agreement than not :)

...

If by contention you mean the semaphore has a permit count of 20 and the average threads in flow is 25, then that's not what I mean by contention.

No, it's more like a few hundred of threads in different processes synchronizing on a single lock-free queue.

As a "lock contention brake" wrapping other locking mechanisms by gating out contention before reaching the critical code, something like a semaphore can be very useful. In that situation any race conditions are simply inefficiency, not incorrectness. BTW I'm sure you'll agree that we're all looking forward to widespread transactional memory. On the limited amount of it I've worked with, there were far fewer threading problems. I think it matches the mental map people have of memory better, so you get less problematic code, but equally it could be selection bias due to the threading experienced perhaps embracing writing in TM sooner than others. Niall -- Currently unemployed and looking for work. Work Portfolio: http://careers.stackoverflow.com/nialldouglas/

On 18 September 2013 17:28, Gottlob Frege wrote:

But it still doesn't make it easy to use. It might have been easier to somehow wrap the lock and CV together (and a lambda for the condition?) and tell people to make sure they also lock the same CV+lock thing when pushing/pulling from the queue.

I think the problem with wrapping them together is that the binding of the three things is dynamic, not static. It's OK to use the same CV with different mutexes (as long as no waits using different mutexes ever overlap) although doing so correctly can be tricky :)

On 9/18/2013 12:04 PM, Gottlob Frege wrote:

On Wed, Sep 18, 2013 at 12:33 PM, Jonathan Wakely wrote:

...

On 18 September 2013 17:28, Gottlob Frege wrote:

...

But it still doesn't make it easy to use. It might have been easier to somehow wrap the lock and CV together (and a lambda for the condition?) and tell people to make sure they also lock the same CV+lock thing when pushing/pulling from the queue.

I think the problem with wrapping them together is that the binding of the three things is dynamic, not static. It's OK to use the same CV with different mutexes (as long as no waits using different mutexes ever overlap) although doing so correctly can be tricky :)

I wouldn't let that stop a wrapping - most cases don't need that, and you could still use "raw" CVs and locks for that.

I think it is more likely that the "devil is in the details". If we actually sat down and tried to make a simple+powerful class, we would find the gotchas. (Tends to happen with simple+powerful.)

But it might be worth trying.

FWIW latch is one such all-in-one class albeit without a customizable predicate. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3666.html

On 18 Sep 2013 at 12:33, Tim Blechmann wrote:

condition_variables have their use, but stating that other synchronization primitives are more error-prone to use is just wrong!

A CAS lock + CV is very straightforward.

semaphores and win32-style events do have a well-defined semantics, which is more suited in many use cases. of course, they can be emulated with cvs, if you don't care about performance

I have a soft spot for win32-style events because I think they fill a certain useful niche where rolling your own implementation is hard to get race condition free and performant under contention. I tried persuading WG14 to adopt one for C11, but they felt it needed to go through the AWG and POSIX, and libc maintainers weren't interested so I got nowhere. A C++11 future is effectively a one shot win32 pulse event object however, while a C++11 shared_future is effectively a one shot win32 event object. I have been known to use them with <int> and me writing 1 to the promise as a quick and dirty event object ... Niall -- Currently unemployed and looking for work. Work Portfolio: http://careers.stackoverflow.com/nialldouglas/

On 9/18/2013 3:11 PM, Ion Gaztañaga wrote:

El 18/09/2013 8:19, Tim Blechmann escribió:

...

...

As I understood the reason semaphores were not included in c++11 was because they were too hard to use and the recommendation is to just use condition_variable instead.

i'm not sure about the rationale for not including semaphores, but tbo condition_variables are not exactly easy to use, either and i've seen a lot of code, which does not use them correctly. also the API is a bit crippled, as they do not allow to identify spurious wakeups ...

performance is another point.

Yes, performance is much better if you only need to wake up a thread because an event has occurred (like an incoming packet). Some years ago I proposed semaphores for the standard:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2043.html#Semaphore...

"Certainly, the semaphore interface can be emulated with a condition and a mutex, but this emulation can't be used for important system programming tasks, like device driver implementations, signal handling or interrupt handlers."

"Condition variables can't be used in interrupt handlers because interrupt handlers should never block and thus, they shouldn't acquire locks. The post() semaphore operation turns out to be the only synchronization operation that can be safely used in an interrupt handler. Shared variables protected by locks cannot be safely accessed in interrupt handlers."

This rationale seems surely enough to provide them. Thanks for that.