"Peter Dimov" <pdimov@mmltd.net> writes:
Peter Dimov wrote:
Chris Thomasson wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:001801c6f7bd$c32f62a0$6607a8c0@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