Subj : Re: Hazard Pointers w/o memory barrier.
To   : comp.programming.threads
From : Joe Seigh
Date : Mon May 02 2005 11:40 pm

On Mon, 2 May 2005 19:07:37 -0700, Chris Thomasson <_no_damn_spam_cristom@_no_damn_comcast.net_spam> wrote:

>> Finally getting around to modifying my current RCU
>> implementation to see how fast this will run.  Just
>> taking the memory barriers out gave a 3x improvement
>> in read access throughput.  At that rate that can be
>> considered as effectively zero overhead.
>
> Yes it can. I have already been experimenting with it for a couple of days
> and am extremely pleased with the initial results. The thing that makes me a
> bit uneasy with my windows ( and some other os's ) implementation is the
> dependence on undocumented functions. All of my code that uses this form of
> garbage collection could suddenly stop working when the next service pack
> gets installed...
>

You could always have a fall back plan of putting the membar back in
that case.  It would run slower but that's Microsoft's problem
especially since it would be their platform running worse than their
competitor's platforms.

>
>
>
>> About a 3x
>> slowdown in write access but that's because I don't
>> have the SMR logic in yet plus I have to stay with a
>> slightly crippled version of RCU to avoid imperial
>> entanglement.
>
> We aren't the programmers there looking for...  ;)
>
> Seriously though, this is why I don't provide the public with my user-space
> rcu ( URCU ) implementation. Did you inform McKenney that you were posting
> your algorithm? I am not sure if I need to ask permission...

McKenney and Michael both know about it.  The problem is you have to stick
with a implementation based on the first patent that is in the public
domain.  The claims were more narrow than they might have been because
we believed they had to be tied to the actual methods in the patent.
Not really a problem if you're monitoring per processor/thread counters
or clocks since that's probably how you'd have to do it but with a commom
counter you could speed up the polling somewhat but it wouldn't strictly
be covered by the first patent.
>
>
>
>
>> Adding the SMR logic should give me a
>> dramatic improvement in write throughput.
>
> Yeah. Original SMR is well suited for high write throughput because of the
> guarantees it puts on the way nodes are deleted. This new URCU_SMR thing
> can't seem to handle frequent and persistent writes as good as the original.
> It caused some problems in a couple of my algorithms. Its probably a good
> idea to export two versions of SMR...
>
If you have a really high write rate then you would probably be better off
with a mutex or one of the write lock-free algorithms.  I'm not claiming
the read lock-free stuff is good for all situations.


-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.