[Haskell] Programming language shootout (completing the Haskell entry)

[Simon Marlow]

> >From: John Hughes <rjmh at 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.

I've done some cache profiling of GHC's code myself, and Nick Nethercote
did some very detailed measurements a while back (see his recent post
for details).

The upshot of what he found is that we could benefit from some
prefetching, perhaps on the order of 10-20%.  Particularly prefetching
in the allocation area during evaluation, to ensure that memory about to
be written to is in the cache, and similar techniques during GC could
help.  However, actually taking advantage of this is quite hard -
prefetching instructions aren't standard, and even when they are getting
any benefit can depend on cache architecture and other effects which
vary between processor families.  Getting things wrong often results in
a slowdown.  It's just too brittle.

There are probably other techniques that could help improve cache
behaviour, but my feeling is that there aren't any significant wins to
be had here; John's comments above appear to back this up too.

Cheers,
	Simon