title: Best Practices for cache locality in Multicore Parallelism in F#
body: <p>I'm studying multicore parallelism in F#.  I have to admit that immutability really helps to write correct parallel implementation.  However, it's hard to achieve good speedup and good scalability when the number of cores grows.  For example, my experience with Quick Sort algorithm is that many attempts to implement parallel Quick Sort in a purely functional way and using <code>List</code> or <code>Array</code> as the representation are failed.  Profiling those implementations shows that the number of cache misses increases significantly compared to those of sequential versions. However, if one implements parallel Quick Sort using mutation inside arrays, a good speedup could be obtained. Therefore, I think mutation might be a good practice for optimizing multicore parallelism.</p>
  
  <p>I believe that <a href="http://en.wikipedia.org/wiki/Locality_of_reference" rel="nofollow">cache locality</a> is a big obstacle for multicore parallelism in a functional language. Functional programming involves in creating many short-lived objects; destruction of those objects may destroy coherence property of CPU caches. I have seen many suggestions how to improve cache locality in imperative languages, for example, <a href="http://drdobbs.com/high-performance-computing/196902836" rel="nofollow">here</a> and <a href="http://www.codeproject.com/KB/threads/FalseSharing.aspx" rel="nofollow">here</a>. But it's not clear to me how they would be done in functional programming, especially with recursive data structures such as trees, etc, which appear quite often.</p>
  
  <p><em>Are there any techniques to improve cache locality in an impure functional language (specifically F#)</em>? Any advices or code examples are more than welcome.</p>