{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T17:23:58Z","timestamp":1787592238993,"version":"build-2736575974"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:00:00Z","timestamp":1744156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1656518"],"award-info":[{"award-number":["DGE-1656518"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Stanford IOG Research Hub","award":["281101-1-UDCPQ 298911"],"award-info":[{"award-number":["281101-1-UDCPQ 298911"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,4,9]]},"abstract":"<jats:p>\n                    Although existing garbage collectors (GCs) perform extremely well on typical programs, there still exist pathological programs for which modern GCs significantly degrade performance. This observation begs the question: might there exist a \u2018holy grail\u2019 GC algorithm, as yet undiscovered, guaranteeing both constant-length pause times and that memory is collected promptly upon becoming unreachable? For decades, researchers have understood that such a GC is\n                    <jats:italic toggle=\"yes\">not<\/jats:italic>\n                    always possible, i.e., some pathological behavior is unavoidable when the program can make heap cycles and operates near the memory limit, regardless of the GC algorithm used. However, this understanding has until now been only informal, lacking a rigorous formal proof.\n                  <\/jats:p>\n                  <jats:p>\n                    This paper complements that informal understanding with a rigorous proof, showing with mathematical certainty that\n                    <jats:italic toggle=\"yes\">every<\/jats:italic>\n                    GC algorithm that can implement a realistic mutator-observer interface has some pathological program that forces it to either introduce a long GC pause into program execution or reject an allocation even though there is available space. Hence, language designers must either accept these pathological scenarios and design heuristic approaches that minimize their impact (e.g., generational collectio\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ), or restrict programs and environments to a strict subset of the behaviors allowed by our mutator-observer-style interface (e.g., by enforcing a type system that disallows cycles or overprovisioning memory).\n                  <\/jats:p>\n                  <jats:p>We do not expect this paper to have any effect on garbage collection practice. Instead, it provides the first mathematically rigorous answers to these interesting questions about the limits of garbage collection. We do so via rigorous reductions between GC and the dynamic graph connectivity problem in complexity theory, so future algorithms and lower bounds from either community transfer to the other via our reductions.<\/jats:p>\n                  <jats:p>We end by describing how to adapt techniques from the graph data structures community to build a garbage collector making worst-case guarantees that improve performance on our motivating, pathologically memory-constrained scenarios, but in practice find too much overhead to recommend for typical use.<\/jats:p>","DOI":"10.1145\/3720430","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T13:48:26Z","timestamp":1744206506000},"page":"449-476","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Pathological Cases for a Class of Reachability-Based Garbage Collectors"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2060-1009","authenticated-orcid":false,"given":"Matthew","family":"Sotoudeh","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,9]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"2023. Programming Language and compiler Benchmarks. https:\/\/programming-language-benchmarks.vercel.app\/."},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604155"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028976.1028982"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45337-7_12"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/130854.130862"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.23919\/MIPRO55190.2022.9803445"},{"key":"e_1_3_1_8_1","unstructured":"J. Bloch. 2017. Effective Java. Pearson Education. https:\/\/books.google.com\/books?id=BIpDDwAAQBAJ"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155109"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15975-4_42"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS55109.2022.00005"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394450.3397469"},{"key":"e_1_3_1_13_1","unstructured":"Brent Christian and Stuart Marks. 2021. JEP 421: Deprecate Finalization for Removal. https:\/\/openjdk.org\/jeps\/421."},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509557"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510107"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/367487.367501"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/321021.321022"},{"key":"e_1_3_1_18_1","unstructured":"Go. [n. d.]. A Guide to the Go Garbage Collector. https:\/\/tip.golang.org\/doc\/gc-guide."},{"key":"e_1_3_1_19_1","volume-title":"15th Workshop on Hot Topics in Operating Systems, HotOS XV, Kartause Ittingen, Switzerland, May 18-20, 2015","author":"Gog Ionel","year":"2015","unstructured":"Ionel Gog, Jana Giceva, Malte Schwarzkopf, Kapil Vaswani, Dimitrios Vytiniotis, Ganesan Ramalingam, Manuel Costa, Derek Gordon Murray, Steven Hand, and Michael Isard. 2015. Broom: Sweeping Out Garbage Collection from Big Data Systems. In 15th Workshop on Hot Topics in Operating Systems, HotOS XV, Kartause Ittingen, Switzerland, May 18-20, 2015. USENIX Association. https:\/\/www.usenix.org\/conference\/hotos15\/workshop-program\/presentation\/gog"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.23919\/MIPRO.2018.8400277"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","unstructured":"H. Grgic B. Mihaljevi\u0107 and A. Radovan. 2018b. Comparison of garbage collectors in Java programming language. In 2018 41st International Convention on Information and Communication Technology Electronics and Microelectronics (MIPRO). 1539\u20131544. https:\/\/doi.org\/10.23919\/MIPRO.2018.8400277 10.23919\/MIPRO.2018.8400277","DOI":"10.23919\/MIPRO.2018.8400277"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/949305.949337"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617651.3622986"},{"key":"e_1_3_1_26_1","unstructured":"Roberto Ierusalimschy. [n. d.]. Garbage Collection in Lua. https:\/\/www.lua.org\/wshop18\/Ierusalimschy.pdf."},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315388021"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/359460.359470"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385978"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597809.2597824"},{"key":"e_1_3_1_32_1","unstructured":"Donald Ervin Knuth. 1997. The art of computer programming Volume I: Fundamental Algorithms 3rd Edition. Addison-Wesley. https:\/\/www.worldcat.org\/oclc\/312910844"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00096"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/358141.358147"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90088-D"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508293.1508307"},{"key":"e_1_3_1_37_1","unstructured":"Peter Marshall. [n. d.]. Trash talk: the Orinoco garbage collector. https:\/\/v8.dev\/blog\/trash-talk."},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90226-N"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/367593.367649"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/367177.367199"},{"key":"e_1_3_1_41_1","unstructured":"Marvin L Minsky. 1963. A LISP garbage collector algorithm using serial secondary storage. (1963)."},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455567.1455606"},{"key":"e_1_3_1_43_1","first-page":"349","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016","author":"Nguyen Khanh","year":"2016","unstructured":"Khanh Nguyen, Lu Fang, Guoqing Xu, Brian Demsky, Shan Lu, Sanazsadat Alamian, and Onur Mutlu. 2016. Yak: A High-Performance Big-Data-Friendly Garbage Collector. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016, Kimberly Keeton and Timothy Roscoe (Eds.). USENIX Association, 349\u2013365. https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/nguyen"},{"key":"e_1_3_1_44_1","unstructured":"Oracle. [n. d.]. Java Garbage Collection Basics. https:\/\/www.oracle.com\/webfolder\/technetwork\/tutorials\/obe\/java\/gc01\/index.html."},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007435"},{"key":"e_1_3_1_46_1","unstructured":"EJH Pepels MCJD van Eekelen and Marinus Jacobus Plasmeijer. 1988. A cyclic reference counting algorithm and its proof. Department of Theoretical Computer Science and Computational Models Faculty . . . ."},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542431.1542438"},{"key":"e_1_3_1_48_1","unstructured":"Pablo Galindo Salgado and Irit Katriel. [n. d.]. Garbage collector design. https:\/\/github.com\/python\/cpython\/blob\/main\/InternalDocs\/garbage_collector.md."},{"key":"e_1_3_1_49_1","unstructured":"J.D. Salkild. 1985. Implementation and analysis of two cyclic reference counting algorithms."},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3546918.3546926"},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","unstructured":"Matthew Sotoudeh. 2025. (Artifact) Pathological Cases for a Class of Reachability-Based Garbage Collectors. https:\/\/doi.org\/10.5281\/zenodo.14942312 10.5281\/zenodo.14942312.","DOI":"10.5281\/zenodo.14942312"},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715896"},{"key":"e_1_3_1_53_1","unstructured":"Bill Venners. 1998. Object Finalization and Cleanup How to Design Classes for Proper Object Cleanup. https:\/\/www.artima.com\/articles\/object-finalization-and-cleanup."},{"key":"e_1_3_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/366862.366897"},{"key":"e_1_3_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/363872.363881"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/363156.363159"},{"key":"e_1_3_1_57_1","unstructured":"Josh Wolfe. 2017. Why Zig When There is Already C++ D and Rust?. https:\/\/ziglang.org\/learn\/why_zig_rust_d_cpp\/#nohidden-allocations."},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.33"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720430","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720430","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720430","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T16:31:04Z","timestamp":1787589064000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720430"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":57,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2025,4,9]]}},"alternative-id":["10.1145\/3720430"],"URL":"https:\/\/doi.org\/10.1145\/3720430","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-10-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}