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.
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.
This is a description of what a data dependency is; I'm still not sure what your point is regarding mutable data structures specifically.
Now, call it mutable, but don't change a thing. Congratulations, it's now a mutable data structure that's exactly as fast as your favorite immutable one.
_But_ you now have extra opterations you can perform to optimize slow parts if you can. You have strictly more power than you started with, because you can modify data. You don't have to, but you can.
Just don't make any bad optimizations. If some attempt to make it better instead makes it worse, go back to the starting point and try something else.
The point is that this procedure applies to anything. Immutable data structures are a strict subset of mutable ones. Every immutable data structure is open to moving any number of steps, in any direction, in the space of data structures. It's _purely_ extra freedom that immutable data structures don't have.
If you want specific ones, first things that would come to mind for me is to start with any immutable tree impl, and start adding small mutable ~caching things on top. Batch up updates a bit to try to avoid repeated deep traversals maybe. You can do this without adding much complexity at all, and it's very flexibly for whatever operations or access patterns you want to improve.
I get that you can imagine it. I'm saying it wouldn't work in practice.
No it won't, not at the myriads of places they're needed when there are mutations all over the place.
Of course there are mutations in FP, so of course sometimes we need write locks and use things like CAS.
The point is not that FP doesn't use them, but that it uses them far less because they are needed only in a very limited number of places.
When I write code with STM, for example, the only uses of locks or CAS are in the STM engine, not in my Haskell code, and not even in my compiled code, because my code only ever reads memory that's immutable, and immutable data structures.
When I write pure code, there are no locks at all. And that makes it trivial to execute in parallel, either out of order or on several cores.
Even when you aren't writing concurrent code, mutability will prevent the CPU from using its internal concurrency to execute it faster.
Also, immutable data structures can include caches that are extremely simple whereas mutable data structure would face the problem if cache invalidation if they tried.
And a mutable data structure that would operate as if it's immutable? That's a nice recipe for an epic disaster.