[Haskell-cafe] Flattening tail recursion?

[John Meacham]

On Mon, Dec 13, 2004 at 11:56:45AM +0100, Daniel Fischer wrote:
> I had the idea that, instead of using 'seq', one might check for parity:
> 
> countLines2 aux (_:l)
>       | even aux = ...
>       | odd aux  = ...
> 
> that prevents stack overflow, but is much slower than
> countLines1 aux (_:l)
>      | aux `seq` False = ...
>      | otherwise          = ...
> 
> I also tried
> countLines3 aux (_:l)
>      | even aux || odd aux = ...
>      | otherwise                 = ...
> and
> countLines4 aux (_:l)
>      | even aux || True = ...
>      | otherwise            = ...
> which also are slower than countLines1.
> Well, checking for parity takes time, so that is no real surprise. 
> What somehow puzzles me is that, compiling with -O, all versions of countLines 
> are equally fast, if I give the type
> 
> countLines :: Int -> [a] -> Int,
> 
> but if I replace Int with Integer, the plain version without guards and the 
> 'seq' version are equally fast whereas the parity-check versions are equally 
> fast among themselves but slower than plain. 

This is likely because since Int is builtin to the compiler and compiled
directly into 'case' statments in core,
it can deduce that one of even or odd must be true and via normal case
simplifications transform
(even x || odd x) directly into (x `seq` True).
Integer, however is implemented partially by the gmp library, so ghc is
less privy to its internals and probably was unable to deduce that one
of even or odd must be true for Integer. In particular, pattern matching
on Integers is implemented via nested equality tests rather than direct
case statements. (AFAIK) 

> If I omit the type-declaration, all versions perform differently, plain 
> producing stack overflow, countLines1 being by far the fastest, countLines4 
> coming in second, then countLines3 and last countLines2.

This is because if you omit the type declaration, ghc will deduce the
much more general type of

countLines :: Num a => [x] -> a

which in ghc's implementation of overloading will take an extra argument
describing how to work on 'a's and call the overloaded functions, the
compiler cannot know how they are implemented so is unable to apply
certain transformations.

> 
> If I give the type Int -> [a] -> Int and use interpreted code, plain 
> overflows, countLines1 is by far the fastest, but then things change. Now 
> countLines2 comes in second, third is countLines4, relatively close, last, at 
> a distance, is countLines3. (Qualitatively the same, but slower, without 
> type-declaration).
> 
> With type Int -> [a] -> Int, but compiled without -O, the results are (for 
> countLinesX 0 [1 .. 1500000])
> plain : stack overflow,
> 1  : 0.43 secs,
> 2  : 1.10 secs,
> 3  : 1.26 secs,
> 4  : 0.93 secs.
> 
> Now obviously -O does a good job (though 'seq' isn't so bad even without -O), 
> but why does checking for parity take extra time for Integer and not for Int?

see first response above for my guess :)
> 
> And why does compilation without -O change the order of versions 2-4 ?

This is likely because of strictness analysis. What
strictness analysis does in effect is analyze the program to determine
whether a result will definitly be required, it is a rather expensive
operation in the presence of higher order and mutually recursive
functions, but the end result is that if ghc deduces that a value will
always be needed, such as the first argument to countLines', it places
(the equivalant) of a seq in there for you :). This is called the
'let-to-case' transformation in the compiler because a 'case' always
evaluates its argument in the internal language while a let allocates a
lazy thunk.

It is just something that one must get used to in haskell programming
(with ghc at least) that -O can have drastic order changing  effects
compared to the relativly incremental ones for other languages. The
various papers available on the net regarding ghc's internals are
fascinating if you are interested in the various optimizations it trys. 

> If anybody knows, mind telling me?

nope :). A lot of the above is speculation, I am by no means a ghc
expert, but I belive it is what is happening.


-- 
John Meacham - ⑆repetae.net⑆john⑈