> When you use a mutable data structure, and your code is concurrent, you'll force the CPU to put locks everywhere in your code so that several cores won't see stale data in their internal caches.

Do you mean to say the compiler will insert locks? As far as I'm aware, on AMD64/Intel64, the processor won't lock the bus for ordinary loads and stores unless an instruction has the lock prefix. The processor is otherwise perfectly happy to let different cores observe loads and stores to different addresses in different orders (except for stores being reordered past each other).

> Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster.

For an out-of-order superscalar machine, mutability has nothing to do with it; register renaming takes care of that. The things to watch out for are tight dependencies chains.

If you're referring to loads and stores, store-forwarding and coalescing can spare you from having to hit the cache repeatedly for reads and writes to the same location.