SwirlyMyself

2014-05-26T12:10:46+00:00

Does list fusion work?

I’m writing this in the lunch break of TFP in Soesterberg. The invited talk this morning was by Geoffrey Mainland, and he talked about the difficulties of (informal) reasoning about performance in high-level languages like Haskell, especially with fancy stuff in the compiler like fusion. So I couldn’t help but think about a (very small) help here.

Consider the the two very similar expressions foldl (+) 0 [0..1000] and foldr (+) 0 [0..1000]. Which of these fuse away the list? Hopefully both, but hard to predict.

So with my list-fusion-probe library, you can write

import Data.List.Fusion.Probe (fuseThis)
main = print $ foldr (+) 0 (fuseThis [0..1001])

and find out. If you compile this (with -O!), it will print

500500

If you change the foldr to foldl, it will print

Test: fuseThis: List did not fuse

So you can see that the function fuseThis :: [a] -> [a] does nothing if the list gets fused away, but causes a run-time error if not. It allows you to annotate your code with your assumptions of list fusion, and get shouted at if your assumptions are wrong.

It wouldn’t be hard to have the compiler give a warning or error message at compile time; we’d just need to introduce a special function abortCompilation that, when found in the code during compilation, does just that.

Note that you’ll have trouble reproducing the above in GHC HEAD, where foldl does fuse (which is what I’m going to talk about tomorrow here).

Comments

FYI, it's Soesterberg (with an "e").
#1 Anonymous am 2014-05-26T21:53:29+00:00
Thx!
#2 Joachim Breitner (Homepage) am 2014-05-27T08:09:39+00:00

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.