Sunday, 6 May 2012

Functional programming and multicores


I've read somewhere that functional programming is suitable to take advantage of multi-core trend in computing... I didn't really get the idea. Is it related to the lambda calculus and von neumann architecture?
The argument behind the belief you quoted is that purely functional programming controls side effects which makes it much easier and safer to introduce parallelism and, therefore, that purely functional programming languages should be advantageous in the context of multicore computers.
Unfortunately, this belief was long since disproven for several reasons:
  • The absolute performance of purely functional data structures is poor. So purely functional programming is a big initial step in the wrong direction in the context of performance (which is the sole purpose of parallel programming).
  • Purely functional data structures scale badly because they stress shared resources including the allocator/GC and main memory bandwidth. So parallelized purely functional programs often obtain poor speedups as the number of cores increases.
  • Purely functional programming renders performance unpredictable. So real purely functional programs often see performance degradation when parallelized because granularity is effectively random.
For example, the two-line "quicksort" in Haskell typically runs thousands of times slower than a real in-place quicksort written in a more conventional language like F#. Moreover, although you can easily parallelize the elegant Haskell program the result does not scale well on a multicore because all of the unnecessary copying makes a single core saturate the entire main memory bandwidth of a multicore machine, rendering parallelism worthless.
However, functional programming as a style that emphasizes the use of first-class functions does actually turn out to be very useful in the context of multicore programming because this paradigm is ideal for factoring parallel programs. For example, see the new higher-orderParallel.For function from the System.Threading.Tasks namespace in .NET 4.

2 comments:

coco said...

Interesting, I've read your post about "F# Map vs .NET Dictionary performance" and I was searching any benchmark between clojure maps and native java...I guess clojure is slower but I'm not sure if is so dramatic...clojure is much more functional than f# (although they are similar, the clojure community only use mutable data when it is really necesary) and the clojure performance is not so bad (you must considered it's a dynamic language too...

For me (I come from clojure and CLips) functional code is much more readable and expressive, f# code seems olny a better c# where the programmers only encapsulate mutable code between functions, and problem solve!!..

Is really a lack than f# inmutable estructure be so slow?, can be it improve??...o the real solution for multicore and hight performance is a language with functional tools but where you program in an wmpiric way??...

Flying Frog Consultancy Ltd. said...

@coco: "functional code is much more readable and expressive". Not always. Graph algorithms are one place where functional programming falls down, not least because there are no purely functional weak dictionaries. The implementations of many graph algorithms in languages like Haskell are several times longer than their C equivalents.

"Is really a lack than f# inmutable estructure be so slow?, can be it improve??...o the real solution for multicore and hight performance is a language with functional tools but where you program in an wmpiric way??" Improvements to the .NET garbage collector could dramatically improve the performance of purely functional data structures. Some significant advances were made in .NET 4. But it is not possible for purely functional data structures to be competitively performant in the general case. They come with too much baggage.