from Hacker News

Lock-Free Data Structures: Exploring Queues

by skazka16 on 5/6/15, 12:34 PM with 5 comments

  • by cjensen on 5/6/15, 6:55 PM

    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.

    [1] http://en.wikipedia.org/wiki/Double_compare-and-swap

  • by ccrolf on 5/6/15, 7:11 PM

    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..