[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1989493.1989500acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
research-article

A study of transactional memory vs. locks in practice

Published: 04 June 2011 Publication History

Abstract

Transactional Memory (TM) promises to simplify parallel programming by replacing locks with atomic transactions. Despite much recent progress in TM research, there is very little experience using TM to develop realistic parallel programs from scratch. In this paper, we present the results of a detailed case study comparing teams of programmers developing a parallel program from scratch using transactional memory and locks. We analyze and quantify in a realistic environment the development time, programming progress, code metrics, programming patterns, and ease of code understanding for six teams who each wrote a parallel desktop search engine over a fifteen week period. Three randomly chosen teams used Intel's Software Transactional Memory compiler and Pthreads, while the other teams used just Pthreads. Our analysis is exploratory: Given the same requirements, how far did each team get? The TM teams were among the first to have a prototype parallel search engine. Compared to the locks teams, the TM teams spent less than half the time debugging segmentation faults, but had more problems tuning performance and implementing queries. Code inspections with industry experts revealed that TM code was easier to understand than locks code, because the locks teams used many locks (up to thousands) to improve performance. Learning from each team's individual success and failure story, this paper provides valuable lessons for improving TM.

References

[1]
M. Ansari et al. Lee-TM: A non-trivial benchmark suite for transactional memory. In Algorithms and Architectures for Parallel Processing, pages 196--207, 2008.
[2]
™ bibliography. http://www.cs.wisc.edu/trans-memory/biblio/index.html, March 2011.
[3]
A.-R. Adl-Tabatabai and T. Shpeisman (editors). Draft specification of transactional language constructs for C++ (v.1.0), 2009.
[4]
A.-R. Adl-Tabatabai et al. Compiler and runtime support for efficient software transactional memory. In Proc. ACM PLDI '06, pages 26--37, 2006.
[5]
D. Bacon et al. The "double-checked locking is broken" declaration. http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html, Dec. 2010.
[6]
W. Baek et al. The Open™ transactional application programming interface. In Proc. ACM PACT '07, 2007.
[7]
R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, May 1999.
[8]
C. Bienia et al. The PARSEC benchmark suite: characterization and architectural implications. In Proc. ACM PACT '08, pages 72--81, 2008.
[9]
C. Cascaval et al. Software transactional memory: why is it only a research toy? Commun. ACM, 51(11):40--46, 2008.
[10]
P. Damron et al. Hybrid transactional memory. In Proc. ACM ASPLOS-XII, pages 336--346, 2006.
[11]
R. Guerraoui et al. STMBench7: a benchmark for software transactional memory. SIGOPS OSR, 41(3), 2007.
[12]
T. Harris et al. Composable memory transactions. In Proc. ACM PPoPP '05, pages 48--60, 2005.
[13]
S. Heinz et al. Burst tries: a fast, efficient data structure for string keys. ACM Trans. Inf. Syst., 20(2):192--223, 2002.
[14]
M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In Proc. ACM ISCA '93, pages 289--300, 1993.
[15]
Intel. Intel C++STM compiler prototype edition 2.0. language extensions and user's guide, 2008.
[16]
C. J.Rossbach et al. Txlinux: using and managing hardware transactional memory in an operating system. In Proc. ACM SOSP '07, pages 87--102, 2007.
[17]
S. Kumar et al. Hybrid transactional memory. In Proc. ACM PPoPP '06, pages 209--220, 2006.
[18]
N. Lester et al. Efficient online index construction for text databases. ACM Trans. Database Syst., 33(3):1--33, 2008.
[19]
C. C. Minh et al. STAMP: Stanford transactional applications for multi-processing. In Proc. IISWC, 2008.
[20]
K. Moore et al. LogTM: log-based transactional memory. In Proc. HPCA'06, pages 254--265, 2006.
[21]
Y. Ni et al. Design and implementation of transactional constructs for C/C++. In Proc. ACM OOPSLA, 2008.
[22]
V. Pankratius et al. Does transactional memory keep its promises? Results from an empirical study. Technical report, 2009-12, University of Karlsruhe, Germany, 2009.
[23]
M. F. Ringenburg and D. Grossman. AtomCaml: first-class atomicity via rollback. In Proc. ACM ICFP, 2005.
[24]
C. J. Rossbach et al. Is transactional programming actually easier? In Proc. ACM PPoPP, 2010.
[25]
P. Runeson and M. Höst. Guidelines for conducting and reporting case study research in software engineering. Empirical Software Engineering, 14(2):131--164, 2009.
[26]
B. Saha et al. McRT-STM: a high performance software transactional memory system for a multi-core runtime. In Proc. ACM PPoPP '06, pages 187--197, 2006.
[27]
M. Scott et al. Delaunay triangulation with transactions and barriers. In Proc. IEEE IISWC, 2007.
[28]
N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, V10(2):99--116, 1997.
[29]
Standard Performance Evaluation Corporation. SPEC OpenMP Benchmark Suite. www.spec.org/omp, 2009.
[30]
I. Watson et al. A study of a transactional parallel routing algorithm. In Proc. ACM PACT '07, pages 388--398, 2007.
[31]
S. C. Woo et al. The SPLASH-2 programs: characterization and methodological considerations. In ACM ISCA, 1995.
[32]
R. K. Yin. Case Study Research: Design and Methods. Sage Publications, Inc, 3rd edition, 2002.
[33]
C. Zannier et al. On the success of empirical studies in the International Conference on Software Engineering. In Proc. ACM ICSE '06, pages 341--350, 2006.
[34]
F. Zyulkyarov et al. Atomic quake: using transactional memory in an interactive multiplayer game server. In Proc. ACM PPoPP '09, pages 25--34, 2009.

Cited By

View all
  • (2024)When Is Parallelism Fearless and Zero-Cost with Rust?Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659966(27-40)Online publication date: 17-Jun-2024
  • (2024)PIM-STM: Software Transactional Memory for Processing-In-Memory SystemsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640428(897-911)Online publication date: 27-Apr-2024
  • (2023)Survey of Hallucination in Natural Language GenerationACM Computing Surveys10.1145/357173055:12(1-38)Online publication date: 3-Mar-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SPAA '11: Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures
June 2011
404 pages
ISBN:9781450307437
DOI:10.1145/1989493
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

In-Cooperation

  • EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2011

Permissions

Request permissions for this article.

Check for updates

Author Tag

  1. transactional memory

Qualifiers

  • Research-article

Conference

SPAA '11

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)When Is Parallelism Fearless and Zero-Cost with Rust?Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659966(27-40)Online publication date: 17-Jun-2024
  • (2024)PIM-STM: Software Transactional Memory for Processing-In-Memory SystemsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640428(897-911)Online publication date: 27-Apr-2024
  • (2023)Survey of Hallucination in Natural Language GenerationACM Computing Surveys10.1145/357173055:12(1-38)Online publication date: 3-Mar-2023
  • (2023)15 Years of (Who)man Robot Interaction: Reviewing the H in Human-Robot InteractionACM Transactions on Human-Robot Interaction10.1145/357171812:3(1-28)Online publication date: 14-Apr-2023
  • (2023)User Perception of Recommendation Explanation: Are Your Explanations What Users Need?ACM Transactions on Information Systems10.1145/356548041:2(1-31)Online publication date: 25-Jan-2023
  • (2022)Applications of Big Data Analytics in Investment ManagementJournal of Database Management10.4018/JDM.29955733:1(1-32)Online publication date: 23-May-2022
  • (2022)A Temporal JSON Data Model and Its Query LanguagesJournal of Database Management10.4018/JDM.29955633:1(1-29)Online publication date: 23-May-2022
  • (2022)HyTM-AP Hybrid Transactional Memory Scheme Using Abort Prediction and Adaptive Retry Policy for Multi-Core In-Memory DatabasesJournal of Database Management10.4018/JDM.29955533:1(1-22)Online publication date: 29-Jun-2022
  • (2021)A Graph Transformation System formalism for correctness of Transactional Memory algorithmsProceedings of the 25th Brazilian Symposium on Programming Languages10.1145/3475061.3475080(49-57)Online publication date: 27-Sep-2021
  • (2021)Investigating the semantics of futures in transactional memory systemsProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441594(16-30)Online publication date: 17-Feb-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media