Concurrent Data Structures Made Easy
summary
Library named OBatcher implements implicit batching in Multicore OCaml using async/await and functors; implicit-batching core is ~230 LOC, each generic strategy 150–200 LOC, a Rust prototype ~150 LOC. Batch-parallel strategies (notably split-join and expose-repair) convert sequential structures—Red‑Black, AVL, van Emde Boas, skip lists, plus a Datalog solver—into parallel versions. Benchmarks run with 2 million initial elements and 1 million concurrent operations; batch versions beat coarse‑grained locks from two domains onward and scale, but a hand-tuned fine‑grain skip list still outperforms due to batching overhead.
AI-written summary · about
chapters (11)
- 0:00Concurrent data structures intro
- 1:46Coarse vs fine-grained limits
- 3:31Batch parallelism intro
- 5:40Split-join strategy
- 9:14Implementation & benchmarks
- 12:44Datalog solver batching
- 13:25Key takeaways & future
- 14:08Q&A: Supported ops & factors
- 15:56Q&A: Caching impact
- 17:03Q&A: Deadlocks in batch
- 18:07Q&A: Deletion handling
related talks
23mParallel Sequences in Multicore OCaml
40mRetrofitting Concurrency – Lessons from the Engine Room
40mWhen magic meets multicore - OCaml and its elegant era of parallelism
44mThe Parallel Batch-Dynamic Model with Asynchronous Reads
01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
01h 02mIntro to Concurrent Programming 2/3: Modern Queues and Flat Combining
16mWhen Concurrency Matters: Behaviour-Oriented Concurrency
49mStriving to Make Things Simple and Fast