Concurrent Data Structures Made Easy (Extended Version)

Overview

• Designing efficient concurrent data structures involves balancing implementation complexity and performance.
• Lock-based structures are easy to implement but suffer from poor throughput.
• Lock-free structures offer high throughput but are difficult to implement correctly.
• Batch parallelism is a promising approach, but has not seen wide adoption due to inconvenient usage and lack of a systematic implementation methodology.

Plain English Explanation

When you're building software that needs to handle multiple tasks at the same time (a "concurrent" system), one of the key challenges is designing data structures that can be safely accessed by multiple threads of execution without running into problems. Lock-based concurrent data structures are relatively straightforward to build, as you can just take your existing data structures and add locks to protect them. However, this approach often leads to poor performance, especially when you have a lot of threads trying to access the data at the same time.

On the other hand, lock-free concurrent structures can offer much better throughput, but they're notoriously difficult to implement correctly. You have to be really careful to avoid race conditions and other subtle concurrency issues.

The researchers in this paper propose a middle ground - an approach called "batch parallelism." The key insight is that it's easier to efficiently process a batch of related operations in parallel than to optimize for a stream of arbitrary, asynchronous requests. However, batch-parallel structures haven't been widely adopted, mainly because it's inconvenient for developers to have to explicitly group their operations into batches, and there hasn't been a systematic way to implement these structures as easily as the lock-based ones.

Technical Explanation

The researchers present a new OCaml library called OBatcher that addresses these challenges. It provides a lightweight, implicit batching mechanism built on top of generic asynchronous programming tools, making it easier for developers to use batch-parallel structures. To implement these structures, the researchers identify a family of strategies for converting common sequential data structures into efficient batch-parallel versions.

The paper evaluates OBatcher's performance across a variety of benchmarks, showing that the batch-parallel implementations consistently outperform their coarse-grained, lock-based counterparts, and that their throughput scales reasonably as the number of processing cores increases.

Critical Analysis

The paper presents a promising approach to designing efficient concurrent data structures, but it's worth considering a few potential limitations and areas for future research:

• The evaluation focuses on large asynchronous workloads, but it's not clear how the batch-parallel structures would perform under different types of concurrency patterns, such as streaming dynamic graph processing or concurrent aggregate queries.
• The paper doesn't explore the impact of the batch size on performance, or provide guidance on how to choose an optimal batch size for different use cases.
• The proposed strategies for converting sequential data structures into batch-parallel versions may not be applicable to all types of data structures, and the paper doesn't discuss the generalizability of the approach.

Conclusion

The OBatcher library and the batch parallelism approach it embodies offer a compelling middle ground between lock-based and lock-free concurrent data structures. By making it easier to design and use batch-parallel structures, the researchers have taken an important step towards improving the performance and usability of concurrent systems. While the technique has some limitations, it represents a promising direction for future research and development in the field of concurrent data structure design.