Building a Lock-Free Multi-producer, Multi-consumer Queue for Tcmalloc - CppCon 2021 Summary
0:27 Introduction: Matt Kulukundis introduces the talk, focusing on his work building a lock-free multi-producer, multi-consumer queue for tcmalloc, Google's malloc implementation.
1:49 Tcmalloc Overview: Tcmalloc is presented as a series of caches (per-CPU cache, transfer cache, central free list) aiming to efficiently manage memory allocation requests. The transfer cache is identified as a bottleneck due to its mutex.
3:52 Concurrent Programming Principles: Rich Hickey's "Are We There Yet?" talk is referenced, emphasizing that observation shouldn't block mutation in well-designed concurrent systems.
5:35 Importance of Formalism: Jeremy Manson's "The Java Memory Model" talk is mentioned, stressing the importance of understanding concepts like "happens-before" for correct concurrent programming.
6:24 The Disruptor Pattern: The LMAX Disruptor pattern is introduced as a major inspiration for the queue design, featuring multiple producers and consumers working on different sections of a ring buffer.
7:16 Multi-producer, Multi-consumer Queue Design: The core design of the lock-free queue is explained, utilizing pending and committed pointers to allow concurrent operations with minimal synchronization points.
11:35 Claim Insert & Commit Line Implementation: Code examples for claiming space in the queue (claim insert) and advancing the commit line are shown, highlighting the use of atomic operations and spinlocks.
16:08 Tcmalloc Optimization and Testing: Refactoring tcmalloc to enable unit testing and experimentation with the transfer cache is discussed. Whitebox testing strategies and a randomized poking approach are explained.
20:58 Debugging with Sanitizers: The importance of tools like ASan, MSan, UBSan, and TSan for detecting data races and other concurrency bugs is emphasized.
22:50 The ABA Bug: A subtle ABA bug is identified, and the traditional epoch counter solution is considered. A clever workaround is implemented by leveraging unused bits in pointers to effectively prevent ABA issues within a reasonable timeframe.
28:09 Benchmarks and Artificial Environments: Micro-benchmarks show significant performance improvements with the new queue, but these gains don't translate to real-world web search performance. The limitations of artificial benchmarks are discussed.
32:59 Stat Counters for Insights: Stat counters are added to the micro-benchmarks to measure hit ratios, revealing that the new queue leads to increased fallback to the central free list under high contention.
34:15 Adapting the Queue Logic: The queue logic is modified to "sniff" the tail for ongoing operations and potentially wait instead of immediately falling back to the central free list. This reduces contention and improves performance.
35:51 Introducing Futex: Futex is presented as a powerful kernel primitive for building efficient user-space synchronization mechanisms. Futex operations like futex_wait and futex_wake are explained.
38:35 Optimizing with Futex: The spinlocks in await_change and advance_commit_line are replaced with Futex-based waiting, reducing CPU waste and improving responsiveness. A bitset-based wake-up strategy is employed to selectively wake only the necessary threads.
42:19 Performance Results: The Futex-optimized queue performs well in micro-benchmarks, achieving higher hit rates than even the original mutex-based implementation.
43:14 Web Search Results: Web search performance is no longer negatively impacted by the new queue. However, statistically significant improvements are not observed in web search or other production systems.
45:15 Conclusion and Future Work: Despite the lack of major production wins, the project provided valuable learning experiences in refactoring, testing, debugging, and understanding concurrent data structure behavior. Future work may explore techniques like flat combiners and elimination buckets to further improve performance.