research-article

Transactional predication: high-performance concurrent sets and maps for STM

Authors:

Nathan G. Bronson,

Kunle OlukotunAuthors Info & Claims

PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 6 - 15

https://doi.org/10.1145/1835698.1835703

Published: 25 July 2010 Publication History

Abstract

Concurrent collection classes are widely used in multi-threaded programming, but they provide atomicity only for a fixed set of operations. Software transactional memory (STM) provides a convenient and powerful programming model for composing atomic operations, but concurrent collection algorithms that allow their operations to be composed using STM are significantly slower than their non-composable alternatives.

We introduce transactional predication, a method for building transactional maps and sets on top of an underlying non-composable concurrent map. We factor the work of most collection operations into two parts: a portion that does not need atomicity or isolation, and a single transactional memory access. The result approximates semantic conflict detection using the STM's structural conflict detection mechanism. The separation also allows extra optimizations when the collection is used outside a transaction. We perform an experimental evaluation that shows that predication has better performance than existing transactional collection algorithms across a range of workloads.

References

[1]

J. Bobba, K. E. Moore, H. Volos, L. Yen, M. D. Hill, M. M. Swift, and D. A. Wood. Performance pathologies in hardware transactional memory. In ISCA '07: Proceedings of the 34th Annual International Symposium on Computer Architecture, pages 81--91, New York, NY, USA, 2007. ACM.

Digital Library

[2]

N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. In PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 257--268, New York, NY, USA, January 2010. ACM.

Digital Library

[3]

N. G. Bronson, H. Chafi, and K. Olukotun. CCSTM : A library-based STM for Scala. In The First Annual Scala Workshop at Scala Days 2010, April 2010.

[4]

B. D. Carlstrom, A. McDonald, M. Carbin, C. Kozyrakis, and K. Olukotun. Transactional collection classes. In PPoPP '07: Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 56--67, New York, NY, USA, 2007. ACM Press.

Digital Library

[5]

C. Cascaval, C. Blundell, M. Michael, H. W. Cain, P. Wu, S. Chiras, and S. Chatterjee. Software transactional memory: Why is it only a research toy? Queue, 6(5):46--58, 2008.

Digital Library

[6]

D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In DISC '06: Proceedings of the 20th International Symposium on Distributed Computing, pages 194--208. Springer, March 2006.

Digital Library

[7]

A. Dragojević, R. Guerraoui, and M. Kapalka. Stretching transactional memory. In PLDI '09: Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, pages 155--165, New York, NY, USA, 2009. ACM.

Digital Library

[8]

P. Felber, V. Gramoli, and R. Guerraoui. Elastic transactions. In DISC '09: Proceedings of the 23rd International Symposium on Distributed Computing, pages 93--107. Springer, 2009.

Digital Library

[9]

R. Guerraoui, M. Herlihy, and B. Pochon. Toward a theory of transactional contention managers. In PODC '05: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, pages 258--264, New York, NY, USA, 2005. ACM.

Digital Library

[10]

R. Guerraoui and M. Kapalka. On the correctness of transactional memory. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 175--184, New York, NY, USA, 2008. ACM.

Digital Library

[11]

T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 48--60, New York, NY, USA, 2005. ACM.

Digital Library

[12]

T. Harris and S. Stipic. Abstract nested transactions. In TRANSACT '07: 2nd Workshop on Transactional Computing, August 2007.

[13]

M. Herlihy and E. Koskinen. Transactional Boosting: A methodology for highly-concurrent transactional objects. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 207--216, New York, NY, USA, 2008. ACM.

Digital Library

[14]

M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. A provably correct scalable concurrent skip list. In OPODIS '06: Proceedings of the 10th International Conference On Principles Of Distributed Systems, December 2006.

[15]

M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software transactional memory for dynamic-sized data structures. In PODC '03: Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, pages 92--101, New York, NY, USA, 2003. ACM.

Digital Library

[16]

M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, San Francisco, CA, USA, March 2008.

Digital Library

[17]

B. Hindman and D. Grossman. Atomicity via source-to-source translation. In MSPC '06: Proceedings of the 2006 Workshop on Memory System Performance and Correctness, pages 82--91, New York, NY, USA, 2006. ACM.

Digital Library

[18]

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 211--222, New York, NY, USA, 2007. ACM.

Digital Library

[19]

D. Lea. Concurrent hash map in JSR 166 concurrency utilities. http://gee.cs.oswego.edu/dl/concurrency-interest/index.html, December 2007.

[20]

M. M. Michael. Hazard P ointers: Safe memory reclamation for lock-free objects. IEEE Transactions on Parallel Distributed Systems, 15(6):491--504, 2004.

Digital Library

[21]

J. E. B. Moss. Open nested transactions: Semantics and support. In Poster at the 4th Workshop on Memory Performance Issues (WMPI-2006). February 2006.

[22]

Y. Ni, V. S. Menon, A.-R. Adl-Tabatabai, A. L. Hosking, R. L. Hudson, J. E. B. Moss, B. Saha, and T. Shpeisman. Open nesting in software transactional memory. In PPoPP '07: Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 68--78, New York, NY, USA, 2007. ACM Press.

Digital Library

[23]

B. Saha, A.-R. Adl-Tabatabai, R. L. Hudson, C. Cao Minh, and B. Hertzberg. McRT-STM: A high performance software transactional memory system for a multi-core runtime. In PPoPP '06: Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 187--197, New York, NY, USA, March 2006. ACM Press.

Digital Library

[24]

N. Shavit and D. Touitou. Software transactional memory. In PODC '95: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, pages 204--213, New York, NY, USA, 1995. ACM.

Digital Library

Cited By

Zhang JYi QPeterson CDechev D(2023)Compiler‐driven approach for automating nonblocking synchronization in concurrent data abstractionsConcurrency and Computation: Practice and Experience10.1002/cpe.793536:5Online publication date: 24-Oct-2023
https://doi.org/10.1002/cpe.7935
Dalvandi SDongol B(2022)Implementing and verifying release-acquire transactional memory in C11Proceedings of the ACM on Programming Languages10.1145/35633526:OOPSLA2(1817-1844)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563352
Chen AFathololumi PKoskinen EPincus J(2022)Veracity: declarative multicore programming with commutativityProceedings of the ACM on Programming Languages10.1145/35633496:OOPSLA2(1726-1756)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563349
Show More Cited By

Recommendations

Safe privatization in transactional memory
PPoPP '18

Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...
An efficient software transactional memory using commit-time invalidation
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization

To improve the performance of transactional memory (TM), researchers have found many eager and lazy optimizations for conflict detection, the process of determining if transactions can commit. Despite these optimizations, nearly all TMs perform one ...
Safe privatization in transactional memory
PPoPP '18: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

July 2010

494 pages

ISBN:9781605588889

DOI:10.1145/1835698

General Chairs:
Andrea Richa
Arizona State University, USA
,
Rachid Guerraoui
EPFL, Switzerland

Copyright © 2010 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '10

Sponsor:

PODC '10: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2010

Zurich, Switzerland

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
342
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang JYi QPeterson CDechev D(2023)Compiler‐driven approach for automating nonblocking synchronization in concurrent data abstractionsConcurrency and Computation: Practice and Experience10.1002/cpe.793536:5Online publication date: 24-Oct-2023
https://doi.org/10.1002/cpe.7935
Dalvandi SDongol B(2022)Implementing and verifying release-acquire transactional memory in C11Proceedings of the ACM on Programming Languages10.1145/35633526:OOPSLA2(1817-1844)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563352
Chen AFathololumi PKoskinen EPincus J(2022)Veracity: declarative multicore programming with commutativityProceedings of the ACM on Programming Languages10.1145/35633496:OOPSLA2(1726-1756)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563349
Lesani MXia LKaseorg ABell CChlipala APierce BZdancewic S(2022)C4: verified transactional objectsProceedings of the ACM on Programming Languages10.1145/35273246:OOPSLA1(1-31)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527324
Patil MHoushmand FLesani MSen KNaik M(2020)Learning quantitative representation synthesisProceedings of the 4th ACM SIGPLAN International Workshop on Machine Learning and Programming Languages10.1145/3394450.3397467(29-37)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1145/3394450.3397467
Chen DGibbons PMowry T(2020)TardisTMProceedings of the Eleventh International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3380536.3380538(1-10)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3380536.3380538
LaBorde PLebanoff LPeterson CZhang DDechev D(2020)Dynamic Transactional TransformationConcurrency and Computation: Practice and Experience10.1002/cpe.573234:2Online publication date: 3-Apr-2020
https://doi.org/10.1002/cpe.5732
LaBorde PLebanoff LPeterson CZhang DDechev D(2019)Wait-free Dynamic Transactions for Linked Data StructuresProceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3303084.3309491(41-50)Online publication date: 17-Feb-2019
https://dl.acm.org/doi/10.1145/3303084.3309491
Zhang JYi QDechev DZimmermann TLawall JMarinov D(2019)Automating non-blocking synchronization in concurrent data abstractionsProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00074(735-747)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00074
Dickerson TGazzillo PHerlihy MKoskinen E(2019)Adding concurrency to smart contractsDistributed Computing10.1007/s00446-019-00357-zOnline publication date: 6-Jul-2019
https://doi.org/10.1007/s00446-019-00357-z
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents