Is functional programming faster in multithreading because I write things differently or because things are compiled differently?

Question

I'm diving into the world of functional programming and I keep reading everywhere that functional languages are better for multithreading/multicore programs. I understand how functional languages do a lot of things differently, such as recursion, random numbers etc but I can't seem to figure out if multithreading is faster in a functional language because it's compiled differently or because I write it differently.

For example, I have written a program in Java which implements a certain protocol. In this protocol the two parties send and receive to each other thousands of messages, they encrypt those messages and resend them (and receive them) again and again. As expected, multithreading is key when you deal in the scale of thousands. In this program there's no locking involved.

If I write the same program in Scala (which uses the JVM), will this implementation be faster? If yes, why? Is it because of the writing style? If it is because of the writing style, now that Java includes lambda expressions, couldn't I achieve the same results using Java with lambda? Or is it faster because Scala will compile things differently?

Answer 1

The reason people say functional languages are better for parallel processing is due to the fact that they usually avoid mutable state. Mutable state is the "root of all evil" in the context of parallel processing; they make it really easy to run into race conditions when they are shared between concurrent processes. The solution to the race conditions then involve locking and synching mechanisms, as you mentioned, which cause runtime overhead, as the processes wait for one another to make use of the shared resource, and greater design complexity, as all of these concepts tend to be deeply nested within such applications.

When you avoid mutable state, the need for synchronization and locking mechanisms disappears along with it. Because functional languages usually avoid mutable state, they are naturally more efficient and effective for parallel processing - you won't have the runtime overhead of shared resources, and you won't have the added design complexity that usually follows.

However, this is all incidental. If your solution in Java also avoids mutable state (specifically shared between threads), converting it to a functional language like Scala or Clojure would not yield any benefits in terms of the concurrent efficiency, because the original solution is already free of the overhead caused by the locking and synching mechanisms.

TL;DR: If a solution in Scala is more efficient in parallel processing than one in Java, it is not because of the way the code is compiled or run through the JVM, but instead because the Java solution is sharing mutable state between threads, either causing race conditions or adding the overhead of synchronization in order to avoid them.

Answer 2

Sort of both. It's faster because it's easier to write your code in a way that's easier to compile faster. You won't necessarily get a speed difference by switching languages, but if you had started with a functional language, you could have probably done the multithreading with a lot less programmer effort. Along the same lines, it's a lot easier for a programmer to make threading mistakes that will cost speed in an imperative language, and a lot more difficult to notice those mistakes.

The reason is imperative programmers generally try to put all the lock-free, threaded code in as small a box as possible, and escape it as soon as possible, back into their comfortable mutable, synchronous world. Most mistakes that cost you speed are made on that boundary interface. In a functional programming language, you don't have to worry as much about making mistakes on that boundary. Most of your calling code is also "inside the box," so to speak.

Answer 3

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:

1. 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.
2. 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:

1. 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.
2. 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.

Answer 4

In Haskell, modification is literally impossible without getting special modifiable variables through a modification library. Instead, functions create the variables they need at the same time as their values (which are computed lazily), and garbage collected when no longer needed.

Even when you do need modification variables, you can usually get by using sparely, and along with the unmodifiable variables. (Another nice thing in haskell is STM, which replaces locks with atomic operations, but I'm not sure if this is only for functional programming or not.) Usually, only one part of the program will need to be made parallel to improve things performance-wise.

This makes parallelism in Haskell easy a lot of the time, and in fact efforts are under way to make it automatic. For simple code, the parallelism and logic can even be separated.

Also, due to the fact that evaluation order doesn't matter in Haskell, the compiler just creates a queue things that need evaluated, and sends them to whatever cores are avaible, so you can make a bunch of "threads" that don't actually become threads until necessary. Evaluation order not mattering is characteristic of purity, which usually necessitates functional programming.

Further Reading
Parallelism in Haskell (HaskellWiki)
Concurrent and Multicore Programming in "Real-World Haskell"
Parallel and Concurrent Programming in Haskell by Simon Marlow