Adaptive lock-free data structures in Haskell: a general method for concurrent implementation swapping

ABSTRACT

A key part of implementing high-level languages is providing built- in and default data structures. Yet selecting good defaults is hard. A mutable data structure’s workload is not known in advance, and it may shift over its lifetime—e.g., between read-heavy and write- heavy, or from heavy contention by multiple threads to single- threaded or low-frequency use. One idea is to switch implementa- tions adaptively, but it is nontrivial to switch the implementation of a concurrent data structure at runtime. Performing the transition requires a concurrent snapshot of data structure contents, which normally demands special engineering in the data structure’s de- sign. However, in this paper we identify and formalize an relevant property of lock-free algorithms. Namely, lock-freedom is su cient to guarantee that freezing memory locations in an arbitrary order will result in a valid snapshot. Several functional languages have data structures that freeze and thaw, transitioning between mutable and immutable, such as Haskell vectors and Clojure transients, but these enable only single-threaded writers. We generalize this approach to augment an arbitrary lock-free data structure with the ability to gradually freeze and optionally transition to a new representation. This aug- mentation doesn’t require changing the algorithm or code for the data structure, only replacing its datatype for mutable references with a freezable variant. In this paper, we present an algorithm for lifting plain to adaptive data and prove that the resulting hy- brid data structure is itself lock-free, linearizable, and simulates the original. We also perform an empirical case study in the context of heating up and cooling down concurrent maps.

References

1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. 1993. Atomic Snapshots of Shared Memory. J. ACM 40, 4 (Sept. 1993), 873–890. DOI:
2. Kunal Agrawal, Charles E. Leiserson, and Jim Sukha. 2010. Helper Locks for Fork-join Parallel Programming. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’10). ACM, New York, NY, USA, 245–256. DOI:
3. Phil Bagwell. 2001. Ideal Hash Trees. Es Grands Champs 1195 (2001).
4. Spenser Bauman, Carl Friedrich Bolz, Robert Hirschfeld, Vasily Kirilichev, Tobias Pape, Jeremy G. Siek, and Sam Tobin-Hochstadt. 2015. Pycket: A Tracing JIT for a Functional Language. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming (ICFP 2015). ACM, New York, NY, USA, 22–34. DOI:
5. Carl Friedrich Bolz, Lukas Diekmann, and Laurence Tratt. 2013. Storage Strategies for Collections in Dynamically Typed Languages. SIGPLAN Not. 48, 10 (Oct. 2013), 167–182. DOI:
6. Mattias De Wael, Stefan Marr, Joeri De Koster, Jennifer B. Sartor, and Wolfgang De Meuter. 2015. Just-in-time Data Structures. In 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!) (Onward! 2015). ACM, New York, NY, USA, 61–75. DOI:
7. Colin S. Gordon, Matthew J. Parkinson, Jared Parsons, Aleks Bromfield, and Joe Duffy. 2012. Uniqueness and Reference Immutability for Safe Parallelism. SIGPLAN Not. 47, 10 (Oct. 2012), 21–40. DOI:
8. Vincent Gramoli. 2015. More Than You Ever Wanted to Know About Synchronization: Synchrobench, Measuring the Impact of the Synchronization on Concurrent Algorithms. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2015). ACM, New York, NY, USA, 1–10. DOI:
9. Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In Proceedings of the 15th International Conference on Distributed Computing (DISC ’01). Springer-Verlag, London, UK, UK, 300–314. http://dl.acm.org/citation.cfm?id= 645958.676105
10. Timothy L. Harris, Keir Fraser, and Ian A. Pratt. 2002. A Practical Multi-word Compare-and-Swap Operation. In Proceedings of the 16th International Conference on Distributed Computing (DISC ’02). Springer-Verlag, London, UK, UK, 265–279. http://dl.acm.org/citation.cfm?id=645959.676137
11. Danny Hendler, Nir Shavit, and Lena Yerushalmi. 2004. A Scalable Lock-free Stack Algorithm. In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’04). ACM, New York, NY, USA, 206–215. DOI:
12. Maurice Herlihy, Victor Luchangco, and Mark Moir. 2003a. Obstruction-Free Synchronization: Double-Ended Queues As an Example. In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS ’03). IEEE Computer Society, Washington, DC, USA, 522–. http://dl.acm.org/citation.cfm?id=850929.851942
13. Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer, III. 2003b. Software Transactional Memory for Dynamic-sized Data Structures. In Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing (PODC ’03). ACM, New York, NY, USA, 92–101. DOI:
14. Maurice P. Herlihy and Jeannette M. Wing. 1990. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12, 3 (July 1990), 463–492. DOI:
15. Scott Kilpatrick, Derek Dreyer, Simon Peyton Jones, and Simon Marlow. 2014. Backpack: retrofitting Haskell with interfaces. In ACM SIGPLAN Notices, Vol. 49. ACM, 19–31.
16. Amlan Kusum, Iulian Neamtiu, and Rajiv Gupta. 2016. Safe and Flexible Adaptation via Alternate Data Structure Representations. In Proceedings of the 25th International Conference on Compiler Construction (CC 2016). ACM, New York, NY, USA, 34–44. DOI:
17. K. Rustan Leino, Peter Müller, and Angela Wallenburg. 2008. Flexible Immutability with Frozen Objects. In Proceedings of the 2Nd International Conference on Verified Software: Theories, Tools, Experiments (VSTTE ’08). Springer-Verlag, Berlin, Heidelberg, 192–208. DOI:
18. Simon Marlow, Ryan R. Newton, and Simon Peyton Jones. 2011. A monad for deterministic parallelism. In Proceedings of the 4th ACM symposium on Haskell (Haskell ’11). ACM, 71–82.
19. Faisal Nawab, Dhruva R Chakrabarti, Terence Kelly, and Charles B Morrey III. 2015. Procrastination Beats Prevention: Timely Sufficient Persistence for Efficient Crash Resilience.. In EDBT. 689–694.
20. Ryan R. Newton, Peter P. Fogg, and Ali Varamesh. 2015. Adaptive Lock-free Maps: Purely-functional to Scalable. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming (ICFP 2015). ACM, New York, NY, USA, 218–229. DOI:
21. Rishiyur S. Nikhil. 1991. ID Language Reference Manual. (1991).
22. Simon Peyton Jones, Andrew Gordon, and Sigbjorn Finne. 1996. Concurrent Haskell. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’96). ACM, New York, NY, USA, 295–308. DOI:
23. Simon Peyton Jones, Alastair Reid, Fergus Henderson, Tony Hoare, and Simon Marlow. 1999. A semantics for imprecise exceptions. In ACM SIGPLAN Notices, Vol. 34. ACM, 25–36.
24. Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky. 2012. Concurrent Tries with Efficient Non-blocking Snapshots. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’12). ACM, New York, NY, USA, 151–160. DOI:
25. Ori Shalev and Nir Shavit. 2006. Split-ordered Lists: Lock-free Extensible Hash Tables. J. ACM 53, 3 (May 2006), 379–405. DOI:
26. Michael Vollmer, Ryan G. Scott, Madan Musuvathi, and Ryan R. Newton. 2017. SC-Haskell: Sequential Consistency in Languages that Minimize Mutable Shared Heap. In To appear in the proceedings of the 22st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’17). ACM, New York, NY, USA.
27. Guoqing Xu. 2013. CoCo: Sound and Adaptive Replacement of Java Collections. In Proceedings of the 27th European Conference on Object-Oriented Programming (ECOOP’13). Springer-Verlag, Berlin, Heidelberg, 1–26. DOI:
28. Edward Z. Yang, Giovanni Campagna, Ömer S. Ağacan, Ahmed El-Hassany, Abhishek Kulkarni, and Ryan R. Newton. 2015. Efficient Communication and Collection with Compact Normal Forms. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming (ICFP 2015). ACM, New York, NY, USA, 362–374. DOI:

Index Terms

• Computing methodologies

  • Concurrent computing methodologies

    • Concurrent algorithms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Functional languages