[eloff]

It's very hard. Bugs in lock-free algorithms are the only class of bugs that have defeated me. I once worked for three months of evenings trying to fix one, before throwing in the towel. I learned from that experience to use only very simple algorithms. Adhering to the single-writer principle[1] helps a lot. When changes and deletes can't interact because they're all on the same thread, life is a _LOT_ easier.

[1] http://mechanical-sympathy.blogspot.com/2011/09/single-write...

[sitkack]

I don't have any evidence, but I have a gut feeling that if we had immutable, write-once persistent data structures, we could relax coherency _a whole lot_ and gain a huge bandwidth and latency advantage. Memory ordering to support mutability is an expensive abstraction.