{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:46:58Z","timestamp":1787017618321,"version":"build-2736575974"},"reference-count":67,"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>Garbage collection (GC) implementations must meet efficiency and maintainability requirements, which are often perceived to be at odds. Moreover, the desire for efficiency typically sacrifices agility, undermining rapid development and innovation, with unintended consequences on longer-term performance aspirations. Prior GC implementations struggle to: i) maximize efficiency, parallelism, and hardware utilization, while ii) correctly and elegantly implementing optimizations and scheduling constraints. This struggle is reflected in today\u2019s implementations, which tend to be monolithic and depend on coarse phase-based synchronization.<\/jats:p>\n                  <jats:p>\n                    This paper presents a new design for GC implementations that emphasizes both agility and efficiency. The design simplifies and unifies all GC tasks into\n                    <jats:italic toggle=\"yes\">work packets<\/jats:italic>\n                    which define: i) work items, ii) kernels that process them, and iii) scheduling constraints. Our simple insights are that execution is dominated by a few very small, heavily executed kernels, and that GC implementations are high-level algorithms that orchestrate vast numbers of performance-critical work items. Work packets comprise groups of like work items, such as the scanning of a thread\u2019s stack or the tracing of a single object in a multi-million object heap. The kernel attached to a packet specifies how to process items within the packet, such as how to scan a stack, or how to trace an object. The scheduling constraints express dependencies, e.g. all mutators must stop before copying any objects. Fully parallel activities, such as scanning roots and performing a transitive closure, proceed with little synchronization. The implementation of a GC algorithm reduces to declaring required work packets, their kernels, and dependencies. The execution model operates transparently of GC algorithms and work packet type. We broaden the scope of work-stealing, applying it to any type of GC work and introduce a novel two-tier work-stealing algorithm to further optimize parallelism at fine granularity.\n                  <\/jats:p>\n                  <jats:p>We show the software engineering benefits of this design via eight collectors that use 23 common work packet types in the MMTk GC framework. We use the LXR collector to show that the work packet abstraction supports innovation and high performance: i) comparing versions of LXR, work packets deliver performance benefits over a phase-based approach, and ii) LXR with work packets outperforms the highly-tuned latest (OpenJDK 24), state-of-the-art G1 garbage collector. We thus demonstrate that work packets achieve high performance, while simplifying GC implementation, making them inherently easier to optimize and verify.<\/jats:p>","DOI":"10.1145\/3763139","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"2482-2510","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Work Packets: A New Abstraction for GC Software Engineering, Optimization, and Innovation"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5148-5736","authenticated-orcid":false,"given":"Wenyu","family":"Zhao","sequence":"first","affiliation":[{"name":"Australian National University, Canberra, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6632-6001","authenticated-orcid":false,"given":"Stephen M.","family":"Blackburn","sequence":"additional","affiliation":[{"name":"Google, Sydney, Australia"},{"name":"Australian National University, Canberra, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7188-2501","authenticated-orcid":false,"given":"Kathryn S.","family":"McKinley","sequence":"additional","affiliation":[{"name":"Google, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1147\/SJ.442.0399"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277678"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806651.1806653"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3669940.3707217"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2004.1317436"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375586"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_9_2","unstructured":"Hans Boehm. 2024. GCBench. https:\/\/www.hboehm.info\/gc\/gc_bench\/GCBench.java"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073974"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/362790.362798"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/367487.367501"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3735950.3735957"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1029873.1029879"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/174675.174673"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158611"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/363269.363280"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2972206.2972210"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/350853.350863"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3617651.3622986"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4236\/JSEA.2009.23020"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134023"},{"key":"e_1_3_2_25_2","unstructured":"kernel.org. 2025. Transparent Hugepage Support. https:\/\/docs.kernel.org\/admin-guide\/mm\/transhuge.html"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/29650.29677"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442524"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/504282.504309"},{"key":"e_1_3_2_29_2","unstructured":"Per Lid\u00e9nand et al. 2018. ZGC: The Z Garbage Collector. https:\/\/wiki.openjdk.java.net\/display\/zgc\/Main"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/367177.367199"},{"key":"e_1_3_2_31_2","first-page":"617","volume-title":"Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference","author":"Miao Hongyu","year":"2017","unstructured":"Hongyu Miao, Heejin Park, Myeongjae Jeon, Gennady Pekhimenko, Kathryn S. McKinley, and Felix Xiaozhu Lin. 2017. StreamBox: modern stream processing on a multicore machine. In Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (Santa Clara, CA, USA) (USENIX ATC \u201917). USENIX Association, USA, 617\u2013629."},{"key":"e_1_3_2_32_2","unstructured":"OpenJDK. 2023. G1 GC root scanning implementation. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/g1\/glRootProcessor.cpp"},{"key":"e_1_3_2_33_2","unstructured":"OpenJDK. 2023. Root scannning implementation for Serial Parallel and CMS GC. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/shared\/genCollectedHeap.cpp#L704-L738"},{"key":"e_1_3_2_34_2","unstructured":"OpenJDK. 2023. Shenandoah GC root scannning implementation. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/shenandoah\/shenandoahRootProcessor.hpp"},{"key":"e_1_3_2_35_2","unstructured":"OpenJDK. 2023. Transitive closure implementation in G1 GC. https:\/\/github.com\/openjdk\/jdk\/blob\/master\/src\/hotspot\/share\/gc\/g1\/glYoungCollector.cpp#L537-L589"},{"key":"e_1_3_2_36_2","unstructured":"OpenJDK. 2023. Transitive closure implementation in G1 GC. https:\/\/github.com\/openjdk\/jdkllu\/blob\/jdk-11%2B28\/src\/hotspot\/share\/gc\/g1\/glCollectedHeap.cpp#L3161-L3186"},{"key":"e_1_3_2_37_2","unstructured":"OpenJDK. 2023. Transitive closure implementation in G1 GC. https:\/\/github.com\/openjdk\/jdkllu\/blob\/jdk-11%2B28\/src\/hotspot\/share\/gc\/g1\/glCollectedHeap.cpp#L4039-L4065"},{"key":"e_1_3_2_38_2","unstructured":"OpenJDK. 2023. Transitive closure implementation in Parallel GC. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/parallel\/psScavenge.cpp#L152-L200"},{"key":"e_1_3_2_39_2","unstructured":"OpenJDK. 2023. Work stealing deque implementation in OpenJDK. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/shared\/taskqueue.hpp#L296-L325"},{"key":"e_1_3_2_40_2","unstructured":"OpenJDK. 2023. Work stealing in G1 GC. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/g1\/glParScanThreadState.cpp#L319"},{"key":"e_1_3_2_41_2","unstructured":"OpenJDK. 2023. Work stealing in Shenandoah GC. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/shenandoah\/shenandoahMark.cpp#L177"},{"key":"e_1_3_2_42_2","unstructured":"OpenJDK. 2023. Work stealing in ZGC. https:\/\/github.eom\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/z\/zMark.cpp#L520-L529"},{"key":"e_1_3_2_43_2","unstructured":"OpenJDK. 2023. ZGC root scannning implementation. https:\/\/github.com\/openjdk\/jdk\/blob\/jdk-21%2B35\/src\/hotspot\/share\/gc\/z\/zRootsIterator.hpp"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512546"},{"key":"e_1_3_2_45_2","unstructured":"Erik \u00d6sterlund. 2025. Keynote: Industry GC Insights from OpenJDK. https:\/\/conf.researchr.org\/details\/ismm-2025\/ismm-2025-papers\/12\/Keynote-Industry-GC-Insights-from-OpenJDK"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3729285"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.5555\/1461409"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509527"},{"key":"e_1_3_2_49_2","unstructured":"Aleksey Shipil\u00ebv. 2024. JDK 21 lusearch and Lucene \u201cregression\u201d. https:\/\/github.com\/dacapobench\/dacapobench\/issues\/264"},{"key":"e_1_3_2_50_2","unstructured":"Peter Styger. 1967. LISP 2 garbage collector specifications. Technical Report TM-3417\/500\/00. System Development Cooperation Santa Monica. https:\/\/www.softwarepreservation.org\/projects\/LISP\/lisp2\/TM-3417_500_00_LISP2_GC_Spec.pdf"},{"key":"e_1_3_2_51_2","unstructured":"The MMTk Team. 2019. V8 with MMTk support. https:\/\/chromium-review.googlesource.com\/c\/v8\/v8\/+\/1928860"},{"key":"e_1_3_2_52_2","unstructured":"The MMTk Team. 2024. JikesRVM with MMTk support. https:\/\/github.com\/mmtk\/jikesrvm\/tree\/f2d3178c2c74e8c8daebl05d98e48feac51dd44d"},{"key":"e_1_3_2_53_2","unstructured":"The MMTk Team. 2024. Memory Management Toolkit. https:\/\/www.mmtk.io\/"},{"key":"e_1_3_2_54_2","unstructured":"The MMTk Team. 2024. MMTk\u2019s JikesRVM binding. https:\/\/github.com\/mmtk\/mmtk-jikesrvm"},{"key":"e_1_3_2_55_2","unstructured":"The MMTk Team. 2024. MMTk\u2019s OpenJDK binding. https:\/\/github.com\/mmtk\/mmtk-openjdk"},{"key":"e_1_3_2_56_2","unstructured":"The MMTk Team. 2024. OpenJDK 11.0.19+1 with MMTk support. https:\/\/github.com\/mmtk\/openjdk\/tree\/bc9669aaedc07924d08b939adedcad33f3e76065"},{"key":"e_1_3_2_57_2","unstructured":"VPP Team. 2024. Vector Packet Processing Platform. https:\/\/s3-docs.fd.io\/vpp\/25.02"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993478.1993491"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/800020.808261"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3735950.3735960"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3546918.3546923"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/0164-1212(90)90084-Y"},{"key":"e_1_3_2_63_2","unstructured":"Wenyu Zhao. 2020. Work Packets #136. https:\/\/github.com\/mmtk\/mmtk-core\/commit\/b9dc15173c881861644f8f48d7abf2eIfc6b4fc7"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381052.3381320"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523440"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","unstructured":"Wenyu Zhao Stephen M. Blackburn and Kathryn S. McKinley. 2025. Latest Work Packets Artifact. doi:10.5281\/zenodo.15760953","DOI":"10.5281\/zenodo.15760953"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","unstructured":"Wenyu Zhao Stephen M. Blackburn and Kathryn S. McKinley. 2025. Work Packets Artifact. do:10.5281\/zenodo.15760953","DOI":"10.5281\/zenodo.15760953"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3764118"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763139","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:11:44Z","timestamp":1784196704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763139"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":67,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763139"],"URL":"https:\/\/doi.org\/10.1145\/3763139","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-25","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"}}]}}