{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:03Z","timestamp":1750220343138,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T00:00:00Z","timestamp":1651622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000287","name":"Royal Academy of Engineering","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000287","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>Traditional offline optimization frameworks rely on representative hardware, software, and inputs to compare different optimizations on. With application-specific optimization for mobile systems though, the idea of a representative testbench is unrealistic while creating offline inputs is non-trivial. Online approaches partially overcome these problems but they might expose users to suboptimal or even erroneous code. Therefore, our mobile code is poorly optimized, resulting in wasted performance and energy and user frustration.<\/jats:p>\n          <jats:p>\n            In this article, we introduce a novel compiler optimization approach designed for mobile applications. It requires no developer effort, it tunes applications for the user\u2019s device and usage patterns, and it has no negative impact on the user experience. It is based on a lightweight capture and replay mechanism. Our previous work\u00a0[\n            <jats:xref ref-type=\"bibr\">46<\/jats:xref>\n            ] captures the state accessed by any targeted code region during its online stage. By repurposing existing OS capabilities, it keeps the overhead low. In its offline stage, it replays the code region but under different optimization decisions to enable sound comparisons of different optimizations under realistic conditions. In this article, we propose a technique that further decreases the storage sizes without any additional overhead. It captures only the intersection of reachable objects and accessed heap pages. We compare this with another new approach that has minimal runtime overheads at the cost of higher capture sizes. Coupled with a search heuristic for the compiler optimization space, our capture and replay mechanism allows us to discover optimization decisions that improve performance without testing these decisions directly on the user. Finally, with crowd-sourcing we split this offline evaluation effort between several users, allowing us to discover better code in less time.\n          <\/jats:p>\n          <jats:p>\n            We implemented a prototype system in Android based on LLVM combined with a genetic search engine and a crowd-sourcing architecture. We evaluated it on both benchmarks and real Android applications. Online captures are infrequent and introduce ~5 ms or 15 ms on average, depending on the approach used. For this negligible effect on user experience, we achieve speedups of 44%\u00a0 on average over the Android compiler and 35% over LLVM -O3. Our collaborative search is just 5% short of that speedup, which is impressive given the acceleration gains. The user with the highest workload concluded the search 7\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\times \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            faster.\n          <\/jats:p>","DOI":"10.1145\/3517338","type":"journal-article","created":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T11:37:50Z","timestamp":1648553870000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Object Intersection Captures on Interactive Apps to Drive a Crowd-sourced Replay-based Compiler Optimization"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9004-4853","authenticated-orcid":false,"given":"Paschalis","family":"Mpeis","sequence":"first","affiliation":[{"name":"University of Edinburgh, Manchester, England, UK"}]},{"given":"Pavlos","family":"Petoumenos","sequence":"additional","affiliation":[{"name":"University of Manchester, UK"}]},{"given":"Kim","family":"Hazelwood","sequence":"additional","affiliation":[{"name":"Facebook AI Research, Menlo Park, California, USA"}]},{"given":"Hugh","family":"Leather","sequence":"additional","affiliation":[{"name":"Facebook AI Research, Menlo Park, California, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,5,4]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0002894"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2006.37"},{"key":"e_1_3_2_4_2","unstructured":"The Algorithms. 2020. Sorting Algoirthms. Retrieved from https:\/\/github.com\/TheAlgorithms\/Java."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/998300.997196"},{"key":"e_1_3_2_6_2","unstructured":"Android. 2020. Android Compiler: Pathological Cases It Cannot Compile. Retrieved from https:\/\/android.googlesource.com\/platform\/art\/+\/refs\/tags\/android-10.0.0_r11\/compiler\/compiler.cc#48."},{"key":"e_1_3_2_7_2","unstructured":"Android. 2020. Dalvik Bytecode: Distibution Format of Android Code. Retrieved from https:\/\/source.android.com\/devices\/tech\/dalvik\/dalvik-bytecode."},{"key":"e_1_3_2_8_2","unstructured":"Android. 2020. HGraph: Android Compiler\u2019s Intermediate Representation (IR). Retrieved from https:\/\/android.googlesource.com\/platform\/art\/+\/refs\/tags\/android-10.0.0_r11\/compiler\/optimizing\/nodes.h#312."},{"key":"e_1_3_2_9_2","unstructured":"Quarzo Apps. 2020. 4 in a Row. Retrieved from https:\/\/play.google.com\/store\/apps\/details?id=com.quarzo.fourinarow&hl=en&gl=US."},{"key":"e_1_3_2_10_2","unstructured":"GSM Association. 2020. The Mobile Economy 2020. Retrieved from https:\/\/www.gsma.com\/mobileeconomy\/wp-content\/uploads\/2020\/03\/GSMA_MobileEconomy2020_Global.pdf."},{"key":"e_1_3_2_11_2","unstructured":"Fran\u00e7ois Bodin Toru Kisuki Peter Knijnenburg Mike O\u2019Boyle and Erven Rohou. 1998. Iterative compilation in a non-linear optimisation space. In Proceedings of the Workshop on Profile and Feedback-Directed Compilation . https:\/\/hal.inria.fr\/inria-00475919."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2724717"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.32"},{"key":"e_1_3_2_14_2","unstructured":"CDC. 2021. CDC Sleep Statistics for the United States. Retrieved from https:\/\/www.cdc.gov\/sleep\/data_statistics.html."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2248487.2150983"},{"key":"e_1_3_2_16_2","volume-title":"Compilation Order Matters","author":"Cooper K.","year":"2002","unstructured":"K. Cooper, Timothy Harvey, Devika Subramanian, and Linda Torczon. 2002. Compilation Order Matters. Technical Report. Technical Report, Rice University."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/315253.314414"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015729001611"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3213846.3213848"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1070838.1070856"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"Peter Deutsch. 1996. RFC1951: DEFLATE compressed data format specification version 1.3. (1996).","DOI":"10.17487\/rfc1951"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971811"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1155\/2014\/818579"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCAM.2004.11"},{"key":"e_1_3_2_25_2","unstructured":"FelipeRRM. 2020. Reversi Android. Retrieved from https:\/\/github.com\/FelipeRRM\/AndroidReversi."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21726-5_2"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1155\/2014\/797348"},{"key":"e_1_3_2_28_2","volume-title":"GCC Summit","author":"Fursin Grigori","year":"2008","unstructured":"Grigori Fursin, Cupertino Miranda, Olivier Temam, Mircea Namolaru, Elad Yom-Tov, Ayal Zaks, Bilha Mendelson, Edwin Bonilla, John Thomson, Hugh Leather, et\u00a0al. 2008. MILEPOST GCC: Machine learning based research compiler. In GCC Summit."},{"key":"e_1_3_2_29_2","unstructured":"Google. 2020. Android Optimizing Compiler Backend. Retrieved from https:\/\/android.googlesource.com\/platform\/art\/+\/refs\/tags\/android-10.0.0_r11\/compiler\/optimizing\/optimizing_compiler.cc."},{"key":"e_1_3_2_30_2","unstructured":"Google. 2020. Android Optimizing Compiler Backend: Code Transformations. Retrieved from https:\/\/android.googlesource.com\/platform\/art\/+\/refs\/tags\/android-10.0.0_r11\/compiler\/optimizing\/optimization.h#68."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3368826.3377928"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814320"},{"key":"e_1_3_2_33_2","unstructured":"Takanori Ishikawa. 2020. Fibonacci. Retrieved from https:\/\/gist.github.com\/ishikawa\/16670."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.2316\/P.2013.796-025"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSM.2007.4362636"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0094916","volume-title":"High Performance Computing","author":"Kisuki Toru","year":"1999","unstructured":"Toru Kisuki, Peter M. Knijnenburg, M. O\u2019Boyle, Fran\u00e7ois Bodin, and Harry A. Wijshoff. 1999. A feasibility study in iterative compilation. In High Performance Computing. Springer, 121\u2013132."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2384616.2384628"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2536688"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/APCSAC.2008.4625477"},{"key":"e_1_3_2_41_2","unstructured":"Linux. 2020. \/proc Pseudo-filesystem on Linux. Retrieved from https:\/\/www.kernel.org\/doc\/html\/latest\/filesystems\/proc.html."},{"key":"e_1_3_2_42_2","unstructured":"Velbazhd Software LLC. 2020. Brainstonz. Retrieved from https:\/\/f-droid.org\/en\/packages\/eu.veldsoft.brainstonz."},{"key":"e_1_3_2_43_2","unstructured":"Velbazhd Software LLC. 2020. ColorOverflow. Retrieved from https:\/\/f-droid.org\/en\/packages\/eu.veldsoft.colors.overflow."},{"key":"e_1_3_2_44_2","unstructured":"Velbazhd Software LLC. 2020. PokerOdds (Vitosha). Retrieved from https:\/\/f-droid.org\/en\/packages\/eu.veldsoft.vitosha.poker.odds."},{"key":"e_1_3_2_45_2","unstructured":"Velbazhd Software LLC. 2020. Svarka Calculator. Retrieved from https:\/\/f-droid.org\/en\/packages\/eu.veldsoft.svarka.odds.calculator."},{"key":"e_1_3_2_46_2","unstructured":"Paschalis Mpeis. 2020. LLVM Backend for the Android Compiler. Retrieved from https:\/\/github.com\/Paschalis\/android-llvm."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454043"},{"key":"e_1_3_2_48_2","unstructured":"NIH. 2020. Sieve. Retrieved from https:\/\/imagej.nih.gov\/nih-image\/java\/benchmarks\/sieve.html."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1082983.1083251"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2038698.2038711"},{"key":"e_1_3_2_51_2","unstructured":"Roldan Pozo and Bruce Miller. 2004. SciMark 2.0. Retrieved from https:\/\/math.nist.gov\/scimark2\/."},{"key":"e_1_3_2_52_2","unstructured":"scoutant. 2020. Blokish. Retrieved from https:\/\/f-droid.org\/en\/packages\/org.scoutant.blokish."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2014.6983040"},{"key":"e_1_3_2_54_2","unstructured":"Juanky Soriano. 2020. MaterialLife. Retrieved from https:\/\/play.google.com\/store\/apps\/details?id=com.juankysoriano.materiallife&hl=en&gl=US."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/347324.348993"},{"key":"e_1_3_2_56_2","unstructured":"Virtuozzo. 2020. Checkpoint and Restore In Userspace. Retrieved from https:\/\/www.criu.org."},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/358274.358283"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287638"},{"key":"e_1_3_2_59_2","unstructured":"Peter \u00d6sterlund. 2020. DroidFish Chess. Retrieved from https:\/\/play.google.com\/store\/apps\/details?id=org.petero.droidfish&hl=en&gl=US."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:16:58Z","timestamp":1750191418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,4]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3517338"],"URL":"https:\/\/doi.org\/10.1145\/3517338","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2022,5,4]]},"assertion":[{"value":"2021-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}