Article

An implementation of composable memory transactions in Haskell

Author:

André Rauber Du BoisAuthors Info & Claims

SC'11: Proceedings of the 10th international conference on Software composition

Pages 34 - 50

Published: 30 June 2011 Publication History

Abstract

This paper describes an implementation of STM Haskell [11] in Haskell using the Transactional Locking 2 (TL2) algorithm by Dice, Shalev, and Shavit. TL2 provides an important characteristic that makes it suitable for implementing transactions as a library: it efficiently avoids periods of unsafe execution, guaranteeing that transactions always see a consistent state of memory. Preliminary measurements suggest that our library performs reasonably well, and provides similar scalability to the original STM Haskell runtime system, that was implemented in C. The implementation presented in this paper could work as a testbed to experiment with new extensions for STM Haskell. As an example, we demonstrate how to modify the basic library to support the unreadTVar [20] construct.

References

[1]

Heterogenous collections in Haskell (October 2010), http://www.haskell.org/haskellwiki/Hete\discretionary-rogenous_collections

[2]

The Haskell STM Benchmark. WWW page (October 2010), http://www.bscmsrc.eu/software/haskell-stm-benchmark

[3]

Twilight STM for Haskell. WWW page (October 2010), http://proglang.informatik.uni-freiburg.de/projects/twilight/

[4]

TL2 STM Haskell. WWW page (February 2011), https://sites.google.com/site/tl2stmhaskell/STM.hs

[5]

Bieniusa, A., Middelkoop, A., Thiermann, P.: Twilight in Haskell: Software Transactional Memory with Safe I/O and Typed Conflict Management. In: Preprocedings of IFL 2010 (September 2010).

[6]

Dice, D., Shalev, O., Shavit, N.N.: Transactional locking II. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 194-208. Springer, Heidelberg (2006).

Digital Library

[7]

Felber, P., Fetzer, C., Riegel, T.: Dynamic performance tuning of word-based software transactional memory. In: PPoPP 2008, pp. 237-246. ACM, New York (2008).

Digital Library

[8]

Harris, T., Fraser, K.: Language support for lightweight transactions. SIGPLAN Not. 38(11), 388-402 (2003).

Digital Library

[9]

Harris, T., Larus, J.R., Rajwar, R.: Transactional Memory, 2nd edn. Morgan & Claypool Publishers, San Francisco (2010).

Digital Library

[10]

Harris, T., Marlow, S., Peyton Jones, S.: Haskell on a shared-memory multiprocessor. In: Haskell Workshop 2005, pp. 49-61. ACM, New York (2005).

Digital Library

[11]

Harris, T., Marlow, S., Peyton Jones, S., Herlihy, M.: Composable memory transactions. In: PPoPP 2005. ACM Press, New York (2005).

Digital Library

[12]

Harris, T., Peyton Jones, S.: Transactional memory with data invariants. In: TRANSACT 2006 (June 2006).

[13]

Harris, T., Plesko, M., Shinnar, A., Tarditi, D.: Optimizing memory transactions. SIGPLAN Not. 41(6), 14-25 (2006).

Digital Library

[14]

Huch, F., Kupke, F.: A high-level implementation of composable memory transactions in concurrent haskell. In: IFL, pp. 124-141 (2005).

Digital Library

[15]

Kiselyov, O., Lämmel, R., Schupke, K.: Strongly typed heterogeneous collections. In: Haskell Workshop 2004, pp. 96-107. ACM Press, New York (2004).

Digital Library

[16]

Lourenço, A., Cunha, G.: Testing patterns for software transactional memory engines. In: PADTAD 2007, pp. 36-42. ACM, New York (2007).

Digital Library

[17]

Perfumo, C., Sönmez, N., Stipic, S., Unsal, O., Cristal, A., Harris, T., Valero, M.: The limits of software transactional memory (STM): dissecting haskell stm applications on a many-core environment. In: CF 2008, pp. 67-78. ACM Press, New York (2008).

Digital Library

[18]

Peyton Jones, S., Marlow, S., Elliot, C.: Stretching the storage manager: weak pointers and stable names in haskell. In: Koopman, P., Clack, C. (eds.) IFL 1999. LNCS, vol. 1868, Springer, Heidelberg (2000).

Digital Library

[19]

Riegel, T., Felber, P., Fetzer, C.: A Lazy Snapshot Algorithm with Eager Validation, pp. 284-298 (2006).

Digital Library

[20]

Sonmez, N., Perfumo, C., Stipic, S., Cristal, A., Unsal, O.S., Valero, M.: Unreadtvar: Extending Haskell software transactional memory for performance. In: Trends in Functional Programming, vol. 8. Intellect Books (2008).

[21]

Sulzmann, M., Lam, E.S., Marlow, S.: Comparing the performance of concurrent linked-list implementations in Haskell. SIGPLAN Not. 44(5), 11-20 (2009).

Digital Library

[22]

Zhang, R., Budimlic, Z., Scherer III., W.N.: Commit phase in timestamp-based STM. In: SPAA 2008, pp. 326-335. ACM Press, New York (2008).

Digital Library

Cited By

Duarte RDu Bois APilla MCavalheiro GWainwright RCorchado JBechini AHong J(2015)Composable memory transactions with eager version managementProceedings of the 30th Annual ACM Symposium on Applied Computing10.1145/2695664.2695816(2093-2098)Online publication date: 13-Apr-2015
https://dl.acm.org/doi/10.1145/2695664.2695816

An implementation of composable memory transactions in Haskell
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types

Recommendations

A high-level implementation of composable memory transactions in concurrent haskell
IFL'05: Proceedings of the 17th international conference on Implementation and Application of Functional Languages

Composable memory transactions are a new communication abstraction for Concurrent Haskell which provides the programmer with a composable communication concept. Unfortunately, composable memory transactions are implemented as external functions for ghc ...
Composable memory transactions
PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming

Writing concurrent programs is notoriously difficult, and is of increasing practical importance. A particular source of concern is that even correctly-implemented concurrency abstractions cannot be composed together to form larger abstractions. In this ...
Composable memory transactions with eager version management
SAC '15: Proceedings of the 30th Annual ACM Symposium on Applied Computing

STM Haskell extends the Haskell functional programming language with a set of primitives for writing composable memory transactions. STM Haskell employs lazy version management and lazy conflict detection algorithms. This paper describes a new ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SC'11: Proceedings of the 10th international conference on Software composition

June 2011

181 pages

ISBN:9783642220449

Editors:
Sven Apel
University of Passau, Passau, Germany
,
Ethan Jackson
Microsoft Research, Redmond, WA

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 30 June 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Duarte RDu Bois APilla MCavalheiro GWainwright RCorchado JBechini AHong J(2015)Composable memory transactions with eager version managementProceedings of the 30th Annual ACM Symposium on Applied Computing10.1145/2695664.2695816(2093-2098)Online publication date: 13-Apr-2015
https://dl.acm.org/doi/10.1145/2695664.2695816

View Options

View options

Media

Figures

Other

Tables

View Table of Contents