12

Pure functions are known to facilitate parellelizing. What is it about functional programming that makes it inherently adapted to parallel execution?

Are compilers such as Javac smart enough to detect when a method is a pure function? One can always implement classes which implement functional interfaces such as Function, but have side effects.

  • 7
    The question is not only whether the compiler can know if a function is pure, but also whether it can intelligently schedule parallel execution of pure functions. It is not enough to fire off a new thread for each one: this is inefficient. GHC (Haskell) deals with this using laziness and "green threads"; I would honestly be surprised if any impure language even tried, given the additional difficulty of making sure the pure threads were correctly scheduled with respect to the main impure thread. – Ryan Reich Jul 9 '17 at 7:54
  • @RyanReich, are there any performance gains of using functional programming in an impure functional language such as Java? are the gains of functional programming purely functional such as modularity? – Naveen Jul 9 '17 at 8:53
  • @RyanReich GHC deals with the problem by having the programmer annotate when they want parallelism. Purity implies that these annotations never change semantics, just performance. (There are also concurrency mechanisms that can give rise to parallelism, but this is a different kettle of fish.) – Derek Elkins Jul 9 '17 at 9:19
  • @Naveen There are other benefits to pure functions with regards to optimization besides parallelism such as greater freedom reordering code, memoization and common subexpression elimination. I could be wrong, but I doubt javac attempts to detect purity though, as it's probably fairly rare in idiomatic code and somewhat difficult for all but the most trivial cases. For example, you need to know that there won't be any NullPointerExceptions. The benefits of optimizations based on this are also probably fairly small for typical Java applications. – Derek Elkins Jul 9 '17 at 9:25
  • 6
    javac is the java compiler, which takes java source code and generates java byte code class files. It is pretty constrained as to what it can (and is supposed to) do. It does not have the liberty to or the necessary underlying mechanisms for introducing parallelism into the byte code class file. – Erik Eidt Jul 9 '17 at 17:49
33

are compilers such as Javac smart enough to detect when a method is a pure function.

It's not a question of "smart enough". This is called Purity Analysis and is provably impossible in the general case: it is equivalent to solving the Halting Problem.

Now, of course, optimizers do provably impossible things all the time, "provably impossible in the general case" doesn't mean that it never works, it only means that it cannot work in all cases. So, there are in fact algorithms to check whether a function is pure or not, it's just that more often than not the result will be "I don't know", which means that for reasons of safety and correctness, you need to assume that this particular function might be impure.

And even in the cases where it does work, the algorithms are complex and expensive.

So, that is Problem #1: it only works for special cases.

Problem #2: Libraries. In order for a function to be pure, it can only ever call pure functions (and those functions can only call pure functions, and so on and so forth). Javac obviously only knows about Java, and it only knows about code it can see. So, if your function calls a function in another compilation unit, you cannot know whether it is pure or not. If it calls a function written in another language, you can't know. If it calls a function in a library which might not even be installed yet, you can't know. And so on.

This only works, when you have whole-program analysis, when the entire program is written in the same language, and all is compiled at once in one go. You can't use any libraries.

Problem #3: Scheduling. Once you have figured out which parts are pure, you still have to schedule them to separate threads. Or not. Starting and stopping threads is very expensive (especially in Java). Even if you keep a thread pool and don't start or stop them, thread context switching is also expensive. You need to be sure that the computation will run significantly longer than the time it takes to schedule and context switch, otherwise you will lose performance, not gain it.

As you probably guessed by now, figuring out how long a computation will take is provably impossible in the general case (we cannot even figure out whether it will take a finite amount of time, let alone how much time) and hard and expensive even in the special case.

Aside: Javac and optimizations. Note that most implementations of javac don't actually perform many optimizations. Oracle's implementation of javac, for example, relies on the underlying execution engine to do optimizations. This leads to another set of problems: say, javac decided that a particular function is pure and it is expensive enough, and so it compiles it to be executed on a different thread. Then, the platform's optimizer (for example, the HotSpot C2 JIT compiler) comes along and optimizes the entire function away. Now, you have an empty thread doing nothing. Or, imagine, again, javac decides to schedule a function on a different thread, and the platform optimizer could optimize it away completely, except it cannot perform inlining across thread boundaries, and so a function that could be optimized away completely is now needlessly executed.

So, doing something like this only really makes sense if you have a single compiler making most of the optimizations in one go, so that the compiler knows about and can exploit all the different optimizations at different levels and their interactions with each other.

Note that, for example, the HotSpot C2 JIT compiler actually does perform some auto-vectorization, which is also a form of auto-parallelization.

  • Well, depending on your definition of "pure function", using impure functions in the implementation may be allowed. – Deduplicator Jul 9 '17 at 11:21
  • @Deduplicator Well, depending on your definition of definition, using a disparate definition of purity is probably obscure – cat Jul 9 '17 at 17:10
  • 1
    Your problem #2 is mostly invalidated by the fact that practically all optimizations get executed by the JIT (you obviously know it, but ignore it). Similarly problem #3 gets partially invalidated as JIT heavily relies on statistics gathered by the interpreter. I especially disagree with "You can't use any libraries" as there's deoptimization to the rescue. I agree that the added complexity would be a problem. – maaartinus Jul 9 '17 at 20:46
  • 2
    @maaartinus: Besides, only the very end of my answer is specific to javac. I specifically do mention, for example, that "This only works, when you have whole-program analysis, when the entire program is written in the same language, and all is compiled at once in one go." This is obviously true for C2: it only deals with one language (JVM bytecode), and it has access to the entire program at once. – Jörg W Mittag Jul 9 '17 at 21:19
  • 1
    @JörgWMittag I know that the OP asks about javac, but I'd bet they're assuming that javac is the thing responsible for optimizations. And that they hardly know that there's C2. I'm not saying, your answer is bad. It's just that letting javac do any optimization (except for trivialities like using StringBuilder) is a non-sense, so I'd dismiss it and simply assume, the OP writes javac but means Hotspot. Your problem #2 is a pretty good reason against optimizing anything in javac. – maaartinus Jul 9 '17 at 21:47
5

The upvoted answer failed to note one thing. Synchronous communication between threads is extremely expensive. If the function is capable of being executed at a rate of many million calls per second, it actually hurts you more to parallelize it rather than to leave it as-is.

The fastest form of synchronous inter-thread communication, using busy loops with atomic variables, is unfortunately energy-inefficient. If you have to resort to using condition variables to save energy, the performance of your inter-thread communication suffers.

So, the compiler does not only need to determine whether a function is pure, it would also need to estimate the execution time of the function to see whether parallelization is a net win. Also, it would need to choose between busy loops using atomic variables or condition variables. And it would need to create threads behind your back.

If you create the threads dynamically, it is even slower than using condition variables. So, the compiler would need to set up a certain number of threads already running.

So, the answer to your question is no, compilers are not "smart" enough to auto-parallelize pure functions especially in the Java world. They are smart by not auto-parallelizing them!

  • 5
    "They are smart by not auto-parallelizing them!": This goes too far. While it's true that parallelizing at every possible point just for its own sake would generally be inefficient, a smart compiler would identify a practical parallelization strategy. I think that most people understand this, so when we talk about auto-parallelization, we mean auto-practical-parallelization. – Nat Jul 9 '17 at 14:43
  • @Nat: Ridiculously too hard. This would require identifying pure functions on the runtime scale of 100s of milliseconds, and expecting the compiler to get any idea of runtime of loops that don't have constants in their iterations (and the cases you want don't) is silly. – Joshua Jul 10 '17 at 4:06
  • I agree - @Nat's comment implies that parallelization does not necessarily mean multiple threads, which is true. The JIT could, for example, inline multiple calls to a pure function and interleave their CPU instructions in certain cases. For example, if both method calls fetch a constant, it could be fetched once and kept in a CPU register for both instances of the method to use. Modern CPUs are beasts with numerous general-purpose registers and specialized instructions that can be quite helpful when optimizing code. – user22815 Jul 10 '17 at 4:09
  • 1
    @Joshua: Much easier indeed for a JIT compiler. The JIT compiler also can figure out that a function may not be pure, but no call so far has invoked impure behaviour. – gnasher729 Jul 10 '17 at 8:29
  • I agree with @Joshua. I have a hard-to-parallelize algorithm at work. I have tried to manually parallelize it, even by doing some simplifying approximations (and thus modifying the algorithm), and have miserably failed every time. Even a program telling whether it's feasible to parallelize something is extremely hard, even though it would be much simpler than actually parallelizing it. Remember we're talking about Turing-complete programming languages. – juhist Jul 10 '17 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.