{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:46:09Z","timestamp":1780994769491,"version":"3.54.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2022,N00014-19-1-2493,N00014-21-1-2523"],"award-info":[{"award-number":["N00014-18-1-2022,N00014-19-1-2493,N00014-21-1-2523"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-16-1-0371"],"award-info":[{"award-number":["FA9550-16-1-0371"]}],"id":[{"id":"10.13039\/100000181","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":[[2024,6,20]]},"abstract":"<jats:p>Historically, memory management based on lock-free reference counting was very inefficient, especially for read-dominated workloads. Thus, approaches such as epoch-based reclamation (EBR), hazard pointers (HP), or a combination thereof have received significant attention. EBR exhibits excellent performance but is blocking due to potentially unbounded memory usage. In contrast, HP are non-blocking and achieve good memory efficiency but are much slower. Moreover, HP are only lock-free in the general case. Recently, several new memory reclamation approaches such as WFE and Hyaline have been proposed. WFE achieves wait-freedom, but is less memory efficient and performs suboptimally in oversubscribed scenarios; Hyaline achieves higher performance and memory efficiency, but lacks wait-freedom.<\/jats:p>\n          <jats:p>We present a family of non-blocking memory reclamation schemes, called Crystalline, that simultaneously addresses the challenges of high performance, high memory efficiency, and wait-freedom. Crystalline can guarantee complete wait-freedom even when threads are dynamically recycled, asynchronously reclaims memory in the sense that any thread can reclaim memory retired by any other thread, and ensures (an almost) balanced reclamation workload across all threads. The latter two properties result in Crystalline\u2019s high performance and memory efficiency. Simultaneously ensuring all three properties requires overcoming unique challenges. Crystalline supports ubiquitous x86-64 and ARM64 architectures, while achieving superior throughput than prior fast schemes such as EBR as the number of threads grows.<\/jats:p>\n          <jats:p>\n            We also accentuate that many recent approaches, unlike HP, lack strict non-blocking guarantees when used with\n            <jats:italic toggle=\"yes\">multiple<\/jats:italic>\n            data structures. By providing full wait-freedom, Crystalline addresses this problem as well.\n          <\/jats:p>","DOI":"10.1145\/3658851","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"2174-2198","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["A Family of Fast and Memory Efficient Lock- and Wait-Free Reclamation"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1699-0593","authenticated-orcid":false,"given":"Ruslan","family":"Nikolaev","sequence":"first","affiliation":[{"name":"Pennsylvania State University, University Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8663-739X","authenticated-orcid":false,"given":"Binoy","family":"Ravindran","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"2020. Private communication with PEBR\u2019s authors."},{"key":"e_1_3_1_3_2","unstructured":"2024. Crossbeam: epoch-based memory reclamation. https:\/\/docs.rs\/crossbeam\/latest\/crossbeam\/epoch\/index.html."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064214"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755600"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454060"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523730"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935790"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486184"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767436"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276513"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814298"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755579"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374523"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441596"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3232559"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0079-z"},{"key":"e_1_3_1_18_2","article-title":"A scalable concurrent malloc (3) implementation for FreeBSD","author":"Evans Jason","year":"2006","unstructured":"Jason Evans. 2006. A scalable concurrent malloc (3) implementation for FreeBSD. In Proceedings of the BSDCan Conference, Ottawa, Canada. https:\/\/www.bsdcan.org\/2006\/papers\/jemalloc.pdf","journal-title":"Proceedings of the BSDCan Conference, Ottawa, Canada"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989549"},{"key":"e_1_3_1_20_2","volume-title":"Practical lock-freedom","author":"Fraser Keir","year":"2004","unstructured":"Keir Fraser. 2004. Practical lock-freedom. Technical Report. Univ. of Cambridge, Computer Laboratory. https:\/\/www.cl.cam.ac.uk\/techreports\/UCAM-CL-TR-579.pdf"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.167"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45414-4_21"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.04.010"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1062247.1062249"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36108-1_23"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/1734069"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385978"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941585"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34175-6_13"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.8"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/898203"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591089"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442527"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2019.28"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331575"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374540"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2021.60"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454090"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538572"},{"key":"e_1_3_1_40_2","author":"Nikolaev Ruslan","year":"2024","unstructured":"Ruslan Nikolaev and Binoy Ravindran. 2024. A Family of Fast and Memory Efficient Lock- and Wait-Free Reclamation (an extended arXiv version of this paper). https:\/\/arxiv.org\/abs\/2108.02763","journal-title":"A Family of Fast and Memory Efficient Lock- and Wait-Free Reclamation (an extended arXiv version of this paper)"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.10775789"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210661"},{"key":"e_1_3_1_43_2","author":"Ramalhete Pedro","year":"2016","unstructured":"Pedro Ramalhete and Andreia Correia. 2016. A Wait-Free Queue with Wait-Free Memory Reclamation (Full Version) https:\/\/github.com\/pramalhe\/ConcurrencyFreaks\/raw\/master\/papers\/crturnqueue-2016.pdf","journal-title":"A Wait-Free Queue with Wait-Free Memory Reclamation (Full Version)"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087588"},{"key":"e_1_3_1_45_2","unstructured":"Pedro Ramalhete and Andreia Correia. 2017. Hazard Eras - Non-Blocking Memory Reclamation (Full Version). https:\/\/github.com\/pramalhe\/ConcurrencyFreaks\/raw\/master\/papers\/hazarderas-2017.pdf"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3019022"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2019.00028"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2021.35"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3583668.3594564"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441625"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_23"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2555243.2555261"},{"key":"e_1_3_1_53_2","volume-title":"Systems Programming: Coping with Parallelism.","author":"Treiber R. K.","year":"1986","unstructured":"R. K. Treiber. 1986. Systems Programming: Coping with Parallelism. Technical Report RJ 5118. IBM Almaden R. Center."},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224988"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178488"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851168"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658851","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:39:21Z","timestamp":1751661561000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":55,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3658851"],"URL":"https:\/\/doi.org\/10.1145\/3658851","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}