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

From: Cory Nelson (phrosty_at_[hidden])
Date: 2006-10-26 05:10:11

On 10/26/06, Anthony Williams <anthony_w.geo_at_[hidden]> wrote:
> "Chris Thomasson" <cristom_at_[hidden]> writes:
>
> > "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 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.
>
> I'm running some longer tests now, to see how it comes out.
>
> >> 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...
>
> It's just a consequence of writer priority when there's more than one
> writer. The particular trouble spots were when there is 4 writer threads, so
> there's pretty much always a writer waiting.  I would revise the rwmutex to be
> "fairer" as a first port of call.
>
> > Okay, FWIW... Here some pseudo-code for an alter version of my algorithm
> > that gives strict priority to the readers...
>
> I thought we all agreed that was a bad plan. That's why I'm trying to revise
> my algorithm to not do this.
>
> Incidentally, I've just been reviewing the read-write lock algorithm in
> Butenhof's "Programming with POSIX Threads", and he uses a reader-priority
> algorithm. He does say that it might not be suitable for all uses, however,
> and shows how to change it to writer-priority.

Is there a reason for wanting a priority?  Why not make the lock fair.
 I'd rather have locks take out a ticket so everything is processed in
a FIFO order, with no starvation.

> > This "newly augmented algorithm" should do better on Peters test...
> > Hopefully!!!
>
> I'll add it to the list.
>
> The test I'm running does cover a wide variety of scenarios, with 0, 1, 2 or 4
> writers, each matched against 0, 1, 2, 4, 16 or 64 readers, so it's not biased
> --- a "reader priority" algorithm should give high "write wait" times when
> there's lots of readers, just as a "writer priority" algorithm will give high
> "read wait" times when there's more than one writer.
>
> Anthony
> --
> Anthony Williams
> Software Developer
> Just Software Solutions Ltd
> http://www.justsoftwaresolutions.co.uk
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Cory Nelson
http://www.int64.org