research-article

Comparing the performance of concurrent linked-list implementations in Haskell

Authors:

Martin Sulzmann,

Edmund S.L. Lam,

Simon MarlowAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 5

Pages 11 - 20

https://doi.org/10.1145/1629635.1629643

Published: 06 October 2009 Publication History

Get Access

Abstract

Haskell has a rich set of synchronization primitives for implementing shared-state concurrency abstractions, ranging from the very high level (Software Transactional Memory) to the very low level (mutable variables with atomic read-modify-write).

In this paper we perform a systematic comparison of these different concurrent programming models by using them to implement the same abstraction: a concurrent linked-list. Our results are somewhat surprising: there is a full two orders of magnitude difference in performance between the slowest and the fastest implementation. Our analysis of the performance results gives new insights into the relative performance of the programming models and their implementation.

Finally, we suggest the addition of a single primitive which in our experiments improves the performance of one of the STM-based implementations by more than a factor of 7.

References

[1]

R. Bayer and M. Schkolnick. Concurrency of operations on b-trees. pages 129--139, 1988.

Digital Library

Google Scholar

[2]

H.-J. Boehm and S.V. Adve. Foundations of the c++ concurrency memory model. In Proc. of PLDI'08, pages 68--78. ACM Press, 2008.

Crossref

Google Scholar

[3]

K. Fraser and T. Harris. Concurrent programming without locks. ACM Trans. Comput. Syst., 25(2):5, 2007.

Digital Library

Google Scholar

[4]

Glasgow haskell compiler home page. http://www.haskell.org/ghc/.

Google Scholar

[5]

T. Harris, S. Marlow, S. Peyton Jones, and M. Herlihy. Composable memory transactions. In Proc. of PPoPP'05, pages 48--60. ACM Press, 2005.

Crossref

Google Scholar

[6]

T.L. Harris. A pragmatic implementation of non-blocking linkedlists. In LNCS, volume 2180, pages 300--314. Springer-Verlag, 2001.

Digital Library

Google Scholar

[7]

M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In Proc. of PPoPP'08, pages 207--216. ACM Press, 2008.

Crossref

Google Scholar

[8]

J. Manson, W. Pugh, and S.V. Adve. The Java memory model. In Proc. of POPL'05, pages 378--391. ACM Press, 2005.

Crossref

Google Scholar

[9]

S. Marlow, S.L. Peyton Jones, A. Moran, and J. Reppy. Asynchronous exceptions in Haskell. In ACM Conference on Programming Languages Design and Implementation (PLDI'01), pages 274--285, Snowbird, Utah, June 2001. ACM Press.

Digital Library

Google Scholar

[10]

C. Perfumo, N. Sönmez, S. Stipic, O.S. Unsal, A. Cristal, T. Harris, and M. Valero. The limits of software transactional memory (stm): dissecting haskell stm applications on a many-core environment. In Proc. of 5th Conference on Computing Frontiers, pages 67--78. ACM Press, 2008.

Digital Library

Google Scholar

[11]

S. Peyton Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.

Google Scholar

[12]

S. Peyton Jones, A. Gordon, and S. Finne. Concurrent Haskell. In Proc. of POPL'96, pages 295--308. ACM Press, 1996.

Crossref

Google Scholar

[13]

N. Sonmez, C. Perfumo, S. Stipic, A. Cristal, O.S. Unsal, and M. Valero. unreadTVar: Extending haskell software transactional memory for performance. In Proc. of Eighth Symposium on Trends in Functional Programming (TFP 2007), 2007.

Google Scholar

Cited By

View all

Duarte RDu Bois APilla MCavalheiro GReiser R(2016)Concurrent Hash Tables for HaskellProgramming Languages10.1007/978-3-319-45279-1_8(110-124)Online publication date: 17-Sep-2016
https://doi.org/10.1007/978-3-319-45279-1_8
Du Bois APilla MDuarte R(2014)Transactional Boosting for HaskellProgramming Languages10.1007/978-3-319-11863-5_11(145-159)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11863-5_11
Du Bois A(2011)An implementation of composable memory transactions in HaskellProceedings of the 10th international conference on Software composition10.5555/2025951.2025955(34-50)Online publication date: 30-Jun-2011
https://dl.acm.org/doi/10.5555/2025951.2025955
Show More Cited By

Index Terms

Comparing the performance of concurrent linked-list implementations in Haskell
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Comparing the performance of concurrent linked-list implementations in Haskell
DAMP '09: Proceedings of the 4th workshop on Declarative aspects of multicore programming

Haskell has a rich set of synchronization primitives for implementing shared-state concurrency abstractions, ranging from the very high level (Software Transactional Memory) to the very low level (mutable variables with atomic read-modify-write).

In ...
Comparing the performance of concurrent linked-list implementations in Haskell (abstract only)

Haskell has a rich set of synchronization primitives for implementing shared-state concurrency abstractions, ranging from the very high level (Software Transactional Memory) to the very low level (mutable variables with atomic read-modifywrite).

In this ...
Looking for efficient implementations of concurrent objects
PaCT'11: Proceedings of the 11th international conference on Parallel computing technologies

As introduced by Taubenfeld, a contention-sensitive implementation of a concurrent object is an implementation such that the overhead introduced by locking is eliminated in the common cases, i.e., when there is no contention or when the operations ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 44, Issue 5

May 2009

19 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1629635

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 October 2009

Published in SIGPLAN Volume 44, Issue 5

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
161
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Duarte RDu Bois APilla MCavalheiro GReiser R(2016)Concurrent Hash Tables for HaskellProgramming Languages10.1007/978-3-319-45279-1_8(110-124)Online publication date: 17-Sep-2016
https://doi.org/10.1007/978-3-319-45279-1_8
Du Bois APilla MDuarte R(2014)Transactional Boosting for HaskellProgramming Languages10.1007/978-3-319-11863-5_11(145-159)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11863-5_11
Du Bois A(2011)An implementation of composable memory transactions in HaskellProceedings of the 10th international conference on Software composition10.5555/2025951.2025955(34-50)Online publication date: 30-Jun-2011
https://dl.acm.org/doi/10.5555/2025951.2025955
Du Bois A(2011)An Implementation of Composable Memory Transactions in HaskellSoftware Composition10.1007/978-3-642-22045-6_3(34-50)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22045-6_3

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Comparing the performance of concurrent linked-list implementations in Haskell

Comparing the performance of concurrent linked-list implementations in Haskell (abstract only)

Looking for efficient implementations of concurrent objects