Aleksandar Prokopec
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.
- Akka documentation, 2015. http://akka.io/docs/.Google Scholar
- SnapQueue Implementation, 2015. https://github.com/stormenroute/reactive-collections/tree/master/reactive-collectionscore.Google Scholar
- G. M. Adelson-Velsky and E. M. Landis. An algorithm for the organization of information. Doklady Akademii Nauk SSSR, 146:263–266, 1962.Google Scholar
- Y. Afek, N. Shavit, and M. Tzafrir. Interrupting snapshots and the JavaTM size method. J. Parallel Distrib. Comput., 72(7):880–888, July 2012. Google ScholarDigital Library
- E. Allen, D. Chase, J. Hallett, V. Luchangco, J.-W. Maessen, S. Ryu, G. Steele, and S. Tobin-Hochstadt. The Fortress Language Specification. Technical report, Sun Microsystems, Inc., 2007.Google Scholar
- N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. SIGPLAN Not., 45(5):257– 268, Jan. 2010. Google ScholarDigital Library
- C. Click. Towards a scalable non-blocking coding style, 2007.Google Scholar
- A. Georges, D. Buytaert, and L. Eeckhout. Statistically rigorous java performance evaluation. SIGPLAN Not., 42(10):57– 76, Oct. 2007. Google ScholarDigital Library
- P. Haller, A. Prokopec, H. Miller, V. Klang, R. Kuhn, and V. Jovanovic. Scala Improvement Proposal: Futures and Promises (SIP-14). 2012.Google Scholar
- M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. Google ScholarDigital Library
- R. Hinze and R. Paterson. Finger trees: A simple generalpurpose data structure. J. Funct. Program., 16(2):197–217, Mar. 2006. Google ScholarDigital Library
- H. Kaplan and R. E. Tarjan. Purely functional representations of catenable sorted lists. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 202–211, 1996. Google ScholarDigital Library
- D. Lea. Doug Lea’s workstation, 2014.Google Scholar
- M. M. Michael and M. L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In PODC, pages 267–275, 1996. Google ScholarDigital Library
- M. Moir and N. Shavit. Concurrent data structures. In Handbook of Data Structures and Applications, D. Metha and S. Sahni Editors, pages 47–14 — 47–30, 2007. Chapman and Hall/CRC Press.Google Scholar
- C. Okasaki. Purely Functional Data Structures. Cambridge University Press, New York, NY, USA, 1998. Google ScholarDigital Library
- A. Prokopec. Data Structures and Algorithms for Data-Parallel Computing in a Managed Runtime. PhD thesis, IC, EPFL, Lausanne, 2014.Google Scholar
- A. Prokopec. ScalaMeter Benchmarking Suite Website, 2014. http://scalameter.github.io.Google Scholar
- A. Prokopec, N. G. Bronson, P. Bagwell, and M. Odersky. Concurrent tries with efficient non-blocking snapshots. pages 151–160, 2012.Google Scholar
- A. Prokopec, H. Miller, T. Schlatter, P. Haller, and M. Odersky. FlowPools: A lock-free deterministic concurrent dataflow abstraction. In LCPC, pages 158–173, 2012.Google Scholar
- W. Pugh. Concurrent maintenance of skip lists. Technical report, College Park, MD, USA, 1990. Google ScholarDigital Library
- W. N. Scherer, D. Lea, and M. L. Scott. Scalable synchronous queues. Commun. ACM, 52(5):100–111, 2009. Google ScholarDigital Library
- T. Schlatter, A. Prokopec, H. Miller, P. Haller, and M. Odersky. Multi-lane flowpools: A detailed look. Technical report, EPFL, Lausanne, September 2012.Google Scholar
- R. Soulé, M. I. Gordon, S. Amarasinghe, R. Grimm, and M. Hirzel. Dynamic expressivity with static optimization for streaming languages. In Proceedings of the 7th ACM International Conference on Distributed Event-based Systems, DEBS ’13, pages 159–170, New York, NY, USA, 2013. ACM. Google ScholarDigital Library
- G. Steele. Organizing functional code for parallel execution; or, foldl and foldr considered slightly harmful. International Conference on Functional Programming (ICFP), 2009. Google ScholarDigital Library
- S. Tasharofi. Efficient testing of actor programs with nondeterministic behaviors. PhD thesis, University of Illinois at Urbana-Champaign, 2014.Google Scholar
- M. Thompson, D. Farley, M. Barker, P. Gee, and A. Stewart. Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads. May 2011.Google Scholar
Index Terms
- SnapQueue: lock-free queue with constant time snapshots
Recommendations
Lock-Free Transactional Transformation for Linked Data Structures
Special Issue on SPAA 2016Nonblocking data structures allow scalable and thread-safe access to shared data. They provide individual operations that appear to execute atomically. However, it is often desirable to execute multiple operations atomically in a transactional manner. ...
Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CAS
PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computingSnapshots are fundamental shared objects which provide consistent views of blocks of shared memory. A snapshot object consists of an array of m memory cells and allows processes to execute UPDATES to write new values in any of the snapshot cells, and ...
Lock-free transactional vector
PMAM '20: Proceedings of the Eleventh International Workshop on Programming Models and Applications for Multicores and ManycoresThe vector is a fundamental data structure, offering constant-time traversal to elements and a dynamically resizable range of indices. While several concurrent vectors exist, a composition of concurrent vector operations dependent on each other can lead ...
Comments