Strict foldl

Manuel M. T. Chakravarty [email protected]
Fri, 07 Dec 2001 13:33:13 +1100


Hal Daume III <[email protected]> wrote,

> > Is this what I think it is?  Do you benchmark the
> > interpreter?  Interpreted code isn't optimised.  When I
> > compile 
> > 
> >   main = print $ sum [1..10000000]
> > 
> > with -O2, it takes 13s on a 600MHz P3 and runs in 1.5MB of
> > space.
> 
> Out of curiousity, why doesn't this get compiled down to
> 
>   main = print 50000005000000
> 
> ?
> 
> That is, why doesn't the compiler carry out the calculation and then just
> embed that in the compiled version?

Because the compiler can't be sure that the computation
terminates.  If it doesn't, the compiler would not
terminate, which usually makes users quite unhappy ;-)

> I know that some C compilers do (at least somewhat) similar things when,
> for example, you say:
> 
>   x = y * 4
> 
> it will rewrite this as
> 
>   x = y << 2
> 
> and even do more complicated stuff, like if you say
> 
>   x = y * 12
> 
> it will give
> 
>   x = 3 * (y << 2)
> 
> or whatnot.
> 
> can I expect this from ghc/nhc/etc?

These kinds of optimisations are different from the use of a
Prelude function like `sum', because they don't affect the
termination behaviour of the compiler.  With -fvia-C GHC
will generate C code that is, then, run through the C
compiler.  If you take this route, then optimisations, such
as those you describe, are performed by the C compiler on
your Haskell code.

The natice code generator probably also performs some of
those optimisations, but I am not sure exactly which.

Cheers,
Manuel