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@klingt.org http://tim.klingt.org You can play a shoestring if you're sincere John Coltrane