{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T15:13:18Z","timestamp":1714057998256},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p> This paper presents a fast concurrent binary search tree algorithm. To achieve high performance under contention, the algorithm divides update operations within an eager abstract access that returns rapidly for efficiency reason and a lazy structural adaptation that may be postponed to diminish contention. To achieve high performance under read-only workloads, it features a rebalancing mechanism and guarantees that read-only operations searching for an element execute lock-free. <\/jats:p><jats:p> We evaluate the contention-friendly binary search tree using Synchrobench, a benchmark suite to compare synchronization techniques. More specifically, we compare its performance against five state-of-the-art binary search trees that use locks, transactions or compare-and-swap for synchronization on Intel Xeon, AMD Opteron and Oracle SPARC. Our results show that our tree is more efficient than other trees and double the throughput of existing lock-based trees under high contention. <\/jats:p>","DOI":"10.1142\/s0129626416500158","type":"journal-article","created":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T22:37:55Z","timestamp":1474411075000},"page":"1650015","source":"Crossref","is-referenced-by-count":5,"title":["A Fast Contention-Friendly Binary Search Tree"],"prefix":"10.1142","volume":"26","author":[{"given":"Tyler","family":"Crain","sequence":"first","affiliation":[{"name":"INRIA, France"}]},{"given":"Vincent","family":"Gramoli","sequence":"additional","affiliation":[{"name":"NICTA and University of Sydney, Australia"}]},{"given":"Michel","family":"Raynal","sequence":"additional","affiliation":[{"name":"Institut Universitaire de France and Universit\u00e9 de Rennes, France"}]}],"member":"219","published-online":{"date-parts":[[2016,9,20]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289509"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1511"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407003125"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1145\/182.358442"},{"issue":"2","key":"p_27","volume":"5","author":"Korland G.","year":"2010","journal-title":"Transactions on HiPEAC"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050057"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626416500158","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:15:24Z","timestamp":1565097324000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626416500158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":8,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2016,9,20]]},"published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1142\/S0129626416500158"],"URL":"https:\/\/doi.org\/10.1142\/s0129626416500158","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}