{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T15:36:51Z","timestamp":1692373011069},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T00:00:00Z","timestamp":1540339200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319786, OAC-1740210 and CNS-1703598"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,10,24]]},"abstract":"Eliminating so-called \u201cout-of-thin-air\u201d (OOTA) results is an open problem with many existing programming language memory models including Java, C, and C++. OOTA behaviors are problematic in that they break both formal and informal modular reasoning about program behavior. Defining memory model semantics that are easily understood, allow existing optimizations, and forbid OOTA results remains an open problem. This paper explores two simple solutions to this problem that forbid OOTA results. One solution is targeted towards C\/C++-like memory models in which racing operations are explicitly labeled as atomic operations and a second solution is targeted towards Java-like languages in which all memory operations may create OOTA executions. Our solutions provide a per-candidate execution criterion that makes it possible to examine a single execution and determine whether the memory model permits the execution. We implemented and evaluated both solutions in the LLVM compiler framework. Our results show that on an ARMv8 processor the first solution has no overhead on average and a maximum overhead of 6.3% on 43 concurrent data structures, and that the second solution has an average overhead of 3.1% and a maximum overhead of 17.6% on the SPEC CPU2006 C\/C++ benchmarks.<\/jats:p>","DOI":"10.1145\/3276506","type":"journal-article","created":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T11:57:18Z","timestamp":1540382238000},"page":"1-29","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Towards understanding the costs of avoiding out-of-thin-air results"],"prefix":"10.1145","volume":"2","author":[{"given":"Peizhao","family":"Ou","sequence":"first","affiliation":[{"name":"University of California at Irvine, USA"}]},{"given":"Brian","family":"Demsky","sequence":"additional","affiliation":[{"name":"University of California at Irvine, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,10,24]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/325164.325100"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3173162.3177156"},{"key":"e_1_2_2_3_1","unstructured":"Azul. 2017. https:\/\/www.azul.com\/press_release\/falcon- jit- compiler\/ . Azul. 2017. https:\/\/www.azul.com\/press_release\/falcon- jit- compiler\/ ."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429099"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46669-8_12"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46669-8_12"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926394"},{"key":"e_1_2_2_8_1","unstructured":"Pete Becker. 2011. ISO\/IEC 14882:2011 Information Technology \u2013 Programming Languages \u2013 C++. Pete Becker. 2011. ISO\/IEC 14882:2011 Information Technology \u2013 Programming Languages \u2013 C++."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2618128.2618134"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375591"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1893586.1893595"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.32"},{"key":"e_1_2_2_13_1","volume-title":"Axiomatically. In Proceedings of the 2007 European Symposium on Programming.","author":"Cenciarelli Pietro","year":"2007"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429110"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192421"},{"key":"e_1_2_2_16_1","unstructured":"Facebook. 2018. https:\/\/github.com\/facebook\/folly . Facebook. 2018. https:\/\/github.com\/facebook\/folly ."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186736.1186737"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11957-6_17"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934536"},{"key":"e_1_2_2_20_1","unstructured":"ISO JTC. 2011. ISO\/IEC 9899:2011 Information Technology \u2013 Programming Languages \u2013 C. ISO JTC. 2011. ISO\/IEC 9899:2011 Information Technology \u2013 Programming Languages \u2013 C."},{"key":"e_1_2_2_21_1","unstructured":"ISO JTC. 2014. ISO\/IEC 14882:2014 Information Technology \u2013 Programming Languages \u2013 C++. ISO JTC. 2014. ISO\/IEC 14882:2014 Information Technology \u2013 Programming Languages \u2013 C++."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009850"},{"key":"e_1_2_2_23_1","unstructured":"Max Khiszinsky. 2017. https:\/\/github.com\/khizmax\/libcds . Max Khiszinsky. 2017. https:\/\/github.com\/khizmax\/libcds ."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158105"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062352"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133873"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040336"},{"key":"e_1_2_2_29_1","unstructured":"Luc Maranget Susmit Sarkar and Peter Sewell. 2012. A Tutorial Introduction to The ARM and POWER Relaxed Memory Models. http:\/\/www.cl.cam.ac.uk\/~pes20\/ppc- supplemental\/test7.pdf . Luc Maranget Susmit Sarkar and Peter Sewell. 2012. A Tutorial Introduction to The ARM and POWER Relaxed Memory Models. http:\/\/www.cl.cam.ac.uk\/~pes20\/ppc- supplemental\/test7.pdf ."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993522"},{"key":"e_1_2_2_31_1","unstructured":"Paul E. McKenney Alan Jeffrey Ali Sezgin and Tony Tye. 2016. Out-of-Thin-Air Execution is Vacuous. http:\/\/www.open- std. org\/jtc1\/sc22\/wg21\/docs\/papers\/2016\/p0422r0.html . Paul E. McKenney Alan Jeffrey Ali Sezgin and Tony Tye. 2016. Out-of-Thin-Air Execution is Vacuous. http:\/\/www.open- std. org\/jtc1\/sc22\/wg21\/docs\/papers\/2016\/p0422r0.html ."},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Yuri Meshman Noam Rinetzky and Eran Yahav. 2015. Pattern-based Synthesis of Synchronization for the C++ Memory Model. In Formal Methods in Computer-Aided Design. Yuri Meshman Noam Rinetzky and Eran Yahav. 2015. Pattern-based Synthesis of Synchronization for the C++ Memory Model. In Formal Methods in Computer-Aided Design.","DOI":"10.1109\/FMCAD.2015.7542261"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509514"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814286"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018749"},{"key":"e_1_2_2_36_1","unstructured":"Peizhao Ou and Brian Demsky. 2018. Towards Understanding the Costs of Avoiding Out-of-Thin-Air Results (extended version). http:\/\/plrg.eecs.uci.edu\/publications\/OOTA- Extended- Version.pdf . Peizhao Ou and Brian Demsky. 2018. Towards Understanding the Costs of Avoiding Out-of-Thin-Air Results (extended version). http:\/\/plrg.eecs.uci.edu\/publications\/OOTA- Extended- Version.pdf ."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2006.38"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837616"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 31st European Conference on Object-Oriented Programming.","author":"Podkopaev Anton","year":"2017"},{"key":"e_1_2_2_40_1","unstructured":"Jeff Preshing. 2018. https:\/\/github.com\/preshing\/junction . Jeff Preshing. 2018. https:\/\/github.com\/preshing\/junction ."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158107"},{"key":"e_1_2_2_42_1","unstructured":"Erik Rigtorp. 2017a. https:\/\/github.com\/rigtorp\/SPSCQueue . Erik Rigtorp. 2017a. https:\/\/github.com\/rigtorp\/SPSCQueue ."},{"key":"e_1_2_2_43_1","unstructured":"Erik Rigtorp. 2017b. https:\/\/github.com\/rigtorp\/MPMCQueue . Erik Rigtorp. 2017b. https:\/\/github.com\/rigtorp\/MPMCQueue ."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851150"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73562"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487241.2487248"},{"key":"e_1_2_2_47_1","unstructured":"Aleksey Shipil\u00ebv. 2016a. Java Memory Model Pragmatics. https:\/\/shipilev.net\/blog\/2014\/jmm- pragmatics\/ . Aleksey Shipil\u00ebv. 2016a. Java Memory Model Pragmatics. https:\/\/shipilev.net\/blog\/2014\/jmm- pragmatics\/ ."},{"key":"e_1_2_2_48_1","unstructured":"Aleksey Shipil\u00ebv. 2016b. Java Memory Model Pragmatics. https:\/\/shipilev.net\/ . Aleksey Shipil\u00ebv. 2016b. Java Memory Model Pragmatics. https:\/\/shipilev.net\/ ."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079856.3080206"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2337159.2337220"},{"key":"e_1_2_2_51_1","unstructured":"Michael J Sullivan. 2017. Low-level Concurrent Programming Using the Relaxed Memory Calculus. Ph.D. Dissertation. Carnegie Mellon University. Michael J Sullivan. 2017. Low-level Concurrent Programming Using the Relaxed Memory Calculus. Ph.D. Dissertation. Carnegie Mellon University."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509532"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70592-5_3"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-015-4492-4"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276506","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T10:24:29Z","timestamp":1672568669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,24]]},"references-count":54,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2018,10,24]]}},"alternative-id":["10.1145\/3276506"],"URL":"http:\/\/dx.doi.org\/10.1145\/3276506","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,24]]},"assertion":[{"value":"2018-10-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
