Abstract
Do you like optimizing code? Do you feel the adrenaline rush of making things unnecessarily fast? Do you get frustrated when slow programs are single-threaded? Then I *cannot* recommend concurrent data structures. Stay away from them -- they are awfully fun and awfully painful.
In this talk, I'll show you why. I'm writing a Rust compiler with performance as the first priority, and I've written several concurrent data structures to help it parallelize work. Each one was a distinct monster that needed a unique approach; but I have collected some common tools and paradigms that ease that work. I'm going to talk about the very worst one -- managing heap allocations. You see, in the dark and subtle world of concurrent programming, there may be ghosts on your heap.
"But, Arya!" you cry. "Rust has `Drop` -- we don't worry about heap allocations anymore!" Unfortunately for you, young padawan, `Drop` can't save us today. Suppose your concurrent data structure needs to grow and reallocate memory -- when is it safe to deallocate it? How do you know that no thread is accessing that memory? You might say "We have `Arc`!" but `Arc` doesn't work here either. Your threads can see ghosts on the heap, and preventing this is hard.
It turns out this problem has a name -- concurrent memory reclamation. I'm going to tell you how I ran into it, existing solutions for it, and how I built [my own implementation](https://docs.rs/housekeeping). I'll show you the concurrent hash table I built on top of it, and compare `housekeeping` to existing solutions.
For those of you who wisely avoid concurrent data structures, I hope this shows you you made the right choice. If it's too late for you, and you are already writing your own -- I hope you find this tool and its history helpful in your quest. Good luck.
