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

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'.

Answer 2

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 3

FWIW there are Purely functional data structures, which benefit from functional programming.

There's also a nice book on Purely Functional Data Structures by Chris Okasaki, which presents data structures from the point of view of functional languages.

Another interesting article Announcing Intel Concurrent Collections for Haskell 0.1, about parallel programming, they note:

Well, it happens that the CnC notion of a step is a pure function. A step does nothing but read its inputs and produce tags and items as output. This design was chosen to bring CnC to that elusive but wonderful place called deterministic parallelism. The decision had nothing to do with language preferences. (And indeed, the primary CnC implementations are for C++ and Java.)

Yet what a great match Haskell and CnC would make! Haskell is the only major language where we can (1) enforce that steps be pure, and (2) directly recognize (and leverage!) the fact that both steps and graph executions are pure.

Add to that the fact that Haskell is wonderfully extensible and thus the CnC "library" can feel almost like a domain-specific language.

It doesn't say about performance – they promise to discuss some of the implementation details and performance in future posts, – but Haskell with its "pureness" fits nicely into parallel programming.

Answer 4

One could argue that all programs boil down to machine code.

So, if I dis-assemble the machine code (of an imperative program) and tweak the assembler, I could perhaps end up with a faster program. Or I could come up with an "assembler algorithm" that exploits some specific CPU feature, and therefor it really is faster than the imperative language version.

Does this situation lead to the conclusion that we should use assembler everywhere? No, we decided to use imperative languages because they are less cumbersome. We write pieces in assembler because we really need to.

Ideally we should also use FP algorithms because they are less cumbersome to code, and use imperative code when we really need to.

Answer 5

Well, I guess you meant to ask if there is an implementation of an algorithm in functional programming language that is faster than another implementation of the same algorithm but in an imperative language. By "faster" I mean that it performs better in terms of execution time or memory footprint on some inputs according to some measurement that we deem trustworthy.

I do not exclude this possibility. :)

Answer 6

To elaborate on Yasir Arsanukaev's answer, purely functional data structures can be faster than mutable data structures in some situations becuase they share pieces of their structure. Thus in places where you might have to copy a whole array or list in an imperative language, where you can get away with a fraction of the copying because you can change (and copy) only a small part of the data structure. Lists in functional languages are like this -- multiple lists can share the same tail since nothing can be modified. (This can be done in imperative languages, but usually isn't, because within the imperative paradigm, people aren't usually used to talking about immutable data.)

Also, lazy evaluation in functional languages (particularly Haskell which is lazy by default) can also be very advantageous because it can eliminate code execution when the code's results won't actually be used. (One can be very careful not to run this code in the first place in imperative languages, however.)