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

From: Peter Dimov (pdimov_at_[hidden])
Date: 2006-10-26 16:19:16

>> (This redundant wakeup may not be visible in a benchmark, but it
>> can steal CPU from other busy non-contending threads in a real 
>> application.)

To test this, I added "free" threads to the benchmark. These compete on a 
different mutex. With my latest experiment, this reveals odd/intriguing 
patterns of the form

2R+4W+0F: 29
2R+4W+4F: 18

The additional four free threads improve performance!

Test code:

// Copyright (c) 2005, 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)

#undef NDEBUG
#include "rw_mutex_.hpp"

#include <boost/thread/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/bind.hpp>
#include <vector>
#include <iostream>
#include <ctime>

int const N = 1048576;
int const n = 1000; // vector size

rw_mutex mtx;
std::vector<int> v( n );

boost::mutex mx2;
std::vector<int> v2( n );

boost::mutex cmx;

//

void reader( int r )
{
    for( int i = 0; i < N; ++i )
    {
        rw_mutex::scoped_read_lock lock( mtx );

        int m = v.front();

        for( std::vector<int>::const_iterator j = v.begin(), end = v.end(); 
j != end; ++j )
        {
            assert( *j == m );
        }

        if( i == N / 4 || i == N / 2 || i == N / 2 + N / 4 )
        {
            boost::mutex::scoped_lock lock( cmx );
            std::cout << " r" << r;
        }
    }

    boost::mutex::scoped_lock lock( cmx );
    std::cout << " R" << r;
}

void writer( int w )
{
    for( int i = 0; i < N; ++i )
    {
        rw_mutex::scoped_write_lock lock( mtx );

        int m = v.front();

        for( std::vector<int>::iterator j = v.begin(), end = v.end(); j != 
end; ++j )
        {
            ++*j;
            assert( *j == m + 1 );
        }

        if( i == N / 4 || i == N / 2 || i == N / 2 + N / 4 )
        {
            boost::mutex::scoped_lock lock( cmx );
            std::cout << " w" << w;
        }
    }

    boost::mutex::scoped_lock lock( cmx );
    std::cout << " W" << w;
}

void free_( int f )
{
    for( int i = 0; i < N; ++i )
    {
        boost::mutex::scoped_lock lock( mx2 );

        int m = v2.front();

        for( std::vector<int>::iterator j = v2.begin(), end = v2.end(); j != 
end; ++j )
        {
            ++*j;
            assert( *j == m + 1 );
        }

        if( i == N / 4 || i == N / 2 || i == N / 2 + N / 4 )
        {
            boost::mutex::scoped_lock lock( cmx );
            std::cout << " f" << f;
        }
    }

    boost::mutex::scoped_lock lock( cmx );
    std::cout << " F" << f;
}

void test( int nr, int nw, int nf )
{
    try
    {
        std::cout << nr << "R + " << nw << "W + " << nf << "F:";

        std::time_t tm = std::time( 0 );

        boost::thread_group group;

        for( int i = 0; i < nr || i < nw || i < nf; ++i )
        {
            if( i < nw )
            {
                group.create_thread( boost::bind( writer, i ) );
            }

            if( i < nr )
            {
                group.create_thread( boost::bind( reader, i ) );
            }

            if( i < nf )
            {
                group.create_thread( boost::bind( free_, i ) );
            }
        }

        group.join_all();

        std::cout << ": " << std::time( 0 ) - tm << std::endl;

        //for( int i = 0; i < 6; ++i )
        //{
        //  std::cout << mtx.retries( i ) << ' ';
        //}

        std::cout << std::endl;
    }
    catch( std::exception const & x )
    {
        std::cout << x.what() << std::endl;
    }
}

int main()
{
    test(  0,  1,  0 );
    test(  0,  1,  1 );
    test(  0,  4,  0 );
    test(  0,  4,  4 );

    test(  1,  0,  0 );
    test(  1,  0,  1 );

    test(  1,  1,  0 );
    test(  1,  1,  1 );

    test(  1,  4,  0 );
    test(  1,  4,  4 );

    test(  2,  0,  0 );
    test(  2,  0,  2 );

    test(  2,  1,  0 );
    test(  2,  1,  1 );

    test(  2,  2,  0 );
    test(  2,  2,  2 );

    test(  2,  4,  0 );
    test(  2,  4,  4 );

    test(  4,  0,  0 );
    test(  4,  0,  4 );

    test(  4,  1,  0 );
    test(  4,  1,  1 );
    test(  4,  1,  4 );

    test(  4,  4,  0 );
    test(  4,  4,  4 );

    test( 16,  0,  0 );
    test( 16,  0,  4 );

    test( 16,  1,  0 );
    test( 16,  1,  1 );
    test( 16,  1,  4 );

    test( 16,  4,  0 );
    test( 16,  4,  4 );

    //test( 64,  0 );
    //test( 64,  1 );
    //test( 64,  4 );
}