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

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2006-10-26 21:42:14

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.

Btw, cool suggestion on the twist in the rdlock.  I got half way  
through implementing it, discovered a fatal flaw, got half way  
through writing up why it's a fatal flaw and convinced myself it  
wasn't a fatal flaw.  :-)  Still tinkering...  Looks promising! :-)

-Howard