One thing I've picked up, looking at Clojure, is that the lack of mutable state allows certain cool optimizations. For example, let's say you have a map A with a million key-value pairs. You want to do something with B = A + (k', v'). In a mutable-state language, you'd physically add (k', v') to the map, which is usually implemented as a hash table. Clojure creates a new map (32-ary tree) for B that shares most of its pointers and structure with A, which allows you to do FP without FP's greatest drawback, which is the copying of large data structures. Since the nodes will never change, this sharing is entirely safe. A remains entirely unchanged, so a thread working with A still has A.
Functional programming doesn't actually eliminate side effects and mutability. Haskell has the IO and Array monads. Clojure has refs and agents. FP simply segregates them from the rest of the program so that they exist only when desirable, and can be more easily managed.
I don't know the details about cache and local memory. This is a weak area for me.