Functional programming doesn't make for faster programs, as a general rule. What it makes is for easier parallel and concurrent programming. There are two main keys to this:
- The avoidance of mutable state tends to reduce the number of things that can go wrong in a program, and even more so in a concurrent program.
- The avoidance of shared-memory and lock-based synchronization primitives in favor of higher-level concepts tends to simplify synchronization between threads of code.
One excellent example of point #2 is that in Haskell we have a clear distinction between deterministic parallelism vs. non-deterministic concurrency. There's no better explanation than quoting Simon Marlow's excellent book Parallel and Concurrent Programming in Haskell (quotes are from Chapter 1):
A parallel program is one that uses a multiplicity of computational hardware (e.g., several processor cores) to perform a computation more quickly. The aim is to arrive at the answer earlier, by delegating different parts of the computation to different processors that execute at the same time.
By contrast, concurrency is a program-structuring technique in which there are multiple threads of control. Conceptually, the threads of control execute “at the same time”; that is, the user sees their effects interleaved. Whether they actually execute at the same time or not is an implementation detail; a concurrent program can execute on a single processor through interleaved execution or on multiple physical processors.
In addition to this, Marlow mentions also brings up the dimension of determinism:
A related distinction is between deterministic and nondeterministic programming models. A deterministic programming model is one in which each program can give only one result, whereas a nondeterministic programming model admits programs that may have different results, depending on some aspect of the execution. Concurrent programming models are necessarily nondeterministic because they must interact with external agents that cause events at unpredictable times. Nondeterminism has some notable drawbacks, however: Programs become significantly harder to test and reason about.
For parallel programming, we would like to use deterministic programming models if at all possible. Since the goal is just to arrive at the answer more quickly, we would rather not make our program harder to debug in the process. Deterministic parallel programming is the best of both worlds: Testing, debugging, and reasoning can be performed on the sequential program, but the program runs faster with the addition of more processors.
In Haskell the parallelism and concurrency features are designed around these concepts. In particular, what other languages group together as one feature set, Haskell splits into two:
- Deterministic features and libraries for parallelism.
- Non-deterministic features and libraries for concurrency.
If you're just trying to speed up a pure, deterministic computation, having deterministic parallelism often makes things much easier. Often you just do something like this:
- Write a function that produces a list of answers, each of which is expensive to compute but don't very much depend on each other. This is Haskell, so lists are lazy—the values of their elements are not actually computed until a consumer demands them.
- Use the Strategies library to consume your function's result lists' elements in parallel across multiple cores.
I actually did this with one of my toy project programs a few weeks ago. It was trivial to parallelize the program—the key thing I had to do was, in effect, add some code that says "compute the elements of this list in parallel" (line 90), and I got a near-linear throughput boost in some of my more expensive test cases.
Is my program faster than if I had gone with conventional lock-based multithreading utilities? I very much doubt so. The neat thing in my case was getting so much bang out of so little buck—my code is probably very suboptimal, but because it's so easy to parallelize I got a big speedup out of it with much less effort than properly profiling and optimizing it, and no risk of race conditions. And that, I would claim, is the main way functional programming allows you to write "faster" programs.