{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:11:44Z","timestamp":1760033504602,"version":"build-2065373602"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>GraalVM Native Image is increasingly used to optimize the startup performance of applications that run on the Java Virtual Machine (JVM), and particularly of Function-as-a-Service and Serverless workloads. Native Image resorts to Ahead-of-Time (AOT) compilation to produce a binary from a JVM application that contains a snapshot of the pre-initialized heap memory, reducing the initialization time and hence improving startup performance. However, this performance improvement is hindered by page faults that occur when accessing objects in the heap snapshot. Related work has proposed profile-guided approaches to reduce page faults by reordering objects in the heap snapshot of an optimized binary based on the order in which objects are first accessed, obtaining this information by profiling an instrumented binary of the same application. This reordering is effective only if objects in the instrumented binary can be matched to the semantically equivalent ones in the optimized binary. Unfortunately, this is very challenging because objects do not have unique identities and the heap-snapshot contents are not persistent across Native-Image builds of the same program.  \nThis work tackles the problem of matching heap snapshots, and proposes a novel approach to improve the mapping between semantically equivalent objects in different binaries of a Native-Image application. We introduce the concept of context-augmented heap path (CAHP)\u2014a list of elements that describes a path to an object stored in the heap snapshot. Our approach associates a CAHP to each object in a way that is as unique as possible. Objects with the same CAHP across different binaries are considered semantically equivalent. Moreover, since some semantically equivalent objects may have different CAHPs in the instrumented and optimized binaries (due to nondeterminism in the image-build process and other factors), we present an approach that finds, for each unmatched CAHP in the optimized binary, the most similar CAHP in the instrumented binary, associating the two objects. We integrate our approach into Native Image, reordering the objects stored in the heap snapshot more efficiently using the improved mapping. Our experiments show that our approach leads to much less page faults (2.98\u00d7 on average) and considerably improves startup time (1.98\u00d7 on average) w.r.t. the original Native-Image implementation.<\/jats:p>","DOI":"10.1145\/3763103","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"1484-1511","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Heap-Snapshot Matching and Ordering using CAHPs: A Context-Augmented Heap-Path Representation for Exact and Partial Path Matching using Prefix Trees"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7219-9077","authenticated-orcid":false,"given":"Matteo","family":"Basso","sequence":"first","affiliation":[{"name":"Universit\u00e0 della Svizzera Italiana (USI), Lugano, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0260-2729","authenticated-orcid":false,"given":"Aleksandar","family":"Prokopec","sequence":"additional","affiliation":[{"name":"Oracle Labs, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6467-0113","authenticated-orcid":false,"given":"Andrea","family":"Ros\u00e0","sequence":"additional","affiliation":[{"name":"Universit\u00e0 della Svizzera Italiana (USI), Lugano, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-2182","authenticated-orcid":false,"given":"Walter","family":"Binder","sequence":"additional","affiliation":[{"name":"Universit\u00e0 della Svizzera Italiana (USI), Lugano, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Amazon Web Services - Labs. 2025. LLRT GitHub Repository. https:\/\/github.com\/awslabs\/llrt"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","unstructured":"Matthew Arnold Adam Welc and V. T. Rajan. 2005. Improving Virtual Machine Performance Using a Cross-Run Profile Repository. In OOPSLA. 297\u2013311. https:\/\/doi.org\/10.1145\/1094811.1094835 10.1145\/1094811.1094835","DOI":"10.1145\/1094811.1094835"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","unstructured":"Matteo Basso Daniele Bonetta and Walter Binder. 2023. Automatically Generated Supernodes for AST Interpreters Improve Virtual-Machine Performance. In GPCE. 1\u201313. https:\/\/doi.org\/10.1145\/3624007.3624050 10.1145\/3624007.3624050","DOI":"10.1145\/3624007.3624050"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Matteo Basso Aleksandar Prokopec Andrea Ros\u00e0 and Walter Binder. 2025. Improving Native-Image Startup Performance. In CGO. 689\u2013703.","DOI":"10.1145\/3696443.3708927"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","unstructured":"Matteo Basso Aleksandar Prokopec Andrea Ros\u00e0 and Walter Binder. 2025. Artifact associated to the paper \"Heap-Snapshot Matching and Ordering using CAHPs: A Context-Augmented Heap-Path Representation for Exact and Partial Path Matching using Prefix Trees\" published in OOPSLA\u201925. https:\/\/doi.org\/10.5281\/zenodo.16522289 artifact 10.5281\/zenodo.16522289","DOI":"10.5281\/zenodo.16522289"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"S. M. Blackburn R. Garner C. Hoffman A. M. Khan K. S. McKinley R. Bentzur A. Diwan D. Feinberg D. Frampton S. Z. Guyer M. Hirzel A. Hosking M. Jump H. Lee J. E. B. Moss A. Phansalkar D. Stefanovi\u0107 T. VanDrunen D. von Dincklage and B. Wiedermann. 2006. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. OOPSLA\u201906. 169\u2013190.","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.28"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","unstructured":"Brad Calder Chandra Krintz Simmi John and Todd Austin. 1998. Cache-Conscious Data Placement. In ASPLOS. 139\u2013149. https:\/\/doi.org\/10.1145\/291006.291036 10.1145\/291006.291036","DOI":"10.1145\/291006.291036"},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Minsu Cho Jungmin Lee and Kyoung Mu Lee. 2010. Reweighted Random Walks for Graph Matching. ECCV\u201910. 492\u2013505.","DOI":"10.1007\/978-3-642-15555-0_36"},{"key":"e_1_2_2_10_1","volume-title":"Catalyzer: Sub-millisecond Startup for Serverless Computing with Initialization-less Booting. ASPLOS\u201920. 467\u2013481.","author":"Yu Dong","year":"2020","unstructured":"Du, Dong and Yu, Tianyi and Xia, Yubin and Zang, Binyu and Yan, Guanglu and Qin, Chenggang and Wu, Qixuan and Chen, Haibo. 2020. Catalyzer: Sub-millisecond Startup for Serverless Computing with Initialization-less Booting. ASPLOS\u201920. 467\u2013481."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","unstructured":"Gilles Duboscq Thomas W\u00fcrthinger Lukas Stadler Christian Wimmer Doug Simon and Hanspeter M\u00f6ssenb\u00f6ck. 2013. An Intermediate Representation for Speculative Optimizations in a Dynamic Compiler. In VMIL. 1\u201310. https:\/\/doi.org\/10.1145\/2542142.2542143 10.1145\/2542142.2542143","DOI":"10.1145\/2542142.2542143"},{"key":"e_1_2_2_12_1","unstructured":"Eclipse. 2025. Vert.x Framework. https:\/\/vertx.io\/"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.51"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111583.1111594"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","unstructured":"Alexander Fuerst and Prateek Sharma. 2021. FaasCache: Keeping Serverless Computing Alive with Greedy-Dual Caching. In ASPLOS. 386\u2013400. https:\/\/doi.org\/10.1145\/3445814.3446757 10.1145\/3445814.3446757","DOI":"10.1145\/3445814.3446757"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.491619"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","unstructured":"Dirk Grunwald Benjamin Zorn and Robert Henderson. 1993. Improving the Cache Locality of Memory Allocation. In PLDI. 177\u2013186. https:\/\/doi.org\/10.1145\/173262.155107 10.1145\/173262.155107","DOI":"10.1145\/173262.155107"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","unstructured":"Christopher Haine Olivier Aumage and Denis Barthou. 2017. Rewriting System for Profile-Guided Data Layout Transformations on Binaries. In Euro-Par. 260\u2013272. https:\/\/doi.org\/10.1007\/978-3-319-64203-1_19 10.1007\/978-3-319-64203-1_19","DOI":"10.1007\/978-3-319-64203-1_19"},{"key":"e_1_2_2_19_1","volume-title":"Pointer Analysis: Haven\u2019t We Solved This Problem Yet? In PASTE. 54\u201361.","author":"Hind Michael","year":"2001","unstructured":"Michael Hind. 2001. Pointer Analysis: Haven\u2019t We Solved This Problem Yet? In PASTE. 54\u201361."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","unstructured":"Ellis Hoag Kyungwoo Lee Juli\u00e1n Mestre and Sergey Pupyrev. 2023. Optimizing Function Layout for Mobile Applications. In LCTES. 52\u201363. https:\/\/doi.org\/10.1145\/3589610.3596277 10.1145\/3589610.3596277","DOI":"10.1145\/3589610.3596277"},{"key":"e_1_2_2_21_1","unstructured":"JetBrains. 2025. Ktor Framework. https:\/\/ktor.io\/"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","unstructured":"Alin Jula and Lawrence Rauchwerger. 2009. Two Memory Allocators that Use Hints to Improve Locality. In ISMM. 109\u2013118. https:\/\/doi.org\/10.1145\/1542431.1542447 10.1145\/1542431.1542447","DOI":"10.1145\/1542431.1542447"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","unstructured":"Kyungwoo Lee Ellis Hoag and Nikolai Tillmann. 2022. Efficient Profile-guided Size Optimization for Native Mobile Applications. In CC. 243\u2013253. https:\/\/doi.org\/10.1145\/3497776.3517764 10.1145\/3497776.3517764","DOI":"10.1145\/3497776.3517764"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Marius Leordeanu and Martial Hebert. 2009. Unsupervised Learning for Graph Matching. CVPR\u201909. 864\u2013871.","DOI":"10.1109\/CVPR.2009.5206533"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3585007"},{"key":"e_1_2_2_26_1","unstructured":"LLVM Project. 2025. Benchmarking Tips. https:\/\/llvm.org\/docs\/Benchmarking.html"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132190.3132210"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","unstructured":"Chaitanya Mamatha Ananda Rajiv Gupta Sriraman Tallam Han Shen and Xinliang David Li. 2025. PreFix: Optimizing the Performance of Heap-Intensive Applications. In CGO. 405\u2013417. isbn:9798400712753 https:\/\/doi.org\/10.1145\/3696443.3708960 10.1145\/3696443.3708960","DOI":"10.1145\/3696443.3708960"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","unstructured":"Stefan Marr Benoit Daloze and Hanspeter M\u00f6ssenb\u00f6ck. 2016. Cross-language Compiler Benchmarking: Are We Fast Yet? In DLS. 120\u2013131. https:\/\/doi.org\/10.1145\/2989225.2989232 10.1145\/2989225.2989232","DOI":"10.1145\/2989225.2989232"},{"key":"e_1_2_2_30_1","unstructured":"Micronaut Foundation. 2024. Micronaut Framework. https:\/\/micronaut.io\/"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527853"},{"key":"e_1_2_2_32_1","unstructured":"Oracle and\/or its affiliates. 2021. GraalVM: Native Image. https:\/\/www.graalvm.org\/jdk21\/reference-manual\/native-image\/"},{"key":"e_1_2_2_33_1","unstructured":"Oracle and\/or its affiliates. 2025. DaCapoBenchmarkSuite. https:\/\/github.com\/oracle\/graal\/blob\/1ff637ab400c9098d2c06606d646e4733e8af9a5\/java-benchmarks\/mx.java-benchmarks\/mx_java_benchmarks.py##L1000"},{"key":"e_1_2_2_34_1","unstructured":"Oracle and\/or its affiliates. 2025. Helidon Framework. https:\/\/helidon.io\/"},{"key":"e_1_2_2_35_1","unstructured":"Oracle and\/or its affiliates. 2025. RenaissanceBenchmarkSuite. https:\/\/github.com\/oracle\/graal\/blob\/1ff637ab400c9098d2c06606d646e4733e8af9a5\/java-benchmarks\/mx.java-benchmarks\/mx_java_benchmarks.py##L1988"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","unstructured":"Guilherme Ottoni and Bin Liu. 2021. HHVM Jump-Start: Boosting Both Warmup and Steady-State Performance at Scale. In CGO. 340\u2013350. https:\/\/doi.org\/10.1109\/CGO51591.2021.9370314 10.1109\/CGO51591.2021.9370314","DOI":"10.1109\/CGO51591.2021.9370314"},{"key":"e_1_2_2_37_1","unstructured":"Play Framework. 2025. Play Framework. https:\/\/spring.io\/"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","unstructured":"Todd A. Proebsting. 1995. Optimizing an ANSI C Interpreter with Superoperators. In POPL. 322\u2013332. https:\/\/doi.org\/10.1145\/199448.199526 10.1145\/199448.199526","DOI":"10.1145\/199448.199526"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","unstructured":"Aleksandar Prokopec Gilles Duboscq David Leopoldseder and Thomas W\u00fcrthinger. 2019. An Optimization-Driven Incremental Inline Substitution Algorithm for Just-In-Time Compilers. In CGO. 164\u2013179. https:\/\/doi.org\/10.1109\/CGO.2019.8661171 10.1109\/CGO.2019.8661171","DOI":"10.1109\/CGO.2019.8661171"},{"key":"e_1_2_2_40_1","volume-title":"Renaissance: Benchmarking Suite for Parallel Applications on the JVM. PLDI\u201919\u2019. 31\u201347.","author":"Prokopec Aleksandar","year":"2019","unstructured":"Aleksandar Prokopec, Andrea Ros\u00e0, David Leopoldseder, Gilles Duboscq, Petr T\u016fma, Martin Studener, Lubom\u00edr Bulej, Yudi Zheng, Alex Villaz\u00f3n, Doug Simon, Thomas W\u00fcrthinger, and Walter Binder. 2019. Renaissance: Benchmarking Suite for Parallel Applications on the JVM. PLDI\u201919\u2019. 31\u201347."},{"key":"e_1_2_2_41_1","unstructured":"Red Hat. 2025. Quarkus. https:\/\/quarkus.io\/"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","unstructured":"Shai Rubin Rastislav Bod\u00edk and Trishul Chilimbi. 2002. An Efficient Profile-analysis Framework for Data-layout Optimizations. In POPL. 140\u2013153. https:\/\/doi.org\/10.1145\/565816.503287 10.1145\/565816.503287","DOI":"10.1145\/565816.503287"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","unstructured":"Barbara G. Ryder. 2003. Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages. In CC. 126\u2013137. https:\/\/doi.org\/10.1007\/3-540-36579-6_10 10.1007\/3-540-36579-6_10","DOI":"10.1007\/3-540-36579-6_10"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368826.3377914"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","unstructured":"Lukas Stadler Thomas W\u00fcrthinger and Hanspeter M\u00f6ssenb\u00f6ck. 2014. Partial Escape Analysis and Scalar Replacement for Java. In CGO. 165\u2013174. https:\/\/doi.org\/10.1145\/2581122.2544157 10.1145\/2581122.2544157","DOI":"10.1145\/2581122.2544157"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Jovan Stojkovic Tianyin Xu Hubertus Franke and Josep Torrellas. 2023. SpecFaaS: Accelerating Serverless Applications with Speculative Function Execution. HPCA\u201923. 814\u2013827.","DOI":"10.1109\/HPCA56546.2023.10071120"},{"key":"e_1_2_2_47_1","unstructured":"The Kernel Development Community. 2025. Documentation for \/proc\/sys\/vm\/. https:\/\/www.kernel.org\/doc\/html\/latest\/admin-guide\/sysctl\/vm.html?highlight=drop_caches#drop-caches"},{"key":"e_1_2_2_48_1","unstructured":"VMware Tanzu. 2025. Spring Framework. https:\/\/spring.io\/"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","unstructured":"Yongliang Wang Naijie Gu Junjie Su Dongsheng Qi and Zhuorui Ning. 2022. Data Layout Optimization based on the Spatio-Temporal Model of Field Access. In AEMCSE. 238\u2013244. https:\/\/doi.org\/10.1109\/AEMCSE55572.2022.00055 10.1109\/AEMCSE55572.2022.00055","DOI":"10.1109\/AEMCSE55572.2022.00055"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360610"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","unstructured":"Christian Wimmer Codrut Stancu David Kozak and Thomas W\u00fcrthinger. 2024. Scaling Type-Based Points-to Analysis with Saturation. In PLDI. 990\u2013101. https:\/\/doi.org\/10.1145\/3656417 10.1145\/3656417","DOI":"10.1145\/3656417"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276494"},{"key":"e_1_2_2_53_1","doi-asserted-by":"crossref","unstructured":"Junchi Yan Xu-Cheng Yin Weiyao Lin Cheng Deng Hongyuan Zha and Xiaokang Yang. 2016. A Short Survey of Recent Advances in Graph Matching. ICMR\u201916. 167\u2013174.","DOI":"10.1145\/2911996.2912035"},{"key":"e_1_2_2_54_1","unstructured":"Yang Guo. 2015. Custom Startup Snapshots. https:\/\/www.v8.dev"},{"key":"e_1_2_2_55_1","volume-title":"Spark: Cluster Computing with Working Sets. HotCloud\u201910. 10 pages.","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. HotCloud\u201910. 10 pages."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:43:37Z","timestamp":1760031817000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":55,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763103"],"URL":"https:\/\/doi.org\/10.1145\/3763103","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}