Re: [boost] [lockfree::fifo] Review

Subject: Re: [boost] [lockfree::fifo] Review
From: Helge Bahmann (hcb_at_[hidden])
Date: 2010-01-20 04:50:58

On Mon, 18 Jan 2010, Chris M. Thomasson wrote:

> "Helge Bahmann" <hcb_at_[hidden]> wrote in message 
> news:201001181953.33044.hcb_at_chaoticmind.net...
>> Am Saturday 16 January 2010 03:15:44 schrieb Chris M. Thomasson:
>>> FWIW Helge, here is a new proxy garbage collector algorithm of mine that I
>>> am currently experimenting with:
>>> 
>>> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/a
>>> 53f24de178b419f
>> 
>> interesting concept, but AFAICT it shares two undesirable properties with 
>> my
>> implementation: Reclamation can be delayed indefinitely if
>> 
>> - one thread is "stuck" within the critical section (e.g. scheduled away)
>
> Well, if a thread actually deadlocks or "permanently livelocks" within the 
> critical section, then no reclamation can occur.

this means that reclamation (and by extension writing with bounded amount 
of memory) is not wait-free (this is not a problem I think, just pointing 
out)

>> - threads interlock such that at least one thread is always within the
>> critical section
>
>> Right?
>
> No. My proxy algorithm is N = 2, while yours is N = 1 where N is the number 
> of collector objects. This means that you only have a _single_ reference 
> count. During periods of load, this single reference count might never reach 
> zero and the garbage will keep piling up.

[snip explanation]

Okay thanks for your explanation, I did not understand your code correctly 
the first time, but now things are much more clear.

The concept is very nice indeed, and I agree that N=1 and N=2 makes quite 
a difference. I *think* that your approach is much more valuable as a 
building block for "object-local RCU" for data structures with long-lived 
read access than ABA prevention for producer/consumer data structures 
(where the read-side critical section is very short).

Thanks for sharing the code, I can already think of an application 
for this in my own code :)

Best regards,
Helge