[Haskell-cafe] Re: Difference in Runtime but no explanation

[Daniel Fischer]

Am Dienstag 15 Dezember 2009 19:30:06 schrieb Maciej Piechotka:
> On Tue, 2009-12-15 at 09:52 -0800, Johann Höchtl wrote:
> > Hello,
> >
> > I'm still to Haskell, and after I read through
> > http://users.aber.ac.uk/afc/stricthaskell.html#seq
> >
> > I thought, that these tow fragments after term rewriting are really
> > the same:
> >
> > myLength :: [a] -> Integer
> > myLength xs = len xs 0
> >     where len [] l = l
> >           len (x:xs) l = l `seq` len xs (l+1)
> >
> > main = print $ myLength [1..10000000]
> >
> >
> > -- vs.
> >
> > myLength :: [a] -> Integer
> > myLength xs = len xs 0
> > where len [] l = l
> >       len (x:xs) l = len xs $! (l+1)
> >
> >       main = print $ myLength [1..10000000]
> >
> > main = print $ myLength [1..10000000]
> >
> > But the first expression evaluates more then twice as fast as the
> > second one. Tested on GHC 6.10.4 and Windows XP, dual core (for what
> > it's worth)

Is that
a) interpreted
b) compiled without optimisations
c) compiled with optimisations
?

If c), that's a serious bug. With optimisations turned on, both should give 
(approximately) identical code, the same as with "len (x:xs) l = len xs (l+1)".
With -O2, that gives exactly the same core as the first, the second has one (unnecesary, 
because everything is recognized as strict) case expression in otherwise identical core.
All three perform identically here.

If a) or b), it's because the second has one more function call per list element, first 
($!) is called and then seq via that, while the first calls seq directly.

> >
> > It's on http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=5321#a5321
> > btw.
> >
> > I can't see the difference, especially as $! is expressed in terms of
> > seq
>
> The second one is IMGO:
> myLength :: [a] -> Integer
> myLength xs = len xs 0
>               where len [] l = l
>                     len (x:xs) l = let l' = l+1
>                                    in l' `seq` len xs l'
>
> So in thew first + is not forced to be evaluated.
>
> My results (ghc 6.12.1, Core 2 Duo 2.8 GHz, Linux 2.6.32, Gentoo):
>
> Not Optimized & not compiled:
> First:	12.47 secs, 1530911440 bytes
> Second:	17.40 secs, 1929614816 bytes

Wow. Here, interpreted and not optimised:
First:  10.10 secs (Integer) 10.45 secs (Int)
Second: 11.80 secs (Integer) 11.93 secs (Int)

ghc 6.12.1, built from source, 3GHz Pentium 4 (2 Cores), Linux linux-mkk1 2.6.27.39-0.2-
pae (openSuse 11.1)

With ghci-6.10.3
First:  14.58 secs (Integer) 14.53 secs (Int)
Second: 17.05 secs (Integer) 18.31 secs (Int)

Nowhere near the difference that you have.

> Optimized & compiled:
> First:	 1.24 secs, 966280832 bytes
> Second:	 1.11 secs, 966277152 bytes

Compiled with -O (same with -O2)
First:  0.36 secs (Integer) 0.30 secs (Int)
Second: 0.36 secs (Integer) 0.30 secs (Int)
length: 0.32 secs

Astonishing that compiling does so much less on your box.

With ghc-6.10.3 (-O/-O2)
First:  0.23 secs (Integer) 0.17 secs (Int)
Second: 0.26 secs (Integer) 0.17 secs (Int)
length: 0.19 secs

Ouch! Why is 6.10.3 so much better here?

Compiled without optimisations
First:  0.48 secs (Integer) 0.49 secs (Int)
Second: 1.07 secs (Integer) 1.01 secs (Int)

With 6.10.3
First:  0.38 secs (Integer) 0.36 secs (Int)
Second: 1.47 secs (Integer) 1.46 secs (Int)

Wait, what?