[GHC] #7436: Derived Foldable and Traversable instances become extremely inefficient due to eta-expansion

[GHC]

#7436: Derived Foldable and Traversable instances become extremely inefficient due
to eta-expansion
---------------------------------+------------------------------------------
    Reporter:  shachaf           |       Owner:                         
        Type:  bug               |      Status:  new                    
    Priority:  normal            |   Milestone:                         
   Component:  Compiler          |     Version:  7.6.1                  
    Keywords:                    |          Os:  Unknown/Multiple       
Architecture:  Unknown/Multiple  |     Failure:  Runtime performance bug
  Difficulty:  Unknown           |    Testcase:                         
   Blockedby:                    |    Blocking:                         
     Related:                    |  
---------------------------------+------------------------------------------

Comment(by shachaf):

 I'd think what I said above about the eta-expansion happening at each
 iteration
 is sufficient to explain it.

 The reduction should happen something like this (not all at once, of
 course,
 but this is enough to demonstrate what I mean):

 {{{
 slow S Z
   $ S (S (S (S Z)))

 S $ slow (\a -> S a) Z
   $ S (S (S Z))

 S $ (\a -> S a)
   $ slow (\b -> (\a -> S a) b) Z
   $ S (S Z)

 S $ (\a -> S a)
   $ (\b -> (\a -> S a) b)
   $ slow (\c -> (\b -> (\a -> S a) b)) Z
   $ (S Z)

 S $ (\a -> S a)
   $ (\b -> (\a -> S a) b)
   $ (\c -> (\b -> (\a -> S a) b))
   $ slow (\d -> (\c -> (\b -> (\a -> S a) b))) Z
   $ Z

 S $ (\a -> S a)
   $ (\b -> (\a -> S a) b)
   $ (\c -> (\b -> (\a -> S a) b))
   $ Z
 }}}

 So we'd expect a tower of `1+2+3+...+n-1` reductions of the lambda.

 The profiling results seem to agree (sum [1..100000-1] = 4999950000):

 {{{
 shachaf at carbon:~/9$ ghc -prof -fprof-auto -rtsopts -O2 C.hs && time ./C
 +RTS -p
 ()

 real    1m3.477s
 user    1m3.372s
 sys     0m0.004s
 shachaf at carbon:~/9$ cat C.prof
         Wed Nov 21 06:21 2012 Time and Allocation Profiling Report
 (Final)

            C +RTS -p -RTS

         total time  =       49.32 secs   (49319 ticks @ 1000 us, 1
 processor)
         total alloc =  11,249,528 bytes  (excludes profiling overheads)

 COST CENTRE MODULE    %time %alloc

 slow.\      Main      100.0   14.2
 slow        Main        0.0   49.8
 mkNat       Main        0.0   35.6


                                                        individual
 inherited
 COST CENTRE  MODULE                  no.     entries  %time %alloc   %time
 %alloc

 MAIN         MAIN                     45           0    0.0    0.0   100.0
 100.0
  main        Main                     91           0    0.0    0.1     0.0
 0.1
  CAF         Main                     89           0    0.0    0.0   100.0
 99.6
   main       Main                     90           1    0.0    0.0   100.0
 99.6
    mkNat     Main                     95      100001    0.0   35.6     0.0
 35.6
    slow      Main                     94      100001    0.0   49.8   100.0
 64.0
     slow.\   Main                     96  4999950000  100.0   14.2   100.0
 14.2
    unNat     Main                     93      100001    0.0    0.0     0.0
 0.0
    main.n    Main                     92           1    0.0    0.0     0.0
 0.0
  CAF         GHC.IO.Handle.FD         88           0    0.0    0.3     0.0
 0.3
  CAF         GHC.Show                 87           0    0.0    0.0     0.0
 0.0
  CAF         GHC.Conc.Signal          86           0    0.0    0.0     0.0
 0.0
  CAF         GHC.IO.Encoding          76           0    0.0    0.0     0.0
 0.0
  CAF         GHC.IO.Encoding.Iconv    75           0    0.0    0.0     0.0
 0.0
 }}}

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/7436#comment:5>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler