{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:39:03Z","timestamp":1755999543805,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1102\/21"],"award-info":[{"award-number":["1102\/21"]}],"id":[{"id":"10.13039\/501100003977","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":[[2022,10,31]]},"abstract":"<jats:p>The size of a data structure (i.e., the number of elements in it) is a widely used property of a data set. However, for concurrent programs, obtaining a correct size efficiently is non-trivial. In fact, the literature does not offer a mechanism to obtain a correct (linearizable) size of a concurrent data set without resorting to inefficient solutions, such as taking a full snapshot of the data structure to count the elements, or acquiring one global lock in all update and size operations. This paper presents a methodology for adding a concurrent linearizable size operation to sets and dictionaries with a relatively low performance overhead. Theoretically, the proposed size operation is wait-free with asymptotic complexity linear in the number of threads (independently of data-structure size). Practically, we evaluated the performance overhead by adding size to various concurrent data structures in Java\u2212a skip list, a hash table and a tree. The proposed linearizable size operation executes faster by orders of magnitude compared to the existing option of taking a snapshot, while incurring a throughput loss of 1%\u221220% on the original data structure\u2019s operations.<\/jats:p>","DOI":"10.1145\/3563300","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T20:23:35Z","timestamp":1667247815000},"page":"345-372","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Concurrent size"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2342-6955","authenticated-orcid":false,"given":"Gal","family":"Sela","sequence":"first","affiliation":[{"name":"Technion, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6353-956X","authenticated-orcid":false,"given":"Erez","family":"Petrank","sequence":"additional","affiliation":[{"name":"Technion, Israel"}]}],"member":"320","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2022. Java Platform Version 18 API Specification. https:\/\/docs.oracle.com\/en\/java\/javase\/18\/docs\/api\/index.html \t\t\t\t  2022. Java Platform Version 18 API Specification. https:\/\/docs.oracle.com\/en\/java\/javase\/18\/docs\/api\/index.html"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.03.007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178489"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185815"},{"key":"e_1_2_1_6_1","unstructured":"Trevor Brown. 2018. Java Lock-Free Data Structure Library. https:\/\/bitbucket.org\/trbot86\/implementations\/src\/master\/java\/src\/algorithms\/published \t\t\t\t  Trevor Brown. 2018. Java Lock-Free Data Structure Library. https:\/\/bitbucket.org\/trbot86\/implementations\/src\/master\/java\/src\/algorithms\/published"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276478"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835736"},{"key":"e_1_2_1_10_1","unstructured":"Keir Fraser. 2004. Practical lock-freedom. Ph. D. Dissertation. \t\t\t\t  Keir Fraser. 2004. Practical lock-freedom. Ph. D. Dissertation."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45414-4_21"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72951-8_11"},{"key":"e_1_2_1_15_1","unstructured":"Maurice Herlihy and Nir Shavit. 2008. The art of multiprocessor programming. Morgan Kaufmann. \t\t\t\t  Maurice Herlihy and Nir Shavit. 2008. The art of multiprocessor programming. Morgan Kaufmann."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060697"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675439"},{"key":"e_1_2_1_19_1","unstructured":"Doug Lea. 2004. The java concurrency package (JSR-166). http:\/\/gee.cs.oswego.edu\/dl\/concurrency-interest \t\t\t\t  Doug Lea. 2004. The java concurrency package (JSR-166). http:\/\/gee.cs.oswego.edu\/dl\/concurrency-interest"},{"volume-title":"Distributed algorithms","author":"Lynch Nancy A","key":"e_1_2_1_20_1","unstructured":"Nancy A Lynch . 1996. Distributed algorithms . Elsevier . Nancy A Lynch. 1996. Distributed algorithms. Elsevier."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2989225.2989233"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508412"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_16"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00412-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467944"},{"key":"e_1_2_1_26_1","volume-title":"Linearizability: A typo. arXiv preprint, arxiv:2105.06737.","author":"Sela Gal","year":"2021","unstructured":"Gal Sela , Maurice Herlihy , and Erez Petrank . 2021 . Linearizability: A typo. arXiv preprint, arxiv:2105.06737. Gal Sela, Maurice Herlihy, and Erez Petrank. 2021. Linearizability: A typo. arXiv preprint, arxiv:2105.06737."},{"key":"e_1_2_1_27_1","unstructured":"Gal Sela and Erez Petrank. 2022. Concurrent Size. arXiv preprint arxiv:2209.07100. \t\t\t\t  Gal Sela and Erez Petrank. 2022. Concurrent Size. arXiv preprint arxiv:2209.07100."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7079982"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/235543.235546"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.12.005"},{"key":"e_1_2_1_31_1","unstructured":"Yuanhao Wei. 2021. vcaslib. https:\/\/github.com\/yuanhaow\/vcaslib \t\t\t\t  Yuanhao Wei. 2021. vcaslib. https:\/\/github.com\/yuanhaow\/vcaslib"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441602"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563300","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:10Z","timestamp":1750178290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":32,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563300"],"URL":"https:\/\/doi.org\/10.1145\/3563300","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2022-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}