Haskell as fast as C: working at a high altitude for low level performance

http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/

by Menachem • 14 years ago

123 55 14 years ago

donsbot.wordpress.com

jberryman6• 14 years ago

(2008)

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

z92• 14 years ago

Thank you. This [2008] tag indicates I probably read it when it came out. Therefore didn't click on it now. And you probably have saved some of my time.

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

duaneb2• 14 years ago

Having seen hundreds of these types of blog posts, touting faster-than-c (superluminal?) benchmarks in arbitrary languages, I'm extremely skeptical. Real-world applications are rarely solely limited by small chunks of code that are simple enough to be optimized independently of the rest of the program. Accurate comparisons should be done on large, complex code bases that mirror an equivalent C program.

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.

tel• 14 years ago

It's just part of the prescription though. The idea is to use GHC profiling code to find the real bottlenecks and then use techniques like stream fusion to cause those inner loops to compile to near C-optimal assembly.

That said, it's a tough process.

Periodic2• 14 years ago

The benchmark is pretty simple and artificial.

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.

Drbble2• 14 years ago

One of the touted benefits of pure strongly typed code in languages like Haskell or OCaml is that they can compile to assembler that is faster than C, because the compiler can guarantee certain behaviors and thereby increase sharing of computations and insert multicore parallelism .

sigil• 14 years ago

> Real-world applications are rarely solely limited by small chunks of code that are simple enough to be optimized independently of the rest of the program.

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.

joeyh2• 14 years ago

At 15 thousand lines, git-annex is only 5 thousand lines less of haskell than darcs. I happen to know, since I wrote git-annex. I'm not sure where you're coming from with your statement about there only being two large haskell programs.

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.

duaneb2• 14 years ago

> I'm not sure where you're coming from with your statement about there only being two large haskell programs.

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.

maxcan• 14 years ago

A big reason for this is that a big chunk of Haskell adoption is in software you will never know about: financial risk systems for major investment banks (one of which has over 400 KLoC in Haskell), crypto work for the NSA, backends powering parts of large sites (facebook, bump, etc) and the full stack on some smaller ones (planely, yesodweb, and quite a few others I can't mention).

dons2• 14 years ago

There are several million lines of code in Haskell on Hackage now - so any non-trivial Hackage-based app is going to pull in 100k+ lines.

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.

bo10242• 14 years ago

This is very cool, but it still makes me extremely skeptical. In brief, the more posts of this type I see, the more I'm implicitly being convinced that writing performant code in high-level languages requires a series of tricks that get around the "natural" or "naive" way to write the code. The impression I get is that high-level languages allow you to express your thoughts concisely, or they perhaps allow you to mimic the performance of low-level languages, but not both at the same time.

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.

kruhft• 14 years ago

I've always wondered why language designers don't strive to optimize for the trivial cases. There is a natural way to design code for a beginner, and having that map to the most efficient constructs seems to be one of the areas of programming language research that is lacking. Maybe it's the need for the 'sufficiently smart compiler' that is holding things back, but given that PLs are abstractions, couldn't the underlying abstraction be completely different than the user visible abstractions?

pcwalton• 14 years ago

In the design of Rust, as a rule of thumb, we've always tried to make the simplest code also the fastest code, to minimize performance footguns. (Writing the Rust compiler in Rust and constantly running it through Instruments.app helps to keep us honest.)

Periodic2• 14 years ago

I believe they do optimize for the simple cases, but just in very different ways. Haskell optimizes for composition, abstraction and expressiveness in a function-application sense. C optimizes for imperative loops, simple functions and controlling your memory layout and execution precisely [There is probably a better characterization of C, please comment].

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.

stcredzero7• 14 years ago

There is a natural way to design code for a beginner

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.

regularfry• 14 years ago

The thing is, barring the intervention of marketing departments, compilers don't get more dumb over time. If this is possible now, it ought to be easy soon (for some value of "soon").

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.

T_S_• 14 years ago

You should think of this post as being aimed at Haskell library writers. The benefit to the application developer is that more and more optimizations are available through identical or nearly identical, familiar interfaces such as those for lists.

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.

jberryman6• 14 years ago

Exactly. A this point you can just write idiomatic haskell-98 list code and just do an

    import qualified Data.Vector.Unboxed as V

and get blazing-fast performance.

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.

freshhawk• 14 years ago

As someone who knows a bit of haskell but not a lot I don't see this so much as a series of tricks. Ignoring all the explanatory pieces it comes down to "use the fusible Data.Array.Vector library and unbox your doubles". The unboxing is a given, optimization 101 in haskell, and the fusion stuff is the cool bit.

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.

dkarl• 14 years ago

It's simpler to write efficient low-level code in C, but you have to pay the cost of efficiency (in effort, clarity, and LOC) everywhere in your program, in every single function you write. For some kinds of programming, such as kernel coding, almost all of your code needs to be as efficient as you can make it, so that's fine. For a lot of application programming, though, low-level efficiency only matters for a small percentage of the code, so it's a good trade-off to use a more elegant and expressive language, if optimizing the performance-sensitive parts isn't so difficult that it cancels out the savings elsewhere.

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.)

true_religion• 14 years ago

Not to take away from Haskell, but this is exactly why many people in academia use Python. It's easy to express an idea in it, and test at a low performing level. Then when you know where your bottle necks are, you can re-write that tiny bit in Cython and gain 90% of the speed improvement of writing the whole thing in C.

berkut2• 14 years ago

Getting languages to run as fast as (or faster than) C for things like tight floating point or int calculations isn't that difficult - at the end of the day, any decent compiler JIT or pre-compiled is going to produce roughly the same asm.

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.

stcredzero7• 14 years ago

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

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.)

berkut2• 14 years ago

There's a reason languages with garbage collectors aren't used where speed is important - because they normally get in the way.

eta_carinae• 14 years ago

Please don't make any claims about high performance based on micro-benchmarks.

forgottenpaswrd2• 14 years ago

If you are new to programming languages, please don't listen to those non sense articles "X language faster than c" that comes from people that are religious about high level languages.

If you have only a hammer, everything is a nail.

It is a very dangerous meme that will make you incompetent in the real world when real life high level languages are >100 times slower that programs written in c(from people that know what the computer is doing as they knew assembler first).

Microsoft geniuses fell on this meme and as a result created Windows Vista, and a 50KB file transfer could take you 20 minutes.

In Android garbage collector will start collecting memory once it wished and will visually break the continuity of the screen, making it irresponsible at times. This is unacceptable for Apple that used c for this reason(yes c, not Obj c). Samsumg and HTC started using c too for this.

C has this place, high level languages have their place. you trade abstraction for control and (if you know what you are doing) performance.

Go and learn low level and high level and decide for yourself witch one is appropriate for what circumstance.

E.g the fast python in python, things like numeric python, are written in c for this reason(once they discover how slow high level programming was in real life).

If you are going to spend the same time optimizing language X on c, you can make c super fast as well, not 10% faster, with using c you should get 100%, 1000% or 10000%.

Sorry, I feel super dumb by having to say the obvious, but good programmers are busy coding and the void is filled with non sense.

derleth2• 14 years ago

You can say all the same things if you replace 'C' with 'assembly' and 'high-level languages' with 'C'.

forgottenpaswrd2• 14 years ago

C is "portable assembler".

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.

jberryman6• 14 years ago

To be honest, your comment strikes me as far more "religious" than the article, which (since you obviously didn't RTFA) documents optimizing a particular bit of haskell code to be on par with an equivalent implementation in C. The article is not saying that haskell (the language) is faster than C.

If all you have is a hammer...

stcredzero7• 14 years ago

when real life high level languages are >100 times slower that programs written in c(from people that know what the computer is doing as they knew assembler first)

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!

wingo• 14 years ago

> The fix is straightforward: just use a strict pair type for nested accumulators:

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

Tyr42• 14 years ago

But the rest of the fusion and other transformations work better when lazy.

neutronicus• 14 years ago

A year or so ago I tried for a couple days to write a 1-D neutron transport solver based on this post, and found the experience frustrating in the extreme. Obviously, I'm no Haskell expert, but I was really turned off of using Haskell for numerical work.

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).

jberryman6• 14 years ago

A lot of really clever folks monitor the Haskell tag on stackoverflow, including dons. I would post there.

stcredzero7• 14 years ago

It seems to me that machine learning has advanced to the point, where those "obligatory" points made again and again in things like language efficiency threads could actually be automated.

What if we used a Bayesian filter for threads where such "obligatory" points on both sides of a heated debate are made again and again, then use machine learning to post well a written and well curated set of "obligatory" comments? This would save a lot of man-hours online.

it• 14 years ago

I tried to reproduce the results, but the Haskell bit failed to compile on my Mac with the -fvia-C flag. Without the -fvia-C flag, the Haskell version takes about 11 times as long to run as the C version. A simple Go version runs at the same speed as the C version.

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

dons2• 14 years ago

These days you'd use the -fllvm flag

comex• 14 years ago

I was going to go into a series of optimizations that could make the C code faster, starting by comparing against the integer counter rather than the double, then switching to vector math if applicable...

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.

jrockway• 14 years ago

I started reading this and wondered, "why is dons back to using via-C instead of LLVM". Then I realized that this article is 4 years old.

Haskell as fast as C: working at a high altitude for low level performance

Related Stories