ghc more aggressive with Ints?

[Simon Peyton-Jones]

| > sumMinusOnce l =3D foldr sumMinus (0,0) l
| >     where sumMinus c (a,b) =3D (a+c, c-b)
| >
| > sumMinusTwice l =3D (foldr (+) 0 l, foldr (-) 0 l)


| Here, we see that for everything but INT, the ONCE version is about
two
| times slower.  For the other versions
| (say DOUBLE), the ONCE version is consistently two times slower.  This
| raises the question as to why.

The reason turns out to be that Int enumerations [1..100] are carefully
expanded to
	build (enumFromToInt 1# 100#)

where enumFromToInt is a hand-written unboxed version of enumFromTo.  So
we get list deforestation from the fold/build.  (Incidentally, this may
not happen if there are several calls to sumMinusOnce, or it's exported,
because the fold will only see the build if sumMinusOnce is inlined.)

The Double version uses the vanilla numericEnumFromTo (as in the Report)
which does not expand to a 'build'.  So no fold/build happens.

By adding more code to the Prelude, one could 'fix' this, by making
numericEnumFromTo have a build version.  Whether this is worth the
bother is not clear to me.  If anyone is motivated to do it (needs
understanding of how RULES work) by all means do so.

Simon


|=20
| Looking at the -ddump-simpl output, we can see why.  In the
sumMinusOnce
| version, when given an Int type signature, the tuple gets
| unboxed and the primitive GHC.Prim.+# and GHC.Prim.-# functions are
| used.  In the one where we've given a Double type signature, we don't
get
| this.  The tuple still gets unboxed, but the non-unboxed functions
| GHC.Float.plusDouble and GHC.Float.minusDouble functions are used
instead.
|=20
| Perhaps more importantly, the Double version is left as a recursive
call,
| looking something like:
|=20
| > Main.$wgo =3D \w ->
| >   case w of
| >     (y:ys) -> case Main.$wgo ys of
| >                 (# ww1, ww2 #) ->
| >                    (# plusDouble ww1 y, minusDouble y ww2) #)
| >    []     -> (# 0, 0 #)
|=20
| (converted by hand from simpl-core to a more Haskelly syntax)
|=20
| However, the Int version becomes a very tight loop in which the list
is
| deforested.
|=20
| My understanding was that using list comprehensions like [1..100000]
| together with foldr you would always get build/fold deforestation, but
| this only seems to happen when the list is a list of Ints, not a list
of
| Doubles.
|=20
| If we change the Once function to:
|=20
| > i2d :: Int -> Double
| > i2d =3D fromInteger.toInteger
| >
| > sumMinusOnce :: [Int] -> (Double, Double)
| > sumMinusOnce l =3D foldr sumMinus (0,0) l
| >     where sumMinus c (a,b) =3D (a+i2d c, (i2d c)-b)
|=20
| then we do get full deforestation as we want.  This new version, when
run
| with [1..250000], yields a time of
|=20
| 4.12u 0.23s 0:04.44
|=20
| which is actually faster than the TWICE/DOUBLE version.
|=20
| So...why is GHC more aggressive with Ints than with Doubles and what
are
| the additional conditions under which fold/build deforestation occurs?
|=20
|  - Hal
|=20
| --
| Hal Daume III
|=20
|  "Computer science is no more about computers    | hdaume@isi.edu
|   than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
|=20
|=20
|=20
|=20
|=20
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users@haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users