Concurrent Data Structures Made Easy (Extended Version)
<|reference_start|>Concurrent Data Structures Made Easy (Extended Version): Design of an efficient thread-safe concurrent data structure is a balancing act between its implementation complexity and performance. Lock-based concurrent data structures, which are relatively easy to derive from their sequential counterparts and to prove thread-safe, suffer from poor throughput under even light multi-threaded workload. At the same time, lock-free concurrent structures allow for high throughput, but are notoriously difficult to get right and require careful reasoning to formally establish their correctness.   We explore a solution to this conundrum based on batch parallelism, an approach for designing concurrent data structures via a simple insight: efficiently processing a batch of a priori known operations in parallel is easier than optimising performance for a stream of arbitrary asynchronous requests. Alas, batch-parallel structures have not seen wide practical adoption due to (i) the inconvenience of having to structure multi-threaded programs to explicitly group operations and (ii) the lack of a systematic methodology to implement batch-parallel structures as simply as lock-based ones.   We present OBatcher-an OCaml library that streamlines the design, implementation, and usage of batch-parallel structures. It solves the first challenge (how to use) by suggesting a new lightweight implicit batching design that is built on top of generic asynchronous programming mechanisms. The second challenge (how to implement) is addressed by identifying a family of strategies for converting common sequential structures into efficient batch-parallel ones. We showcase OBatcher with a diverse set of benchmarks. Our evaluation of all the implementations on large asynchronous workloads shows that (a) they consistently outperform the corresponding coarse-grained lock-based implementations and that (b) their throughput scales reasonably with the number of processors.<|reference_end|>
@article{le2024concurrent,
    title={Concurrent Data Structures Made Easy (Extended Version)},
    author={Callista Le, Kiran Gopinathan, Koon Wen Lee, Seth Gilbert, Ilya Sergey},
    journal={arXiv preprint arXiv:2408.13779},
    year={2024},
    doi={10.1145/3689775},
    archivePrefix={arXiv},
    eprint={2408.13779},
    primaryClass={cs.PL cs.DC}
}