Sunday, May 18, 2008

Haskell and Performance

There has been lots of discussion on the Haskell mailing lists about the speed of Haskell. There are many conflicting opinions, and lots of different advice. Some of the information on Haskell's performance is written as a sales pitch, some is based on outdated knowledge. Since I've been working on optimisation for a while, I thought I'd try and give a snapshot of Haskell performance. Most of the following is personal opinion, and others could quite validly disagree. Since GHC is the best performing Haskell compiler, I have used Haskell to mean GHC with the -O2 flag throughout.

High-level Haskell is not as fast as C

If you write Haskell in a standard manner, it is unlikely to perform as fast as C. In most cases, linked-lists are slower than arrays. Laziness is more expensive than strictness. The Haskell code will almost always be shorter, and more concise, since it will abstract over low-level detail. But by writing that low-level detail in the C code, you are likely to produce faster code.

Low-level Haskell is competitive with C

If you use GHC, with unboxed operations, written in a low-level style, you can obtain similar performance to C. The Haskell won't be as nice as it was before, but will still probably express fewer details than the C code. Writing in such a low-level manner requires more knowledge of Haskell, and is probably something that a beginner should not be attempting. However, for a critical inner loop, low-level Haskell is a very attractive option.

Haskell's Code Generator is weak

The back end assembly generator in GHC is a weak link, but improvements are being carried out. After this work has been finished, it is likely that low-level Haskell will be able to produce nearly identical assembly code to C.

Some Haskell libraries are poorly optimised

Some of the central Haskell libraries have functions which are badly optimised. For example, the MTL library is known to be poorly performing. The words and isSpace functions in the base library aren't very good. These issues are being addressed over time, the Binary and ByteString libraries have fixed two holes. A new implementation of inits has been contributed. Over time, more issues will be identified and fixed, improving the speed of all code.

Haskell's multi-threaded performance is amazing

A lot of clever people have done a lot of clever work on making multi-threaded programming in Haskell both simple and fast. While low-level speed matters for general programming, for multi-threaded programming there are lots of much higher-level performance considerations. Haskell supports better abstraction, and can better optimise at this level, outperforming C.

Reading the Core is not easy

A standard advice to people trying to optimise Haskell is to read the Core - the low-level functional language used as an intermediate form in the compiler. While Core provides much useful information about what optimisations were performed, it isn't easy to read, and takes a lot of practice. Some effort has been done to make reading Core easier, but I still wouldn't recommend it for beginners.

Optimisation without profiling is pointless

People often want to make programs run faster. In general, this activity is a waste of time. I recently wrote a program for the HCI group at my university, which takes 10 minutes to run, and requires 4Gb of RAM, on a very expensive machine. I haven't even bothered to profile the program, because I have better things to do. Unless the speed of something actually makes a difference, you should not be spending excessive effort on optimisation.

If you have determined that the program in question is running too slowly, then profile. After profiling, you can usually identify some small part of the program that needs optimisation. Too often there is a focus on speeding up something that is not slow enough to make a difference.

The trend is for higher-level optimisation

As time goes buy, higher-level programs keep getting faster and faster. The ByteString work allows programmers to write high-level programs that are competitive with C. Performance enhancements are being made to the compiler regularly, pointer tagging, constructor specialisation etc. are all helping to improve things. More long term projects such as Supero and NDP are showing some nice results. Optimisation is a difficult problem, but progress is being made, allowing programs to be written in a higher-level.

My goal is that one day Haskell programs will be written in a very declarative, high-level style - and outperform C at the same time. I think this goal is obtainable, albeit some way in the future.

15 comments:

Miles said...

I have used Haskell to mean GHC with the -O2 flag throughout.

I think this point needs to be emphasized - I'm no expert, but there appears to be a big difference between other Haskell compilers and GHC, and between GHC with optimisation and without (strictness analysis in particular makes a big difference). As far as I can tell, the sensible default Haskell compiler should be ghc -fglasgow-exts -O2. Hopefully experts can confirm or deny this...

Neil Mitchell said...

If you want good performance, -O is probably a sensible default, with -O2 when you really care. If you want lots of features (which aren't portable) then -fglasgow-exts is a sensible default.

I personally use Hugs, with an occasional bout of GHC (typically at -O0). I rarely use extensions.

Pelikan Fountain Pens said...

I also use Hugs. I think that it is one of the best.

Ben Lippmeier said...

Nicely said. If only there was a haskell-cafe FAQ. Then we could make this required reading and prevent the next 700 flamewars.

Mitesh said...

Could you provide the benchmarks(or atleast the kind of applications) used to do the comparison for multi-threaded runs.

Miles said...

The real advantage of -fglasgow-exts is that it tells you when something you wanted to do requires an extension. Otherwise the error messages are a bit puzzling, IME.

Cristiano Paris said...

Glad to hear from you! You wrote such an enlighting piece of text about what to expect from Haskell's performances.

And looking forward to seeing Supero in action...

Anonymous said...

Thanks for the article.

While it's great to hear that haskell optimization is proceeding, how likely is it to catch up with C overall? Keep in mind that while haskell improves, C optimization techniques will also improve.

Neil Mitchell said...

Miles: with GHC 6.8.2, the error messages are quite clear about what extension should be enabled - in my experience.

Anon: Catching up with C would be impressive, but I don't think its impossible. C is great for low-level optimisations, but higher-level ones are a lot more tricky - things like loop fusion etc are difficult in C compilers, but fairly easy in Haskell compilers. We'll see how things are in 10 years time!

Alberto said...

To think that is possible to run almost as fast as C for a very high level, lazy functional language is something that no one would dream then years ago.

Think on the face of the people that program in Java, Rubi etc when they look at the current and future haskell performance goals.

Whit this i mean that the haskell performance is right now really impressive, given its nature.

Anonymous said...

2> Neil Mitchell said...
ad "We'll see how things are in 10 years time!"

i'm currently deciding whether to start learning haskell or ocaml.

not that performance is unimportant, but even ruby has been "fast enough" for majority of tasks even without writing custom c extensions, and what a crummy implementation MRI (matz's ruby interpreter) is.

i'm concerned more along the lines of what the language offers and what can it teach me, so not even your line will detract me, but you do realize that in IT 10 years means "whent the hell freezes over" ? ;-)))

Neil Mitchell said...

Anon: If performance matters to you, base performance on how the language does currently. 10 years isn't a massive amount of time, and C will probably still be the low-level language of choice then.

mac01021 said...

Hi.

I realize this is an old post, but I would be most grateful if you could direct me to some resources for learning to write haskell at a lower level.

Thanks

Neil Mitchell said...

mac01021: I think the book Real World Haskell (http://www.realworldhaskell.org/blog/) has some good things in it, and the Haskell Wiki has a nice section (http://www.haskell.org/haskellwiki/Performance)

Rafael said...

I recall when C was considered slow and critical parts must be written in Assembly... Things just change...