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

[Andrew Cheadle]

On Tue, 30 Mar 2004 haskell at 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 at doc.ic.ac.uk *
*  Department of Computing           http://www.doc.ic.ac.uk/~amc4/ *
*  Imperial College                                                 *
*  University of London                                             *
*********************************************************************