Are functional languages inherently slow?

Question

Why are functional languages always tailing behind C in benchmarks? If you have a statically typed functional language, it seems to me it could be compiled to the same code as C, or to even more optimized code since more semantics are available to the compiler. Why does it seem like all functional languages are slower than C, and why do they always need garbage collection and excessive use of the heap?

Does anyone know of a functional language appropriate for embedded / real-time applications, where memory allocation is kept to a minimum and the produced machine code is lean and fast?

Answer 1

The short answer: because C is fast. As in, blazingly ridiculously crazy fast. A language simply doesn't have to be 'slow' to get its rear handed to it by C.

The reason why C is fast is that it was created by really great coders, and gcc has been optimized over the course of a couple more decades and by dozens more brilliant coders than 99% of languages out there.

In short, you're not going to beat C except for specialized tasks that require very specific functional programming constructs.

Answer 2

As for now, functional languages aren't used heavily for industry projects, so not enough serious work goes into optimizers. Also, optimizing imperative code for an imperative target is probably way easier.

Functional languages have one feat that will let them outdo imperative languages really soon now: trivial parallelization.

Trivial not in the sense that it is easy, but that it can be built into the language environment, without the developer needing to think about it.

The cost of robust multithreading in a thread-agnostic language like C is prohibitive for many projects.

Answer 3

Functional languages require the elimination of mutable state that is visible at the level of the language abstraction. Therefore, data that would be mutated in place by an imperative language needs to be copied instead, with the mutation taking place on the copy. For a simple example, see a quick sort in Haskell vs. C.

Furthermore, garbage collection is required because free() is not a pure function, as it has side effects. Therefore, the only way to free memory that does not involve side effects at the level of the language abstraction is with garbage collection.

Of course, in principle, a sufficiently smart compiler could optimize out much of this copying. This is already done to some degree, but making the compiler sufficiently smart to understand the semantics of your code at that level is just plain hard.

Answer 4

Will a multithreaded functional language app be faster or slower than a single threaded C app?

I think that is the most important question.

Answer 5

I disagree with tuinstoel. The important question is whether the functional language provides a faster development time and results in faster code when it is used to what functional languages were meant to be used. See the efficiency issues section on Wikipedia for a glimpse of what I mean.

Answer 6

The control flow of proceedural languages much better matches the actual processing patterns of modern computers.

C maps very closely onto the assembly code its compilation produces, hence the nickname "cross-platform assembly". Computer manufacturers have spent a few decades making assembly code run as fast as possible, so C inherits all of this raw speed.

In comparison, the no side-effects, inherent parallelism of functional languages does not map onto a single processor at all well. The arbitrary order in which functions can be invoked needs to be serialised down to the CPU bottleneck: without extremely clever compilation, you're going to be context switching all the time, none of the pre-fetching will work because you're constantly jumping all over the place, ... Basically, all the optimisation work that computer manufacturers have done for nice, predictable proceedural languages is pretty much useless.

However! With the move towards lots of less powerful cores (rather than one or two turbo-charged cores), functional languages should begin to close the gap, as they naturally scale horizontally.

Answer 7

C is fast because it's basically a set of macros for assembler :) There is no "behind the scene" when you are writing a program in C. You alloc memory when you decide it's time to do that and you free in the same fashion. This is a huge advantage when you are writing a real time application, where predictabily is important (more than anything else, actually).

Also, C compilers are generally extremly fast because language itself is simple. It even doesn't make any type checkings :) This also means that is easier to make hard to find errors. Ad advantage with the lack of type checking is that a function name can just be exported with its name for example and this makes C code easy to link with other language's code

Answer 8

One more reason for bigger executable size could be lazy evaluation and non-strictness. The compiler can't figure out at compile-time when certain expressions get evaluated, so some runtime gets stuffed into the executable to handle this (to call upon the evaluation of the so-called thunks). As for performance, laziness can be both good and bad. On one hand it allows for additional potential optimization, on the other hand the code size can be larger and programmers are more likely to make bad decisions, e.g. see Haskell's foldl vs. foldr vs. foldl' vs. foldr'.

Answer 9

Nothing is inherently anything. Here is an example where interpreted OCaml runs faster than equivalent C code, because the OCaml optimizer has different information available to it, due to differences in the language. Of course, it would be foolish to make a general claim that OCaml is categorically faster than C. The point is, it depends upon what you're doing, and how you do it.

That said, OCaml is an example of a (mostly) functional language which is actually designed for performance, in contrast to purity.

Answer 10

Well Haskel is only 1.8 times slower than GCC's C++, which is faster than GCC's C implementation for typical benchmark tasks. That makes Haskel very fast, even faster than C#(Mono that is).

relative Language speed

• 1.0 C++ GNU g++
• 1.1 C GNU gcc
• 1.2 ATS
• 1.5 Java 6 -server
• 1.5 Clean
• 1.6 Pascal Free Pascal
• 1.6 Fortran Intel
• 1.8 Haskell GHC
• 2.0 C# Mono
• 2.1 Scala
• 2.2 Ada 2005 GNAT
• 2.4 Lisp SBCL
• 3.9 Lua LuaJIT

source

For the record I use Lua for Games on the iPhone, thus you could easily use Haskell or Lisp if you prefer, since they are faster.