ghc more aggressive with Ints?

[Hal Daume III]

Hi,

This is somewhat related to an earlier post about streaming by Jorge, and
to a similar post by me a bunch of months back regarding multiple ways of
writing a similar function.

Many times when processing data which you need to process in more than
once way, you have two options: (1) process it in one go and store
intermediate results as, eg, tuples; (2) process it in more than one
go.

I've been told that the latter is the more "haskelly" way to do it, but I
don't completely buy that.  Especially in cases like Jorge's, since the
data will not be able to be garbage collected between runs and thus the
whole program will require a much larger stack/heap/whatever.

In either case, consider the following (semantically
equivalent) functions:

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

The first takes one pass over the data, while the second takes two.  Now,
we can give these functions various type signatures, Int, Integer, Float
or Double (more, of course, but these are the basics).  When the list is
[1..250000], the timing results look like:

        | ONCE                   | TWICE
--------+------------------------+------------------------
INT     | 1.81u 0.18s 0:02.07    | 1.84u 0.15s 0:01.99
INTEGER | 9.77u 0.28s 0:10.29    | 5.07u 0.07s 0:05.23
FLOAT   | 8.60u 0.30s 0:09.08    | 3.79u 0.16s 0:04.07
DOUBLE  | 9.50u 0.25s 0:09.82    | 4.25u 0.16s 0:04.44

Here, we see that for everything but INT, the ONCE version is about two
times slower.  If we pump the input size up to [1..1000000], then the
times for INT become

INT     | 16.38u 0.66s 0:17.22   | 20.75u 0.34s 0:21.33

Here, there's a much smaller difference in speed.  For the other versions
(say DOUBLE), the ONCE version is consistently two times slower.  This
raises the question as to why.

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.

Perhaps more importantly, the Double version is left as a recursive call,
looking something like:

> Main.$wgo = \w ->
>   case w of
>     (y:ys) -> case Main.$wgo ys of
>                 (# ww1, ww2 #) ->
>                    (# plusDouble ww1 y, minusDouble y ww2) #)
>    []     -> (# 0, 0 #)

(converted by hand from simpl-core to a more Haskelly syntax)

However, the Int version becomes a very tight loop in which the list is
deforested.

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.

If we change the Once function to:

> i2d :: Int -> Double
> i2d = fromInteger.toInteger
>
> sumMinusOnce :: [Int] -> (Double, Double)
> sumMinusOnce l = foldr sumMinus (0,0) l
>     where sumMinus c (a,b) = (a+i2d c, (i2d c)-b)

then we do get full deforestation as we want.  This new version, when run
with [1..250000], yields a time of

4.12u 0.23s 0:04.44

which is actually faster than the TWICE/DOUBLE version.

So...why is GHC more aggressive with Ints than with Doubles and what are
the additional conditions under which fold/build deforestation occurs?

 - Hal

--
Hal Daume III

 "Computer science is no more about computers    | hdaume@isi.edu
  than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume