How to avoid mutable state (when multithreading)

Question

Multithreading is hard. The only this you can do is program very carefully and follow good advice. One great advice I got from the answers on this forum is to avoid mutable state. I understand this is even enforced in the Erlang language. However, I fail to see how this can be done without a severe performance hit and huge amounts of caches.

For example. You have a big list of objects, each containing quite a lot of properties; in other words: a large datastructure. Suppose you have got a bunch of threads and they all need to access and modify the list. How can this be done without shared memory without having to cache the whole datastructure in each of the threads?

Update: After reading the reactions so far, I would like to put some more emphasis on performance. Don't you think that copying the same data around will make the program slower than with shared memory?

Answer 1

Not each algorithm can be parallelized in a successful manner.

If your program doesn't exhibit any "parallel structure", then you're pretty doomed to use locking and shared, mutable structures.

If your algorithm exhibit structure, then you can express your computation in terms of some patterns or formalism (for ex., a macro dataflow graph) that makes the choice of an immutable datastruct trivial.

So: think in term of the structure of the algorithm and just not in term of the properties of the datastructure to use.

Answer 2

You can get a great start in thinking about immutable collections, where they are applicable, how they can actually work without requiring lots of copying, etc. by looking through Eric Lippert's articles tagged with immutability:

http://blogs.msdn.com/ericlippert/archive/tags/Immutability/default.aspx