[Haskell-cafe] not enough fusion?

[Bertram Felgenhauer]

Hi,

Johannes Waldmann wrote:
> s2 :: Int -> Int       
> s2 n = sum $ do 
>       x <- [ 0 .. n-1 ]
>       y <- [ 0 .. n-1 ]
>       return $ gcd x y

This code shows some interesting behaviour: its runtime depends heavily
on the allocation area size.

For comparison, with  main = print $ s1 10000  I see the following GC
statistics.

# ./a.out +RTS -A512k -s
  15,201,891,976 bytes allocated in the heap
       4,272,144 bytes copied during GC
  Total   time    9.97s  ( 10.00s elapsed)
  %GC     time       1.1%  (1.1% elapsed)

For s2, using  main = print $ s2 10000,  I get

# ./s2 +RTS -A512k -s
  20,801,251,976 bytes allocated in the heap
   3,438,870,504 bytes copied during GC
  Total   time   15.90s  ( 15.95s elapsed)
  %GC     time      34.3%  (34.4% elapsed)
# ./s2 +RTS -A1m -s
  20,801,251,976 bytes allocated in the heap
   2,724,903,032 bytes copied during GC
  Total   time   14.74s  ( 14.80s elapsed)
  %GC     time      29.2%  (29.3% elapsed)
# ./s2 +RTS -A2m -s
  20,801,251,976 bytes allocated in the heap
      20,311,952 bytes copied during GC
  Total   time   10.74s  ( 10.78s elapsed)
  %GC     time       1.2%  (1.2% elapsed)
# ./a.out +RTS -A2052k -s
  20,801,251,976 bytes allocated in the heap
       1,812,776 bytes copied during GC
  Total   time   10.35s  ( 10.38s elapsed)
  %GC     time       0.8%  (0.8% elapsed)

Note that the number of bytes copied during GC drops by three orders of
magnitude when we increase the allocation area size from 1 MB to 2 MB,
and another order of magnitude when adding an additional 4kB to that.

Why does this happen? The reason is a failure of generational GC
heuristics. If we look at the core, we find that the inner loop (which
generates a list that is consumed by sum) translates to something like

    nums = [0..9999]

    go xs0 = case xs0 of
        [] -> []
        x : xs -> let
            go' ys0 = case ys0 of
                [] -> []
                y : ys -> GHC.Real.gcdInt x y : go' ys
          in
            case go' nums of
                [] -> go xs
                (z : zs) -> z : zs ++ go xs

At a first glance, this looks fine - there's one big chunk of fixed data
(the nums list) that will end up in the old generation. The rest of the
data is consumed as it is created. However, this is not quite true: The
thunk for the second argument to (++) (representing 'go xs') is already
allocated on the heap when the first element of the result of (++), i.e.,
the first element of zs, is consumed. While  zs  is processed, this thunk
is never touched. If it survives a whole GC-mutator cycle, then the next
garbage collection will consider the thunk mature and put it into the
old generation. But when the code starts evaluating this 'go xs' call,
it produces a long list, all of which is being kept alive by the (now
updated) thunk in generation 1, and as a result will be copied during
GC, until the next major GC.

So the observed behaviour hinges on the question whether the  go xs
thunk can survive processing the zs list. The memory allocated during
this time is constant - besides the list, some memory is allocated
for thunks in go', and for intermediate Integers[*] in gcdInt. If the
allocation area size exceeds this constant, then the program will
run as expected. Note that every time a 'go xs' thunk survives, a lot
of extra work is caused for the GC -- this explains the sharp increase
in bytes copied observed above.

Bertram

[*] gcdInt really ought to only do a single allocation for the result,
with an inlining opportunity to get rid of that as well. It is defined
in GHC.Real as

gcdInt :: Int -> Int -> Int
gcdInt a b = fromIntegral (gcdInteger (fromIntegral a) (fromIntegral b))

which used to optimize to a single low-level GHC.Integer.Type.gcdInt call
in ghc 7.2. With 7.4 and HEAD, integerToInt and smallInteger are no longer
inlined, resulting in worse code. See also

  http://hackage.haskell.org/trac/ghc/ticket/7041