[agalunar]

> 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.

[kephasp]

> Do you mean to say the compiler will insert locks?

I think you're right, it's the compiler that'll insert the locks according to the semantics of the language.

> For an out-of-order superscalar machine, mutability has nothing to do with it;

Yes it does, because it creates data dependencies. If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A.

[agalunar]

> If a piece of code B loads the contents of memory where a piece of code A writes that's before B, then you can never execute B before or in parallel with A.

This is a description of what a data dependency is; I'm still not sure what your point is regarding mutable data structures specifically.

[kephasp]

A mutable data structure will have such data dependencies all around. An immutable data structure cannot, because it will never be written in after creation.

[agalunar]

But an immutable data structure will cause data dependencies – the only way it couldn't cause a data dependency would be if it was never read.

[kephasp]

But once it is created, all pieces of code accessing it can be executed in any order because there will never be a write on it again.