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

From: Chris Thomasson (cristom_at_[hidden])
Date: 2006-10-25 19:57:57

"Anthony Williams" <anthony_w.geo_at_[hidden]> wrote in message 
news:wt6ok7ow.fsf_at_yahoo.com...
> "Peter Dimov" <pdimov_at_[hidden]> writes:
>> Peter Dimov wrote:
>>> Chris Thomasson wrote:
>>>> "Peter Dimov" <pdimov_at_[hidden]> wrote in message
>>>> news:001801c6f7bd$c32f62a0$6607a8c0_at_pdimov2...
>>>>> Chris Thomasson wrote:

[...]

> Hi,
>
> I have run a test against Peter's "naive" implementation, Peter's
> implementation of Chris's algorithm, my algorithm from the thread_rewrite
> branch (v1.1.2.8), my old condition-based algorithm from the 
> thread_rewrite
> branch (v1.1.2.4), and a new variation of my latest offering that has a
> "waiting exclusive" bit, and blocks readers if that bit is set, in line 
> with
> my last post on the subject. The test is essentially Peter's test, with a 
> mod
> to count the max time any reader or any writer spends waiting, in order to
> check for starvation.
>
> The tests were run on a Pentium D dual core machine. The output format is
>
> num readers + num writers: : time-in-seconds 
> max-reader-wait-in-milliseconds
> max-writer-wait-in-milliseconds
>
> The total count N in Peter's algorithm was 65536, in order to get runtimes 
> I
> could handle.
>
> The first thing to note is that my current V1.1.2.8 deadlocks, so I got 
> the
> algorithm wrong :-(

;^(...

> The next thing to note is that the total runtimes of the remainder are all
> comparable. I would have to run longer tests to really tell them apart.
>
> The next thing to note is that Peter's implementation of Chris's algorithm 
> has
> some REALLY long wait times for readers --- 12 seconds! --- which follows 
> from
> the "writer priority" nature of the algorithm.

12 Seconds? Something is off kilter wrt the writer frequency 
per-writer-thread and/or the critical-section the writes make use of... 
IMHO, this would prompt me to revise my applications synchronization 
scheme...

Again, IMHO of course, anytime you are getting enough writes to tank a 
"rw-mutex w/ stick writer priority"
, then you are probably better off using PDR instead of rw-mutexs.

Okay, FWIW... Here some pseudo-code for an alter version of my algorithm 
that gives strict priority to the readers...

This "newly augmented algorithm" should do better on Peters test... 
Hopefully!!!

lol.

;^)

// write lock
rw_mutex_t cmp, xchg;

for ( ;; )
{
  cmp = mtx;

  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;
  }

  sem_wait( &w_wset );

}

// read lock
rw_mutex_t cmp, xchg;

for ( ;; )
{
  cmp = mtx;

  do
  {
    xchg = cmp;

    if ( ! cmp.writes )
    {
      ++xchg.reads;
    }
    else
    {
      ++xchg.r_waits;
    }

  } while ( dwcas( &mtx, &cmp, &xchg ) );

  if ( ! cmp.writes )
  {
    break;
  }

  sem_wait( &r_wset );

}

// write unlock
rw_mutex_t cmp, xchg;

do
{
  xchg = cmp;

  --xchg.writes;

  if ( cmp.w_waits && ! cmp.r_waits )
  {
    --xchg.w_waits;
  }
  else if ( cmp.r_waits )
  {
    xchg.r_waits = 0;
  }

} while ( dwcas( &mtx, &cmp, &xchg ) );

if ( cmp.w_waits && ! cmp.r_waits )
{
  sem_post( &w_wset );

}

else if ( cmp.r_waits )
{
  sem_post_multiple( &r_wset, cmp.r_waits );

}

// read unlock
rw_mutex_t cmp, xchg;

do
{
  xchg = cmp;

  --xchg.reads;

  if ( ! cmp.r_waits && cmp.w_waits )
  {
    --xchg.w_waits;
  }
  else if ( cmp.r_waits )
  {
    xchg.r_waits = 0;
  }

} while ( dwcas( &mtx, &cmp, &xchg ) );

if ( ! cmp.r_waits && cmp.w_waits )
{
  sem_post( &w_wset );

}

else if ( cmp.r_waits )
{
  sem_post_multiple( &r_wset, cmp.r_waits );

}

Try that on for size everybody! However, beware, this algorithm can 
potentially starve writers!!

Enjoy...

;^)