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