Correctness is very important. But being correct and faster is better. A lot of the techniques I use to accomplish that start to look similar to immutable. Copy on write is the cornerstone of good lock-free algorithms as well as immutable data structures. However, not being religious about mutability has tangible performance benefits - depending on the details, as always.
Immutability is easier (safer, more correct) on the whole. I think both Rust and Clojure take a good stance on mutation.
Only for anecdotal evidence, my ad-hoc immutable (lots of copying) ETLs performed better than the mutation happy ones. The GC was able to throw stuff away faster, the code was cleaner, kept only what it needed. The gaussian circle of confusion was smaller.
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.
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.
