Re: [boost] A fast-pathed rw-mutex algorithm for Boost...

From: Peter Dimov (pdimov_at_[hidden])
Date: 2006-10-26 21:52:22

Howard Hinnant wrote:
> On Oct 26, 2006, at 9:20 PM, Peter Dimov wrote:
>
>> Howard Hinnant wrote:
>>
>>> Here is my implementation of Terekhov's *fair* read/write algorithm,
>>> with upgradable thrown in.  This algorithm is just as you say:  The
>>> OS alone decides who gets to run next.
>>>
>>> http://home.twcny.rr.com/hinnant/cpp_extensions/upgrade_mutex.html
>>
>> I'm having trouble eliminating the notify_all from the unlock()
>> "fast path".
>> Under Windows, it is ridiculously expensive; all other algorithms run
>> circles around it, even those that had errors in them. :-) Did you
>> have an
>> unconditional notify_all in your "real" unlock?
>
> No.  I had extra 1-bit flags that let me know if there was someone
> waiting on gates 1 or 2:
>
> static const unsigned write_entered_ = 1U << (sizeof(unsigned)
> *_STD::__char<>::bits-1);
> static const unsigned upgradable_entered_ = write_entered_ >> 1;
> static const unsigned entry_sleeping_ = upgradable_entered_ >> 1;
> static const unsigned fw_sleeping_ = entry_sleeping_ >> 1;
> static const unsigned max_readers_ = ~(write_entered_ |
> upgradable_entered_ |
>                                        entry_sleeping_ |
> fw_sleeping_);
>
> So the fast path would check these bits and avoid the notify_all if
> they weren't set.

Thanks, I'll try this tomorrow. Later today, I mean.

BTW... why do you count the upgradable among the readers? It seems a bit 
simpler not to include it in the reader count; it already has a bit all for 
itself.