Notice that it takes an entire blog post to use Haskell to emulate the performance of a straightforward 20-line C program that can be written in under 60 seconds. There are high-performance tasks which are practically trivial in an imperative language but which merit a conference paper when accomplished in Haskell.

So it's hard to see something like this as an argument that higher-level languages are simplifying anything.

In my case (joe average haskell dev) that means I can just stick to normal constructs and switch out the underlying data structure to get the speed benefit. This article actually might lead to such a change in a computer vision package I work on.

You can expect to see this pattern over and over with Haskell, so that by the time you get to data structures that abstract away GPU-based calculations, nobody will be wishing people would just write the darn code in C.

    import qualified Data.Vector.Unboxed as V

Even with the complication of laziness, getting great (for most reasonable definitions of great) performance out of pure haskell code was a solved problem years ago. Doing high-performance IO looks like it's getting there too.

That caveat makes analyses like this one interesting, because the trade-off hinges on how hard it is to write efficient code when you need to. For me, the significance of this article is that it's possible to write high-performance Haskell in a simple and readable style if you're a Haskell expert who knows a lot about how the compiler optimizes code. That's a useful thing to know if you're considering using Haskell for a project. (The next thing I would ask is whether you're screwed if you're just an intermediate programmer who knows the language but not the implementation.)

You can probably make the argument that the tail recursive function is not the "natural" way to write this code but conceptually that's on the same level as loop unrolling in C.

It doesn't take an entire blog post unless you are explaining the compiler tricks working behind the scenes and comparing the assembly produced.

So basically I agree that there is some express concisely vs. low level performance tension here but the takeaway is how little of it there is. This is probably lost if you are also having to try and parse this weird haskell stuff at the same time.

Haskell's main benefit, to my mind, is its type safety. That's what saves programmer time in the long run. If that can be fused (hah!) with decent performance - even if it's not quite up to C without contortions - it's a net win.

I think there are plenty of tricks involved in writing performant C code that aren't obvious. Things like cache behavior, memory access patterns, etc. The job of the compiler and PL is to help us by making it unnecessary to worry about such things unless we really need to.

It's a testament to the power of modern programming languages and computer speeds that there are many programmers who don't understand registers, caches, assembly, virtual memory, etc.

Smalltalk was purposely aimed at children. The thing is, our culture is quite complicated, and there are expectations set up in different fields. A grade school child might find operator precedence confusing, while an engineer would view it as second nature and a non-negotiable feature. Likewise, someone steeped in the Unix way of doing things might find a language incorporating Sed/Awk syntax to be very "intuitive" while someone from a different discipline might find it to be cryptic.

given that PLs are abstractions, couldn't the underlying abstraction be completely different than the user visible abstractions?

They almost always are for PL.

Unfortunately, those don't exist, so in my mind the true performance potential of haskell is still unknown. I do have high hopes for the language, especially since whole-program optimization and aggressive inlining/code folding should yield very, very efficient code, but as of yet the only large programs in haskell remain GHC and darcs, and darcs is extremely slow.

Still: a single benchmark showing a good result is better than one showing a bad result.

For that matter, I don't know if I'd consider darc's 20 kloc very large. Or that I'd consider another haskell program I wrote, github-backup, to be small -- that 2 kloc program sits at the apex of a lot of libraries, and probably combined they have more lines of code than darcs. Your whole premise about lines of code feels thoroughly flawed to me.

Anyway, As a git extension, git-annex is expected to run quite fast. I've never had any difficulty, in writing git-annex, with the speed of haskell code. I'm sure darcs is slow due to its patch theory thing, not due to its implementation language.

I concede the point, but I'd rather say that there's only one large haskell program.

Let's consider large C/C++ programs:

1. Chromium clocks in around 4 million lines of code.

2. LLVM/clang together has a (fuzzy) estimate of ~1165539 LOC on my system.

3. GHC has unknown lines of code, and I am unsure as how to count it, whether to include the standard library, etc, but it has at least 100k, so we'll just call that sufficiently large.

Now, I know haskell can be fast—I've spent a lot of time myself hand-tuning ghc processed code. But I've noticed that unless I can trace the bottleneck to a single function or small set of functions, optimization to near-c levels is extremely difficult. Now, even 2-3x slower than c—far slower than ghc-generated code—is still very fast, so I'm not calling haskell slow. Far from it.

Two reactions to this:

1. If they aren't, maybe they should be. Not sure the large applications of the past are a good guide to the future. Perhaps a large pile of functional code is a clear software engineering win for some value of "large," and we're still discovering this.

2. In my experience, large applications are often performance-limited by small chunks of code. The results of actually profiling never cease to amaze me -- my guesses are so often wrong. Of course, once you fix the bottleneck in one spot, the bottleneck moves to another, but hey that's the game of optimization in any language.

The current project I'm working on commercially has 600k lines of Haskell, though I expect we'll hit the 1M mark in the next year or two.

It benefits massively from the compiler being able to see the forest from the trees.

From my point of view, this stuff was all solved years ago. There's nothing much left to prove -- so get on with building great things in Haskell.

I think what we should be looking at is that the performance can asymptotically approach C, where C is used because it's the closest to the theoretical optimum assembly that is still practical for writing large programs.

If a language can get arbitrarily close to C in performance, it starts to become a much better design trade-off to use.

That said, it's a tough process.

Then I realized that all this program does is compute an approximation of `(d + 1) / 2`. If you need the exact same result as it computes (500000000.067109), it's hard to add any parallelism because it depends on the imprecision of the intermediate add results, but if you can settle for the mathematically correct solution (500000000.500000), it's hard to distinguish between "fair" optimizations and "unfair" ones - indeed, if you go ahead and just change all the doubles to long longs (they can fit), the compiler will automatically use the formula.

In general, I think that to get maximum performance on many problems on this, you must make assumptions the compiler cannot, which means your code cannot be naive; but the difference between naive and non-naive code in C is much less than in Haskell.

I'd really like to give it a go again, but I feel like I'm missing a lot of the knowledge required to solve P-(I)DEs in any kind of moderately clever way in Haskell. If anyone can point me towards a nice resource for Haskell numerics I'd be grateful (repa is not flexible enough for my needs).

What's difficult is getting the whole application as fast, as opposed to just a few functions. The hot points of an application are rarely due to CPU throughput or lack of asm instruction optimisation - they're normally due to memory allocation inefficiencies or cache thrashing, or bad thread concurrency, and this is where using C/C++/(ADA in embedded world) shine, as you have complete control over pretty much everything, from struct bit packing, allocation size, allocation location (stack/heap), when to deallocate memory (if ever in real-time's case), optimising for memory access patterns, etc, etc.

What you are saying is that C/C++/ADA are wonderful because compilers optimize one thing (CPU throughput/instruction optimisation) whereas other factors are more important (memory allocation inefficiencies or cache thrashing, or bad thread concurrency).

Whenever a programmer says they need manual control of [X] -- it's time to start looking at automation of [X]. (It may not work in all contexts, however.)

Yet, there must be something that programmers conceptualize when they allocate a struct, do whatever they do with it, then free it. Everything that I know about how programmer's minds work tells me that, most likely, 80% of this work is fairly mechanical.

Then again, you might want to look at iGC. (Granted, phones are pretty ridiculously powerful in comparison to lots of embedded devices.) By tailoring their GC to the particular way it's used, they can do interesting optimizations. (Use comparisons to addresses to drastically reduce the number of roots for tracing.)

Uf. Haskell impresses me a lot, but it seems that performance-wise, it would be better if it were strict by default.

...not that things have gotten slower since then.

Just wanted to inform you and others how much these little bits of information help us.

I posted some code to run the comparison at https://github.com/ijt/fast-as-c-article. Here are the results:

    [ issactrotts ~/haskell/fast-as-c-article ] ./compare
    == cmean ==
    gcc -O2 -o cmean cmean.c
    mean: 500000000.500000

    real    0m0.774s
    user    0m0.770s
    sys 0m0.002s
    == gomean ==
    6g gomean.go
    6l -o gomean gomean.6
    mean: 500000000.500000

    real    0m0.776s
    user    0m0.769s
    sys 0m0.003s
    == hsmean ==
    ghc -O2 hsmean.hs -optc-O2 -fvia-C --make
    [1 of 1] Compiling Main             ( hsmean.hs, hsmean.o )
    In file included from /usr/local/Cellar/ghc/7.0.4/lib/ghc-7.0.4/include/Stg.h:230,

                     from /var/folders/g2/ylbqfw5533n65z6qkxljg0_h0000gn/T/ghc23078_0/ghc23078_0.hc:3:0:
     

    /usr/local/Cellar/ghc/7.0.4/lib/ghc-7.0.4/include/stg/Regs.h:177:0:
         sorry, unimplemented: LLVM cannot handle register variable ‘R1’, report a bug
    make: *** [hsmean] Error 1
    == hsmean_nollvm ==
    ghc -O2 hsmean.hs -optc-O2 --make -o hsmean_nollvm
    [1 of 1] Compiling Main             ( hsmean.hs, hsmean.o )
    Linking hsmean_nollvm ...
    ld: warning: could not create compact unwind for .LFB3: non-standard register 5 being saved in prolog
    mean: 500000000.067109

    real    0m8.886s
    user    0m8.863s
    sys 0m0.018s

If all you have is a hammer...

There is an important truth here, in the article, and in other comments here: Speed doesn't come free.

You don't get the very best speed and efficiency by just using a certain language, a certain library, or a certain algorithm. It's essential that the programmer has some specialized knowledge. (How a particular GC works, how a particular library is put together, or exactly what your compiler is doing under the covers.)

In the end, it's all a trade-off between hardware resources, human capital, and time. Have an excess of hardware resource? Then why not spring for GC? Have very tight and fixed hardware resource, well you're going to have to pay in another way!

If I do something like

if (foo = bar) { }

I know that the computer is comparing one value to another(witch means an op, eg.substraction ), then doing a jump.

I don't need to code the assembler, but I could estimate how much it takes everything really well(orders of magnitude). This is invaluable with coding.

If you do: [object foo] in objective c

or object.foo()

You lost all you control, sometimes classes will use iterative methods or alloc and free memory every time you call a method, from nested methods, making it super slow.

Sometimes I want abstraction, sometimes I want to know what is happening.

Let's challenge this specific claim, that when you do "if (foo == bar)" -- I corrected the syntax error, which is a symptom of C's high-level syntax and not of the underlying assembly code -- you compare one value to another and then jump. For this challenge,I will write some trivial code that we should be able to make easy assumptions about, and I will compile it with debugging enabled so that I can dump the results with gdb.

  $ gcc -g example.c

  1       #include <stdio.h>
  2
  3       int main() {
  4          int foo = 10;
  5          int bar = 20;
  6          if (foo == bar) {
  7             printf("Fun\n");
  8          }
  9          return 0;
  10      }

  Dump of assembler code for function main:
  0x0000000100000ef8 <main+0>:    push   rbp
  0x0000000100000ef9 <main+1>:    mov    rbp,rsp
  0x0000000100000efc <main+4>:    sub    rsp,0x10
  0x0000000100000f00 <main+8>:    mov    DWORD PTR [rbp-0x4],0xa
  0x0000000100000f07 <main+15>:   mov    DWORD PTR [rbp-0x8],0x14
  0x0000000100000f0e <main+22>:   mov    eax,DWORD PTR [rbp-0x4]
  0x0000000100000f11 <main+25>:   cmp    eax,DWORD PTR [rbp-0x8]
  0x0000000100000f14 <main+28>:   jne    0x100000f22 <main+42>
  0x0000000100000f16 <main+30>:   lea    rdi,[rip+0x19]        # 0x100000f36
  0x0000000100000f1d <main+37>:   call   0x100000f30 <dyld_stub_puts>
  0x0000000100000f22 <main+42>:   mov    eax,0x0
  0x0000000100000f27 <main+47>:   leave  
  0x0000000100000f28 <main+48>:   ret    

Now, let's get smarter. The variables foo and bar do not change value, and we only work with two variables in the routine. Therefore, we could optimize by storing those values in temporary registers instead of using expensive memory transfers. Further,since our two constants are being compared and will always return a false, we actually have a section of code -- the printf -- that is dead code, that can be completely removed from final compilation. Well, that's simple, and everyone who uses C in production at least turns on some minor optimization:

  $ gcc -g -O1 example.c  # the only difference is the -O1

  Dump of assembler code for function main:
  0x0000000100000f34 <main+0>:    push   rbp
  0x0000000100000f35 <main+1>:    mov    rbp,rsp
  0x0000000100000f38 <main+4>:    mov    eax,0x0
  0x0000000100000f3d <main+9>:    leave  
  0x0000000100000f3e <main+10>:   ret    

The point here is that you are not properly guessing the assembler code that will be produced. The compiler is doing a better job of that; that is the compiler's job. As a programmer, you can just focus on the algorithm. C is not an assembler macro language. For that, you would use things like "gas".

For example in C "array[0] = (x + y);" will never be more than a couple assembly instructions long. In many languages, including Haskell (and in the case of operator overloading, C++), the equivalent construct might map to hundreds if not thousands of instructions. Or it might map to the same one or two that C would emit. It's impossible to know and there is no reasonable upper bound on what could happen.

Over every possible piece of code that could be compiled anywhere, this might well be true. But for a properly informed programmer for a given piece of code, not so much.

There are a couple reasons that even for "informed" programmers this is still important

1) For most dynamic languages, even simple operations can take a highly variable amount of time to execute. How many instructions does an array access take in Javascript? The answer depends on everything from the state of the JIT to the types involved, both of which are usually impossible to know before hand. In C we can answer this pretty easily.

2) The modern trend is towards writing more and more generic code. Even for statically compiled languages like C++ and Haskell, the actual underlying operations are purposely* abstracted away from you. Unless you know every possible instance that your code could be used it is impossible to know how long any operation will take.

And all this is assuming that the programmer knows everything about their compiler, assembler, standard library, imported libraries, ect, which isn't true for all but the most expert programmers.

*Admittedly, the actual length of time it takes is dependent on the state of the processor which can be very difficult to predict, but we will have a lot more information than we would have had otherwise.

In other words, you're talking about one end of the spectrum. You are right, though, that things are moving in that direction.

> in C you both control the memory layout of data types very finely

True to an extent.

> code maps very directly to an equivalent assembly construct

True but less and less relevant.

Here's where C disconnects you from the processor in the ways that matter most:

1. malloc()/free() are too high-level: You can't control where the allocation subsystem gets your next chunk from, you can't see whether your malloc arena is getting full, you can't see whether you're about to double-free something, and you have no way to recover from a failure to allocate (if that's even possible on your OS).

2. C has no concept of cache; admittedly, assembly usually tries to hide it from you to an extent as well, but assembly language at least has hooks into the cache hardware in the form of memory barriers. C doesn't even have that much.

3. C completely hides the processor status word from you. A minor concern, usually, except in precisely the kind of tight loops people most advocate C for.

4. C has no concept of out-of-order execution or opcode pairing or pipelining in general. Just hope your compiler does.

So, added up, that means C is farther and farther from the hardware all the time. It was reasonably close on the PDP-7 where it was born, was fortuitously even closer to the PDP-11 where it was later implemented, and remained fairly good for a while after, but once you get to dual-core superscalar designs with cache hierarchies and SIMD hardware, you have to rely on the compiler to turn your C into good assembly. Which is, really, a lot like what you do when you write Haskell.

Actually it isn't.