4 ms·
Lock-Free Data Structures: Exploring Queues
- cjensen 11y agoOne 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. [1] http://en.wikipedia.org/wiki/Double_compare-and-swap http://en.wikipedia.org/wiki/Double_compare-and-swap
- runT1ME 11y agoDWCAS 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.
- cjensen 11y agoDWCAS is mentioned in the DCAS article.
- the8472 11y agoPresumably because DCAS is less portable than CAS. E.g. C++11 has CAS in std::atomic but no DCAS.
- ccrolf 11y agoThis 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..