research-article

Comparing the performance of concurrent linked-list implementations in Haskell

Authors:

Martin Sulzmann,

Edmund S.L. Lam,

Simon MarlowAuthors Info & Claims

DAMP '09: Proceedings of the 4th workshop on Declarative aspects of multicore programming

Pages 37 - 46

https://doi.org/10.1145/1481839.1481845

Published: 20 January 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.

Digital Library

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.

Digital Library

Google Scholar

[6]

T. L. Harris. A pragmatic implementation of non-blocking linked-lists. 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.

Digital Library

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.

Digital Library

Google Scholar

[9]

S Marlow, SL 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.

Digital Library

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

Conceição JDu Bois AFeitosa SCavalheiro GRibeiro RPolikarpova N(2022)Open transactional actions: interacting with non-transactional resources in STM HaskellProceedings of the 15th ACM SIGPLAN International Haskell Symposium10.1145/3546189.3549924(54-65)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1145/3546189.3549924
Le MYates RFluet M(2016)Revisiting software transactional memory in HaskellACM SIGPLAN Notices10.1145/3241625.297602051:12(105-113)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/3241625.2976020
Le MYates RFluet MMainland G(2016)Revisiting software transactional memory in HaskellProceedings of the 9th International Symposium on Haskell10.1145/2976002.2976020(105-113)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2976002.2976020
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

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 ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAMP '09: Proceedings of the 4th workshop on Declarative aspects of multicore programming

January 2009

76 pages

ISBN:9781605584171

DOI:10.1145/1481839

General Chair:
Leaf Petersen
Intel Corporation, USA
,
Program Chair:
Manuel Chakravarty
University of New South Wales, Australia

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 January 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL09

Sponsor:

POPL09: The 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 20, 2009

GA, Savannah, USA

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
297
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Conceição JDu Bois AFeitosa SCavalheiro GRibeiro RPolikarpova N(2022)Open transactional actions: interacting with non-transactional resources in STM HaskellProceedings of the 15th ACM SIGPLAN International Haskell Symposium10.1145/3546189.3549924(54-65)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1145/3546189.3549924
Le MYates RFluet M(2016)Revisiting software transactional memory in HaskellACM SIGPLAN Notices10.1145/3241625.297602051:12(105-113)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/3241625.2976020
Le MYates RFluet MMainland G(2016)Revisiting software transactional memory in HaskellProceedings of the 9th International Symposium on Haskell10.1145/2976002.2976020(105-113)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2976002.2976020
Wevers LHuisman Mvan Keulen MDesai BToyama MBernardino J(2016)Lazy Evaluation for Concurrent OLTP and Bulk TransactionsProceedings of the 20th International Database Engineering & Applications Symposium10.1145/2938503.2938555(115-124)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2938503.2938555
Veldema RPhilippsen M(2009)Safe and familiar multi-core programming by means of a hybrid functional and imperative languageProceedings of the 22nd international conference on Languages and Compilers for Parallel Computing10.1007/978-3-642-13374-9_11(157-171)Online publication date: 8-Oct-2009
https://dl.acm.org/doi/10.1007/978-3-642-13374-9_11

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

Looking for efficient implementations of concurrent objects

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