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

Subject: Re: [boost] [lockfree::fifo] Review
From: Tim Blechmann (tim_at_[hidden])
Date: 2009-12-11 11:02:54

> Also, Tim, it Chris Thomasson found another problem with the current 
> code. In non pointer packing solution your head and tail are 
> multi-words. You can't load multi-word atomically without some special 
> instructions. Here's his comment:

i ported boost.lockfree to boost.atomic, which deals with this ...

>> i just went through the replies ... (maybe i should upcase some parts in
>> the documentation, that the implementation focus on WORST CASE, not
>> AVERAGE CASE performance ... people keep complaining that the stack/fifo
>> may be outperformed be blocking algorithms, which is both true and
>> irrelevant for me, as these implementations are soft real-time safe (and
>> could be made hard real-time safe).
> 
> Agreed.
> Are you planning to augment your library with algorithms for different 
> needs? Like MPSC, SPMC and so forth? I think that could be useful, 
> because it looks like implementing the most generic MPMC case won't give 
> you the best results.

for now, i will provide mpmc queues only ... maybe it makes sense to add
some specializations for single producers/consumers, later, especially,
if more people are requesting it ...

>> by definition ll/sc are immune to aba problems, but implementing cas via
>> ll/sc, one loses this feature ... personally i would prefer to have
>> language support for ll/sc transactions instead of aba-prone cas ...
>>
>> most cas-architectures provide dcas, while most ll/sc architectures
>> shouldn't use cas emulation, but ll/sc-style transactions directly, as
>> it is by definition aba immune ... too bad, c++0x doesn't provide
>> language support for ll/sc, but only for cas :/
> 
> Totally agree - when I was implementing this algorithm, I had two 
> different versions - one CAS-based with ABA tag and the other LL/SC 
> based without the tag. The problem with LL/SC on some platforms however 
> is sometimes not solvable. On PowerPC 7447, for example, the LL is 
> invalidated when ANY thread writes to ANY memory location, not just to 
> the same cache line.... ugh...

one wouldn't be able to convert every cas-based algorithm to ll/sc, but
ll/sc gives another technique for implementing lockfree data structures ...

cheers, tim

-- 
tim_at_[hidden]
http://tim.klingt.org
You can play a shoestring if you're sincere
  John Coltrane