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

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-10-25 06:31:43

"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:
>>>>
>>>>> 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 

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.

Anthony

AAJW thread_rewrite v1.1.2.8

DEADLOCK!!!!!

AAJW condition based v1.1.2.4

0R + 1W:            : 3 max r wait: 0, max w wait: 0
0R + 4W:            : 14 max r wait: 0, max w wait: 297
1R + 0W:            : 2 max r wait: 0, max w wait: 0
1R + 1W:            : 5 max r wait: 46, max w wait: 32
1R + 4W:            : 16 max r wait: 265, max w wait: 375
2R + 0W:            : 2 max r wait: 16, max w wait: 0
2R + 1W:            : 5 max r wait: 46, max w wait: 406
2R + 4W:            : 16 max r wait: 94, max w wait: 296
4R + 0W:            : 4 max r wait: 16, max w wait: 0
4R + 1W:            : 8 max r wait: 63, max w wait: 360
4R + 4W:            : 18 max r wait: 250, max w wait: 578
16R + 0W:           : 17 max r wait: 31, max w wait: 0
16R + 1W:           : 20 max r wait: 141, max w wait: 609
16R + 4W:           : 33 max r wait: 188, max w wait: 1422
64R + 0W:           : 67 max r wait: 47, max w wait: 0
64R + 1W:           : 72 max r wait: 281, max w wait: 562
64R + 4W:           : 86 max r wait: 468, max w wait: 984

AAJW new algo with waiting writer flag

0R + 1W:            : 3 max r wait: 0, max w wait: 16
0R + 4W:            : 14 max r wait: 0, max w wait: 187
1R + 0W:            : 2 max r wait: 16, max w wait: 0
1R + 1W:            : 5 max r wait: 47, max w wait: 16
1R + 4W:            : 16 max r wait: 140, max w wait: 94
2R + 0W:            : 2 max r wait: 15, max w wait: 0
2R + 1W:            : 6 max r wait: 32, max w wait: 32
2R + 4W:            : 16 max r wait: 125, max w wait: 109
4R + 0W:            : 5 max r wait: 15, max w wait: 0
4R + 1W:            : 7 max r wait: 47, max w wait: 32
4R + 4W:            : 18 max r wait: 63, max w wait: 140
16R + 0W:           : 16 max r wait: 16, max w wait: 0
16R + 1W:           : 20 max r wait: 484, max w wait: 594
16R + 4W:           : 30 max r wait: 703, max w wait: 750
64R + 0W:           : 64 max r wait: 16, max w wait: 0
64R + 1W:           : 72 max r wait: 406, max w wait: 1172
64R + 4W:           : 77 max r wait: 563, max w wait: 875

PD CT algo

0R + 1W:            : 3 max r wait: 0, max w wait: 0
0R + 4W:            : 13 max r wait: 0, max w wait: 359
1R + 0W:            : 2 max r wait: 0, max w wait: 0
1R + 1W:            : 6 max r wait: 47, max w wait: 32
1R + 4W:            : 15 max r wait: 9375, max w wait: 282
2R + 0W:            : 2 max r wait: 0, max w wait: 0
2R + 1W:            : 6 max r wait: 62, max w wait: 32
2R + 4W:            : 16 max r wait: 11422, max w wait: 343
4R + 0W:            : 4 max r wait: 16, max w wait: 0
4R + 1W:            : 7 max r wait: 78, max w wait: 110
4R + 4W:            : 18 max r wait: 12296, max w wait: 531
16R + 0W:           : 16 max r wait: 16, max w wait: 0
16R + 1W:           : 20 max r wait: 125, max w wait: 141
16R + 4W:           : 29 max r wait: 12625, max w wait: 438
64R + 0W:           : 66 max r wait: 16, max w wait: 0
64R + 1W:           : 69 max r wait: 250, max w wait: 141
64R + 4W:           : 78 max r wait: 2110, max w wait: 844

PD naive

0R + 1W:            : 4 max r wait: 0, max w wait: 0
0R + 4W:            : 13 max r wait: 0, max w wait: 438
1R + 0W:            : 2 max r wait: 0, max w wait: 0
1R + 1W:            : 5 max r wait: 47, max w wait: 16
1R + 4W:            : 16 max r wait: 453, max w wait: 297
2R + 0W:            : 2 max r wait: 15, max w wait: 0
2R + 1W:            : 5 max r wait: 47, max w wait: 16
2R + 4W:            : 16 max r wait: 328, max w wait: 313
4R + 0W:            : 4 max r wait: 16, max w wait: 0
4R + 1W:            : 8 max r wait: 63, max w wait: 16
4R + 4W:            : 17 max r wait: 453, max w wait: 437
16R + 0W:           : 16 max r wait: 16, max w wait: 0
16R + 1W:           : 20 max r wait: 218, max w wait: 125
16R + 4W:           : 29 max r wait: 953, max w wait: 734
64R + 0W:           : 65 max r wait: 16, max w wait: 0
64R + 1W:           : 68 max r wait: 343, max w wait: 343
64R + 4W:           : 77 max r wait: 1515, max w wait: 1156

Anthony
-- 
Anthony Williams
Software Developer
Just Software Solutions Ltd
http://www.justsoftwaresolutions.co.uk