One thing I've learned about lock-free structures: DWCAS[1] is your friend. Using DWCAS, the Michael and Scott Queue algorithm is trivial to implement. Not really sure why the author insists on using plain CAS, especially when implementing a DWCAS-based algorithm.
DWCAS is not the same as DCAS which is specifically mentioned in your link, so I'm not sure which you're referring to. Second, the link is clear that no common architecture actually supports a DCAS instruction currently, so the reason the author insisted on CAS is because it's a real life instruction and not a theoretical hardware instruction.
This seems very (very) strange to me. Did a simplified mockup in Java using a ConcurrentLinkedDeque. Got an absolute speed-up of ~8 going from 1 thread to 2 (or 4)...and that's on a laptop.
Did you perhaps measure CPU time rather than wall clock or push entries scaled by the number of threads? Didn't find your test source on GitHub..
5 comments
[ 3.2 ms ] story [ 20.7 ms ] thread[1] http://en.wikipedia.org/wiki/Double_compare-and-swap
E.g. C++11 has CAS in std::atomic but no DCAS.