{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:04:31Z","timestamp":1784199871068,"version":"3.55.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>Traditionally, most concurrent algorithms rely on safe memory reclamation (SMR)schemes for manual memory management. SMR schemes such as epoch-based reclamation (EBR) and hazard pointers (HP) are typically viewed as the only solution for memory recycling.<\/jats:p>\n                  <jats:p>When using SMR, a new object needs to be allocated whenever something new is added to a data structure. However, in more complex scenarios, the same object may need to be moved between different data structures (e.g., moving a node from one list to another, and then back to the original list) in a copy-free manner, i.e., without deallocating and allocating the node again. It is typically impossible for two reasons: (1) the ABA problem would still arise even when using SMR since the same pointer can reappear (without going through the full SMR cycle) if the same node eventually ends up back in the original data structure; (2) while in simple queues and stacks, nodes can immediately be recycled, it is unclear how to adapt data structures which use non-trivial traversal and two-phase deletion strategies, e.g., linked lists, skip lists, hash tables, trees, etc., where it is seemingly impossible to always immediately move (logically) deleted objects since they might still be accessed by other threads.<\/jats:p>\n                  <jats:p>We propose a general method of creating RRR (Reduce, Reuse, Recycle) data structures to allow safe memory recycling when using SMR which addresses the above-mentioned problems. Our method is applicable to linked lists, skip lists, hash tables, Natarajan-Mittal tree, and other data structures. We also discuss and propose a specialized approach \u2013 a more efficient version of Michael-and-Scott\u2019s (recycling) queue. Our evaluation on x86-64 shows promising results when using our methods for different data structures and SMR schemes.<\/jats:p>","DOI":"10.1145\/3729337","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"2156-2179","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["RRR-SMR: Reduce, Reuse, Recycle: Better Methods for Practical Lock-Free Data Structures"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-4341-1954","authenticated-orcid":false,"given":"Md Amit Hasan","family":"Arovi","sequence":"first","affiliation":[{"name":"Pennsylvania State University, University Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1699-0593","authenticated-orcid":false,"given":"Ruslan","family":"Nikolaev","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, University Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","unstructured":"Daniel Anderson Guy E. Blelloch and Yuanhao Wei. 2021. Concurrent deferred reference counting with constant-time overhead. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (Virtual Canada) (PLDI 2021). Association for Computing Machinery New York NY USA 526\u2013541. doi:10.1145\/3453483.3454060","DOI":"10.1145\/3453483.3454060"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","unstructured":"Daniel Anderson Guy E. Blelloch and Yuanhao Wei. 2022. Turning manual concurrent memory reclamation into automatic reference counting. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (San Diego CA USA) (PLDI 2022). Association for Computing Machinery New York NY USA 61\u201375. doi:10.1145\/3519939.3523730","DOI":"10.1145\/3519939.3523730"},{"key":"e_1_3_2_4_2","unstructured":"ARM . 2024. ARM Architecture Reference Manual. http:\/\/developer.arm.com\/."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","unstructured":"Md Amit Hasan Arovi and Ruslan Nikolaev. 2025. Artifact for PLDI\u201925. https:\/\/doi.org\/10.5281\/zenodo.15258497 10.5281\/zenodo.15258497","DOI":"10.5281\/zenodo.15258497"},{"key":"e_1_3_2_6_2","article-title":"Fixing non-blocking data structures for better compatibility with memory reclamation schemes","author":"Arovi Md Amit Hasan","year":"2025","unstructured":"Md Amit Hasan Arovi and Ruslan Nikolaev. 2025. Fixing non-blocking data structures for better compatibility with memory reclamation schemes. arXiv:2504.06254 [cs.DC]. https:\/\/arxiv.org\/abs\/2504.06254","journal-title":"arXiv"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"Naama Ben-David Guy E. Blelloch and Yuanhao Wei. 2022. Lock-free locks revisited. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Seoul Republic of Korea) (PPoPP \u201922). Association for Computing Machinery New York NY USA 278\u2013293. doi:10.1145\/3503221.3508433","DOI":"10.1145\/3503221.3508433"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","unstructured":"Trevor Alexander Brown. 2015. Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Donostia-San Sebasti\u00e1n Spain) (PODC \u201915). Association for Computing Machinery New York NY USA 261\u2013270. doi:10.1145\/2767386.2767436","DOI":"10.1145\/2767386.2767436"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276513"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","unstructured":"Andreia Correia Pedro Ramalhete and Pascal Felber. 2021. OrcGC: Automatic Lock-Free Memory Reclamation. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP \u201921). ACM 205\u2013218. doi:10.1145\/3437801.3441596","DOI":"10.1145\/3437801.3441596"},{"key":"e_1_3_2_11_2","unstructured":"Keir Fraser. 2004. Practical lock-freedom. Technical Report. Univ. of Cambridge Computer Laboratory. http:\/\/www.cl.cam.ac.uk\/techreports\/UCAM-CL-TR-579.pdf"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","unstructured":"Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In Proceedings of the 15th International Conference on Distributed Computing (DISC \u201901). Springer-Verlag Berlin Heidelberg 300\u2013314.","DOI":"10.1007\/3-540-45414-4_21"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.04.010"},{"key":"e_1_3_2_14_2","unstructured":"Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming Revised Reprint (1st ed.). Morgan Kaufmann Publishers Inc. San Francisco CA USA."},{"key":"e_1_3_2_15_2","unstructured":"IBM . 2005. PowerPC Architecture Book Version 2.02. Book I: PowerPC User Instruction Set Architecture. http:\/\/www.ibm.com\/developerworks\/"},{"key":"e_1_3_2_16_2","unstructured":"Intel . 2024. Intel 64 and IA-32 Architectures Developer\u2019s Manual. http:\/\/www.intel.com\/"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656383"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","unstructured":"Jaehwang Jung Janggun Lee Jeonghyeon Kim and Jeehoon Kang. 2023. Applying Hazard Pointers to More Concurrent Data Structures. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (Orlando FL USA) (SPAA \u201923). Association for Computing Machinery New York NY USA 213\u2013226. doi:10.1145\/3558481.3591102","DOI":"10.1145\/3558481.3591102"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","unstructured":"Jeehoon Kang and Jaehwang Jung. 2020. A marriage of pointer - and epoch-based reclamation. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London UK) (PLDI 2020). Association for Computing Machinery New York NY USA 314\u2013328. doi:10.1145\/3385412.3385978","DOI":"10.1145\/3385412.3385978"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Maged M. Michael. 2002. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures (Winnipeg Manitoba Canada) (SPAA \u201902). Association for Computing Machinery New York NY USA 73\u201382. doi:10.1145\/564870.564881","DOI":"10.1145\/564870.564881"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.8"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","unstructured":"Maged M. Michael and Michael L. Scott. 1996. Simple fast and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing (Philadelphia Pennsylvania USA) (PODC \u201996). Association for Computing Machinery New York NY USA 267\u2013275. doi:10.1145\/248052.248106","DOI":"10.1145\/248052.248106"},{"key":"e_1_3_2_23_2","unstructured":"Microsoft . 2021. Windows App Development: Interlocked Singly Linked Lists. https:\/\/learn.microsoft.com\/en-us\/windows\/win32\/sync\/interlocked-singly-linked-lists."},{"key":"e_1_3_2_24_2","unstructured":"Microsoft . 2024. Mimalloc allocator. https:\/\/github.com\/microsoft\/mimalloc."},{"key":"e_1_3_2_25_2","unstructured":"MIPS . 2016. MIPS32\/MIPS64 Rev. 6.06. http:\/\/www.mips.com\/products\/architectures\/."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","unstructured":"Aravind Natarajan and Neeraj Mittal. 2014. Fast concurrent lock-free binary search trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Orlando Florida USA) (PPoPP \u201914). Association for Computing Machinery New York NY USA 317\u2013328. doi:10.1145\/2555243.2555256","DOI":"10.1145\/2555243.2555256"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","unstructured":"Ruslan Nikolaev and Binoy Ravindran. 2020. Universal wait-free memory reclamation. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (San Diego California) (PPoPP \u201920). Association for Computing Machinery New York NY USA 130\u2013143. doi:10.1145\/3332466.3374540","DOI":"10.1145\/3332466.3374540"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","unstructured":"Ruslan Nikolaev and Binoy Ravindran. 2021. Snapshot-free transparent and robust memory reclamation for lock-free data structures. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (Virtual Canada) (PLDI 2021). Association for Computing Machinery New York NY USA 987\u20131002. doi:10.1145\/3453483.3454090","DOI":"10.1145\/3453483.3454090"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3658851"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","unstructured":"Ruslan Nikolaev Mincheol Sung and Binoy Ravindran. 2020. LibrettiOS: a dynamically adaptable multiserver-library OS. In Proceedings of the 16th ACM SIGPLAN\/SIGOPS International Conference on Virtual Execution Environments (Lausanne Switzerland) (VEE \u201920). Association for Computing Machinery New York NY USA 114\u2013128. doi:10.1145\/3381052.3381316","DOI":"10.1145\/3381052.3381316"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","unstructured":"Pedro Ramalhete and Andreia Correia. 2017. Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (Washington DC USA) (SPAA \u201917). Association for Computing Machinery New York NY USA 367\u2013369. doi:10.1145\/3087556.3087588","DOI":"10.1145\/3087556.3087588"},{"key":"e_1_3_2_32_2","unstructured":"RISC-V International . 2024. Ratified Specification. https:\/\/riscv.org\/specifications\/ratified\/."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","unstructured":"Gali Sheffi Maurice Herlihy and Erez Petrank. 2021. VBR: Version Based Reclamation. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (Virtual Event USA) (SPAA \u201921). Association for Computing Machinery New York NY USA 443\u2013445. doi:10.1145\/3409964.3461817","DOI":"10.1145\/3409964.3461817"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","unstructured":"Ajay Singh Trevor Brown and Ali Mashtizadeh. 2021. NBR: neutralization based reclamation. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Virtual Event Republic of Korea) (PPoPP \u201921). Association for Computing Machinery New York NY USA 175\u2013190. doi:10.1145\/3437801.3441625","DOI":"10.1145\/3437801.3441625"},{"key":"e_1_3_2_35_2","unstructured":"R. K. Treiber. 1986. Systems Programming: Coping with Parallelism. Technical Report RJ 5118. IBM Almaden Research Center."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","unstructured":"Haosen Wen Joseph Izraelevitz Wentao Cai H. Alan Beadle and Michael L. Scott. 2018. Interval-based memory reclamation. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Vienna Austria) (PPoPP \u201918). Association for Computing Machinery New York NY USA 1\u201313. doi:10.1145\/3178487.3178488","DOI":"10.1145\/3178487.3178488"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:04:34Z","timestamp":1784196274000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":35,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729337"],"URL":"https:\/\/doi.org\/10.1145\/3729337","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}