[GHC] #10980: Deriving Read instance from datatype with N fields leads to N^2 code size growth

[GHC]

#10980: Deriving Read instance from datatype with N fields leads to N^2 code size
growth
-------------------------------------+-------------------------------------
        Reporter:  slyfox            |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.10.2
      Resolution:                    |             Keywords:  deriving-perf
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by rwbarton):

 However, the quadratic behavior exhibited by the Read instance is more
 similar to this example
 {{{#!hs
 f :: (Int -> a) -> a
 f k = k 0
 {-# NOINLINE f #-}

 v :: (Int,Int,Int,Int,Int,Int,Int,Int,Int,Int)
 v = f (\a1 -> f (\a2 -> f (\a3 -> f (\a4 -> f (\a5 ->
     f (\a6 -> f (\a7 -> f (\a8 -> f (\a9 -> f (\a10 ->
     (a1,a2,a3,a4,a5,a6,a7,a8,a9,a10)))))))))))
 }}}
 `v` is supposed to correspond to the desugaring of the long `do` blocks in
 slyfox's attachments.

 Here the quadratic blowup at the Cmm stage is caused by the fact that the
 free variables of the nth lambda are all the preceding `a1`, ..., `an`. We
 have to copy `a1` through `an` into the (n+1)st lambda that we provide as
 an argument to the next `f`.

 This is the blowup that I said I didn't know how to solve in the code
 generator in comment:7. However, (I claimed that) in this case we can
 avoid generating such nested lambdas in the first place by changing the
 desugaring to use Applicative methods rather than Monad ones.

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