[Haskell] Programming language shootout (completing the Haskell entry)
Hiya, I know it is silly, but I'm interested in helping to complete the Haskell entry in the Programming Language Shootout page[1] (http://www.bagley.org/~doug/shootout/craps.shtml). The Haskell entry is missing 5 (out of 13) entries, and since no points are "scored" for missing entries, this skews Haskell's rank downwards. Since I'm not the worlds Best Haskell Programmer -- and I'm certainly not adept at optimizing, and since I'd like to provide the fastest Haskell code that I can, I thought I'd run it through my code through this list and see if anybody would like to suggest improvements. The implementations for this particular test must be written in the "same way"; this is defined to be that the submissions "use the same logic and data structures", the goal being to "try to measure languages doing the same operations, as closely as possible." The "description" of the test is: "In this test, we create 10000 hash entries, then add them into a new hash N times. " The correct output for this code where N=10 must be: 1 9999 10 99990 I chose to use (lookup) and associative arrays. I create a *bunch* of hashes, rather than just two that I re-use because, honestly, I'm such a novice I don't know how to do it otherwise. Anyway, as I said, any suggestions for optimization are appreciated. This is just for fun. ===== BEGIN hash2.hs module Main where import System (getArgs) import Numeric (readDec) import Maybe main = do argv <- getArgs let h1 = hash1 9999 [] h2 = hash2 (fst $ head $ readDec $ argv!!0) h1 [] print h1 h2 where hash1 0 x = x hash1 n xs = hash1 (n-1) ((mkentry n):xs) mkentry y = ( "foo_"++(show y), y ) hash2 0 _ x2 = x2 hash2 n x1 x2 = hash2 (n-1) x1 [ (k1, v1+(get k1 x2)) | (k1, v1) <- x1 ] print x1 x2 = putStrLn ( (show $ get "foo_1" x1)++" "++ (show $ get "foo_9999" x1)++" "++ (show $ get "foo_1" x2)++" "++ (show $ get "foo_9999" x2) ) get :: String -> [(String, Int)] -> Int get key hash = fromMaybe 0 $ lookup key hash ===== END hash2.hs [1] The page is entirely tounge-in-cheek, but I find it interesting, nonetheless. -- ### SER ### Deutsch|Esperanto|Francaise|Linux|XML|Java|Ruby|Aikido ### http://www.germane-software.com/~ser jabber.com:ser ICQ:83578737 ### GPG: http://www.germane-software.com/~ser/Security/ser_public.gpg
On Fri, 2004-03-26 at 13:26, Sean E. Russell wrote:
Hiya,
I know it is silly, but I'm interested in helping to complete the Haskell entry in the Programming Language Shootout page[1] (http://www.bagley.org/~doug/shootout/craps.shtml).
Are you aware of this: 2001-12-12 * Due to wanting to get on with other things, I'm freezing the shootout as is, with no further updates planned. It isn't complete, just abandoned (for now). (from http://www.bagley.org/~doug/shootout/news.shtml)? So it's unlikely that your updates would get on to the official shootout page... Carl Witty
On Friday 26 March 2004 17:04, Carl Witty wrote:
Are you aware of this:
2001-12-12 * Due to wanting to get on with other things, I'm freezing the shootout as is, with no further updates planned. It isn't complete, just abandoned (for now).
Nope. Didn't see it. But, heck... all of the sources are available, including build files... maybe if I ask him he'll send me the CGIs that generate the page, too.
(from http://www.bagley.org/~doug/shootout/news.shtml)? So it's unlikely that your updates would get on to the official shootout page...
Someday, they might :-) Obviously, some people (perhaps even on this list) provided most of the Haskell code, but a couple of the missing items seem fairly simple (like the one I did), so I assumed they got bored. At least one is excluded because Haskell can't complete the test within the required time limit, which surprised me. Why is Ocaml so darned fast compared to Haskell? -- ### SER ### Deutsch|Esperanto|Francaise|Linux|XML|Java|Ruby|Aikido ### http://www.germane-software.com/~ser jabber.com:ser ICQ:83578737 ### GPG: http://www.germane-software.com/~ser/Security/ser_public.gpg
On Friday 26 Mar 2004 10:39 pm, Sean E. Russell wrote:
Why is Ocaml so darned fast compared to Haskell?
My guess is that strictness vs. non-strictness probably has a lot to do with it. Not that I think non-strictness itself is a particular problem, but I can't help thinking that a lazy by default evaluation strategy (easiest way to comply with non-strict semantics) is always going to be a bit of a performance killer, especially in typical benchmark style code. Of course it isn't to hard to come up with examples where (for given algorithmic elegance) laziness is a big win too. But in these circumstances users of strict languages would probably chose a different (uglier) approach from the obvious Haskell solution, so there's no opportunity for Haskell to shine here either (in raw performance terms at least). Also, I have a hunch that not only is eager evaluation inherently more efficient (in terms of the raw number of operations that need to be performed), it's probably more cache friendly too (you probably end up with code that looks far more like a traditional imperative loops and whatnot that you'll get by performing "itsy bitsy on demand" graph reduction). There are other issues to, like pure vs. impure and the use of packed strings by default (as I believe Ocaml does) vs. lists of Chars in Haskell. All this is, of course, pure speculation and intuition on my part. (I can't produce a shred of evidence to justify these remarks :-) As someone observed the other day, the figures in the shootout are rather old and probably don't accurately reflect current Haskell (I.E. ghc I presume) performance in any case. BTW, there also seems to be a Win32 clone of the shootout here which may have more life in it.. http://dada.perl.it/shootout/ Regards -- Adrian Hey
On Sat, 27 Mar 2004, Adrian Hey wrote:
Also, I have a hunch that not only is eager evaluation inherently more efficient (in terms of the raw number of operations that need to be performed), it's probably more cache friendly too (you probably end up with code that looks far more like a traditional imperative loops and whatnot that you'll get by performing "itsy bitsy on demand" graph reduction).
Branch misprediction causes problems too, at least with GHC's STG-machine.
All this is, of course, pure speculation and intuition on my part. (I can't produce a shred of evidence to justify these remarks :-)
Check out www.cl.cam.ac.uk/~njn25/pubs/cache-large-lazy2002.ps.gz for more detail (probably more than you want :) about this. Analysing this stuff is very difficult. N
Adrian Hey wrote:
On Friday 26 Mar 2004 10:39 pm, Sean E. Russell wrote:
Why is Ocaml so darned fast compared to Haskell?
...
Also, I have a hunch that not only is eager evaluation inherently more efficient (in terms of the raw number of operations that need to be performed), it's probably more cache friendly too (you probably end up with code that looks far more like a traditional imperative loops and whatnot that you'll get by performing "itsy bitsy on demand" graph reduction).
Actually the cache behaviour of code generated by GHC isn't at all bad. I know because I ran a student project a couple of years ago to implement cache-friendly optimisations. The first thing they did was cache profiling of some benchmarks, and to our surprise we discovered the cache behaviour of lazy code is already pretty good. You get a lot of structure in the evaluation of lazy code -- it just isn't evident in the source code! John
From: John Hughes <rjmh@cs.chalmers.se> Actually the cache behaviour of code generated by GHC isn't at all bad. I know because I ran a student project a couple of years ago to implement cache-friendly optimisations. The first thing they did was cache profiling of some benchmarks, and to our surprise we discovered the cache behaviour of lazy code is already pretty good. You get a lot of structure in the evaluation of lazy code -- it just isn't evident in the source code!
John, could you describe in some more detail why the code behaved well w.r.t. cache performance? I think this is interesting, and what you say is quite counterintuitive. Björn Lisper
On Monday 29 Mar 2004 3:49 pm, John Hughes wrote:
Actually the cache behaviour of code generated by GHC isn't at all bad. I know because I ran a student project a couple of years ago to implement cache-friendly optimisations. The first thing they did was cache profiling of some benchmarks, and to our surprise we discovered the cache behaviour of lazy code is already pretty good. You get a lot of structure in the evaluation of lazy code -- it just isn't evident in the source code!
That's interesting. So why do you think "OCaml is so darned fast compared to Haskell" :-) Seriously though, is this finding consistent with the paper Nicholas Nethercote mentioned? I had a quick read of the paper but didn't take the time to digest the full significance of all tests done and graphs presented. But if I understood the overall conclusions correctly there were several reasons for relatively poor performance on modern processors (one of which was a high rate of cache misses). I suppose we should distinguish code from heap accesses here though. Regards -- Adrian Hey
Adrian Hey wrote:
On Monday 29 Mar 2004 3:49 pm, John Hughes wrote:
Actually the cache behaviour of code generated by GHC isn't at all bad. I know because I ran a student project a couple of years ago to implement cache-friendly optimisations. The first thing they did was cache profiling of some benchmarks, and to our surprise we discovered the cache behaviour of lazy code is already pretty good. You get a lot of structure in the evaluation of lazy code -- it just isn't evident in the source code!
That's interesting. So why do you think "OCaml is so darned fast compared to Haskell" :-)
Seriously though, is this finding consistent with the paper Nicholas Nethercote mentioned? I had a quick read of the paper but didn't take the time to digest the full significance of all tests done and graphs presented. But if I understood the overall conclusions correctly there were several reasons for relatively poor performance on modern processors (one of which was a high rate of cache misses). I suppose we should distinguish code from heap accesses here though.
Let me ask Tobias Gedell to comment, since he was directly involved in the project and probably has the actual results to hand. I'm not sure there's any inconsistency though: that paper finds that 60% of the execution time is due to data cache misses, and so a speed up of at most 2.5x is possible by improving the cache behaviour. That's certainly very respectable, but our initial guess was that the potential speed-ups might be considerably greater. Given the high penalty of L2 cache misses, this still corresponds to a hit rate of 98% or so (couldn't find the exact figure in the paper). We were initially expecting that Haskell programs would miss more often than that. The paper reports a 22% speed-up from prefetching to avoid write misses. If I remember rightly, we also got some decent speed-ups from optimisations aimed at improving the cache behaviour, although this wasn't using the GHC code generator, so the results aren't directly comparable. Tobias? John
On Tuesday 30 March 2004 05:50, John Hughes wrote:
execution time is due to data cache misses, and so a speed up of at most 2.5x is possible by improving the cache behaviour. That's certainly very
That's decent, if it could be achieved.
The paper reports a 22% speed-up from prefetching to avoid write misses. If I remember rightly, we also got some decent speed-ups from optimisations aimed at improving the cache behaviour, although this wasn't using the GHC code generator, so the results aren't directly comparable.
So... was there a reason the GHC work of this research wasn't merged into the GHC distribution? I understood the report to say that the GHC compiler was indeed modified to implement the simple prefetching. -- ### SER ### Deutsch|Esperanto|Francaise|Linux|XML|Java|Ruby|Aikido ### http://www.germane-software.com/~ser jabber.com:ser ICQ:83578737 ### GPG: http://www.germane-software.com/~ser/Security/ser_public.gpg
On Tue, 30 Mar 2004 haskell@ser.fdns.net wrote:
So... was there a reason the GHC work of this research wasn't merged into the GHC distribution? I understood the report to say that the GHC compiler was indeed modified to implement the simple prefetching.
If I recall Nick's presentation of the paper at MSP 2002 I believe the prefetches were placed using a post-processing phase of the x86 binary. The prefetching in the collector only made a more modest difference of between 1 and 4%. I did start playing with prefetching within the context of an incremental collector for GHC. As previous mails have hinted, it's not as simple as just splattering the generated code with prefetches. When prefetching for arrays in loops prefetches are executed every n iterations. The strategy attempts to maximise the prefetch win while minimising the number of prefetch instruction issues. Implementing the strategy for closure reduction is not so easy / obvious. You don't want to issue a prefetch _every_ time you manipulate the referees of a closure (and anyway, then you have the issue of the depth to which to prefetch). It really is quite tricky to ensure that prefetch instructions are not redundant and introduce an overhead. It's deffinitely not very portable and it's certainly not maintainable from a GHC developer point of view. Personally I think looking at 'cache-concious' layout of specific data structures within the allocator and depth first vs breadth first copying within the collector provide more realistic optimisation opportunities. I believe there's been a fair amount of work on this, although specific papers elude me at the mo. Cheers Andy ********************************************************************* * Andrew Cheadle email: a.cheadle@doc.ic.ac.uk * * Department of Computing http://www.doc.ic.ac.uk/~amc4/ * * Imperial College * * University of London * *********************************************************************
As another data point, when I was writing the run-time system both for pH (on an 8-way Sun) and later for Eager Haskell (on x86) I experimented with simple prefetching of various sorts. Two things seemed to be moderately effective: * The heap was organized into "chunks" which were parceled out among running threads. By writing into the pages of a chunk when it is allocated, the necessary TLB entries can be pulled in early. This seemed to be a universal win on both architectures. On a system with full software TLB miss handling it would be a wash, I expect. * Writing a line or two ahead in the heap. The idea here is to get the appropriate lines into the cache (and dirty) before they actually saw heavy use. Alas, this can cause fenceposting problems when you get near the end of a chunk (it's not safe to write past a chunk boundary). A processor which buffers writes doesn't benefit enormously, either; we can buffer the last cache line in the heap until it has been completely written, and never fetch from memory at all. There were no big wins here in my experience. One has to be careful about the semantics of prefetch instructions, by the way. At least on SPARC they probably don't do what you want; if my memory serves me correctly, there is a separate prefetch cache that's connected to the floating-point load/store unit, and what you actually want for most Haskell-ish code would be a non-blocking load instruction instead. On x86 the prefetch instructions are part of the SIMD floating-point instruction set, and might (or might not) have similar caveats. The prefetch builtins for gcc are a pretty recent innovation, by the way. I would have loved to have them back when I was experimenting. Of course, you'd want to make sure you got an appropriate instruction out of the compiler. Andrew Cheadle wrote:
Personally I think looking at 'cache-concious' layout of specific data structures within the allocator and depth first vs breadth first copying within the collector provide more realistic optimisation opportunities. I believe there's been a fair amount of work on this, although specific papers elude me at the mo.
I would agree with this---though the conclusion from the GC literature seems to be that no particular copying strategy is best for all applications. -Jan-Willem Maessen
On Fri, 2004-03-26 at 14:39, Sean E. Russell wrote:
On Friday 26 March 2004 17:04, Carl Witty wrote:
Are you aware of this:
2001-12-12 * Due to wanting to get on with other things, I'm freezing the shootout as is, with no further updates planned. It isn't complete, just abandoned (for now).
Nope. Didn't see it. But, heck... all of the sources are available, including build files... maybe if I ask him he'll send me the CGIs that generate the page, too.
(from http://www.bagley.org/~doug/shootout/news.shtml)? So it's unlikely that your updates would get on to the official shootout page...
Someday, they might :-)
Well, it looks like the Shootout has been revived. The revival was announced by Brent Fulgham on June 7; the new site is at http://shootout.alioth.debian.org/ . Carl Witty
participants (9)
-
Adrian Hey -
Andrew Cheadle -
Bjorn Lisper -
Carl Witty -
haskell＠ser.fdns.net -
Jan-Willem Maessen - Sun Labs East -
John Hughes -
Nicholas Nethercote -
Sean E. Russell