Deforestration harmful?

[Olaf Chitil]

Shin-Cheng Mu wrote:
>     g seed = [ z | (s1, s2) <- split seed,
>                     x <- g s1, y <- g s2, z <- join x y ]
> 
> The relation f was almost as simple as a replacing each
> constructor in Tree1 with one or more coresponding constructors in
> Tree2. They two can be fused together and becomes
> 
>    fg seed = [ z | (s1, s2) <- split seed,
>                     x <- fg s1, y <- fg s2, z <- join' x y ]
> 
> The intermediate datatype Tree1 was thus eliminated.
> 
> The problem was: the fused program ran slower than the
> original one! At least if you measure the total running
> time (either via the UNIX time command or use the CPUTime
> module). The time reported in the GHC time profile indeed
> showed that the fused program is faster, though, if GC time
> is excluded.
> 
> We were quite curious why and my guess was: since f maps a
> Tree1 to more than one Tree2, in the two list comprehensions,
> the list produced by (fg s2) is much longer than (g s2).
> The fused program thus has to keep a longer list in memory.
> Worse heap residency results in more GCs. (Luckily GHC did not
> attempt to automatically perform the fusion for us! :) )

Note that you have done more than just deforestation. You have moved f
through join, obtaining join'. Because as you say (fg s2) is much longer
than (g s2), join' is applied more often than join was applied before. I
don't know how expensive your join and join' are.

Furthermore, deforestation itself does not reduce runtime very much.
More important is the secondary effect that deforstation moves formerly
separated expressions close to each other, so that further optimisations
can take place. Maybe in your example there are not many further
optimisations?

In real life it is seldomly clear which transformations are
optimisations... (maybe a different machine will yield different results
again?).

Ciao,
Olaf

-- 
OLAF CHITIL, 
 Dept. of Computer Science, The University of York, York YO10 5DD, UK. 
 URL: http://www.cs.york.ac.uk/~olaf/
 Tel: +44 1904 434756; Fax: +44 1904 432767