Can anyone give some real world examples of lock-free data structures?
neonachronism
In the video lectures, Kayvon makes it sound like the Java stdlib has some.
bob_sacamano
In the database world, B/B+-trees is the data structure of choice to implement indexes. It uses fine-grained locking to support concurrent inserts, deletes and lookups. Modern databases are shifting towards running completely in-memory. With disk accesses no longer being the bottleneck, they need to smartly use the available hardware to provide good performance. Microsoft Research developed a "latch-free" B-tree variant called the "Bw-Tree" that is implemented entirely using CAS primitives to support standard index operations and scale well over many cores. The details of this data structure are available in this publication - http://ieeexplore.ieee.org/document/6544834/ and from this lecture from the 15-721 course - http://cmudb.io/15721-s16-lect07
Can anyone give some real world examples of lock-free data structures?
In the video lectures, Kayvon makes it sound like the Java stdlib has some.
In the database world, B/B+-trees is the data structure of choice to implement indexes. It uses fine-grained locking to support concurrent inserts, deletes and lookups. Modern databases are shifting towards running completely in-memory. With disk accesses no longer being the bottleneck, they need to smartly use the available hardware to provide good performance. Microsoft Research developed a "latch-free" B-tree variant called the "Bw-Tree" that is implemented entirely using CAS primitives to support standard index operations and scale well over many cores. The details of this data structure are available in this publication - http://ieeexplore.ieee.org/document/6544834/ and from this lecture from the 15-721 course - http://cmudb.io/15721-s16-lect07