Seemingly subtle change causes large performance variation

[Malcolm Wallace]

Matthew Danish <mdanish at andrew.cmu.edu> wrote:

> I've been playing with the INTEST problem on SPOJ which demonstrates
> the ability to write a program which processes large quantities of
> input data.  http://www.spoj.pl/problems/INTEST/

I don't know if anyone replied to this already, so here is my attempt to
explain the space leak.

>         doLine :: Int -> Int -> IO Int
>         doLine r _ = B.getLine >>= testDiv r
>         testDiv r l
>          | int l `divisibleBy` k = return (r + 1)
>          | otherwise             = return r
> 
> But when I make a slight modification, the program chews up a ton more
> memory and takes more time:
> 
>         doLine :: Int -> Int -> IO Int
>         doLine r _ = B.getLine >>= return . testDiv r
>         -- 'return' moved here      ^^
>         testDiv r l
>          | int l `divisibleBy` k = r + 1
>          | otherwise             = r

In the first version, the strictness of the IO monad ensures that
'testDiv' must be evaluated, at least sufficiently to find the 'return'
monadic action inside it.  In particular, this forces the evaluation of
the guard, and therefore the call of `divisibleBy`.

Whereas in the latter version, the 'return' is wrapped _outside_ the
call to 'testDiv', so the monadic action is found immediately, whilst
the value being returned in in the monad is still lazily calculated.
Thus, a collection of 'testDiv r' applications builds up until the Int
values are actually used, at which point they are reduced.

Regards,
    Malcolm