Abstract | ||
---|---|---|
Efficient multicore programming demands fundamental data structures that support a high degree of concurrency. Existing research on non-blocking data structures promises to satisfy such demands by providing progress guarantees that allow a significant increase in parallelism while avoiding the safety hazards of lock-based synchronizations. It is well-acknowledged that the use of non-blocking containers can bring significant performance benefits to applications where the shared data experience heavy contention. However, the practical implications of integrating these data structures in real-world applications are not well-understood. In this paper, we study the effective use of non-blocking data structures in a data deduplication application which performs a large number of concurrent compression operations on a data stream using the pipeline parallel processing model. We present our experience of manually refactoring the application from using conventional lock-based synchronization mechanisms to using a wait-free hash map and a set of lock-free queues to boost the degree of concurrency of the application. Our experimental study explores the performance trade-offs of parallelization mechanisms that rely on a) traditional blocking techniques, b) fine-grained mutual exclusion, and c) lock-free and wait-free synchronization. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1145/2508075.2508431 | SPLASH (Companion Volume) |
Keywords | Field | DocType |
non-blocking data structure,shared data,conventional lock-based synchronization mechanism,real-world application,data deduplication application,non-blocking container,fundamental data structure,data structure,data stream,effective use | Data deduplication,Data structure,Programming language,Lock (computer science),Computer science,Data stream,Concurrency,Real-time computing,Mutual exclusion,Code refactoring,Hash table,Distributed computing | Conference |
Citations | PageRank | References |
2 | 0.38 | 18 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Steven D. Feldman | 1 | 17 | 3.56 |
Akshatha Bhat | 2 | 11 | 0.89 |
Pierre LaBorde | 3 | 14 | 3.85 |
Qing Yi | 4 | 190 | 11.89 |
Damain Dechev | 5 | 2 | 0.38 |