[stinkypete]

Immutable data structures let you use compare-and-swap to guarantee all updates to a shared reference are atomic. This can be a win if the amount of contention is low enough such that optimistically generating and setting the modified version usually succeeds, particularly if that modified version can be created in log or amortized constant time.

Another benefit is that since the data structures are immutable you can easily operate over snapshots of them with no worries as to what other threads are doing. This can make them easier to code against and can sometimes be much easier to deal with than locks since you avoid most deadlock/livelock problems that you usually have to worry about with locking, though if you're using straight-up CAS you do have to be mindful of the A-B-A problem.