Paper Info
Title
Versioned Programming: A Simple Technique for Implementing Efficient, Lock-Free, and Composable Data Structures.
Abstract
This paper introduces versioned programming, a technique that can be used to convert pointer-based data structures into efficient, lock-free implementations. Versioned programming allows arbitrary composition of pointer modifications. Taking linked-lists as an example, VLISTs, or versioned lists, support features missing in other lock-free implementations, such as double linking and atomic moves among lists. The main idea of versioning is to allow different versions of a nodes exist at the same time such that each thread can pick the appropriate version and has a consistent view of the whole data structure. We present a detailed example of VLISTs, simple enough to include all code inline. The paper also evaluates versioned tree implementations. We evaluate versioned programming against several concurrency techniques. With a modest number of writers, versioned programming outperforms read-log-update, which locks nodes. VLIST out-perform lists with SwissTM, a highquality STM, showing the value of trading some programmer-transparency for performance. Composability hurts performance compared to a non-composable, hand-written lock-free algorithm. Using the technique described in this paper, application developers can have both the performance scalability of sophisticated synchronization techniques with functionality and simplicity comparable to coarse locks.
Year
DOI
Venue
2016
10.1145/2928275.2928285
SYSTOR
Keywords
Field
DocType
Concurrent Programming, Lock-Free Data Structures, Versioned Programming
Pointer (computer programming),Data structure,Programming language,Computer science,Non-blocking algorithm,Concurrency,Parallel computing,Thread (computing),Concurrent computing,Composability,Scalability
Conference
Citations 
PageRank 
References 
1
0.34
26
Authors
2
Name
Order
Citations
PageRank
Yang Zhan1656.65
Donald E. Porter238932.25