When Haskell is Faster than C

>Conventional wisdom says that no programming language is faster than C, and all higher level languages (such as Haskell) are doomed to be much slower because of their distance from the real machine.

No: conventional wisdom just says that no higher level programming language is consistently faster than C AND/OR better to reason about with regards to memory consumption and runtime behaviour.

(Conventional wisdom also adds fortran, forth, Ada and C++ in the same "speedy" category).

Conventional wisdom adds that micro-benchmarks of some BS outlier examples (Java where the JIT can take advantage of some known condition to do something clever, etc) do not matter in real life programs, which are far more complex.

Conventional wisdom also adds that C to be speedier it doesn't even have to be highly optimized or carefully crafted by some C programming wizard or anything. Merely avoiding gross mistakes (like using an algorithm of the wrong complexity for the job) will do.

Conventional wisdom concludes that writing in your high level language in an unconventional (non idiomatic) way to get to "as fast a C" speeds is bullshit too, because it doesn't represent idiomatic (and far more common) high level language use.

Seconded. I'd add that languages like Python hide an enormous amount of not-close-to-the-metal-ness in every single statement, because every single statement has the implicit context "Interpreter, please interpret this string relative to your potentially complex internal state".

Haskell is only slightly less prone to this, despite being compiled, since every expression by default becomes a request to instantiate a thunk in the runtime's evaluation tree. Yes, you can contort yourself to avoid this, but at that point you are imperatively programming an expression tree evaluator. This can be fun and rewarding, but it's not that different from scripting a Python interpreter, and it's certainly much further from the metal than C.

Apples and oranges yet again. The original article is about Haskell; an entirely different beast from Python. Haskell compiles down to machine code, not byte code.

It's not actually the structure of C programs, it's the guarantees the language offers. So only about the first paragraph of your rant is right.

Fortran had almost no memory aliasing, explicit global accesses, and offered almost unbridled implementor freedom. As long as the operations got done, it didn't care what happened behind the scenes.

None of the rest of the things you talk about matter when it comes to optimizing C, to be honest. If you gave me no aliasing by default and explicit globals, I probably could do near as well as fortran (though it would take significantly more analysis) in terms of loop transformations.

Note that "full alias analysis" is statically undecidable. When you say cubic order, you are thinking of Andersen's subtyping based algorithm. There are unification based algorithms that are almost linear time (inverse ackermann).

At this point, we have scaled these algorithms almost as far as you can on a single computer. You can do context insensitive andersens on many million LOC without too much trouble.

Context-insensitive unification points-to can scale to whatever size you like.

Context sensitive unification based algorithms do quite well in practice with 10 million LOC + codebases.

The main reason you don't see unification based algorithms used often in free compilers is because the entire set of algorithms are covered by patents owned by MS Research.

As a final note, note that C++ does not really help optimization in practice, it often hurts it.

It is very hard to teach a pointer analysis algorithm about virtual calling. Most compilers treat them like function pointers that get type-filtered, and do some form of class hierarchy analysis to limit the number of call graph targets, or try to incrementally discover the call graph. It's a bit of a mess.

On the other hand, straight function pointers get resolved either context-sensitively or insensitively.

In fact, C++ makes type based aliasing a lot worse due to placement new being able to legally change the type of a piece of memory, which is very hard to track over a program.

Even outside the realm of alias analysis, C++ involves a lot more structures, which means a lot more time has to be spent trying to get pieces back into scalars, or struct splitting, or something, so that you don't end up having to fuck around with memory every time you touch a piece of the structure.

I could go on and on.

In short: Any of C++'s lower level optimization advantages come from less pointer usage by programmers, not language guarantees.

At the high level, it's from better standard implementations and common usage idioms.

In any case, high level languages, particularly those with memory objects (not real pointers, just memory objects, like Java) usually solve none of the pointer/alias analysis related problems. You are still stuck with the same pointer analysis algorithms.

For example: The only nice thing about java's memory system is that doing structure-field sensitive pointer analysis can only help, whereas in C it can hurt, due to some weirdness.

It's just nobody usually gets around to doing pointer analysis on the higher level languages (because it's harder and offers no particular benefit), they lower their language to an IR that already has a good algorithm in it.

Just in case you were wondering, i'm not talking out of my ass. I wrote GCC's first set of high level loop optimizations, and also, it's pointer analysis.

In general, JavaScript wouldn't take less time to develop and especially less time to fix than a modern C++ 11 / boost code.

That's a stupid myth ("very slow C++ development times") from the guys who suck at programming.