Re: [boost] a 100% lock-free PDR algorithm for Boost, no patent issues...

From: Chris Thomasson (cristom_at_[hidden])
Date: 2006-11-26 02:01:05

"David Abrahams" <dave_at_[hidden]> wrote in message 
news:873b8fa5wz.fsf_at_pereiro.luannocracy.com...
> "Chris Thomasson" <cristom_at_[hidden]> writes:
[...]

>> IMHO, this would be a major asset to the Boost arsenal!
>
> Sounds interesting, if it works.  I'm not expert enough to do a deep
> analysis.

Yeah. It works. Its not the ideal solution, it makes use of atomic 
operations and memory barriers. There are other techniques that can get 
around those expensive instructions. However, the exotic Reader / Writer 
algorithms problem have patents. I have a commercial library. Joe Seighs 
RCU-SMR has IBM patent applications tied to them.

This solution will be good for Boost, because its one of the only other 
alternatives. You have to hunt your way through the patents. Do a patent 
search on lock-free...

>> Please, search c.p.t for the terms 'PDR' and 'proxy collector'
>>
>> Search, read, and read some more...
>
> Well, I did a bit of that.  Realistically speaking though, in this
> forum, you need to make some claims in lay terms to make it worthwhile
> for people to do the searching.  Like
>
>  "I have an implementatation of an algorithm that makes it easy
>  to write ridiculously efficient lock-free datastructures."
>
> or something.  A little more introductory text that explains why we
> should care would go a long way.

Well, here is some brief introductory text that describes some things:

http://appcore.home.comcast.net/vzoom/

http://appcore.home.comcast.net/vzoom/round-1.pdf

http://appcore.home.comcast.net/vzoom/round-2.pdf

The PDR algorithm for Boost can be lock-free, but I don't think it can be 
Virtually Zero-Overhead... Anyway, I think the lock-free algorithm would be 
good for Boost. I am planning to release some test applications that make 
direct use of the working proxy collector prototype I linked to. Look out 
for them. I also have to finish that atomic static initialization document I 
am working on, and off:

http://appcore.home.comcast.net/vzdoc/atomic/static-init/

;^)

Any thoughts?