[Haskell-cafe] Re: Using loop fusion for writing efficent high-level code Re[2]: [Haskell] [Fwd: Re: Computer Language Shootout]

[Duncan Coutts]

On Wed, 2007-02-28 at 16:38 +0300, Bulat Ziganshin wrote:
> Hello Duncan,
> 
> Tuesday, February 27, 2007, 1:09:53 PM, you wrote:
> 
> can you please provide examples of such code? the ultimate goal is to
> have tutorial on writing efficient code in high-level manner, but that
> is too ambitious. just some examples with a little explanation of how
> this is compiled?

The main example of course is ByteString fusion as presented in our
recent paper:

http://www.cse.unsw.edu.au/~dons/papers/CSL06.html

The first example in the paper is the simple pipeline:

return · foldl hash 5381 · map toLower · filter isAlpha =< readFile f
   where hash h c = h ∗ 33 + ord c


This is fairly fast when just using the ordinary ByteString
implementations of foldl map filter etc but the naive C version is still
faster. That is, just composing highly tuned low level implementations
of list like combinators is not enough.

We do not want to the python approach of stitching together fast C/C++
code with slow glue code. Instead we use the above more like a spec and
try to generate high performance low level code.

We transform each of the functions foldl, map & filter into their stream
style counterparts, fuse them together and inline everything (the
compiler also does some other critical optimisations like case-of-case)
to get a single imperative loop. The result is competitive with C,
indeed we have to rewrite the C code into an even uglier form to be able
to beat the Haskell version.

Duncan