Comment by adwn

You seem to forget that the CPU and memory system, on which you're executing your immutable data structure implementations, provide a fundamentally mutable interface. So the compiler of your immutable language will still have to insert locks and atomic instructions (although not necessarily the same or at the same places).