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

From: Peter Dimov (pdimov_at_[hidden])
Date: 2006-10-24 19:36:45

Peter Dimov wrote:
> Chris Thomasson wrote:
>> "Peter Dimov" <pdimov_at_[hidden]> wrote in message
>> news:001801c6f7bd$c32f62a0$6607a8c0_at_pdimov2...
>>> Chris Thomasson wrote:
>>>
>>>> How does the original algorithm compare to yours?
>>>
>>> I haven't tried it yet. Will do.
>>
>> Humm...
>
> Hmmm. Doesn't seem to work.

Works now.

The performance is somewhat better than my other semaphore-based attempts in 
most common scenarios. But it still doesn't beat the "naive" implementation 
at

http://pdimov.com/cpp/rw_mutex.cpp

Here's the entire header:

#ifndef BOOST_DETAIL_RW_MUTEX_HPP_INCLUDED
#define BOOST_DETAIL_RW_MUTEX_HPP_INCLUDED

// MS compatible compilers support #pragma once

#if defined(_MSC_VER) && (_MSC_VER >= 1020)
# pragma once
#endif

// Copyright (c) 2005 Chris Thomasson
// Copyright (c) 2006 Peter Dimov
//
// Distributed under the Boost Software License, Version 1.0.
// See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include <boost/detail/interlocked.hpp>
#include <cassert>
#include <windows.h>

bool dwcas( void * d, void * c, const void * x )
{
    long ov = *(long*)c;
    long nv = BOOST_INTERLOCKED_COMPARE_EXCHANGE( (long*)d, *(long const*)x, 
ov );

    if( ov == nv )
    {
        return false;
    }
    else
    {
        *(long*)c = nv;
        return true;
    }
}

class rw_mutex
{
private:

    rw_mutex( rw_mutex const & );
    rw_mutex & operator=( rw_mutex const & );

private:

    struct state
    {
        unsigned reads: 10;
        unsigned writes: 2;
        unsigned r_waits: 10;
        unsigned w_waits: 10;
    };

    state mtx_;

    HANDLE sema_r_;
    HANDLE sema_w_;

public:

    rw_mutex()
    {
        state st = { 0 };
        mtx_ = st;

        sema_r_ = CreateSemaphore( 0, 0, 1023, 0 );
        sema_w_ = CreateSemaphore( 0, 0, 1023, 0 );
    }

    ~rw_mutex()
    {
        CloseHandle( sema_r_ );
        CloseHandle( sema_w_ );
    }

    void rdlock()
    {
        for( ;; )
        {
            state cmp = mtx_, xchg;

            do
            {
                xchg = cmp;

                if( !cmp.writes && !cmp.w_waits )
                {
                    ++xchg.reads;
                }
                else
                {
                    ++xchg.r_waits;
                }
            }
            while( dwcas( &mtx_, &cmp, &xchg ) );

            if( !cmp.writes && !cmp.w_waits )
            {
                break;
            }

            WaitForSingleObject( sema_r_, INFINITE );
        }
    }

    void lock()
    {
        for ( ;; )
        {
            state cmp = mtx_, xchg;

            do
            {
                xchg = cmp;

                if( !cmp.reads && !cmp.writes )
                {
                    ++xchg.writes;
                }
                else
                {
                    ++xchg.w_waits;
                }
            }
            while( dwcas( &mtx_, &cmp, &xchg ) );

            if ( !cmp.reads && !cmp.writes )
            {
                break;
            }

            WaitForSingleObject( sema_w_, INFINITE );
        }
    }

    void unlock()
    {
        state cmp = mtx_, xchg;

        do
        {
            assert( cmp.writes == 1 );
            assert( cmp.reads == 0 );

            xchg = cmp;

            --xchg.writes;

            if( cmp.w_waits )
            {
                --xchg.w_waits;
            }
            else if( cmp.r_waits )
            {
                xchg.r_waits = 0;
            }
        }
        while( dwcas( &mtx_, &cmp, &xchg ) );

        if( cmp.w_waits )
        {
            ReleaseSemaphore( sema_w_, 1, 0 );
        }
        else if( cmp.r_waits )
        {
            ReleaseSemaphore( sema_r_, cmp.r_waits, 0 );
        }
    }

    void rdunlock()
    {
        state cmp = mtx_, xchg;

        do
        {
            assert( cmp.writes == 0 );
            assert( cmp.reads > 0 );

            xchg = cmp;

            --xchg.reads;

            if( !xchg.reads && cmp.w_waits )
            {
                --xchg.w_waits;
            }
            else if( cmp.r_waits )
            {
                xchg.r_waits = 0;
            }
        }
        while( dwcas( &mtx_, &cmp, &xchg ) );

        if ( !xchg.reads && cmp.w_waits )
        {
            ReleaseSemaphore( sema_w_, 1, 0 );
        }
        else if ( cmp.r_waits )
        {
            ReleaseSemaphore( sema_r_, cmp.r_waits, 0 );
        }
    }

public:

    // lock classes

    class scoped_read_lock
    {
    private:

        rw_mutex & mx_;

        scoped_read_lock( scoped_read_lock const & );
        scoped_read_lock & operator=( scoped_read_lock const & );

    public:

        scoped_read_lock( rw_mutex & mx ): mx_( mx )
        {
            mx_.rdlock();
        }

        ~scoped_read_lock()
        {
            mx_.rdunlock();
        }
    };

    class scoped_write_lock
    {
    private:

        rw_mutex & mx_;

        scoped_write_lock( scoped_write_lock const & );
        scoped_write_lock & operator=( scoped_write_lock const & );

    public:

        scoped_write_lock( rw_mutex & mx ): mx_( mx )
        {
            mx_.lock();
        }

        ~scoped_write_lock()
        {
            mx_.unlock();
        }
    };
};

#endif // #ifndef BOOST_DETAIL_RW_MUTEX_HPP_INCLUDED