Name
Abstract | ||
|---|---|---|
We introduce SnapQueues - concurrent, lock-free queues with a linearizable, lock-free global-state transition operation. This transition operation can atomically switch between arbitrary SnapQueue states, and is used by enqueue, dequeue, snapshot and concatenation operations. We show that implementing these operations efficiently depends on the persistent data structure at the core of the SnapQueue. This immutable support data structure is an interchangeable kernel of the SnapQueue, and drives its performance characteristics. The design allows reasoning about concurrent operation running time in a functional way, absent from concurrency considerations. We present a support data structure that enables O(1) queue operations, O(1) snapshot and O(log n) atomic concurrent concatenation. We show that the SnapQueue enqueue operation achieves up to 25% higher performance, while the dequeue operation has performance identical to standard lock-free concurrent queues. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2774975.2774976 | Scala@PLDI |
Field | DocType | Citations |
Persistent data structure,Data structure,Computer science,Non-blocking algorithm,Concurrency,Parallel computing,Queue,Concatenation,Snapshot (computer storage),Double-ended queue | Conference | 7 |
PageRank | References | Authors |
0.46 | 9 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksandar Prokopec | 1 | 163 | 13.56 |