Archive for the ‘Lock-Free Algorithms’ Category

A Provably Correct Scalable Concurrent Skip List

Thursday, August 16th, 2012

From High Scalability, report of Paper: A Provably Correct Scalable Concurrent Skip List.

From the post:

In MemSQL Architecture we learned one of the core strategies MemSQL uses to achieve their need for speed is lock-free skip lists. Skip lists are used to efficiently handle range queries. Making the skip-lists lock-free helps eliminate contention and make writes fast.

If this all sounds a little pie-in-the-sky then here’s a very good paper on the subject that might help make it clearer: A Provably Correct Scalable Concurrent Skip List.

The cited paper is by Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. The authors shared Sun Microsystems as an employer so you know the paper is dated.

For more background on lock-free data structures, including Keir Fraser’s “Practical lock freedom” dissertation, see: Practical lock-free data structures.

Lock-Free Algorithms: How Intel X86_64 Processors and Their Memory Model Works

Thursday, May 3rd, 2012

Lock-Free Algorithms: How Intel X86_64 Processors and Their Memory Model Works

Alex Popescu has links to both presentations and other resources by Martin Thompson on how to write lock-free algorithms.

Just in case you are interested in performance for your semantic/topic map applications.