Are functional languages inherently slow?
flyingfrogblog.blogspot.co.uk
flyingfrogblog.blogspot.co.uk
Inevitable is an overly broad characterization. For example, in this particular case, Manticore uses a combination of control-flow analysis and reflow analysis to inline higher-order functions in instances when we can determine that the free variables (if there are any) are obtainable in some other static way. This observation extends to the general allocation result; modern functional language compilers do quite a bit to get that under control (see my IFL paper on arity raising/unboxing/ripping apart datatypes, which provides a survey of the state of the art circa 2009) and, particularly given the additional register freedom when you're not wedded to the C calling convention, can do some real magic to avoid performing allocations, particularly in inner loops. GHC's is type-directed unboxing/type unrolling, IIRC, which in practice is on par (modulo separate compilation issues) with the implemented MLton work cited in this post.
So, it's less that poor performance is "inevitable" and more that it requires fairly insane amounts of work by the compiler developer. And, for example, I seem to remember that the Visual C++ team spent more person-hours on template compiler error message clarity in one product cycle than we will spend on the entire Manticore project in its lifetime. And yes, I know the "sufficiently smart compiler" joke.
A more fundamental complaint is that functional language implementations tend to provide _fragile_ performance. That is, without understanding some fairly gritty details of the compiler and runtime, it is difficult to understand why, for example, the second time you made a call to a non-inlined combinator providing a second function argument at the same type, your program became slower in MLton but not in GHC (YMMV; a representative but not authoritative example). A good way to see this phenomenon is to look at optimized benchmarks for OCaml or GHC (e.g. in the PL shootout) and ask, "is this idiomatic ML/Haskell code?" Many benchmarks for functional languages that perform close to C look suspiciously like the original C benchmark, with just a few functional sprinkles on top.
I don't know of a good answer to that performance problem without requiring users to become near-experts with the compiler, and that's not good practice.
I think it is a fine balance when writing code to find a way to express algorithms such that they a) are understandable to other developers and b) maximize the opportunity for the compiler to optimize the code into machine instructions.
That does not mean that compiler writers can stop after creating an assembler, since its just turtles all the way up from there; but it does mean that compiler writers should be thinking about how to maximize the machine/developer interface.
Given this view, you certainly cannot extract language creators from language compilers, which either leads us to a world where all work is done creating new languages or one where we all develop in lisp ;)
Assuming that performance is a major goal for the language.
This statement is questionable.
What is true is this: many professional software developers are comfortable with imperative/OOP/mutability. This is easier (not simpler) because it's familiar. The benefits of immutability are not obvious/familiar.
Persistent data structures enable immutable data with cheap(ish) operations that can produce updated versions of that data. This means I can expose data to multiple threads, calling functions, etc... without worrying about that data being placed into an inconsistent state or viewed in an inconsistent state by callers.
Back when much of our profession malloc'ed their memory, we always had to answer the question "who is going to free() this chunk of the heap?" And when we answered wrong, or forgot to answer, we leaked memory. Garbage collectors, while imperfect from a controlability and performance standpoint, are much better at this than humans.
An excellent analogy exists with mutable data. When I expose a piece of mutable data via any public interface, I have to ask the question "who can change this data and how will consistency be enforced?" I'm left with the answer "I don't know, I hope no one gets it wrong" or even worse: "they better lock the right semaphore(s) in the correct order". Immutable data (implemented via persistent data structures) enables me to instead say "here's the data, if any caller would like to update, they can a) pass me an updated version which I can validate, or b) call into some part of my public interface and instruct me what update to make"
Or, in the case of Clojure (my blub at the moment), put the runtime in charge of maintaining consistency during mutation using refs and the STM.
A lot of simple tasks are highly relevant. For example, in numerical simulation, you probably want a fast matrix-vector multiply. Conceptually this is extremely simple, and it's easy to benchmark. Examples of practical relevance: climate modeling, simulating combustion in engines, and optimizing control surfaces on airplanes.
"Sort" is simple. Does that make it irrelevant?
How about finding the standard deviation of a bunch of numbers?
- CPUs are inherently not functional. They are imperative, as they are Turing machines. They don't speak high-level math.
- Therefore, programs written in a functional language must always be translated into imperative code for execution. Compare this with an imperative language where the compiler need not perform super-fancy translation.
- If the problem can be mapped efficiently to machine code by the compiler, the functional program is fast; otherwise, it may be slow. Either way, it may be very hard to know what is going on behind the scenes.
- This is not always a lose; sometimes the compiler can perform extensive optimizations because it speaks math, and the functional language will win handily.
- Writing in an imperative language, you always know how your program will behave; however, you lose the opportunity to have the compiler deduce a better way (assuming there is a better way) by writing in a functional language.
- But if there is no better way, you have the opportunity to make the execution very fast by modeling the imperative solution around the constraints of the hardware.
Of course, there are other dimensions to performance, among them programmer productivity and number of defects.
So the relevant question here really is not "are functional languages inherently slow?", but "is pure functional programming inherently slow?". AFAIK, the answer to that question is not conclusively proven yet.
For example choice of boxing or unboxing values is an integral part of language design and has profound impact on the implementation's performance both for speed and memory usage.
If a language requires a feature where making it "fast" is so difficult that nobody can implement a fast version of it, then I think it's fair to say that language is slower than the alternatives.
Knowing that language X can, in theory, be faster than language Y does me no good at all if there are no implementations of language X that are actually faster than Y.
A lot of work goes into getting it that performant, but it's entirely doable with the right knowhow.
(Before anyone gets pedantic, I realize that languages aren't slow, just implementations of them, etc.)
And, looking at the code, a lot of the Haskell is subverting purity and laziness by using things like Data.ByteString.Internal and Data.ByteString.Unsafe, so I think that actually makes the case even stronger.
> Granted, functional languages are never going to be as fast as low-level languages like C, but that doesn't mean they're necessarily slow either.
That's the point.
That's an interesting choice of words. Quite obviously no useful program can be totally pure (otherwise it'd do nothing but heat the machine). And Simon Peyton Jones is on record saying that he's not sure if he'd carry the laziness torch quite so far if he had to do it all over again. Neither is to say that these aren't powerful or useful techniques, but rather that in Haskell they're chosen as defaults -- impure and/or strict code are the outliers that require justification, not the other way around. So given that, in what way is using ByteStrings (safe or unsafe) subversion? Far from it -- use the tool that makes sense.
With most functional languages, the usual technique to writing fast code is to first write it to be correct, and then transform it to be fast. And that's exactly what unsafe ByteStrings are: optimizations. There's nothing wrong with optimized code, and I see no problem with the technique. The only relation it bears to the OP is that it's an explicit unboxing. Perhaps the compiler should automatically do that unboxing, but that's easier said than done.
To put it another way, a naive implementation in C will compile and be relatively fast, while a naive implementation in Haskell will, at the very least, require replacing the standard data structures with things like ByteStrings, just to match the default C speed.
In any case, I don't think people are trying to be disingenuous. Haskell is, or can be, all three of those things. It's just very hard to get them all at the same time.
needless to say that all benchmarks will be very biased, as idiomatic code is not necessarily the most optimized one.
http://dictionary.cambridge.org/dictionary/american-english/...
Can you show that the benchmarks game is as-you-say biased?
My intention was to state that idiomatic code is not necessarily the most performant one, and that the codes used in the benchmarks game may contain some not very idiomatic optimization codes [2].
That said, it tends to evaluate the implementation of a certain compiler, and not exactly how the constructs and concepts of those languages result on the measured performance.
1: http://en.wikipedia.org/wiki/Inductive_bias 2: http://shootout.alioth.debian.org/u32/benchmark.php?test=cha...
None of the other code you wrote uses a linked list, so I don't know why you used them for Haskell. You used vector types for most of them (which Haskell has, by the way). Pretty disingenuous.
I admit that the prominent use of lists in newbie Haskell tutorials could have mislead you, but you seem to know the difference in data types since you used vectors everywhere else.
They aren't linked lists, but you still used a linked list internal to your "iter" function, where you used a vector (or array) there in other implementations.
The code is so incredibly close to your SML code (where you also spell out that you are using the Vector type). I am just blown away by how matter of fact you were in your statement.
Please either change your benchmark to use the same data type as all of the other examples, or stop using it as an example of Haskell's performance.
For your life-array.hs implementation, you replaced the Grid with an array, but not the "surroundings" with one, even though you used Vector for both in your SML implementation.
Built with -O2 option: https://gist.github.com/3189306
Sorry if I came off a bit assholish. People have been saying that you need to be a Haskell expert to get good performance forever, and in my experience this just isn't true. I will admit that there is clearly a problem with how things are introduced, as it is common that new Haskellers think they can use lists for every thing. I am sure part of the problem is that this is one of the few data structures available from the Prelude.
The act of finding the correct strictness hints seems a bit like black magic.
Having spent a large portion of the last five years working on a parallel concurrent collector that scales to 48-AMD and 64-Intel cores, I can say the game's totally different on NUMA architectures. Unfortunately, not much has been written yet on it (I have an MSPC paper; the Intel folks have a paper on Pillar that was at ISMM; that's about it). Feel free to ping me directly if you get to advanced material and need more pointers. Many of the systems have not yet been published, as it's shockingly difficult to publish on modern GC implementations these days.
Why do you suppose it's so hard to publish about them? A general lack of interest?