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