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