[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):

 Here's a simple example of the quadratic code size I was talking about in
 comment:7, not specific to Read or Applicative or Monad.
 {{{#!hs
 f a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
   = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10
 }}}
 At the Core and STG stages the size of `f` is linear in the number of
 arguments. But the Cmm for `f` builds a thunk for the first argument `a1 +
 a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9` and then calls `+`. In order to
 build that thunk it has to copy `a1` through `a9` into the thunk, as they
 are its free variables. Then the code for that thunk is going to build
 another thunk for `a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8`, which requires
 copying `a1` through `a8` again, and so on. The total code size, work done
 and allocations are all quadratic in the number of arguments.

 In this particular case it would clearly be better to do all the thunk
 construction up front in `f`, like (pseudo-STG)
 {{{#!hs
 f a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
   = let t2 = a1 + a2
         t3 = t2 + a3
         t4 = t3 + a4
         ...
         t9 = t8 + a9
     in t9 + a10
 }}}
 which would be linear code size, work and allocations in the number of
 arguments.

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