Concurrent Skip Lists
Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit Concurrent Skip Lists
Set Object Interface
2 Set Object Interface • Collection of elements • No duplicates • Methods – add() a new element – remove() an element – contains() if element is present Art of Multiprocessor Programming
Many are Cold but Few are Frozen
3 Many are Cold but Few are Frozen • Typically high % of contains() calls • Many fewer add() calls • And even fewer remove() calls – 90% contains() – 9% add() – 1% remove() • Folklore? – Yes but probably mostly true Art of Multiprocessor Programming
Concurrent Sets
4 Concurrent Sets • Balanced Trees? – Red - Black trees, AVL trees, … • Problem: no one does this well … • … because rebalancing after add() or remove() is a global operation Art of Multiprocessor Programming
Skip Lists
5 Skip Lists 2 5 8 7 9 0 • Probabilistic Data Structure • No global rebalancing • Logarithmic-time search Art of Multiprocessor Programming
Skip List Property
6 Skip List Property 9 0 • Each layer is sub-list of lower levels Art of Multiprocessor Programming
Skip List Property
7 Skip List Property 7 9 0 • Each layer is sub-list of lower-levels Art of Multiprocessor Programming
Skip List Property
8 Skip List Property 5 7 9 0 • Each layer is sub-list of lower levels Art of Multiprocessor Programming
Skip List Property
9 Skip List Property 5 8 7 9 0 • Each layer is sub-list of lower levels Art of Multiprocessor Programming
Skip List Property
10 Skip List Property 2 5 8 7 9 0 • Each layer is sub-list of lower levels • Lowest level is entire list Art of Multiprocessor Programming
Skip List Property
11 Skip List Property 2 5 8 7 9 0 • Each layer is sub-list of lower levels • Not easy to preserve in concurrent implementations … Art of Multiprocessor Programming
Search
12 Search 2 5 8 7 9 0 contains(8) Too far Art of Multiprocessor Programming
Search
13 Search 2 5 8 7 9 0 contains(8) OK Art of Multiprocessor Programming
Search
14 Search 2 5 8 7 9 0 contains(8) Too far Art of Multiprocessor Programming
Search
15 Search 2 5 8 7 9 0 contains(8) Too far Art of Multiprocessor Programming
Search
16 Search 2 5 8 7 9 0 contains(8) Yes! Art of Multiprocessor Programming
Search
17 7 Search 8 0 2 5 9 contains(8) Art of Multiprocessor Programming
Logarithmic
18 7 Logarithmic 8 0 2 5 9 contains(8) Log N Art of Multiprocessor Programming
Why Logarthimic
19 Why Logarthimic 2 5 8 7 9 0 • Property: Each pointer at layer i jumps over roughly 2 i nodes • Pick node heights randomly so property guaranteed probabilistically 2 i 2 i Art of Multiprocessor Programming
Sequential Find
20 Sequential Find int find(T x, Node<T>[] preds, Node<T>[] succs) { … } Art of Multiprocessor Programming
Sequential Find
21 Sequential Find int find(T x, Node<T>[] preds, Node<T>[] succs) { … } object height (-1 if not there) Art of Multiprocessor Programming
Sequential Find
22 Sequential Find int find( T x, Node<T>[] preds, Node<T>[] succs) { … } Object sought object height (-1 if not there) Art of Multiprocessor Programming
Sequential Find
23 Sequential Find int find( T x, Node<T>[] preds, Node<T>[] succs) { … } object sought return predecessors Object height (-1 if not there) Art of Multiprocessor Programming
Sequential Find
24 Sequential Find int find( T x, Node<T>[] preds, Node<T>[] succs ) { … } object sought return predecessors Object height (-1 if not there) Art of Multiprocessor Programming return successors
Successful Search
25 Successful Search 2 5 8 7 9 0 find(7, …) preds 0 1 2 3 4 Art of Multiprocessor Programming
Successful Search
26 Successful Search 2 5 8 7 9 0 find(7, …) succs 0 1 2 3 4 preds 0 1 2 3 4 Art of Multiprocessor Programming
Unsuccessful Search
27 Unsuccessful Search 2 5 8 7 9 0 find(6, …) preds 0 1 2 3 4 Art of Multiprocessor Programming
Unsuccessful Search
28 Unsuccessful Search 2 5 8 7 9 0 find(6, …) succs 0 1 2 3 4 preds 0 1 2 3 4 Art of Multiprocessor Programming
Lazy Skip List
29 Lazy Skip List • Mix blocking and non-blocking techniques: – Use optimistic-lazy locking for add() and remove() – Wait-free contains() • Remember: typically lots of contains() calls but few add() and remove() Art of Multiprocessor Programming
Review: Lazy List Remove
30 Review: Lazy List Remove a a b c d Art of Multiprocessor Programming
Review: Lazy List Remove
31 Review: Lazy List Remove a a b c d Present in list Art of Multiprocessor Programming
Review: Lazy List Remove
32 Review: Lazy List Remove a a b c d Logically deleted Art of Multiprocessor Programming
Review: Lazy List Remove
33 Review: Lazy List Remove a a b c d Physically deleted Art of Multiprocessor Programming
Lazy Skip Lists
34 Lazy Skip Lists 2 5 8 7 • Use a mark bit for logical deletion 9 0 0 0 0 0 0 0 Art of Multiprocessor Programming
add(6)
35 add(6) • Create node of (random) height 4 2 5 8 7 9 0 0 0 6 Art of Multiprocessor Programming
add(6)
36 add(6) • find() predecessors 6 2 5 8 7 9 0 0 0 0 6 Art of Multiprocessor Programming
add(6)
37 add(6) • find() predecessors • Lock them 6 2 5 8 7 9 0 0 0 0 0 6 Art of Multiprocessor Programming
add(6)
38 add(6) • find() predecessors • Lock them • Validate 6 2 5 8 7 9 0 0 0 0 0 6 Optimistic approach Art of Multiprocessor Programming
add(6)
39 add(6) 8 7 9 2 5 0 • find() predecessors • Lock them • Validate • Splice 0 6 0 0 0 Art of Multiprocessor Programming
add(6)
40 add(6) • find() predecessors • Lock them • Validate • Splice • Unlock 8 7 9 2 5 0 6 0 0 0 0 0 Art of Multiprocessor Programming
remove(6)
41 remove(6) 8 7 9 2 5 0 6 0 0 0 0 0 0 Art of Multiprocessor Programming
remove(6)
42 remove(6) • find() predecessors 8 7 9 2 5 0 6 0 0 0 0 0 0 Art of Multiprocessor Programming
remove(6)
43 remove(6) • find() predecessors • Lock victim 8 7 9 2 5 0 6 0 0 0 0 0 0 Art of Multiprocessor Programming
remove(6)
44 8 7 9 2 5 0 6 remove(6) • find() predecessors • Lock victim • Set mark (if not already set) 0 0 0 0 0 Logical remove… Art of Multiprocessor Programming
remove(6)
45 8 7 9 2 5 0 6 remove(6) • find() predecessors • Lock victim • Set mark (if not already set) • Lock predecessors (ascending order) & validate 0 0 1 0 0 0 Art of Multiprocessor Programming
remove(6)
46 remove(6) • find() predecessors • Lock victim • Set mark (if not already set) • Lock predecessors (ascending order) & validate • Physically remove 8 7 9 2 5 0 6 0 0 1 0 0 0 Art of Multiprocessor Programming
remove(6)
47 remove(6) • find() predecessors • Lock victim • Set mark (if not already set) • Lock predecessors (ascending order) & validate • Physically remove 8 7 9 2 5 0 6 0 0 1 0 0 0 Art of Multiprocessor Programming
remove(6)
48 remove(6) • find() predecessors • Lock victim • Set mark (if not already set) • Lock predecessors (ascending order) & validate • Physically remove 8 7 9 2 5 0 6 0 0 1 0 0 0 Art of Multiprocessor Programming
remove(6)
49 remove(6) • find() predecessors • Lock victim • Set mark (if not already set) • Lock predecessors (ascending order) & validate • Physically remove 8 7 9 2 5 0 6 0 0 1 0 0 0 Art of Multiprocessor Programming
remove(6)
50 remove(6) • find() predecessors • Lock victim • Set mark (if not already set) • Lock predecessors (ascending order) & validate • Physically remove 8 7 9 2 5 0 0 0 0 0 0 Art of Multiprocessor Programming
contains(8)
51 contains(8) • Find() & not marked 8 7 9 2 5 0 6 0 0 0 0 0 0 Art of Multiprocessor Programming
contains(8)
52 contains(8) 8 7 9 2 5 0 6 0 0 0 0 0 0 Node 6 removed while traversed Art of Multiprocessor Programming
contains(8)
53 contains(8) 8 7 9 2 5 0 6 0 0 0 0 0 Node removed while being traversed Art of Multiprocessor Programming
contains(8)
54 contains(8) 8 7 9 2 5 0 6 0 0 0 0 0 Prove : an unmarked node (like 8 ) remains reachable Art of Multiprocessor Programming
remove(6): Linearization
55 8 7 9 2 5 0 6 remove(6): Linearization • Successful remove happens when bit is set 0 0 0 0 0 Logical remove… Art of Multiprocessor Programming
Add: Linearization
56 Add: Linearization 8 7 9 2 5 0 • Successful add() at point when fully linked • Add fullyLinked bit to indicate this • Bit tested by contains() 0 0 6 0 0 0 Art of Multiprocessor Programming
contains(7): Linearization
57 contains(7): Linearization 8 7 9 2 5 0 6 0 0 0 0 0 • When fully-linked unmarked node found • Pause while fullyLinked bit unset Art of Multiprocessor Programming
contains(7): Linearization
58 contains(7): Linearization 8 6 9 2 5 0 7 0 0 1 0 0 • When do we linearize unsuccessful Search? 1 So far OK… Art of Multiprocessor Programming
contains(7): Linearization
59 contains(7): Linearization 8 6 9 2 5 0 7 0 0 0 0 • When do we linearize unsuccessful Search? 7 But what if a new 7 added concurrently? Art of Multiprocessor Programming
contains(7): Linearization
60 contains(7): Linearization 8 6 9 2 5 0 7 0 0 0 0 • When do we linearize unsuccessful Search? 1 7 Prove : at some point 7 was not in the skip list Art of Multiprocessor Programming
A Simple Experiment
61 A Simple Experiment • Each thread runs 1 million iterations, each either: – add() – remove() – contains() • Item and method chosen in random from some distribution Art of Multiprocessor Programming
Lazy Skip List: Performance
62 Lazy Skip List: Performance Multiprogramming Art of Multiprocessor Programming
Lazy Skip List: Performance
63 Lazy Skip List: Performance Multiprogramming Higher contention Art of Multiprocessor Programming
Lazy Skip List: Performance
64 Lazy Skip List: Performance Multiprogramming Unrealistic Contention Art of Multiprocessor Programming
Summary
65 Summary • Lazy Skip List – Optimistic fine-grained Locking • Performs as well as the lock-free solution in “common” cases • Simple Art of Multiprocessor Programming
66   creativecommons.org/licenses/by-sa/2.5/ Creative Commons Attribution -ShareAlike 2.5 License . • You are free : – to Share — to copy, distribute and transmit the work – to Remix — to adapt the work • Under the following conditions : – Attribution . You must attribute the work to “The Art of Multiprocessor Programming” (but not in any way that suggests that the authors endorse you or your use of the work). – Share Alike . If you alter, transform, or build upon this work, you may distribute the resulting work only under the same, similar or a compatible license. • For any reuse or distribution, you must make clear to others the license terms of this work. The best way to do this is with a link to – http://creativecommons.org/licenses/by-sa/3.0/. • Any of the above conditions can be waived if you get permission from the copyright holder. • Nothing in this license impairs or restricts the author's moral rights. Art of Multiprocessor Programming