Partial aborts for transactions via first-class continuations

Abstract

Software transactional memory (STM) has proven to be a useful abstraction for developing concurrent applications, where programmers denote transactions with an atomic construct that delimits a collection of reads and writes to shared mutable references. The runtime system then guarantees that all transactions are observed to execute atomically with respect to each other. Traditionally, when the runtime system detects that one transaction conflicts with another, it aborts one of the transactions and restarts its execution from the beginning. This can lead to problems with both execution time and throughput. In this paper, we present a novel approach that uses first-class continuations to restart a conflicting transaction at the point of a conflict, avoiding the re-execution of any work from the beginning of the transaction that has not been compromised. In practice, this allows transactions to complete more quickly, decreasing execution time and increasing throughput. We have implemented this idea in the context of the Manticore project, an ML-family language with support for parallelism and concurrency. Crucially, we rely on constant-time continuation capturing via a continuation-passing-style (CPS) transformation and heap-allocated continuations. When comparing our STM that performs partial aborts against one that performs full aborts, we achieve a decrease in execution time of up to 31% and an increase in throughput of up to 351%.

References

1. {ABFR11} Auhagen, S., L. Bergstrom, M. Fluet, and J. Reppy. Garbage Collection for Multicore NUMA Machines. In MSPC 2011: Memory Systems Performance and Correctness, San José, California, USA, June 2011. ACM. {App89} Appel, A. W. Simple generational garbage collection and fast allocation. Software – Practice and Experience, 19(2), 1989, pp. 171–183. {App92} Appel, A. W. Compiling with Continuations. Cambridge University Press, Cambridge, England, 1992.
2. {Rep89} Reppy, J. H. First-class synchronous operations in Standard ML. Technical Report TR 89-1068, Department of Computer Science, Cornell University, December 1989.
3. {Rep99} Reppy, J. H. Concurrent Programming in ML. Cambridge University Press, Cambridge, England, 1999.
4. {RFF06} Riegel, T., P. Felber, and C. Fetzer. A lazy snapshot algorithm with eager validation. In Proceedings of the 20th International Distributed Computing Conference, vol. 4167 of Lecture Notes in Computer Science, Stockholm, Sweden, 2006. Springer-Verlag, pp. 284–298. {RFF07} Riegel, T., C. Fetzer, and P. Felber. Time-based transactional memory with scalable time bases. In SPAA ’07, San Diego, California, USA, 2007. ACM, pp. 221–228. {RP00} Ramsey, N. and S. Peyton Jones. Featherweight concurrency in a portable assembly language. Unpublished paper available at https://www.cs.tufts.edu/˜nr/ pubs/c--con-abstract.html, November 2000.
5. {RRX09} Reppy, J., C. Russo, and Y. Xiao. Parallel Concurrent ML. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming ICFP ’09, Edinburgh, Scotland, UK, August–September 2009. ACM, pp. 257–268. {SDMS09} Spear, M. F., L. Dalessandro, V. J. Marathe, and M. L. Scott. A comprehensive strategy for contention management in software transactional memory. In PPoPP ’09, Raleigh, NC, USA, 2009. ACM, pp. 141–150. {Shi97} Shivers, O. Continuations and threads: Expressing machine concurrency directly in advanced languages. In Proceedings of the Second ACM SIGPLAN Workshop on Continuations (CW ’97). ACM, January 1997.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features