Type-aware transactions for faster concurrent code

ABSTRACT

It is often possible to improve a concurrent system's performance by leveraging the semantics of its datatypes. We build a new software transactional memory (STM) around this observation. A conventional STM tracks read- and write-sets of memory words; even simple operations can generate large sets. Our STM, which we call STO, tracks abstract operations on transactional datatypes instead. Parts of the transactional commit protocol are delegated to these datatypes' implementations, which can use datatype semantics, and new commit protocol features, to reduce bookkeeping, limit false conflicts, and implement efficient concurrency control. We test these ideas on the STAMP benchmark suite for STM applications and on our own prior work, the Silo high-performance in-memory database, observing large performance improvements in both systems.

References

1. B. R. Badrinath and K. Ramamritham. Semantics-based concurrency control: Beyond commutativity. ACM Transactions on Database Systems, 17(1):163--199, Mar. 1992.
2. N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. Transactional predication: High-performance concurrent sets and maps for STM. In Proc. PODC '10 (29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing), pages 6--15. ACM, 2010.
3. J. Cachopo and A. Rito-Silva. Versioned boxes as the basis for memory transactions. Science of Computer Programming, 63:172--185, Dec. 2006.
4. I. Calciu, J. Gottschlich, T. Shpeisman, G. Pokam, and M. Herlihy. Invyswell: A hybrid transactional memory for Haswell's Restricted Transactional Memory. In Proc. PACT '14 (23rd International Conference on Parallel Architectures and Compilation), pages 187--200. ACM, 2014.
5. B. D. Carlstrom, A. McDonald, M. Carbin, C. Kozyrakis, and K. Olukotun. Transactional collection classes. In Proc. PPoPP '07 (12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 56--67. ACM, 2007.
6. F. M. Carvalho and J. Cachopo. STM with transparent API considered harmful. In Proc. ICA3PP '11 (11th International Conference on Algorithms and Architectures for Parallel Processing), LNCS 7016, Melbourne, Australia, Oct. Springer.
7. 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? Communications of the ACM, 51(11), Nov. 2008.
8. A. T. Clements, M. F. Kaashoek, N. Zeldovich, R. T. Morris, and E. Kohler. The scalable commutativity rule: Designing scalable software for multicore processors. In Proc. SOSP '13 (24th ACM Symposium on Operating Systems Principles), Farmington, PA, Nov. 2013.
9. L. Dalessandro, M. F. Spear, and M. L. Scott. NOrec: Streamlining STM by abolishing ownership records. In Proc. PPoPP '10 (15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 67--78. ACM, 2010.
10. L. Dalessandro, F. Carouge, S. White, Y. Lev, M. Moir, M. L. Scott, and M. F. Spear. Hybrid NOrec: A case study in the effectiveness of best effort hardware transactional memory. SIGARCH Computer Architecture News, 39(1):39--52, Mar. 2011.
11. P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid transactional memory. In Proc. ASPLOS '06 (12th International Conference on Architectural Support for Programming Languages and Operating Systems), pages 336--346. ACM, 2006.
12. D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In Proc. DISC '06 (20th International Conference on Distributed Computing), Stockholm, Sept. 2006.
13. A. Dragojević and T. Harris. STM in the small: Trading generality for performance in software transactional memory. In Proc. EuroSys'12 (7th European Conference on Computer Systems), Bern, Switzerland, Apr. 2012.
14. A. Dragojević, R. Guerraoui, and M. Kapałka. Stretching transactional memory. In Proc. PLDI '09 (ACM SIGPLAN 2009 Conference on Programming Language Design and Implementation), Dublin, June 2009.
15. K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Communications of ACM, 19(11):624--633, Nov. 1976.
16. P. Felber, V. Gramoli, and R. Guerraoui. Elastic transactions. In Proc. DISC '09 (23rd International Conference on Distributed Computing), pages 93--107, Berlin, Heidelberg, 2009. Springer-Verlag.
17. S. M. Fernandes and J. Cachopo. A scalable and efficient commit algorithm for the JVSTM. In Proc. TRANSACT 2010 (5th ACM SIGPLAN Workshop on Transactional Computing), Paris, Apr. 2010.
18. S. M. Fernandes and J. Cachopo. Lock-free and scalable multi-version software transactional memory. In Proc. PPoPP '11 (16th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming), San Antonio, TX, Feb. 2011.
19. K. Fraser. Practical Lock-freedom. PhD thesis, University of Cambridge, 2004.
20. G. Golan-Gueta, G. Ramalingam, M. Sagiv, and E. Yahav. Automatic scalable atomicity via semantic locking. In Proc. PPoPP '15 (20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 31--41. ACM, 2015.
21. R. Guerraoui and M. Kapalka. On the correctness of transactional memory. In Proc. PPoPP '08 (13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 175--184. ACM, 2008.
22. T. Harris, J. Larus, and R. Rajwar. Transactional Memory. Morgan and Claypool Publishers, 2nd edition, 2010.
23. A. Hassan, R. Palmieri, and B. Ravindran. Optimistic transactional boosting. In Proc. PPoPP '14 (19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 387--388, Orlando, FL, 2014. ACM.
24. A. Hassan, R. Palmieri, and B. Ravindran. On developing optimistic transactional lazy set. In Proc. OPODIS '14 (18th International Conference on Principles of Distributed Systems), LNCS 8878, pages 437--452, Cortina d'Ampezzo, Italy, 2014. Springer-Verlag.
25. M. Herlihy and E. Koskinen. Transactional boosting: A methodology for highly-concurrent transactional objects. In Proc. PPoPP '08 (13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 207--216. ACM, 2008.
26. M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proc. ISCA '93 (20th Annual International Symposium on Computer Architecture), pages 289--300. ACM Press, 1993.
27. M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufmann, 2008.
28. M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized lock-free data structures. In Proc. PODC '02 (21st Symposium on Principles of Distributed Computing), pages 131--131. ACM, 2002.
29. M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer, III. Software transactional memory for dynamic-sized data structures. In Proc. PODC '03 (22nd Annual Symposium on Principles of Distributed Computing), pages 92--101. ACM, 2003.
30. M. P. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programing Languages and Systems, 12(3):463--492, July 1990.
31. H. F. Korth. Locking primitives in a database system. Journal of ACM, 30(1):55--79, Jan. 1983.
32. M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. In Proc. PLDI '07 (ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation), pages 211--222, San Diego, CA, 2007. ACM.
33. M. Kulkarni, D. Nguyen, D. Prountzos, X. Sui, and K. Pingali. Exploiting the commutativity lattice. In Proc. PLDI '11 (32nd ACM SIGPLAN Conference on Programming Language Design and Implementation), pages 542--555, San Jose, CA, 2011. ACM.
34. H.-T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM Transactions on Database Systems (TODS), 6(2):213--226, 1981.
35. M. Lesani and J. Palsberg. Decomposing opacity. In Proc. DISC '14 (28th International Conference on Distributed Computing), 2014.
36. Y. Mao, E. Kohler, and R. Morris. Cache craftiness for fast multicore key-value storage. In Proc. EuroSys'12 (7th European Conference on Computer Systems), Bern, Switzerland, Apr. 2012.
37. A. Matveev and N. Shavit. Reduced hardware NOrec: A safe and scalable hybrid transactional memory. In Proc. ASPLOS '15 (20th International Conference on Architectural Support for Programming Languages and Operating Systems), pages 59--71, Istanbul, 2015. ACM.
38. P. E. McKenney and J. D. Slingwine. Read-copy update: Using execution history to solve concurrency problems. In Proc. PDCS '98 (10th IASTED International Conference on Parallel and Distributed Computing and Systems), pages 509--518, Las Vegas, NV, October 1998.
39. C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In Proc. IISWC '08 (4th International Symposium on Workload Characterization), 2008.
40. 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 Proc. PPoPP '07 (12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 68--78, San Jose, CA, 2007. ACM.
41. L. Pina and J. Cachopo. Profiling and tuning the performance of an STM-based concurrent program. In Proc. TMC '11 (Workshop on Transitioning to MultiCore, part of SPLASH '11, ACM SIGPLAN Conference on Systems, Programming, and Applications: Software for Humanity), Portland, OR, Oct. 2011.
42. T. Riegel, P. Felber, and C. Fetzer. A lazy snapshot algorithm with eager validation. In Proc. DISC '06 (20th International Conference on Distributed Computing), pages 284--298, Stockholm, 2006. Springer-Verlag.
43. W. Ruan and M. Spear. Hybrid transactional memory re-visited. In Distributed Computing, pages 215--231. Springer, 2015.
44. W. Ruan, Y. Liu, and M. Spear. STAMP need not be considered harmful. In TRANSACT'14 (9th ACM SIGPLAN Workshop on Transactional Computing), 2014.
45. P. M. Schwarz and A. Z. Spector. Synchronizing shared abstract types. ACM Transactions on Computer Systems, 2 (3):223--250, Aug. 1984.
46. M. Shapiro, N. Preguica, C. Baquero, and M. Zawirski. Conflict-free replicated data types. In Proc. SSS '11 (13th International Conference on Stabilization, Safety, and Security of Distributed Systems), pages 386--400, Grenoble, France, 2011. Springer-Verlag.
47. The Transaction Processing Council. TPC-C benchmark (revision 5.9.0). http://www.tpc.org/tpcc/, June 2007.
48. S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy transactions in multicore in-memory databases. In Proc. SOSP '13 (24th ACM Symposium on Operating Systems Principles), pages 18--32. ACM, 2013.
49. W. E. Weihl. Commutativity-based concurrency control for abstract data types. IEEE Transactions on Computing, 37(12): 1488--1505, Dec. 1988.
50. L. Xiang and M. L. Scott. Software partitioning of hardware transactions. In Proc. PPoPP '15 (20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 76--86. ACM, 2015.
51. R. M. Yoo, C. J. Hughes, K. Lai, and R. Rajwar. Performance evaluation of Intel Transactional Synchronization Extensions for high-performance computing. In Proc. SC'13 (International Conference for High Performance Computing, Networking, Storage and Analysis), Denver, CO, Nov. 2013.
52. M. Zhang, J. Huang, M. Cao, and M. D. Bond. Low-overhead software transactional memory with progress guarantees and strong semantics. In Proc. PPoPP '15 (20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming), pages 97--108. ACM, 2015.

• Computing methodologies

  • Parallel computing methodologies

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types