{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T18:34:38Z","timestamp":1771958078654,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T00:00:00Z","timestamp":1647993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1102\/21"],"award-info":[{"award-number":["1102\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>Concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such operations can then be executed more efficiently than the standard execution of one operation at a time. In this article, we develop a novel algorithmic extension to the prevalent FIFO queue data structure that exploits such batching scenarios. An implementation in C++ on a multicore demonstrates significant performance improvement of more than an order of magnitude (depending on the batch lengths and the number of threads) compared to previous queue implementations.<\/jats:p>","DOI":"10.1145\/3512757","type":"journal-article","created":{"date-parts":[[2022,3,24]],"date-time":"2022-03-24T22:38:03Z","timestamp":1648161483000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["BQ: A Lock-Free Queue with Batching"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2342-6955","authenticated-orcid":false,"given":"Gal","family":"Milman-Sela","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4419-4340","authenticated-orcid":false,"given":"Alex","family":"Kogan","sequence":"additional","affiliation":[{"name":"Oracle Labs"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3514-8016","authenticated-orcid":false,"given":"Yossi","family":"Lev","sequence":"additional","affiliation":[{"name":"Oracle Labs"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1900-5755","authenticated-orcid":false,"given":"Victor","family":"Luchangco","sequence":"additional","affiliation":[{"name":"Oracle Labs"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6353-956X","authenticated-orcid":false,"given":"Erez","family":"Petrank","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,23]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24100-0_44"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755579"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICECCS.2005.49"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989549"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145849"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345215"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17653-1_23"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/70082.68188"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/69624.357206"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2482767.2482789"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810540"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/210223.210225"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","unstructured":"Moshe Hoffman Ori Shalev and Nir Shavit. 2007. The baskets queue. In Proceedings of the 2007 International Conference on Principles of Distributed Systems (OPODIS\u201907) . 401\u2013414.","DOI":"10.1007\/978-3-540-77096-1_29"},{"key":"e_1_3_2_17_2","volume-title":"Proeedings of PaCT","author":"Kirsch Christoph M.","year":"2013","unstructured":"Christoph M. Kirsch, Michael Lippautz, and Hannes Payer. 2013. Fast and scalable, lock-free k-FIFO queues. In Proeedings of PaCT."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611496"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087838"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0050-0"},{"key":"e_1_3_2_21_2","unstructured":"Doug Lea. 2004. The Java Concurrency Package (JSR-166).http:\/\/gee.cs.oswego.edu\/dl\/concurrency-interest."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.8"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/248052.248106"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210388"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074013"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442527"},{"key":"e_1_3_2_27_2","volume-title":"Proceedings of ICDCN","author":"Shafiei Niloufar","year":"2009","unstructured":"Niloufar Shafiei. 2009. Non-blocking array-based algorithms for stacks and queues. In Proceedings of ICDCN."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378611"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851168"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512757","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3512757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:29Z","timestamp":1750183769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,23]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3512757"],"URL":"https:\/\/doi.org\/10.1145\/3512757","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,23]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}