Is there a functional algorithm which is faster than an imperative one?

Question

I'm searching for an algorithm (or an argument of such an algorithm) in functional style which is faster than an imperative one.

I like functional code because it's expressive and mostly easier to read than it's imperative pendants. But I also know that this expressiveness can cost runtime overhead. Not always due to techniques like tail recursion - but often they are slower.

While programming I don't think about runtime costs of functional code because nowadays PCs are very fast and development time is more expensive than runtime. Furthermore for me readability is more important than performance. Nevertheless my programs are fast enough so I rarely need to solve a problem in an imperative way.

There are some algorithms which in practice should be implemented in an imperative style (like sorting algorithms) otherwise in most cases they are too slow or requires lots of memory. In contrast due to techniques like pattern matching a whole program like a parser written in an functional language may be much faster than one written in an imperative language because of the possibility of compilers to optimize the code.

But are there any algorithms which are faster in a functional style or are there possibilities to setting up arguments of such an algorithm?

Answer 1

The short answer:

Anything that can be easily made parallel because it's free of side-effects will be quicker on a multi-core processor.

QuickSort, for example, scales up quite nicely when used with immutable collections: http://en.wikipedia.org/wiki/Quicksort#Parallelization

All else being equal, if you have two algorithms that can reasonably be described as equivalent, except that one uses pure functions on immutable data, while the second relies on in-place mutations, then the first algorithm will scale up to multiple cores with ease.

It may even be the case that your programming language can perform this optimization for you, as with the scalaCL plugin that will compile code to run on your GPU. (I'm wondering now if SIMD instructions make this a "functional" processor)

So given parallel hardware, the first algorithm will perform better, and the more cores you have, the bigger the difference will be.

Answer 2

A simple reasoning. I don't vouch for terminology, but it seems to make sense.

• A functional program, to be executed, will need to be transformed into some set of machine instructions.
• All machines (I've heard of) are imperative.
• Thus, for every functional program, there's an imperative program (roughly speaking, in assembler language), equivalent to it.

So, you'll probably have to be satisfied with 'expressiveness', until we get 'functional computers'.