EUVIMEDEUVIMED entdecken
Open Access · CC BY-SA 4.0

Concurrent Data Structures Made Easy

Callista Le, Kiran Gopinathan, Koon Wen Lee, Seth Gilbert, Ilya Sergey

Proceedings of the ACM on Programming Languages · 08.10.2024 · 8 (OOPSLA2) · 1814-1842

DOI: 10.1145/3689775 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 08.10.2024. Verfasst von Callista Le und 4 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 55 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-SA 4.0). Gefördert von: Singapore Ministry of Education.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. In this work, we explore a solution to this conundrum based on a relatively old idea of batch parallelism —an approach for designing high-throughput 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 OB atcher —a Multicore 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, and by providing functors that embody those strategies. 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.

Förderung

  • Singapore Ministry of Education

Zitieren

APA

Le, C., Gopinathan, K., Lee, K. W., Gilbert, S., & Sergey, I. (2024). Concurrent Data Structures Made Easy. Proceedings of the ACM on Programming Languages, 8(OOPSLA2), 1814-1842. https://doi.org/10.1145/3689775

Vancouver

Le C, Gopinathan K, Lee KW, Gilbert S, Sergey I. Concurrent Data Structures Made Easy. Proceedings of the ACM on Programming Languages. 2024;8(OOPSLA2):1814-1842. doi:10.1145/3689775

BibTeX
@article{Le2024,
  author = {Le, Callista and Gopinathan, Kiran and Lee, Koon Wen and Gilbert, Seth and Sergey, Ilya},
  title = {Concurrent Data Structures Made Easy},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {OOPSLA2},
  pages = {1814--1842},
  doi = {10.1145/3689775}
}
Kostenlos starten →