On Aug 20, 2007, at 6:25 PM, Peter Dimov wrote:

Howard Hinnant wrote:

...

Here is a link to a reference implementation and a FAQ for mutexes, locks and condition variables I am currently anticipating proposing for C++ standardization (or subsequent TR).

http://home.twcny.rr.com/hinnant/cpp_extensions/concurrency_rationale.html

I'm not particularly fond of the unchecked<> adaptor and the requirement that wait is called with the same mutex when the condition is default-constructed (stricter than POSIX). Why not make the latter the unchecked case? Before you answer "overhead", consider that wait blocks and is already a throwing function.

I realize that this is stricter than POSIX, however I'm not sure that the difference in strictness has a practical consequence. We're talking about a condition which would be waited on with mutex1 by a group of threads, and then at some later date (synchronized properly so as not to overlap) waited on with mutex2. Do you have motivating use cases needing this functionality? Providing it gives up some safety checks associated with the default constructor when code waits on the same condition in more than one place (and can be error prone when the locks are more than one type). As far as overhead goes, I'm more concerned about space overhead than performance overhead. On Mac, sizeof(pthread_cond_t) is 28, and sizeof(pthread_mutex_t) is 44. I would really like for there to be be an option for sizeof(std::condition) to be as close to 44 as possible. Consider: class MyClass { std::tr2::upgrade_mutex mut_; ... }; MyClass already has two std::condition's buried under the upgrade_mutex (at least by my reference implementation). And MyClass may be movable, or even copyable. That makes vector<MyClass> a very real concern. And that makes space overhead very relevant. The subsequent space overhead can lead to execution speed problems (not to mention space problems on embedded systems). Just like the std::algorithms, if people can't find a way to get the best performance (both size and speed) out of the high level tools, then there is always pressure to go down to the low level (C) tools. I coded upgrade_mutex using the C level tools directly myself, was really unhappy with the code, but it had the minimum space overhead. It was that experience that led me to look for a high-level, minimum space overhead solution. Perhaps condition<unchecked<mutex>> is the wrong syntax. But I really think the solution has to be there in some syntax. Else there is pressure on Joe Coder to drop down to pthread_cond_t. And I liked the fact that I could change the type of the condition from checked, to unchecked and back, without having to change any other code associated with the condition. I also considered unchecked::condition<mutex>, unchecked_condition<mutex>, etc. But I liked the fact that philosophically condition considered unchecked<mutex> just another kind of mutex. That meant that client code could even by typedef'd on unchecked<mutex> vs mutex for debug and release builds. unchecked<Mutex> could just be a mutex adaptor class which does nothing but alert code of the client's debug/release intent. -Howard

On Aug 20, 2007, at 7:37 PM, Peter Dimov wrote:

Howard Hinnant wrote:

...

I realize that this is stricter than POSIX, however I'm not sure that the difference in strictness has a practical consequence. We're talking about a condition which would be waited on with mutex1 by a group of threads, and then at some later date (synchronized properly so as not to overlap) waited on with mutex2. Do you have motivating use cases needing this functionality?

No, but I also have no motivating use cases needing the check when the condition has been default-constructed.

...

As far as overhead goes, I'm more concerned about space overhead than performance overhead. On Mac, sizeof(pthread_cond_t) is 28, and sizeof(pthread_mutex_t) is 44. I would really like for there to be be an option for sizeof(std::condition) to be as close to 44 as possible. Consider:

class MyClass { std::tr2::upgrade_mutex mut_; ... };

MyClass already has two std::condition's buried under the upgrade_mutex (at least by my reference implementation).

I believe that the main cost of a mutex or a condition is measured in kernel objects, not bytes. One will typically run out of kernel memory much earlier, IMO.

I'm not concerned about running out of memory. I'm concerned about generating more L1 cache misses. As long as the speed of CPU's outstrips the speed of memory, smaller is very often better. I'm aware of entire major organizations that compile with -Os when they want speed, instead of -O3. Size matters, at least for a significant number of clients. We have several opposing use cases we need to satisfy with std::condition: 1. Minimum size - performance overhead. 2. The freedom to dynamically associate mutexes with condition variables. 3. The ability to apply run time check consistency concerning the associated mutex. 4. The ability to wait on general mutex / lock types. #1 I justified in the previous paragraph. #2 is new to my list, and reflects your use case suggested with the default constructor. I believe use of pools for mutexes and/or condition variables might be a sufficiently motivating use case for #2. #3 is the opposite of #2. I believe that the use of condition variables is sufficiently error prone and hard to debug for common use cases that this is a desired feature. #4 is arguably the opposite of #1. And I believe it is also a desirable feature as outlined in several use cases in my "faq", and supported by the existence of Vista's ability to wait on a read/write mutex locked in either mode. std::condition is going to be a core building block to libraries. User-written std::condition replacements will be, at best, difficult to write. The interaction of std::condition::wait and thread interruption is something that intimately ties std::condition to the details of the rest of the std::threading library. This is unlike mutexes and locks which I anticipate can fairly easily be replaced or adapted by user-written code. Therefore I believe we need to make every effort to satisfactorily meet all of the use cases above. I believe my current prototype meets all four use cases: 1: std::condition<std::unchecked<std::mutex>> 2. std::condition<std::unchecked<std::mutex>> and std::condition<std::unchecked<Mutex>> // Mutex is general 3. std::condition<std::mutex> and std::condition<Mutex> 4. std::condition<Mutex> As for the default constructor, I have no strong feelings as to what its semantics should be. In fact at first I didn't even have a default constructor. I added it fairly late in the game on the belief that someone would violently object if it weren't there. I don't object to different syntax in meeting #1 and #2 (in principle). However I do object to not having a way to address either of those two cases (especially #1 obviously). -Howard

Howard Hinnant wrote:

On Aug 21, 2007, at 8:46 AM, Yuval Ronen wrote:

...

Howard Hinnant wrote:

...

Here is a link to a reference implementation and a FAQ for mutexes, locks and condition variables I am currently anticipating proposing for C++ standardization (or subsequent TR).

http://home.twcny.rr.com/hinnant/cpp_extensions/concurrency_rationale.html After some not-so-thorough reading of this, a few comments:

1. I couldn't understand what defer_lock is good for, even after reading Q.9 of the FAQ. I believe the use-case shown in Q.9 should actually use accept_ownership instead. Can you elaborate please?

See if this is any clearer:

http://home.twcny.rr.com/hinnant/cpp_extensions/concurrency_rationale.html#u...

I'm afraid not... This example has 3 lines, the first 2 create unique_lock with defer_lock, and the 3rd calls std::lock. Those unique_lock don't lock, because std::lock to lock. OK. But who unlocks? The unique_locks don't own the mutexes, and therefore don't unlock them. But someone needs to unlock, and it sounds logical that the unique_locks would... Had we used accept_ownership, the unique_locks would have owned the mutexes, and unlock them. That's the difference between defer_lock and accept_ownership, the ownership, isn't it?

...

2. I disagree with the answer to Q.14. I think that shared_mutex should be changed to something like:

class shareable_mutex { public: class exclusive_facade { shareable_mutex &__m; public: exclusive_facade(shareable_mutex &m) : __m(m) { } void lock(); bool try_lock(); void unlock(); };

class shared_facade { shareable_mutex &__m; public: shared_facade(shareable_mutex &m) : __m(m) { } void lock(); bool try_lock(); void unlock(); };

exclusive_facade &exclusive(); shared_facade &shared(); };

This way, the condition c'tor will not get the shareable_mutex, but rather the exclusive_facade or the shared_facade, which model Mutex. condition::wait() can then simply call Mutex::unlock(). An additional benefit (additional to having wait() not accept a lock) is that shared_lock can then be dropped, but I haven't really thought about how well this idea works with upgrade_mutex/upgrade_lock.

This appears to me to be very nearly the "nested lock" design boost currently has, though one could certainly have both these nested facades *and* namespace-scope locks.

Not quite like the "nested lock" design, IMO. Instead of requiring the shared_mutex have a lock/unlock/shared_lock/shared_unlock functions, as in your proposal, I require them to have two facades with lock/unlock functions. Equivalent, IMO.

Either way, I believe this design wouldn't meet the use case which I didn't effectively communicate in #14:

Given a read-write mutex and its associated condition variable:

my::shared_mutex rw_mut; std::condition<my::shared_mutex> cv(rw_mut);

client code wants to wait on that cv in two different ways:

1. With rw_mut read-locked. 2. With rw_mut write-locked.

If we initialized the condition variable with cv(rw_mut.exclusive()), then cv.wait() would wait with rw_mut write-locked, but we wouldn't be able to wait on cv with rw_mut read-locked.

If we initialized the condition variable with cv(rw_mut.shared()), then cv.wait() would wait with rw_mut read-locked, but we wouldn't be able to wait on cv with rw_mut write-locked.

This use case desires *both* types of waits on the *same* mutex/cv pair.

The last sentence starts with "This use case", but I see no use case. Do we really have such a use case? I haven't seen one yet. But even if we had, then maybe the solution is the same solution to the requirement you phrased as "The freedom to dynamically associate mutexes with condition variables" or "The ability to wait on general mutex / lock types" (what's the difference between those two sentences anyway?) in your response to Peter. Add a 'set_mutex(mutex_type &)', or maybe even 'set_mutex(mutex_type *)' to std::condition. I think it will solve this rare case.

...

3. A really minor thing - you suggest a mutex_debug class to ensure we're not using the platform's mutex-recursiveness. I strongly recommend using this when developing on Windows, but there's a actually a simpler way, IMO, to write it (without comparing thread ids):

template <class Mutex> class non_recursive_assert_mutex { Mutex mut_; bool locked_;

public: non_recursive_assert_mutex() : mut_(), locked_(false) { }

void lock() { mut_.lock(); assert(!locked_); locked_ = true; }

bool try_lock() { if (mut_.try_lock()) { assert(!locked_); locked_ = true; return true; } return false; }

void unlock() { locked_ = false; mut_.unlock(); } };

Thanks. You're right, that is simpler and better. I've changed the example to your code (if you don't mind).

I'm honored! And along the lines of what you said to Kai, that "It is all to easy to read a proposal, agree with it, and stay silent", I'd like to say that I certainly like the rest of your proposal :)

Howard Hinnant wrote:

Did I make more sense this time? I often complain when people use too much English and not enough C++ in their arguments, and then I find myself being guilty of the same thing. :-)

Hmmm. Maybe I need to heed this advice as well. template<class M> class condition { public: explicit condition( M * pm = 0 ) { __cndcheck_init( this, pm ); } wait( Lock & lk ) { __cndcheck_wait( this, lk.mutex() ); // ... } }; // Release mode (duh) void __cndcheck_init( void * pc, void * pm ) { } void __cndcheck_wait( void * pc, void * pm2 ) { } // Debug mode map< void*, void* > __cndcheck_state; // must be synchronized void __cndcheck_init( void * pc, void * pm ) { __cndcheck_state[ pc ] = pm; } void __cndcheck_wait( void * pc, void * pm2 ) { assert( __cndcheck_state.count( pc ) ); assert( __cndcheck_state[ pc ] == 0 || __cndcheck_state[ pc ] == pm2 ); } // Checked release mode struct __cndcheck_item // must be atomic { void * pc_; void * pm_; }; __cndcheck_item __cndcheck_state[ 17041 ]; void __cndcheck_init( void * pc, void * pm ) { __cndcheck_state[ (size_t)pc % 17041 ] = { pc, pm }; // atomic store } void __cndcheck_wait( void * pc, void * pm2 ) { __cndcheck_item it = __cndcheck_state[ (size_t)pc % 17041 ]; // atomic load if( it.pc_ == pc ) { assert( it.pm_ == 0 || it.pm_ == pm2 ); } } Or something along those lines. :-)

Howard Hinnant wrote: ...

No, not ignoring your suggestion. Still contemplating it. Of all the condition suggestions I've heard (not just here, but over the past month or so) I like yours second best. ;-)

I'm concerned that we would be relegating goal #3:

...

1. Minimum size - performance overhead. 2. The freedom to dynamically associate mutexes with condition variables. 3. The ability to apply run time check consistency concerning the associated mutex. 4. The ability to wait on general mutex / lock types.

to a non-standard-mandated debug library. In your favor, I believe most current vendors are supplying debug libs. However the checks are not uniform. Even the error reporting mechanism isn't uniform.

In general, I don't like designs that mandate checking by specifying behavior on error because they make incorrect programs correct. That is, it is no longer possible for the library to loudly flag invalid uses as the client may exploit the documented behavior and expect (or worse, ignore) the exception. It also requires that the library catches 100% of the errors, rather than 99.4% of them, and these last 0.6% can be expensive. There could be legitimate use cases that require the exception. If forced, I would probably supply checked_condition to address this need, if it proves justified. Or I might not, as checked_condition seems trivial to write as a wrapper over condition (unless I'm missing something - I haven't actually prototyped the code).

On Aug 21, 2007, at 6:31 PM, Peter Dimov wrote:

Howard Hinnant wrote:

...

...

No, not ignoring your suggestion. Still contemplating it. Of all the condition suggestions I've heard (not just here, but over the past month or so) I like yours second best. ;-)

I'm concerned that we would be relegating goal #3:

...

1. Minimum size - performance overhead. 2. The freedom to dynamically associate mutexes with condition variables. 3. The ability to apply run time check consistency concerning the associated mutex. 4. The ability to wait on general mutex / lock types.

to a non-standard-mandated debug library. In your favor, I believe most current vendors are supplying debug libs. However the checks are not uniform. Even the error reporting mechanism isn't uniform.

In general, I don't like designs that mandate checking by specifying behavior on error because they make incorrect programs correct. That is, it is no longer possible for the library to loudly flag invalid uses as the client may exploit the documented behavior and expect (or worse, ignore) the exception. It also requires that the library catches 100% of the errors, rather than 99.4% of them, and these last 0.6% can be expensive.

There could be legitimate use cases that require the exception. If forced, I would probably supply checked_condition to address this need, if it proves justified. Or I might not, as checked_condition seems trivial to write as a wrapper over condition (unless I'm missing something - I haven't actually prototyped the code).

I've given this a lot of thought. By relegating goal #3 (mutex consistency checking) to a debug build, we are also endangering goal #1. Here's the scenario: As Peter suggests, we make it undefined behavior to call wait referencing a mutex other than the one passed to the constructor. Vendor A provides a std::lib just as we anticipate: goals 1, 2 and 4 are met by the release build, and goal 3 is met by the debug build. Vendor B provides a std::lib, but not a debug build (std::lib vendors exist today that do that). So clients can now not portably depend on goal #3. They must write their own checked_condition, which isn't that hard (prototype enclosed below), but it is definitely harder than the checked/unchecked method I had proposed. On debug builds they may or may not be paying for double-checking (depending on which platform they are on). Vendor C, with the best of intentions, decides that the release build of the std::lib should contain this checking (std::lib vendors including debug checks in release builds should sound familiar to many of you). Now we have goal #3, but have lost goal #1, and there is no wrapper we can use to get it back. How do we prevent, or at least discourage, Vendor C from taking this path? One answer would be to eliminate the condition constructor taking a mutex. And drop all references to error checking or undefined behavior. We completely chuck goal #3. Writing your own checked_condition is the only way to get this functionality. The next step I fear (after we've gotten rid the condition(mutex) constructor) is that someone will notice we're not using the template parameter Mutex any longer. Why template condition at all? It needlessly complicates the interface. As soon as we take the template parameter off a condition, there goes goal #1 again: class condition { pthread_mutex_t internal_mut_; // this could also be a pthread_mutex_t*, and allocate on heap when needed pthread_cond_t cv_; public: ... }; Another answer would be to cling to goal #1 and chuck goal #4: class condition { pthread_cond_t cv_; public: ... }; Now you can *only* wait on a std::condition with a std::mutex (or a lock referencing a std::mutex). There is no error checking. There is no generalizing to shared_mutex. The good news is that a more general (templated) g_condition<Mutex> can be built on top of such a std::condition. The bad news is that it is sufficiently error prone that Anthony, Peter, and myself have all made very subtle multithread mistakes in implementing the generalized condition. This is not something that is trivial to reinvent. The correct (as far as I know) code for the general condition is freely available: http://home.twcny.rr.com/hinnant/cpp_extensions/condition The source isn't that long. But I repeat, it is subtle. So, those of you who were very much in favor of goal #1 (zero overhead), and/or goal #3 (run time consistency checking), this is your chance to make lots of noise. These goals are in danger of being dropped. Here's checked_condition: template <class Mutex> class checked_condition { public: typedef Mutex mutex_type; private: std::condition<mutex_type> cv_; mutex_type* mut_; public: checked_condition() : mut_(0) {} explicit checked_condition(mutex_type& m) : mut_(&m) {} void notify_one() {cv_.notify_one();} void notify_all() {cv_.notify_all();} template <class Lock> void wait(Lock& lock) { if (!lock.owns() || (mut_ != 0 && lock.mutex() != mut_)) throw std::runtime_error("Or whatever error handling policy you want"); cv_.wait(lock); } template <class Lock, class Predicate> void wait(Lock& lock, Predicate pred) { if (!lock.owns() || (mut_ != 0 && lock.mutex() != mut_)) throw std::runtime_error("Or whatever error handling policy you want"); cv_.wait(lock, std::move(pred)); } template <class Lock> bool timed_wait(Lock& lock, const std::utc_time& abs_time) { if (!lock.owns() || (mut_ != 0 && lock.mutex() != mut_)) throw std::runtime_error("Or whatever error handling policy you want"); cv_.timed_wait(lock, abs_time); } template <class Lock, class Predicate> bool timed_wait(Lock& lock, const std::utc_time& abs_time, Predicate pred) { if (!lock.owns() || (mut_ != 0 && lock.mutex() != mut_)) throw std::runtime_error("Or whatever error handling policy you want"); cv_.timed_wait(lock, abs_time, std::move(pred)); } }; -Howard

Peter Dimov wrote:

Howard Hinnant wrote:

...

Vendor C, with the best of intentions, decides that the release build of the std::lib should contain this checking (std::lib vendors including debug checks in release builds should sound familiar to many of you). Now we have goal #3, but have lost goal #1, and there is no wrapper we can use to get it back.

How do we prevent, or at least discourage, Vendor C from taking this path?

Shouldn't Vendor C be allowed this freedom? If its customers prefer paying the price of a pointer in exchange for the ever-present checks, why should the vendor be prevented from delivering the product they want? We can explain the rationale for the design and our suggested implementation in non-normative notes and let the vendors make the informed decision.

FWIW, I agree. I'm trying to convince removing the Lock argument from wait() function, which might not exactly coincide with this discussion, but as far as this discussion goes, I agree.

Today I don't use list::size() in portable code. Why? Because we gave the vendor too much freedom.

How do you compute the size of a std::list in portable code then? :) Emil Dotchevski http://www.revergestudios.com/reblog/index.php?n=ReCode

Howard Hinnant wrote:

On Aug 22, 2007, at 2:37 PM, Emil Dotchevski wrote:

...

...

Today I don't use list::size() in portable code. Why? Because we gave the vendor too much freedom.

How do you compute the size of a std::list in portable code then? :)

I try not to. If I find I must, I write my own replacement list. It is one of the simpler containers to write.

I think that given a std::list object, the best way for user code to compute its size is to call .size(). It would be a user error to assume that .size() is O(1), but it wouldn't be a mistake to assume that the implementation of size() will use the strategy that makes the most sense on that platform.

Howard Hinnant wrote:

...

Vendor C, with the best of intentions, decides that the release build of the std::lib should contain this checking (std::lib vendors including debug checks in release builds should sound familiar to many of you). Now we have goal #3, but have lost goal #1, and there is no wrapper we can use to get it back.

We haven't lost goal #1. What has happened is that the vendor decided that the benefits of supplying debug checks (goal #3) outweight the performance cost of those checks, on that platform. I don't see harm in that, as long as it doesn't violate the standard. Consider that this decision was made by experts in the problem domain targeting a specific platform. Emil Dotchevski http://www.revergestudios.com/reblog/index.php?n=ReCode

On Aug 22, 2007, at 5:29 PM, Yuval Ronen wrote:

Checking that mutexes match to avoid errors is in the realm of bug-finding aids of debug builds. Putting it in the hands of the implementors is just fine and if they choose to assert, it's best.

In general I agree with the philosophies expressed by you and others in this area. It is best to assert on logic errors. It is best to leave debug/release policies in the hands of the vendors, etc. I think std::condition is a special case. The exception to the rule. This is a really low-level class where we have very strong motivation to provide two conflicting goals: ultimate performance and consistency checking. It must deliver as much performance as possible, because it is a foundation class. It will potentially be used (mostly indirectly) by a large body of code. At the same time, it is inherently easy to misuse. It has two separate parts that must be used together correctly (the condition and the mutex). This is a class that we're proposing can be used in two different ways: Use the default constructor and this code is legal: mutex m1; mutex m2; condition<mutex> cv; ... unique_lock<mutex> lk(m1); while (pred) cv.wait(lk); ... unique_lock<mutex> lk(m2); while (pred) cv.wait(lk); Simply change the condition construction to: condition<mutex> cv(m1); And all of the sudden the above code is no longer legal. If the code is legal with one constructor, what is it that makes the code a logic error **100% of the time**, instead of a fixable exceptional circumstance when using the second constructor? The API of a condition variable is difficult and complex just by its very nature (all designs, not just this one). I think it deserves special treatment. -Howard

on Wed Aug 22 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

This is a class that we're proposing can be used in two different ways:

Who's "we?" Does this correspond to your proposal, or, say, Peter's suggested modification?

Use the default constructor and this code is legal:

mutex m1; mutex m2; condition<mutex> cv; ... unique_lock<mutex> lk(m1); while (pred) cv.wait(lk); ... unique_lock<mutex> lk(m2); while (pred) cv.wait(lk);

Simply change the condition construction to:

condition<mutex> cv(m1);

And all of the sudden the above code is no longer legal. If the code is legal with one constructor, what is it that makes the code a logic error **100% of the time**, instead of a fixable exceptional circumstance when using the second constructor?

I didn't understand any of that sentence after the word "constructor." Could you rephrase? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

Oh, please modify my comment below by assert or whatever. I should've used the word "undefined" instead of throws. I just copied/pasted from the current proposal. -Howard On Aug 22, 2007, at 6:56 PM, Howard Hinnant wrote:

On Aug 22, 2007, at 6:31 PM, David Abrahams wrote:

...

on Wed Aug 22 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

This is a class that we're proposing can be used in two different ways:

Who's "we?" Does this correspond to your proposal, or, say, Peter's suggested modification?

This is my proposal plus Peter's suggested modification. Sorry for the confusion.

My original proposal was:

condition(); // All waits must reference the same mutex of type mutex_type, else condition_error thrown

Peter's suggested modification is:

condition(); // No mutex consistency checking

The motivation for the suggested change is not that it saves performance (it doesn't). But that there may be valid use cases.

The other constructor remains unmodified:

explicit condition(mutex_type& m); // All waits must reference m, else condition_error thrown

...

...

Use the default constructor and this code is legal:

mutex m1; mutex m2; condition<mutex> cv; ... unique_lock<mutex> lk(m1); while (pred) cv.wait(lk); ... unique_lock<mutex> lk(m2); while (pred) cv.wait(lk);

Simply change the condition construction to:

condition<mutex> cv(m1);

And all of the sudden the above code is no longer legal. If the code is legal with one constructor, what is it that makes the code a logic error **100% of the time**, instead of a fixable exceptional circumstance when using the second constructor?

I didn't understand any of that sentence after the word "constructor." Could you rephrase?

With the current proposal, as modified by Peter's suggestion above, waiting on a single cv with multiple mutexes (as long as the waits are not simultaneous) is legal if the condition is default constructed, and illegal if the condition is constructed with a mutex.

If a given bit of code waits on a single cv with multiple mutexes in a legal fashion when the condition is default constructed. Why is that same code necessarily a logic error if the constructor is changed? A contrived example (sorry, best I can do on short notice): The user, via std::cin, selects a mutex to wait on. He is supposed to pick the right one. But he makes a mistake and picks the wrong one. Logic error or exceptional runtime condition? If a logic error, why is it not still a logic error if the condition is default constructed? Simply because we declare it to be so in the documentation?

-Howard

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

On Aug 22, 2007, at 7:14 PM, David Abrahams wrote:

The reason is, "Peter said so." In other words, if you accept Peter's modification, the contract says "if you construct it this way, it's a logic error to use it that way."

I don't see a problem with that.

Ok, so what if Howard says: If you construct it this way, it's a run time error to use it the that way. Is that statement in any way more or less correct? I fear we're arguing about the number of angles that can dance on the head of a pin. We need use cases in this area and we have none (so far). -Howard

Howard Hinnant wrote:

On Aug 22, 2007, at 7:14 PM, David Abrahams wrote:

...

The reason is, "Peter said so." In other words, if you accept Peter's modification, the contract says "if you construct it this way, it's a logic error to use it that way."

I don't see a problem with that.

Ok, so what if Howard says: If you construct it this way, it's a run time error to use it the that way. Is that statement in any way more or less correct?

Howard actually says that using it that way results in an exception, and this statement isn't more or less correct. It's just different.

I think std::condition is a special case. The exception to the rule.

This is a really low-level class where we have very strong motivation to provide two conflicting goals: ultimate performance and consistency checking.

I'm not convinced that std::condition is more special in terms of performance requirements than say std::vector or std::for_each. There are plenty of other components that are commonly used in performance-critical code -- which is precisely why the standard does not require such components to detect and report errors, yet implementations commonly detect and report them, at least in debug builds.

And all of the sudden the above code is no longer legal. If the code is legal with one constructor, what is it that makes the code a logic error **100% of the time**, instead of a fixable exceptional circumstance when using the second constructor?

One can come up with any number of examples of bugs being introduced in previously correct programs by seemingly trivial changes. Emil Dotchevski http://www.revergestudios.com/reblog/index.php?n=ReCode

On 8/22/07, Howard Hinnant <hinnant@twcny.rr.com> wrote:

Vendor C, with the best of intentions, decides that the release build of the std::lib should contain this checking (std::lib vendors including debug checks in release builds should sound familiar to many of you). Now we have goal #3, but have lost goal #1, and there is no wrapper we can use to get it back.

How do we prevent, or at least discourage, Vendor C from taking this path?

One answer would be to eliminate the condition constructor taking a mutex. <snip> Now you can *only* wait on a std::condition with a std::mutex (or a lock referencing a std::mutex). There is no error checking. There is no generalizing to shared_mutex. The good news is that a more general (templated) g_condition<Mutex> can be built on top of such a std::condition. The bad news is that it is sufficiently error prone that Anthony, Peter, and myself have all made very subtle multithread mistakes in implementing the generalized condition. This is not something that is trivial to reinvent. The correct (as far as I know) code for the general condition is freely available:

http://home.twcny.rr.com/hinnant/cpp_extensions/condition

The source isn't that long. But I repeat, it is subtle.

This is exactly the sort of thing I try to avoid. Very direct and obvious multithreading code is hard to get right; why would I want to mess with subtle multithreading code?

So, those of you who were very much in favor of goal #1 (zero overhead), and/or goal #3 (run time consistency checking), this is your chance to make lots of noise. These goals are in danger of being dropped.

In case it wasn't obvious from my previous emails, I am in this camp. I think that the zero-overhead goal is important for the same reason that the STL should try to be as efficient as low-level data structures whenever possible -- to allow people to use abstractions without paying high penalties. Goal #3 is useful because every bit of checking helps make this difficult type of programming a bit easier to get right. I find these arguments so fundamental I have a hard time expressing them. I'd like to know what objections people have to these as goals, per se. As goals I think they're bang-on, and from Howard's responses to the comments in this thread, I think the rest of the design flows inherently from these goals. Could the folks who object to the current design spell it out for me a bit more explicitly -- what in the design is dangerous/inconvenient enough to throw away one or more of the 4 goals? Zach Laine

on Wed Aug 22 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

Ok, this is my last post for approximately 24 hours (for unrelated, personal reasons). If I don't answer in a timely fashion for a day, please know that it is not because I'm ignoring you.

I wanted to leave off with a few "PS" type comments:

On Aug 22, 2007, at 2:59 PM, Zach Laine wrote:

...

Could the folks who object to the current design spell it out for me a bit more explicitly -- what in the design is dangerous/inconvenient enough to throw away one or more of the 4 goals?

I would like to see an answer to Zach's question too. I do not know what the major objection is with the "current proposal". I only know that people are suggesting alternatives.

1. I'm extremely wary of turning what is almost certainly a programming error into an exception (std::vector<T>::at notwithstanding), for reasons laid out in this thread: http://tinyurl.com/2ph58t 2. I think the concept of unique_lock is too fuzzy. I know what unique_ptr (and auto_ptr, and shared_ptr, and scoped_ptr) mean. With unique_lock, I can't quite tell. This might ultimately end up being fixed by a naming change, but I think there's an underlying conceptual problem, or at the very least, a missing rationale. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

on Fri Aug 24 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

2. I think the concept of unique_lock is too fuzzy. I know what unique_ptr (and auto_ptr, and shared_ptr, and scoped_ptr) mean. With unique_lock, I can't quite tell. This might ultimately end up being fixed by a naming change, but I think there's an underlying conceptual problem, or at the very least, a missing rationale.

I will try to better fill out the rationale. And am certainly open to a name change.

In a nutshell, the current unique_lock<Mutex> is an evolution of the current boost::detail::thread::scoped_lock<Mutex>. It has been taken out of namespace detail, renamed, given move semantics, and slightly more flexibility in how it handles the mutex. The only invariant that has changed from the boost design is that one can have a unique_lock which doesn't reference a mutex. This was a consequence of a moved- from unique_lock.

That's not the rationale I'm looking for. I don't mean "how did we get here?" I mean, what *is* this thing, conceptually? What can I understand about a function that accepts one as an argument (for unique_ptr it's very clear, and exceedingly so for scoped_lock, since you can't do that)? What does it mean to return one from a function or store it in a container? I understand what scoped_lock means. If unique_lock doesn't mean "no ownership or sole ownership of the mutex it references" then what does it mean, and what's the justification for calling it "unique?" -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

On 8/26/07, Howard Hinnant <howard.hinnant@gmail.com> wrote:

Conceptually a unique_lock is the sole RAII owner of the exclusive lock state of an object that meets certain Mutex concepts.

...

What can I understand about a function that accepts one as an argument (for unique_ptr it's very clear, and exceedingly so for scoped_lock, since you can't do that)?

To accept a unique_lock (which currently owns the exclusive state) by value in a function parameter means transferring the ownership of that exclusive lock state from the current scope, to the scope within the called function.

...

What does it mean to return one from a function or store it in a container?

It means to transfer the sole ownership of the exclusive lock state from within the function, to the calling scope.

...

I understand what scoped_lock means. If unique_lock doesn't mean "no ownership or sole ownership of the mutex it references" then what does it mean, and what's the justification for calling it "unique?"

unique_lock means "no ownership or sole ownership of the mutex it references".

I think your concern began with my std::lock example:

On Aug 22, 2007, at 10:36 AM, David Abrahams wrote:

...

on Tue Aug 21 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

This line:

unique_lock<_L1> __u1(__l1);

implicitly calls __.l1.lock() inside of the unique_lock constructor. If __l1 is a mutex, the deed is done. If __l1 is a lock, hopefully that will forward to the referenced mutex's lock() function in the proper manner. And in the process, that should set the lock's owns() data to true as well.

That's part of what I found counfounding about the name "unique_." Now you have two locks (__l1 and __u1) that "own" the mutex.

__u1 now uniquely owns the exclusive lock state of __l1. __u1 does not know or care what it means for __l1 to be in an exclusive locked state. It only knows that it uniquely owns it. That is, until further notice, no other object in the program has executed __l1.lock(), or __l1.try_lock() (or any of the other functions which can put a mutex into a exclusive locked state) without having already executed __l1.unlock(). Anything that happens inside of __l1 when __l1 is in its exclusively locked state is an implementation detail of __l1, which __u1 is not privy to.

-Howard

Is 'exclusive_lock' a better name? 'exclusive' implies unique, but seems better for locks. There may also be some confusion between - owning the object - referencing the object - owning the state of the object a unique_ptr references an object, and owns the object, exclusively. In this sense, 'ref' and 'own' mean the same thing. a unique_lock references an objet, and has exclusive ownership of its locked state. Slightly different. And 'ref' != 'own'. Or 'own' is ambiguous between owning the object and owning the state of the object. Does that help? Tony

on Sun Aug 26 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

That's not the rationale I'm looking for. I don't mean "how did we get here?" I mean, what *is* this thing, conceptually?

Conceptually a unique_lock is the sole RAII owner of the exclusive lock state of an object that meets certain Mutex concepts.

Meaning, unless ownership is transferred away from the unique_lock, when it is destroyed, the object is unlocked?

...

What can I understand about a function that accepts one as an argument (for unique_ptr it's very clear, and exceedingly so for scoped_lock, since you can't do that)?

To accept a unique_lock (which currently owns the exclusive state) by value in a function parameter means transferring the ownership of that exclusive lock state from the current scope, to the scope within the called function.

...

What does it mean to return one from a function or store it in a container?

It means to transfer the sole ownership of the exclusive lock state from within the function, to the calling scope.

...

I understand what scoped_lock means. If unique_lock doesn't mean "no ownership or sole ownership of the mutex it references" then what does it mean, and what's the justification for calling it "unique?"

unique_lock means "no ownership or sole ownership of the mutex it references".

I think your concern began with my std::lock example:

Yes.

On Aug 22, 2007, at 10:36 AM, David Abrahams wrote:

...

on Tue Aug 21 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

This line:

unique_lock<_L1> __u1(__l1);

implicitly calls __.l1.lock() inside of the unique_lock constructor. If __l1 is a mutex, the deed is done. If __l1 is a lock, hopefully that will forward to the referenced mutex's lock() function in the proper manner. And in the process, that should set the lock's owns() data to true as well.

That's part of what I found counfounding about the name "unique_." Now you have two locks (__l1 and __u1) that "own" the mutex.

__u1 now uniquely owns the exclusive lock state of __l1. __u1 does not know or care what it means for __l1 to be in an exclusive locked state. It only knows that it uniquely owns it. That is, until further notice, no other object in the program has executed __l1.lock(), or __l1.try_lock() (or any of the other functions which a can put a mutex into a exclusive locked state) without having already executed __l1.unlock().

It sounds like you're saying that it's legit for some "other object in the program" to call __l1.unlock() while __u1 is uniquely holding __l1's lock state. Are you really saying that?

Anything that happens inside of __l1 when __l1 is in its exclusively locked state is an implementation detail of __l1, which __u1 is not privy to.

That part, I understand. __u1 might be analagous to unique_ptr<shared_ptr<T> > if __l1 is a lock analagous to shared_ptr<T>. Right? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

on Mon Aug 27 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

...

until further notice, no other object in the program has executed __l1.lock(), or __l1.try_lock() (or any of the other functions which a can put a mutex into a exclusive locked state) without having already executed __l1.unlock().

It sounds like you're saying that it's legit for some "other object in the program" to call __l1.unlock() while __u1 is uniquely holding __l1's lock state. Are you really saying that?

No. I'm saying __u1 owns the exclusively locked state of __l1. What that ownership means is __l1's business.

What was all that about executing __l1.unlock(), then? Should I just ignore it? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

I'm trying to summarize the renaming suggestions so they do not get lost. Here's my current list: The format is: current name ------------ suggestion 1 suggestion 2 ... unique_lock<Mutex> ------------------ exclusive_lock<Mutex> The boost name is Mutex::scoped_lock unique_lock<Mutex>::owns() -------------------------- owned() owns_lock() held() holds_lock() The boost name is locked() try_to_lock ----------- immediate The boost name is true defer_lock ---------- deferred Boost doesn't have this functionality accept_ownership ---------------- prelocked Boost doesn't have this functionality Have I missed any "renaming" suggestions? Comments pro or con on any of the above? My current feeling is that exclusive_lock has strong support, and I have no problem with that one myself. I'm not quite sure which of the owns() substitutes is the current front runner (holds_lock?). My only concern with this decision is that the name we choose should clearly not be ambiguous with "referencing a mutex". And the name should also not be ambiguous with asking if the mutex is locked (it may be locked by another thread). "try_lock" or "trylock" is a well known term. I fear "immediate" is not a good substitute as it does not imply to me that a "try_lock" is going to be performed. The existing "try_to_lock" is a compromise to avoid conflicts with a namespace-scope try_lock function. "try" would be nice, but is a keyword. I have no opinion on the last two (defer_lock, accept_ownership). -Howard

Howard Hinnant wrote:

On Aug 22, 2007, at 2:59 PM, Zach Laine wrote:

...

Could the folks who object to the current design spell it out for me a bit more explicitly -- what in the design is dangerous/inconvenient enough to throw away one or more of the 4 goals?

I would like to see an answer to Zach's question too. I do not know what the major objection is with the "current proposal". I only know that people are suggesting alternatives.

I deliberately only submitted an alternative for consideration instead of poking holes in your design or argumentation. But if you insist... I don't believe that my suggested alternative throws away any of the four goals, hypothetical malicious vendor D notwithstanding. It is still possible for the vendor to meet the goals. In addition, it adds Goal 5: the ability to control the level of checking globally; Goal 6: ... without source changes or even recompilation. This can help if hypothetical user D, lured by the "no overhead, less L1 cache misses!" slogan, uses unchecked<> as a matter of habit. "Checking is for other people." On reflection though, I'll change the constructor from explicit condition( Mutex * pm = 0 ); to explicit condition( Mutex * pm ); as it's too easy to accidentally disable checking by not including the condition in the member init list. Going back to: class shared_mutex { typedef mutex mutex_t; typedef condition<unchecked<mutex_t>> cond_t; mutex_t mut_; cond_t gate1_; cond_t gate2_; unsigned state_; ... and the L1 cache miss argument for: class A { shared_mutex mx_; ... }; vector<A> v; 1. The size of shared_mutex, according to your numbers, is 104. If we assume 16 bytes of state in A, this makes sizeof(A) 120. The addition of two pointers makes it 128. This is a 7% increase, but it also happens to round up the size of A to 128, which makes it never straddle a cache line, so the "more bloated" version will actually be faster. Note that I picked the number 16 before realizing that. :-) If A had 24 bytes of state the two pointers would of couse be detrimental. 2. I'm having a hard time imagining a program where the L1 cache misses due to the increased size of A would matter. An object of type A allocates a not insignificant amount of kernel resources, so it would be hard to keep so many A's in memory for the +7% L1 misses to show up. 3. What is sizeof(pthread_rwlock_t) on your platform? Is it not something like 48-56? This is half the size of the above shared_mutex, so users who are L1 cache miss conscious will not use the shared_mutex anyway. 4. The vector v would need to be protected by its own rwlock as well since you can't reallocate it while someone is accessing the A's, which creates a central bottleneck. vector< shared_ptr<A> > does not suffer from this problem as you can reallocate it while someone is holding a reference to an element in the form of shared_ptr. 5. If optimizing the L1 cache friendliness of shared_mutex is an important goal, I would consider moving the conditions to the heap as they aren't accessed on the fast path. class shared_mutex { mutex mx_; unsigned state_; void * rest_; }; I know that your actual shared_mutex will use atomics on state_, so you could even be able to make class shared_mutex { unsigned state_; // , state2_? void * rest_; }; work. Uncontended access now doesn't touch *rest_ and L1 cache misses are a fraction of what they used to be. Contended access does cause more cache misses, but this is shadowed by the cost of the contention.

Howard Hinnant wrote:

On Aug 23, 2007, at 10:35 AM, Peter Dimov wrote:

...

On reflection though, I'll change the constructor from

explicit condition( Mutex * pm = 0 );

to

explicit condition( Mutex * pm );

as it's too easy to accidentally disable checking by not including the condition in the member init list.

Doesn't this remove goal 2?

2. The freedom to dynamically associate mutexes with condition variables.

No, condition( 0 ) still works as before, it's just not a default constructor. The problem is that in: class X { mutex mx_; condition cn_; public: X() {} }; the author of X may have accidentally omitted the initialization of cn_. Without a default constructor, this doesn't compile and one needs to explicitly choose between X(): cn_( &mx_ ) {} and X(): cn_( 0 ) {} // no checking The compromise where a default-constructed (checked) condition is automatically associated with the mutex the first time wait is called doesn't help if one consistently uses wait with the wrong mutex (as could happen if there is a single wait call in the code - not unusual).

Ion Gaztañaga wrote:

Peter Dimov wrote:

...

the author of X may have accidentally omitted the initialization of cn_. Without a default constructor, this doesn't compile and one needs to explicitly choose between

X(): cn_( &mx_ ) {}

and

X(): cn_( 0 ) {} // no checking

What about...

template<Mutex> class condition { condition(); explicit condition(any_mutex_type); explicit condition(mutex_type& m); //... };

This is possible, but the default constructor still allows you to forget to associate the condition with a mutex: X() {} any_mutex vs 0 is a style issue; I prefer to use an old-fashioned way if it does the job as this is what the majority of the audience expects and understands, as un-Boost-y this may sound. :-) Not a big deal though.

On Aug 24, 2007, at 5:22 PM, Howard Hinnant wrote:

The current boost::condition::wait(lock) throws if lock.locked() returns false. To people view this as a recoverable run time error? Or a debug feature that should not be present in release builds?

I.e. if lock.locked() (lock.owns() or lock.holds_mutex() or whatever) returns false, is that undefined or defined behavior?

-Howard

Or should condition::wait() not take any parameters, or take only mutexes, making the issue moot? -Howard

Peter Dimov wrote:

Howard Hinnant wrote:

...

Or should condition::wait() not take any parameters, or take only mutexes, making the issue moot?

I think that we ought to keep the lock argument, even if we end up not using it for anything except debug checks. It helps people avoid accidental calls to 'wait' without locking the mutex first.

If, by "It helps people avoid accidental...", you mean "at compile time", then it's not always detected in compile time, because the existence of a lock doesn't mean a mutex is locked (e.g. unique_lock). If you mean "at run time", then it can be checked without the lock being passed as a parameter to wait(). Either way, I see no need for passing it.

Peter Dimov wrote:

Yuval Ronen wrote:

...

Peter Dimov wrote:

...

Howard Hinnant wrote:

...

Or should condition::wait() not take any parameters, or take only mutexes, making the issue moot? I think that we ought to keep the lock argument, even if we end up not using it for anything except debug checks. It helps people avoid accidental calls to 'wait' without locking the mutex first. If, by "It helps people avoid accidental...", you mean "at compile time", then it's not always detected in compile time, because the existence of a lock doesn't mean a mutex is locked (e.g. unique_lock).

I meant "helps people avoid accidental mistakes at the time they're writing the code". The function encourages correct use by asking for a lock, implying that the mutex needs to be locked first.

Hinting the user to lock a mutex by accepting a lock is getting too psychological for my taste. If it was enforced by the compiler, then maybe, but since the compiler can't... When it comes to locking, nobody hints anyone to lock a mutex before accessing a shared resource - it's the user responsibility, and we assume he does it. No hinting or hand-holding is required. The last sentence is both a "psychological" argument, and a technical one. The technical being that if before the call to wait(), the user accesses a shared resource (the while condition), and if the user pedantically locks when it comes to shared resources, then the mutex is locked when calling wait(), and there's no need to hint. That said, I know that any "psychological" debate has the potential of never being settled. Too many things depending on "taste". It's even less of an exact science than computer science :)

There was an article by Andrei Alexandrescu somewhere on informit.com where he advocated a similar pattern: the functions that assume that a mutex has been locked should take a lock argument.

Did he take unique_locks into account?

Peter Dimov wrote:

Yuval Ronen:

...

Peter Dimov wrote:

...

...

I meant "helps people avoid accidental mistakes at the time they're writing the code". The function encourages correct use by asking for a lock, implying that the mutex needs to be locked first. Hinting the user to lock a mutex by accepting a lock is getting too psychological for my taste. If it was enforced by the compiler, then maybe, but since the compiler can't...

The hint isn't particularly subtle. You have to pass a lock, and this _is_ enforced by the compiler. The rest of the enforcement (that the lock 'owns' the correct mutex) is necessarily postponed to run time; we simply can't do better than that.

I'm really not sure how you propose to achieve the same level of encouraging and enforcing correct use with a wait function that doesn't take a lock argument,

I'm saying that there's no need to achieve the same level of enforcing. Checking in runtime is enough, IMO. Just as we don't enforce locking before accessing a shared resource (because we can't), there's no need to go over hoops (see my next paragraph) to enforce more than at runtime.

and I'm also unsure what specific problems with requiring a lock argument are you trying to solve.

I find the lock argument cumbersome. In a way it's redundant to passing the mutex, and for no good reason - just for hinting, subtle or no subtle. Where else in C++ a user is hinted in such a way? It's without precedent, and plain weird in my eyes. And if we add to this the fact that it's only a partial compile-time check, then it makes things even weirder. The user, for example, can confuse and think that he is fully covered by the compile-time check, and continue with his guards down, passing it a non-owning unique_lock. If we can't do a complete job, it's better to not do it at all, at least this way our users are forced to be aware of what's happening.

Peter Dimov wrote:

Yuval Ronen:

...

Checking in runtime is enough, IMO.

How do you suggest this runtime checking be implemented?

assert(m_mutex.locked());

Peter Dimov wrote:

Yuval Ronen:

...

Peter Dimov wrote:

...

Yuval Ronen:

...

Checking in runtime is enough, IMO. How do you suggest this runtime checking be implemented? assert(m_mutex.locked());

Well... this implies that a condition is always associated with a mutex

Of course a condition is always associated with a mutex. Except when it doesn't... So let's rewrite that line: assert(m_mutex && m_mutex->locked());

and that the Mutex concept provides a locked() query, which it currently does not.

Then we add such locked() query. And if we have to add a flag and increase sizeof(mutex), I have no problem with it, since it can be ifdefed for debug only. We only need the locked() query in debug.

In principle one may check for a try_lock failure, although this doesn't tell us which thread has locked the mutex.

At least in theory, a lock also doesn't tell us which thread has the mutex.

Given that you already have a lock variable at the point you are calling wait, what's wrong with just passing it?

I may also have a std::vector<int> filled with prime numbers right there, but I don't pass it to wait(). A function should get what it needs, nothing more, nothing less. A lock is, IMO, redundant. Oh, and BTW, I'm not sure I have a lock variable at that point. One possibility is that the wait() is performed not in the function that holds the lock, but form a deeper function (upper the call stack), which don't have access to the lock. Another "principal" argument is that I don't want to force using a lock. We added lock/unlock to mutex, and I think it's a good thing, because we think it's a needed flexibility. The user might even decide to use them... By adding smart pointer to C++, do we remove 'delete'? No. We encourage using smart pointer, but not forcing it.

On Aug 25, 2007, at 2:52 PM, Yuval Ronen wrote:

I find the lock argument cumbersome. In a way it's redundant to passing the mutex, and for no good reason - just for hinting, subtle or no subtle. Where else in C++ a user is hinted in such a way? It's without precedent, and plain weird in my eyes. And if we add to this the fact that it's only a partial compile-time check, then it makes things even weirder. The user, for example, can confuse and think that he is fully covered by the compile-time check, and continue with his guards down, passing it a non-owning unique_lock. If we can't do a complete job, it's better to not do it at all, at least this way our users are forced to be aware of what's happening.

We have to have a wait which takes at the very least a mutex, if not a lock. This is to support the legal "dynamic" binding mutex binding. We could possibly achieve the same functionality through your set_mutex suggestion, but that interface seems error prone to me, as it then takes two calls to wait instead of one: condition<mutex> cv; ... while (true) { Data d = get_data(); unique_lock<mutex> lk = d.get_lock(); d.process(); while (d.not_ready_to_pass_on()) { cv.set_mutex(lk.mutex()); cv.wait(); } stream << d; } as opposed to just: while (d.not_ready_to_pass_on()) cv.wait(lk); One possibility would be to have both wait(lock) and set_mutex(mutex)/ wait(). But this doesn't allow anything that wait(lock) alone allows. -Howard

on Fri Aug 24 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

The above appears to be a reasonable and valid use case to me for "correcting" the condition/mutex binding. The retooling operation is a rare (exceptional) event. Using exceptions for this makes the main processing routine simpler/cleaner as it does not have to deal with the complication of retooling.

In summary, we have valid use cases for both not checking condition/ mutex consistency, and for checking condition/mutex consistency, with both use cases built on "correctness" concerns as opposed to "performance" concerns. Where this leads us next, I'm not yet sure...

This is exactly the sort of use case in which I'd want to have complete control of detecting the need for an exception and throwing it myself. And, as described in http://tinyurl.com/2ph58t, if you rely on the std's checking and exception here you end up with the same exception representing a severe programming error in one part of the program and an expected, recoverable condition in another. At some point up the call stack, you don't know which is which. I would always want a specific "retooling" exception for the non-error case. And, I repeat, when the mutex mismatch *does* represent an error, I *really* don't want a mandated throw. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

Beman Dawes:

Or would you prefer only "condition", but with one or more additional signatures that take an additional argument that says, in effect, "throw rather than assert on mutex mismatch?

Against. "Throw on mutex mismatch" implies that the class needs to be able to detect mutex mismatch with 100% certainty, and this makes it impossible to provide less than perfect checking at close to zero overhead, an important design goal of the "default condition".

On Aug 22, 2007, at 11:55 AM, Howard Hinnant wrote:

Here's checked_condition:

After investigating the use cases for the "unchecked condition", I realized that my earlier checked_condition that I posted here wasn't quite right, at least if you considered it a debug tool. To this end I've rewritten it, and renamed it to condition_debug to emphasize its role. The previous version was allowing default constructed conditions to wait on different mutexes at the same time. This revised condition_debug allows default constructed conditions to only wait on different mutexes at different times. All simultaneous waits must be on the same mutex (even for a default constructed condition). The reason I'm posting it here is that I believe this is a little more complicated, and has a larger sizeof than we first anticipated (if we are to check for error cases on the default constructed condition). In general it adds 3 data members: a mutex, a Mutex*, and an unsigned int. The mutex is for the case that the lock isn't an exclusive lock, but a shared lock. Updating the Mutex* and unsigned int must be protected. There may be a way to do this with atomics, but I haven't figured it out yet. For efficiency purposes, the condition_debug is specialized on exclusive mutex types, which eliminates the need for the external mutex. #include <mutex> #include <condition> #include <type_traits> template <class Mutex> struct is_exclusive : public std::false_type {}; template <> struct is_exclusive<std::mutex> : public std::true_type {}; template <> struct is_exclusive<std::recursive_mutex> : public std::true_type {}; template <> struct is_exclusive<std::timed_mutex> : public std::true_type {}; template <> struct is_exclusive<std::recursive_timed_mutex> : public std::true_type {}; template <class Mutex, bool = is_exclusive<Mutex>::value> class condition_debug { public: typedef Mutex mutex_type; private: std::condition<mutex_type> cv_; std::mutex guard_ckeck_; mutex_type* mut_; unsigned wait_count_; public: condition_debug() : mut_(0), wait_count_(0) {} explicit condition_debug(mutex_type& m) : mut_(&m), wait_count_(1) {} void notify_one() {cv_.notify_one();} void notify_all() {cv_.notify_all();} template <class Lock> void wait(Lock& lock) { precheck(lock); cv_.wait(lock); postcheck(); } template <class Lock, class Predicate> void wait(Lock& lock, Predicate pred) { precheck(lock); cv_.wait(lock, std::move(pred)); postcheck(); } template <class Lock> bool timed_wait(Lock& lock, const std::utc_time& abs_time) { precheck(lock); cv_.timed_wait(lock, abs_time); postcheck(); } template <class Lock, class Predicate> bool timed_wait(Lock& lock, const std::utc_time& abs_time, Predicate pred) { precheck(lock); cv_.timed_wait(lock, abs_time, std::move(pred)); postcheck(); } private: template <class Lock> void precheck(const Lock& lock) { std::scoped_lock<std::mutex> _(guard_ckeck_); if (!lock.owns() || (mut_ != 0 && lock.mutex() != mut_)) throw std::runtime_error("Or whatever error handling policy you want"); ++wait_count_; mut_ = lock.mutex(); } void postcheck() { std::scoped_lock<std::mutex> _(guard_ckeck_); if (--wait_count_ == 0) mut_ = 0; } }; template <class Mutex> class condition_debug<Mutex, true> { public: typedef Mutex mutex_type; private: std::condition<mutex_type> cv_; mutex_type* mut_; unsigned wait_count_; public: condition_debug() : mut_(0), wait_count_(0) {} explicit condition_debug(mutex_type& m) : mut_(&m), wait_count_(1) {} void notify_one() {cv_.notify_one();} void notify_all() {cv_.notify_all();} template <class Lock> void wait(Lock& lock) { precheck(lock); cv_.wait(lock); postcheck(); } template <class Lock, class Predicate> void wait(Lock& lock, Predicate pred) { precheck(lock); cv_.wait(lock, std::move(pred)); postcheck(); } template <class Lock> bool timed_wait(Lock& lock, const std::utc_time& abs_time) { precheck(lock); cv_.timed_wait(lock, abs_time); postcheck(); } template <class Lock, class Predicate> bool timed_wait(Lock& lock, const std::utc_time& abs_time, Predicate pred) { precheck(lock); cv_.timed_wait(lock, abs_time, std::move(pred)); postcheck(); } private: template <class Lock> void precheck(const Lock& lock) { if (!lock.owns() || (mut_ != 0 && lock.mutex() != mut_)) throw std::runtime_error("Or whatever error handling policy you want"); ++wait_count_; mut_ = lock.mutex(); } void postcheck() { if (--wait_count_ == 0) mut_ = 0; } }; -Howard

On Aug 25, 2007, at 11:11 AM, Peter Dimov wrote:

Howard Hinnant:

...

On Aug 22, 2007, at 11:55 AM, Howard Hinnant wrote:

...

Here's checked_condition:

After investigating the use cases for the "unchecked condition", I realized that my earlier checked_condition that I posted here wasn't quite right, at least if you considered it a debug tool. To this end I've rewritten it, and renamed it to condition_debug to emphasize its role. The previous version was allowing default constructed conditions to wait on different mutexes at the same time. This revised condition_debug allows default constructed conditions to only wait on different mutexes at different times. All simultaneous waits must be on the same mutex (even for a default constructed condition).

...

The checks seem too strict. It's valid to notify_all and then rebind the condition to a different mutex, but your condition_debug will likely assert/throw as the awakened threads have not yet executed their postchecks. (Unless I'm overlooking something.)

It's quite likely that only the implementor of pthread_cond_t may catch all errors in the general case. This does not diminish the utility of a checked condition that catches most errors in the typical case IMO.

You're right. A (fully) debugging condition is at best extremely difficult to implement. That's probably why POSIX made this behavior undefined instead of specifying an error code return: http://www.unix.org/single_unix_specification/

When a thread waits on a condition variable, having specified a particular mutex to either the pthread_cond_timedwait() or the pthread_cond_wait() operation, a dynamic binding is formed between that mutex and condition variable that remains in effect as long as at least one thread is blocked on the condition variable. During this time, the effect of an attempt by any thread to wait on that condition variable using a different mutex is undefined. Once all waiting threads have been unblocked (as by the pthread_cond_broadcast() operation), the next wait operation on that condition variable shall form a new dynamic binding with the mutex specified by that wait operation. Even though the dynamic binding between condition variable and mutex may be removed or replaced between the time a thread is unblocked from a wait on the condition variable and the time that it returns to the caller or begins cancellation cleanup, the unblocked thread shall always re-acquire the mutex specified in the condition wait operation call from which it is returning.

I'm currently thinking that we should drop the condition(Mutex&) constructor from condition: template <class Mutex> class condition { public: typedef Mutex mutex_type; condition(); ~condition(); condition(const condition&) = delete; condition& operator=(const condition&) = delete; void notify_one(); void notify_all(); template <class Lock> void wait(Lock& lock); // If ! lock.owns(), condition_error thrown template <class Lock, class Predicate> void wait(Lock& lock, Predicate pred); // If ! lock.owns(), condition_error thrown template <class Lock> // If ! lock.owns(), condition_error thrown bool timed_wait(Lock& lock, const utc_time& abs_time); template <class Lock, class Predicate> // If ! lock.owns(), condition_error thrown bool timed_wait(Lock& lock, const utc_time& abs_time, Predicate pred); }; Adding the condition(Mutex&) constructor which does nothing but specify undefined behavior provides no benefit, and quite possibly adds cost to valid use cases of condition which use the default constructor instead. * The condition(Mutex&) constructor would not provide any guarantee of safety. * If an implementation did provide the error check, clients who had valid use cases using the default constructor would pay for the error checking even though they did not need or want it. * A fully precise debugging condition appears difficult and/or expensive. (worst of both worlds) The above being said, it is easy to add a "constrained condition" with a variety of syntaxes and semantics. A "constrained condition" would be one where the dynamic binding between the condition and the mutex is set at construction time, and can not be altered throughout the lifetime of the condition. The chief motivation for the constrained condition is that the majority of use cases fit into the "constrained use" pattern. I've shown a use case where the violation of this binding is a correctable run time event, thus making an exception appropriate. It might be appropriate to disallow default construction of a constrained condition. I can imagine several different syntaxes for a constrained condition: condition<constrain<Mutex>> cv(mut); constrain_condition<Mutex> cv(mut); constrain::condition<Mutex> cv(mut); All of the above syntaxes could be achieved either by the std::lib, or by the client. Here is an example implementation of the first syntax. It is fairly easy to write, and as far as I know, has no subtleties. template <class Mutex> struct constrain {}; template <class Mutex> class condition<constrain<Mutex>> { public: typedef Mutex mutex_type; private: condition<mutex_type> cv_; mutex_type& ext_mut_; public: explicit condition(mutex_type& mut) : ext_mut_(mut) {} void notify_one() {cv_.notify_one();} void notify_all() {cv_.notify_all();} template <class Lock> void wait(Lock& lock) { check(lock); cv_.wait(lock); } template <class Lock, class Predicate> void wait(Lock& lock, Predicate pred) { check(lock); cv_.wait(lock, std::move(pred)); } template <class Lock> bool timed_wait(Lock& lock, const utc_time& abs_time) { check(lock); cv_.timed_wait(lock, abs_time); } template <class Lock, class Predicate> bool timed_wait(Lock& lock, const utc_time& abs_time, Predicate pred) { check(lock); cv_.timed_wait(lock, abs_time, std::move(pred)); } private: template <class Lock> void check(const Lock& lock); }; template <class Mutex> template <class Lock> void condition<constrain<Mutex>>::check(const Lock& lock) { if (lock.mutex() != &ext_mut_) throw condition_error(); } The reason to make the constrained condition a different type from the unconstrained condition is because the two have different semantics. And there exist valid use cases for both semantics. -Howard

On Aug 25, 2007, at 1:12 PM, Peter Dimov wrote:

Howard Hinnant:

...

Adding the condition(Mutex&) constructor which does nothing but specify undefined behavior provides no benefit, and quite possibly adds cost to valid use cases of condition which use the default constructor instead.

I disagree with both statements, even when taken individually. Together, they obviously contradict one another.

The mutex constructor MAY provide no benefit (except portability and the potential to do a designated checked build) if the implementation chooses to ignore it, in which case there is no cost. I would expect this to be the case on embedded or realtime platforms.

The mutex constructor MAY add cost to the constructor that takes no mutex, in which case it does provide benefit since the cost presumably comes from the checking logic.

It MAY even provide benefit at a cost that is acceptable to the target audience. See "checked release" and vary the number 17041 according to taste.

In contrast, if you make it impossible for the user to explicitly associate a mutex with the condition, the implementation MAY NOT check, even if it can somehow do that for free (it knows about an unused void* in the pthread_cond_t, for example).

What would you recommend for back porting your proposal into boost? A boost debug build? Or to always include the check? And why? Also note that I specifically showed that no matter what we do, we can not make it impossible for the user to explicitly associate a mutex with the condition: On Aug 25, 2007, at 11:53 AM, Howard Hinnant wrote:

The above being said, it is easy to add a "constrained condition" with a variety of syntaxes and semantics. ... condition<constrain<Mutex>> cv(mut); constrain_condition<Mutex> cv(mut); constrain::condition<Mutex> cv(mut);

All of the above syntaxes could be achieved either by the std::lib, or by the client.

For the client who has a use case where they want a constrained condition, and want to correct any mis-bindings at run time, what do you recommend for them? What do you tell the client who wants to regularly change the mutex/ condition binding, and whose design makes it impossible for there to be a mis-binding (because there's only one waiting thread)? Would the boost version of your proposal be best for them? -Howard

On Aug 25, 2007, at 2:11 PM, Peter Dimov wrote:

I'll wait for this hypothetical client to appear.

So if we were targeting boost, or even TR2, we would have this luxury. We're not and we don't. We need to get it right the first time. Failing strong consensus of what is "right", we're going to get the current boost::condition. I'm not even positive how to interpret the spec for boost::condition: either mutex-only, or generalized, but definitely not both since it isn't templated.

To try to provide a summary: we have three conditions on the table: (1) unchecked, (2) possibly checked, and (3) checked. Your original design has (3) as default, (1) when the mutex argument is wrapped by unchecked<>. The direction you now seem to be exploring is (1) by default, (3) as an option, which I regard as a regression. I suggest (2) by default, with (3) as an option, but only if there proves to be demand.

Nice summary. I'm very opposed to (2). It says: Here's a constructor and the only difference between it and the other constructor (or other form of the same constructor) is that it adds a bunch of undefined behavior. That just can't be a good thing to put into a standard.

Regardless of what is chosen, I maintain that the three conditions must syntactically have the same interface, that is, it must be possible to pass a mutex even to (1). It would be painful to switch between them if they do not.

I've actually been doing this switching a lot recently in my prototype and associated test code. It isn't that painful. But I agree it would be nice to not have to do it at all. If we only manage to standardize (1), then justifying a constructor that looks different but has no difference in behavior is hard to justify. If we manage to standardize both (1) and (3), then it becomes much easier to justify such a constructor. I'm strictly looking at this from the client's point of view. I'm the client. I know what I want, and I want to be able to pick something and know what it does. I don't want to be stuck with something that maybe does something, and maybe not. It's like buying something with absolutely no warranty. -Howard

On Aug 25, 2007, at 3:10 PM, Peter Dimov wrote:

Howard Hinnant:

...

I'm strictly looking at this from the client's point of view. I'm the client. I know what I want, and I want to be able to pick something and know what it does. I don't want to be stuck with something that maybe does something, and maybe not. It's like buying something with absolutely no warranty.

No, I don't agree. This is like saying that if the car you bought promises 40 MPG and delivers 45, you'd return it because it doesn't meet the spec.

Bad analogies aside, giving the implementation the opportunity to check the assumptions of your code is not as worthless as you make it to be. It does not just "add a bunch of undefined behavior", it adds a license for the implementation to turn the already erratic behavior into a predictable assertion failure.

If the client has used the mutex constructor, this means that his code has already made the assumption that the condition will be used with that mutex. If you take away the Requires clause (the "bunch of undefined behavior"), this will not make the code any more correct and can never be an improvement; it would be, at worst, a tie if the implementation did no checking.

The main philosophical difference between us is that I want to be able to choose "check", and be assured that I'm actually getting checking. And then I want to be able to choose "don't check". And then not have to pay for it. I want both choices. What I want: std::condition<std::constrain<std::mutex>> cv(mut); // I *know* that if I mix bindings, I will get some kind of noise And then I want to be able to change that code: // I *know* that I'm not paying for checking std::condition<std::mutex> cv(mut); // Either with or without the "mut", I don't care With your proposal I write: std::condition<std::mutex>> cv(mut); and I don't know whether I have checking or not. All I know is that I've given permission for the implementation to check. And if I write: std::condition<std::mutex>> cv; Then I don't know that I'm not still paying for checking. I want your (1) and (3). Your (2) gives me neither, not both. -Howard

On Aug 25, 2007, at 4:54 PM, Peter Dimov wrote:

Howard Hinnant:

...

The main philosophical difference between us is that I want to be able to choose "check", and be assured that I'm actually getting checking. And then I want to be able to choose "don't check". And then not have to pay for it. I want both choices.

The main philosophical difference between us is that you want the specification to guarantee you that, instead of merely allowing the implementor to give you that.

Guaranteed checks on a specification level are only possible if you demand an exception. Guaranteed non-paying is, in your view, only possible if you don't give the adversary the mutex pointer, lest he subvert your intent and increase sizeof(condition) to store it.

Well put. The use of adversary is a bit dramatic, but I must admit to having a good chuckle over it (and thanks!). :-) I also note that I've supplied a reasonable use case for correcting the exceptional condition at run time (giving justification that program termination is too strong of a reaction for all use cases).

As an academic debate solely concerned with this specific class, this can go on. You can cite list::size as evidence that the implementors cannot be trusted to do the right thing, and I can respond with a list of bullet points of why this doesn't apply to our case. You will note that MSVC8 does runtime checks in release builds, and I will counter that while these can show up on the profiler if one is careless, they have helped me find bugs in code and it's possible to eliminate them from the performance-critical regions, so I consider them non-evil.

Just to be clear, I'm extremely well positioned to know that vendors are not evil, and are not adversaries. They are people, just like you and me. And when the standard gives them choices, they must make them. They try to make them in such a way as to please most of their customers. Sometimes they choose correctly, and sometimes they do not (as a vendor I admit to having chosen incorrectly sometimes). No vendor that I'm aware of is immune to making incorrect choices.

In practice, however, sizeof(string), vector, map, list will have much more of an impact on my code than sizeof(condition), for the simple reasons that they (a) occur much more frequently and (b) don't involve blocking kernel calls that can shadow thousands of L1 cache misses. If the implementor doesn't care about the size of the stdlib classes, condition will be the least of my worries.

The above is a valid forward looking statement. But I stress "forward looking". To date: * We have no std::condition to take the sizeof. * The sizeof(boost::condition) == sizeof(pthread_cond_t). * We anticipate a massive explosion in the growth of multithreading code in the next decade, due to an anticipated explosion in the number of cores per processor. And the motivation for that multithreading code explosion is to extract further *performance*, not further functionality out of the hardware. I don't know any more than you do, so my "forward looking" is no more or less valid than yours. But I strongly believe that it would be careless of us to be careless with sizeof(std::condition). -Howard

On Aug 25, 2007, at 6:24 PM, Peter Dimov wrote:

Howard Hinnant:

...

They are people, just like you and me. And when the standard gives them choices, they must make them. They try to make them in such a way as to please most of their customers. Sometimes they choose correctly, and sometimes they do not (as a vendor I admit to having chosen incorrectly sometimes). No vendor that I'm aware of is immune to making incorrect choices.

I accept that. So what's the problem? Vendor A ignores the mutex argument, his users complain, so he finds a way to add checking that doesn't increase sizeof(condition) and doesn't compromise performance for the rest of the user base. Vendor B stores the mutex pointer in std::condition, his users complain, he waits for the next ABI breakage and finds a way to achieve comparable checking quality and efficiency without increasing sizeof(condition). Everyone is happy.

...

...

I don't know any more than you do, so my "forward looking" is no more or less valid than yours. But I strongly believe that it would be careless of us to be careless with sizeof(std::condition).

I'm not being careless with sizeof(condition). I already demonstrated two ways to achieve checking without storing the pointer into the condition itself, and hinted at another possibility (exploiting an unused void* in pthread_cond_t). I also questioned your assertion that increasing sizeof(condition) from 28 to 32 is of practical importance.

I've been using "sizeof(condition)" as shorthand for "reducing L1 cache misses". Your technique of moving the checking to a static map (or unordered_map)<void*, void*> does indeed reduce the sizeof(condition), but does not reduce L1 cache misses. It is simply moving the checking data from one place to another. The checking data still has to be written and read, even when a non-checking condition is desired. My estimation is that your "external checking data storage" plan is less efficient, not more efficient, than just storing the checking data internal to the condition. Though admittedly that is just an estimate. I haven't measured. At this point I'm really leaning towards getting back to basics: class condition { public: condition(); ~condition(); condition(const condition&) = delete; condition& operator=(const condition&) = delete; void notify_one(); void notify_all(); template <class Lock> void wait(Lock& lock); // Lock::mutex_type must be mutex template <class Lock, class Predicate> void wait(Lock& lock, Predicate pred); // Lock::mutex_type must be mutex template <class Lock> // Lock::mutex_type must be mutex bool timed_wait(Lock& lock, const utc_time& abs_time); template <class Lock, class Predicate> // Lock::mutex_type must be mutex bool timed_wait(Lock& lock, const utc_time& abs_time, Predicate pred); }; Or perhaps even: class condition { public: condition(); ~condition(); condition(const condition&) = delete; condition& operator=(const condition&) = delete; void notify_one(); void notify_all(); void wait(unique_lock<mutex>& lock); template <class Predicate> void wait(unique_lock<mutex>& lock, Predicate pred); bool timed_wait(unique_lock<mutex>& lock, const utc_time& abs_time); template <class Predicate> bool timed_wait(unique_lock<mutex>& lock, const utc_time& abs_time, Predicate pred); }; Or perhaps: class condition { public: condition(); ~condition(); condition(const condition&) = delete; condition& operator=(const condition&) = delete; void notify_one(); void notify_all(); void wait(mutex& mut); template <class Predicate> void wait(mutex& mut, Predicate pred); bool timed_wait(mutex& mut, const utc_time& abs_time); template <class Predicate> bool timed_wait(mutex& mut, const utc_time& abs_time, Predicate pred); }; The above is small, relatively simple, and everything else we've discussed can be built on top of it (some parts more easily than others). The above is the one part of the entire original proposal that is indispensable (goal #1). The above is a one-to-one mapping to pthread_cond_t/pthread_mutex_t. We might use the diagnostic library to return error codes or throw system_error for any non-zero returns from pthread_cond_*, perhaps with overloads to specify which error reporting style the user wants to have. class condition { public: condition(); ~condition(); condition(const condition&) = delete; condition& operator=(const condition&) = delete; void notify_one(); void notify_one(error_code&); void notify_all(); void notify_all(error_code&); void wait(mutex& mut); void wait(mutex& mut, error_code&); template <class Predicate> void wait(mutex& mut, Predicate pred); template <class Predicate> void wait(mutex& mut, Predicate pred, error_code&); bool timed_wait(mutex& mut, const utc_time& abs_time); bool timed_wait(mutex& mut, const utc_time& abs_time, error_code&); template <class Predicate> bool timed_wait(mutex& mut, const utc_time& abs_time, Predicate pred); template <class Predicate> bool timed_wait(mutex& mut, const utc_time& abs_time, Predicate pred, error_code&); }; -Howard

On Aug 26, 2007, at 4:49 PM, Peter Dimov wrote:

Howard Hinnant:

...

I've been using "sizeof(condition)" as shorthand for "reducing L1 cache misses". Your technique of moving the checking to a static map (or unordered_map)<void*, void*> does indeed reduce the sizeof(condition), but does not reduce L1 cache misses.

map<> is the "debug" variation, there's also a "checked release" one. They do reduce the L1 cache misses on the only path where these misses can be measured, the path that does not call wait. Once you call wait, you enter a blocking kernel call and L1 misses cease to be of importance.

My knowledge is not what it should be in this area. If there are two threads sharing a processor, and one thread is accessing M1 amount of memory and the other thread is accessing M2 amount of memory, and M1 + M2 is less than the L1 cache size, isn't that faster than if both M1 and M2 are less than the L1 cache size but M1 + M2 is larger than the L1 cache size? I.e. can larger memory use (or more scattered memory use) on one thread make cache misses more likely on another thread? -Howard

Howard Hinnant wrote:

At this point I'm really leaning towards getting back to basics:

<snip options for class condition> It seems I wasn't very successful in convincing, so I'll try one last time. I strongly recommend you seriously consider template <class Mutex> class condition { condition(); explicit condition(Mutex &); // or Mutex* void set_mutex(Mutex &); // or Mutex* void wait(); // more wait() overloads with predicate and timeout // and of course the notify functions }; I'll repeat the advantages I see for this approach: 1. It can work for any user-defined mutex. 2. Yet it can be specialized for better sizeof for std::mutex. 3. It can be made to check for errors (not assigning a mutex or not locking the mutex) when calling wait(). 4. Yet it can be made to be as-fast-as-possible. 5. It can dynamically switch the mutex which the condition works for (for the rare cases when it is needed). 6. It allows easily using the condition in a deeper function than the one that locked the mutex. 7. It doesn't force using locks (which I see as a plus, because there's a reason we brought mutex back his lock/unlock). 8. It doesn't introduce an unprecedented technique of "encouraging" users to lock (by passing a lock to a function). A technique which I find to be cumbersome and misleading (because it works only partially). Unfortunately I have to leave in an hour for two weeks, so I'm out of this discussion for now, but please don't dismiss this idea without careful thought. Yuval

on Sat Aug 25 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

The main philosophical difference between us is that I want to be able to choose "check", and be assured that I'm actually getting checking. And then I want to be able to choose "don't check". And then not have to pay for it. I want both choices.

I think everyone honors your desire to have these choices. I'm just not sure it's the /standard's/ job to give them to you. 1. Aside from vector<T>::at (which IMO was a mistake), there is no precedent for this in the standard. We don't know that such a choice will serve people well. 2. As Peter already pointed out, if we mandate a check in the standard, the result of a failed check must be an exception (or the behavior of a failed assert, which I think is to abort). Neither of these behaviors is -- in and of itself -- useful in debugging (at best, you rely on your vendor to make it useful). 3. I'll say again: turning a logic error into an exception is a bad idea (http://tinyurl.com/2ph58t) and we have no programming model for handling it. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

Howard Hinnant:

On Aug 21, 2007, at 5:14 PM, Peter Dimov wrote:

...

void __cndcheck_init( void * pc, void * pm ) { __cndcheck_state[ (size_t)pc % 17041 ] = { pc, pm }; // atomic store }

So what do you do about collisions?

Nothing; if there's a collision, I miss the opportunity to check. The "permissive" spec allows me to do that. If I had to throw on mutex mismatch, this implementation would be non-conforming. I can tune the magic number 17041 to strike the best ratio of accuracy vs space, and I can vary it slightly on each run to redistribute the collisions.

Howard Hinnant:

Don't we have false positives now?

No. __cndcheck_wait tests for pc_ == pc and skips the check if they don't match.

Howard Hinnant wrote:

On Aug 21, 2007, at 3:22 PM, Yuval Ronen wrote:

...

Howard Hinnant wrote:

...

On Aug 21, 2007, at 8:46 AM, Yuval Ronen wrote:

...

1. I couldn't understand what defer_lock is good for, even after reading Q.9 of the FAQ. I believe the use-case shown in Q.9 should actually use accept_ownership instead. Can you elaborate please? See if this is any clearer:

http://home.twcny.rr.com/hinnant/cpp_extensions/concurrency_rationale.html#u... I'm afraid not...

This example has 3 lines, the first 2 create unique_lock with defer_lock, and the 3rd calls std::lock. Those unique_lock don't lock, because std::lock to lock. OK. But who unlocks? The unique_locks don't own the mutexes, and therefore don't unlock them. But someone needs to unlock, and it sounds logical that the unique_locks would... Had we used accept_ownership, the unique_locks would have owned the mutexes, and unlock them. That's the difference between defer_lock and accept_ownership, the ownership, isn't it?

Ok, the lightbulb went off in my head and I think I understand your question now. Thanks for not giving up on me.

I've tried again here:

http://home.twcny.rr.com/hinnant/cpp_extensions/concurrency_rationale.html#u...

and see the next question (#10) as well. If that doesn't do it, see:

http://home.twcny.rr.com/hinnant/cpp_extensions/mutex_base

and search for "defer_lock_type" and "accept_ownership_type" for the unique_lock implementation of these constructors. Neither constructor does anything to the mutex, and simply sets the owns() flag to false or true respectively. The unique_lock destructor will unlock the mutex iff it owns()'s the mutex.

Not yet... :) One of the added sentences is "After std::lock locks l1 and l2, these locks now own their respective mutexes". How does that happen? I looked at the implementation code, but could see nothing that changes owns() from false to true after construction. Have I missed it? Another related question is why std::lock works with locks and not mutexes? Can't see the benefit in that.

...

...

...

Either way, I believe this design wouldn't meet the use case which I didn't effectively communicate in #14:

Given a read-write mutex and its associated condition variable:

my::shared_mutex rw_mut; std::condition<my::shared_mutex> cv(rw_mut);

client code wants to wait on that cv in two different ways:

1. With rw_mut read-locked. 2. With rw_mut write-locked.

If we initialized the condition variable with cv(rw_mut.exclusive()), then cv.wait() would wait with rw_mut write-locked, but we wouldn't be able to wait on cv with rw_mut read-locked.

If we initialized the condition variable with cv(rw_mut.shared()), then cv.wait() would wait with rw_mut read-locked, but we wouldn't be able to wait on cv with rw_mut write-locked.

This use case desires *both* types of waits on the *same* mutex/cv pair. The last sentence starts with "This use case", but I see no use case. Do we really have such a use case? I haven't seen one yet. But even if we had, then maybe the solution is the same solution to the requirement you phrased as "The freedom to dynamically associate mutexes with condition variables" or "The ability to wait on general mutex / lock types" (what's the difference between those two sentences anyway?) in your response to Peter. Add a 'set_mutex(mutex_type &)', or maybe even 'set_mutex(mutex_type *)' to std::condition. I think it will solve this rare case.

Ok, perhaps I'll clean the following use case up, and include it in the faq. First I'll try it out here. :-)

I've got a "communication node" class. It serves as a node in a network. It gets data from somewhere and temporarily stores it while it uses several threads to forward (or relay) the information to other nodes in the network. For simplicity I'm using vector<int> for the data, and only two relay threads. The example is incomplete (not even compiled), just illustrative right now:

class communication_node { std::vector<int>* from_; std::vector<int> data_; std::vector<int> to_[2];

typedef std::tr2::shared_mutex Mutex; Mutex mut_; std::condition<Mutex> cv_; bool get_data_; bool fresh_data_; bool data_relayed_[2]; public: void supplier() { while (true) { std::unique_lock<Mutex> write_lock(mut_); while (!get_data_ || !data_relayed_[0] || ! data_relayed_[1]) cv_.wait(write_lock); std::copy(from_->begin(), from_->end(), data_.begin()); get_data_ = false; fresh_data_ = true; data_relayed_[0] = false; data_relayed_[1] = false; cv_.notify_all(); } } void relayer(int id) { while (true) { std::tr2::shared_lock<Mutex> read_lock(mut_); while (data_relayed_[id]) cv_.wait(read_lock); std::copy(data_.begin(), data_.end(), to[id].begin()); data_relayed_[id] = true; cv_.notify_all(); } } };

The relayer, which supposed to be a reader, actually is a writer, to data_relayed_[id], so I believe a read_lock is not enough...

Because of this, it is not possible (in the above use case) for there to be a set_mutex on the condition to change the facade, since both facades are simultaneously in use.

Yes, I've realized that too late. My set_mutex() function is useless because it has to be atomic with the wait().

Did I make more sense this time? I often complain when people use too much English and not enough C++ in their arguments, and then I find myself being guilty of the same thing. :-)

You keep on improving. I hope we all are ;-)

Howard Hinnant wrote:

On Aug 21, 2007, at 6:02 PM, Yuval Ronen wrote:

...

One of the added sentences is "After std::lock locks l1 and l2, these locks now own their respective mutexes". How does that happen? I looked at the implementation code, but could see nothing that changes owns() from false to true after construction. Have I missed it?

I think so, but it is rather subtle. Re-quoting std::lock (the two- lock version) here:

template <class _L1, class _L2> void lock(_L1& __l1, _L2& __l2) { while (true) { { unique_lock<_L1> __u1(__l1); if (__l2.try_lock()) { __u1.release(); break; } } std::this_thread::yield(); { unique_lock<_L2> __u2(__l2); if (__l1.try_lock()) { __u2.release(); break; } } std::this_thread::yield(); } }

And I'm going to answer your second question below before continuing:

...

Another related question is why std::lock works with locks and not mutexes? Can't see the benefit in that.

You're absolutely right. This is my fault due to lack of proper documentation at the moment. All that is required of _L1 and _L2 in the above algorithm is that they support:

void lock(); bool try_lock(); void unlock();

It will work for _L1 being a lock or mutex (and same for _L2).

Ok, now back to how std::lock works:

This line:

unique_lock<_L1> __u1(__l1);

implicitly calls __.l1.lock() inside of the unique_lock constructor. If __l1 is a mutex, the deed is done. If __l1 is a lock, hopefully that will forward to the referenced mutex's lock() function in the proper manner. And in the process, that should set the lock's owns() data to true as well.

template <class _Mutex> void unique_lock<_Mutex>::lock() { if (__m == 0 || __owns) throw lock_error(); __m->lock(); __owns = true; // owns() set here!!! }

Similarly for:

if (__l2.try_lock())

OK, I finally see how it works. I completely missed the part that std::lock can work both for mutexes and for locks. However...

This algorithm (the std::lock) is actually my cornerstone of "why I like uncoupled - non-nested - lock types". The local unique_lock is applied to any mutex, or any lock, even another unique_lock, transparently. It just does its job without caring what type of mutex or lock it needs to temporarily hold on to. unique_lock is very, very analogous to unique_ptr (formerly auto_ptr). One holds lock/mutex ownership state, the other holds heap allocated memory. Both are resource holders. Both have virtually the same responsibilities and design. Their names are purposefully similar.

... I don't agree with why this is needed. I don't see any reason why any algorithm would work both for mutexes and locks. Just as you won't write an algorithm that works both for unique_ptrs and the objects they point to. They are different things. All this complexity is simply unnecessary, IMO. You can drop the lock/try_lock/unlock functions from the locks, keep them for mutexes, and declare that std::lock/scoped_lock/unique_lock work only for mutexes. You can then drop defer_lock also, and everything is much simpler...

...

...

Ok, perhaps I'll clean the following use case up, and include it in the faq. First I'll try it out here. :-)

I've got a "communication node" class. It serves as a node in a network. It gets data from somewhere and temporarily stores it while it uses several threads to forward (or relay) the information to other nodes in the network. For simplicity I'm using vector<int> for the data, and only two relay threads. The example is incomplete (not even compiled), just illustrative right now:

class communication_node { std::vector<int>* from_; std::vector<int> data_; std::vector<int> to_[2];

typedef std::tr2::shared_mutex Mutex; Mutex mut_; std::condition<Mutex> cv_; bool get_data_; bool fresh_data_; bool data_relayed_[2]; public: void supplier() { while (true) { std::unique_lock<Mutex> write_lock(mut_); while (!get_data_ || !data_relayed_[0] || ! data_relayed_[1]) cv_.wait(write_lock); std::copy(from_->begin(), from_->end(), data_.begin()); get_data_ = false; fresh_data_ = true; data_relayed_[0] = false; data_relayed_[1] = false; cv_.notify_all(); } } void relayer(int id) { while (true) { std::tr2::shared_lock<Mutex> read_lock(mut_); while (data_relayed_[id]) cv_.wait(read_lock); std::copy(data_.begin(), data_.end(), to[id].begin()); data_relayed_[id] = true; cv_.notify_all(); } } }; The relayer, which supposed to be a reader, actually is a writer, to data_relayed_[id], so I believe a read_lock is not enough...

I should have made to_:

std::vector<int>* to_[2];

Now I lost you. I was talking about 'data_relayed_', not 'to_'. Or maybe you did answer to the point and I failed to understand? Certainly possible.

I.e. a vector to a pointer to data outside the node. And now that I think more about it, the relayer thread is the "missing supplier" thread not demonstrated above, but for the next node downstream. It only needs read access to this node, but it will need write access to a downstream node. The example definitely needs more work.

AFAICU this example, the main point is that the relayer thread needs write access, at least to the flag that means "dear supplier thread, I'm ready for whatever you have for me, bring it on". That same flag that the supplier checks with the call to wait() - someone needs to set it, right? And that someone is the relayer, because I don't see anyone else around... OK, it's time for me to go to sleep. See ya tomorrow :)

Howard Hinnant wrote:

On Aug 21, 2007, at 7:34 PM, Yuval Ronen wrote:

...

All this complexity is simply unnecessary, IMO. You can drop the lock/try_lock/unlock functions from the locks, keep them for mutexes, and declare that std::lock/scoped_lock/unique_lock work only for mutexes. You can then drop defer_lock also, and everything is much simpler...

Consider a use case where the mutex, but not the lock has been encapsulated away, and you want to unlock the lock prior to its destruction:

typedef std::mutex Mutex;

Mutex& get_mutex() { static Mutex mut; return mut; }

typedef std::unique_lock<Mutex> Lock;

Lock get_lock() { return Lock(get_mutex()); }

typedef std::condition<Mutex> Condition;

Condition& get_condition() { static Condition cv(get_mutex()); return cv; }

void foo() { Lock lk = get_lock(); change_data(); if (some_flag) { lk.unlock(); // <--------- here get_condition().notify_all(); } }

Instead of lk.unlock(), we can write lk.get_mutex().unlock(), for example. Another option is to say that encapsulating away the mutex is not a valid use case. Remove the get_lock() function and write: void foo() { Mutex &m = get_mutex(); Lock lk(m); change_data(); if (some_flag) { m.unlock(); get_condition().notify_all(); } } I don't see any benefit in encapsulating the mutex. Just like unique_ptr<T> doesn't encapsulate the T.

Question 10 shows a motivating use case for defer_lock that does not involve the member lock/unlock functions on locks.

It does involve them, even though not directly. If we remove lock/unlock, then there is no reason for unique_lock to have a 'bool owns' data member. The ownership is detemined by null-ness of the 'mutex_type* m' data member. And now the second return statement in Q.10 (the 'else' part) can be replace with 'return std::unique_lock<std::mutex>()'. No need for defer_lock.

on Tue Aug 21 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

This line:

unique_lock<_L1> __u1(__l1);

implicitly calls __.l1.lock() inside of the unique_lock constructor. If __l1 is a mutex, the deed is done. If __l1 is a lock, hopefully that will forward to the referenced mutex's lock() function in the proper manner. And in the process, that should set the lock's owns() data to true as well.

That's part of what I found counfounding about the name "unique_." Now you have two locks (__l1 and __u1) that "own" the mutex. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com The Astoria Seminar ==> http://www.astoriaseminar.com

On Aug 22, 2007, at 8:05 AM, Yuval Ronen wrote:

Yuval Ronen wrote:

...

Howard Hinnant wrote:

...

Because of this, it is not possible (in the above use case) for there to be a set_mutex on the condition to change the facade, since both facades are simultaneously in use.

Yes, I've realized that too late. My set_mutex() function is useless because it has to be atomic with the wait().

I've just thought that it might be not so useless after all. 'set_mutex' is supposed to be called after the mutex was locked, and before calling condition::wait. Because the mutex is locked, we are protected against simultaneous use. There can be a problem when multiple readers lock for read, and simultaneously call set_mutex, but if we assume they all set the same mutex it shouldn't be a problem.

How would wake from wait be handled? I.e. what mutex (facade) would it use to lock with? The last one set may not correspond to the proper one on wake. -Howard

On Aug 22, 2007, at 11:22 AM, Yuval Ronen wrote:

Howard Hinnant wrote:

...

On Aug 22, 2007, at 8:05 AM, Yuval Ronen wrote:

...

...

Howard Hinnant wrote:

...

Because of this, it is not possible (in the above use case) for there to be a set_mutex on the condition to change the facade, since both facades are simultaneously in use. Yes, I've realized that too late. My set_mutex() function is useless because it has to be atomic with the wait(). I've just thought that it might be not so useless after all. 'set_mutex' is supposed to be called after the mutex was locked, and before calling condition::wait. Because the mutex is locked, we are protected against simultaneous use. There can be a problem when multiple readers lock for read, and simultaneously call set_mutex, but if we assume they all set

Yuval Ronen wrote: the same mutex it shouldn't be a problem.

How would wake from wait be handled? I.e. what mutex (facade) would it use to lock with? The last one set may not correspond to the proper one on wake.

It would lock the same mutex it unlocked upon entering wait().

Could you prototype or sketch this out? Sorry, I'm not following. -Howard

On Aug 22, 2007, at 1:07 PM, Yuval Ronen wrote:

Howard Hinnant wrote:

...

On Aug 22, 2007, at 11:22 AM, Yuval Ronen wrote:

...

Howard Hinnant wrote:

...

On Aug 22, 2007, at 8:05 AM, Yuval Ronen wrote:

...

...

Howard Hinnant wrote:

> Because of this, it is > not possible (in the above use case) for there to be a set_mutex > on > the condition to change the facade, since both facades are > simultaneously in use. Yes, I've realized that too late. My set_mutex() function is useless because it has to be atomic with the wait(). I've just thought that it might be not so useless after all. 'set_mutex' is supposed to be called after the mutex was locked, and before calling condition::wait. Because the mutex is locked, we are protected against simultaneous use. There can be a problem when multiple readers lock for read, and simultaneously call set_mutex, but if we assume they all set

Yuval Ronen wrote: the same mutex it shouldn't be a problem. How would wake from wait be handled? I.e. what mutex (facade) would it use to lock with? The last one set may not correspond to the proper one on wake. It would lock the same mutex it unlocked upon entering wait().

Could you prototype or sketch this out? Sorry, I'm not following.

Perhaps some code will help me clarify my ideas (taking your advice :) ):

template <class Mutex> class condition { typedef Mutes mutex_type; mutex_type *m_mutex;

public: condition() : m_mutex(NULL) { } explicit condition(mutex_type &a_mutex) : m_mutex(&a_mutex) { }

void set_mutex(mutex_type &a_mutex) { m_mutex = &a_mutex; }

void wait() { assert(m_mutex); // overhead only in debug builds do_wait(*m_mutex); } };

Of course that's a very partial implementation, but I hope it's enough to convey my intent.

It is the do_wait function that I didn't know how to implement. But maybe something like: do_wait(mutex_type& m) { internal_mutex.lock(); mutex_type* local_m = &m; m.unlock(); sleep on internal_mutex; internal_mutex.unlock(); local_m->lock(); } The local_m is used in case someone calls set_mutex with another facade while we're sleeping. I think that will work, but of course haven't tested it. Now looking at the client side: shared_mutex mut; condition<shared_mutex> cv; void foo() { scoped_lock<shared_mutex> _(mut.exclusive()); while (cant_write()) { cv.set_mutex(mut.exclusive()) cv.wait(); } // now safe to write to protected data } Does that look about right for what you are suggesting? I guess the facades are member data in the shared_mutex? If not, who manages their storage? I at first put the call to set_mutex outside the while-statement, but then realized that doesn't work. Someone else could set_mutex while you're sleeping, then you get a spurious wakeup, then you sleep with the wrong facade on the next iteration. So you have to use the set_mutex directly before the call to wait(). -Howard

Howard Hinnant wrote:

On Aug 21, 2007, at 3:06 PM, Roland Schwarz wrote:

...

What does public lock unlock provide, that cannot be achieved with moveable locks also?

[...}

Alternatively you may want to write your own mutexes, and have them work with the std::supplied locks. This can't be done with the boost design, because there is no standard interface for your mutex to implement.

A practical example: Boost.Interprocess mutexes. I had to reimplement all the locks (following your the proposed interface) because scoped lock has no public requirements on what a mutex should provide. Locks were also tightly coupled with boost::condition via friendship. If generic algorithms are provided, we can safely use them with Boost.Interprocess mutexes and locks. I could also reuse standard locks with process-shared mutexes if a user prefers them or programs generic algorithms templatized on the mutex type. Process-shared condition variables would be a different beast. We'll need to define a new condition variable type (I'm afraid that specialization is not enough, because this pshared_condition should also work with arbitrary mutex types). Regards, Ion

On Aug 21, 2007, at 4:41 PM, Zach Laine wrote:

Are there any plan to add transfer_lock, and any other such generic algoirthms you have lying around, to the proposal as well?

Thanks for the great comments Zach. owns_mutex() or some other suggestion sounds fine to me too. I put transfer_lock into <shared_mutex> which is TR2-targeted. The std::lock and std::try_lock algorithms are in <mutex>, actually in the implementation <mutex_base> header, and targeted towards C++0X. Some of the other examples are just meant to be example client code (like mutex_debug). If you have a burning desire to get one of them into C+ +0X or TR2, please let me know. -Howard

On 8/21/07, Peter Dimov <pdimov@pdimov.com> wrote:

Howard Hinnant wrote:

...

Thanks for the great comments Zach. owns_mutex() or some other suggestion sounds fine to me too.

How about holds_lock? 'owns' doesn't quite ring true with me.

That's the clearest one yet. holds_lock gets my vote. Zach Laine

On Aug 21, 2007, at 7:28 PM, Zach Laine wrote:

...

...

Thanks for the great comments Zach. owns_mutex() or some other suggestion sounds fine to me too.

How about holds_lock? 'owns' doesn't quite ring true with me.

That's the clearest one yet. holds_lock gets my vote.

My problem with lock.owns() is that the grammar suggests the lock owns something, rather then that the lock "is owned" (by the current thread). Furthermore, holds_lock looks like it should be a member function (where this is the current thread), since it uses the same grammar. What about lock.owned() or lock.held()? -- Tack

David Abrahams wrote:

on Mon Aug 20 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

Here is a link to a reference implementation and a FAQ for mutexes, locks and condition variables I am currently anticipating proposing for C++ standardization (or subsequent TR).

http://home.twcny.rr.com/hinnant/cpp_extensions/concurrency_rationale.html

I find the fact that unique_lock can reference a mutex without owning the mutex's lock rather confusing in light of the semantics of unique_ptr. It seems like unique_lock is looking more like the old-old auto_ptr.

I agree. If we remove the lock/try_lock/unlock from the locks, then I think it can be fixed, and we get sizeof(unique_ptr)==sizeof(unique_lock).

On Aug 22, 2007, at 10:11 AM, David Abrahams wrote:

on Mon Aug 20 2007, Howard Hinnant <howard.hinnant-AT-gmail.com> wrote:

...

Here is a link to a reference implementation and a FAQ for mutexes, locks and condition variables I am currently anticipating proposing for C++ standardization (or subsequent TR).

http://home.twcny.rr.com/hinnant/cpp_extensions/concurrency_rationale.html

"However if the external mutex is (or is layout compatible with) a pthread_mutex_t, then there is no need for the internal pthread_mutex_t. When one wants to wait, one simply waits on the external pthread_mutex_t with the internal pthread_cond_t."

This smells a little fishy. It seems to imply that pthreads can wait on any old data type that happens to be layout-compatible with pthread_mutex_t. Is that really true?

Perhaps the wording isn't precise enough. The intent is that on pthreads: class mutex { pthread_mutex_t mut_; public: ... }; template <> class condition<mutex> { pthread_cond_t cv_; public: ... }; When condition<mutex>::wait is called with a lock whose mutex_type is std::mutex (e.g. unique_lock<mutex>), then there is no need for an internal pthread_mutex_t in condition<mutex>. Internally the wait function can simply: pthread_cond_wait(&cv_, lock.mutex()->native_handle()); where lock.mutex()->native_handle() is returning a pointer to the member mut_ of the std::mutex referenced by the passed in lock. Imho this is a critical optimization. It isn't that it makes the wait faster (it does, but who cares, it blocks anyway). It is that it makes the std::condition<std::mutex> smaller in size. Since condition<mutex> is anticipated to be a low level, foundation tool, possibly used in many places, its size becomes important just for reducing L1 cache misses (for the exact same reason that people care that sizeof(vector<int>) is 3 words, not 4 words). -Howard

On Aug 22, 2007, at 10:42 AM, David Abrahams wrote:

on Wed Aug 22 2007, Howard Hinnant <hinnant-AT-twcny.rr.com> wrote:

...

...

"However if the external mutex is (or is layout compatible with) a pthread_mutex_t, then there is no need for the internal pthread_mutex_t. When one wants to wait, one simply waits on the external pthread_mutex_t with the internal pthread_cond_t."

This smells a little fishy. It seems to imply that pthreads can wait on any old data type that happens to be layout-compatible with pthread_mutex_t. Is that really true?

Perhaps the wording isn't precise enough.

The intent is that on pthreads:

<snip explanation that doesn't mention layout-compatibility>

Sure. But where does the layout-compatibility thing come in? Your example uses the native pthread types, not arbitrary types layout-compatible with those.

The vendor will decide on which mutex types it is appropriate to make this specialization/optimization. I used "layout-compatible" in an attempt to communicate which std-defined mutex types would be appropriate for the vendor to specialize on. -Howard

On Aug 22, 2007, at 2:24 PM, Austin Bingham wrote:

Overall I really like the work you've done here.

I have a question about the scheduling of shared v. exclusive locks on shared_mutex. Suppose I have several shared locks already established and then an exclusive lock is tried. Are subsequent shared lock attempts deferred until after theexclusive lock has released? Or is the exclusive lock deferred until after all shared locks (regardless of when they were made) are released? Or is this even defined?

It may be easiest to just leave the scheduling undefined, and perhaps that is the intent of the proposal. Whether it's defined or not, though, it should be documented.

It might be useful, however, if the scheduling policy were configurable. It seems that such a policy could be established on the shared_mutex itself.

I have two answers: 1. This is somewhat of a shocking answer, so please read through the second answer before passing judgement: The proposal purposefully does not mention shared vs exclusive priority. And I would prefer not to. 2. The implementation uses an algorithm which I attribute to Alexander Terekhov. This is a completely fair algorithm, letting the OS scheduler decide which thread is next in line, regardless of whether that thread is seeking shared or exclusive locking. I've beat on this algorithm for years now, stress testing and watching for starvation. I've never seen it starve a reader or a writer. Alexander, if you're listening: REALLY NICE JOB!!! :-) Imho, Alexander's algorithm makes the issue of reader/writer priority moot. If Alexander's algorithm is the automobile, reader/writer policies are the buggy whip. They just aren't needed anymore. I just can't say enough good things about this work. In a nutshell it is a two-gate system. Both readers and writers all wait at the first gate for entry. If no one is yet beyond the first gate, the OS gets to decide who to let in. When a reader gets past the first gate, it has the read lock. When a writer gets past the first gate, it does not yet have the write lock. It must now wait at the second gate until all readers beyond the first gate give up their read lock. While a writer is past the first gate, no one else is allowed to pass through the first gate. The algorithm is implemented here for shared_mutex, and modified appropriately for upgrade_mutex: http://home.twcny.rr.com/hinnant/cpp_extensions/shared_mutex.cpp

Again, this is really excellent and I'm genuinely excited to see this progress. Thanks for all the hard work!

Thanks Austin. -Howard

Austin Bingham wrote:

On 2007-08-22, Howard Hinnant <howard.hinnant@gmail.com> wrote:

...

I have two answers:

1. This is somewhat of a shocking answer, so please read through the second answer before passing judgement: The proposal purposefully does not mention shared vs exclusive priority. And I would prefer not to.

2. The implementation uses an algorithm which I attribute to Alexander Terekhov.

At the risk of defiling a perfectly good metaphor, I think that if Alexander's algorithm is the car, then other policies are more like light trucks, pontoon boats, and tricycles. That is, the algorithm you describe almost certainly works as suggested, but I may really want something completely different.

No, you don't. The other policies are broken cars, not other vehicles. That said, a POSIX rwlock does grant you the ability to shoot yourself in the foot by using thread priorities. Readers will not be blocked waiting for a pending writer of a lower priority.

Frank Mori Hess wrote:

On Friday 24 August 2007 09:57, Phil Endecott wrote:

...

In the same vein, I have sometimes considered making the use of these primitives even more idiot-proof by bundling together a mutex, condition and the variable that they protect:

template <typename T> class locked { mutex m; condition c; T v; };

You might be interested in this paper, which describes a nice way of wrapping an object so a mutex in the wrapper is always locked when accessing the object's member functions.

http://www.research.att.com/~bs/wrapper.pdf

Hi Frank, Thanks; yes, I think this sort of thing would also be a useful addition to Boost. The syntax that I presented had the advantage that a.push_back(123); a.push_back(321); can have a single lock around both operations, while Bjarne's wrapper would lock and unlock for each one. Also, I'm not sure whether his could be extended to offer read locks for some operations and write locks for others. I'll currently hacking an old file that has some ad-hoc mutexes and conditions in it. Perhaps I'll see if I can factor-out a generic wrapper from it. Cheers, Phil.