[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
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 The problem observed on GHC's code base when explored why exactly some
 object files are so huge.

 Let's look at  the stats of text code section sizes on today's HEAD
 (skipping GHCi libraries and stage1 binaries):

 {{{
 ~/dev/git/ghc $ size `find -name *.o -type f | grep -v stage1 | grep -v
 HS` | sort -k1 -n -r | head -n20
    text    data     bss     dec     hex filename
 1791068  145448       0 1936516  1d8c84 ./compiler/stage2/build/DynFlags.o
 1558637   77464       0 1636101  18f705 ./compiler/stage2/build/PprC.o
 1397966   23272       0 1421238  15afb6
 ./compiler/stage2/build/PlatformConstants.o
 1332048  373344       0 1705392  1a05b0 ./libraries/Cabal/Cabal/dist-
 boot/build/Distribution/PackageDescription.o
 1331238  373352       0 1704590  1a028e
 ./bootstrapping/Distribution/PackageDescription.o
 1271578  246240       0 1517818  1728fa ./libraries/template-haskell/dist-
 boot/build/Language/Haskell/TH/Syntax.o
 1229696  311616       0 1541312  1784c0 ./libraries/Cabal/Cabal/dist-
 install/build/Distribution/PackageDescription.o
 1215082  224288       0 1439370  15f68a ./libraries/template-haskell/dist-
 install/build/Language/Haskell/TH/Syntax.o
 1071746  242664       0 1314410  140e6a ./compiler/stage2/build/HsExpr.o
 1015090   40904       0 1055994  101cfa
 ./compiler/stage2/build/Llvm/PpLlvm.o
  970203  124944       0 1095147  10b5eb ./compiler/stage2/build/Parser.o
  849693   79760       0  929453   e2ead ./compiler/stage2/build/HsDecls.o
  833327   35440       0  868767   d419f
 ./compiler/stage2/build/X86/CodeGen.o
  819959  127192       0  947151   e73cf ./libraries/Cabal/Cabal/dist-
 boot/build/Distribution/Simple/Setup.o
  819685  125120       0  944805   e6aa5
 ./bootstrapping/Distribution/Simple/Setup.o
  816927  124520       0  941447   e5d87 ./libraries/Cabal/Cabal/dist-
 install/build/Distribution/Simple/Setup.o
  785398   41536       0  826934   c9e36 ./compiler/stage2/build/CoreLint.o
  772550   42040       0  814590   c6dfe
 ./compiler/stage2/build/DriverPipeline.o
  766461   36280       0  802741   c3fb5 ./compiler/stage2/build/HscMain.o
  735605   23408       0  759013   b94e5 ./libraries/containers/dist-
 install/build/Data/Sequence.o
 }}}

 '''PlatformConstants.o''' is a very clear example of this problem. Trimmed
 down example of this file is:

 {{{#!hs
 module M (D) where
 data D = D { a0
 , a01 , a02 , a03 , a04 , a05 , a06 , a07 , a08 , a09 , a10
 , a11 , a12 , a13 , a14 , a15 , a16 , a17 , a18 , a19 , a20
 , a21 , a22 , a23 , a24 , a25 , a26 , a27 , a28 , a29 , a30
 , a31 , a32 , a33 , a34 , a35 , a36 , a37 , a38 , a39 , a40
 , a41 , a42 , a43 , a44 , a45 , a46 , a47 , a48 , a49 , a50
 , a51 , a52 , a53 , a54 , a55 , a56 , a57 , a58 , a59 , a60
 , a61 , a62 , a63 , a64 , a65 , a66 , a67 , a68 , a69 , a70
 , a71 , a72 , a73 , a74 , a75 , a76 , a77 , a78 , a79 , a80
 , a81 , a82 , a83 , a84 , a85 , a86 , a87 , a88 , a89 , a90
 , a91 , a92 , a93 , a94 , a95 , a96 , a97 , a98 , a99

  :: Int } deriving Read
 }}}

 Results in 800KB file:
 {{{
 $ ghc-stage2 -c -O1 -fforce-recomp M.hs -o M.o
 $ size M.o
    text    data     bss     dec     hex filename
  847039   16080       0  863119   d2b8f M.o
 }}}

 The size growth is quadratic:
 {{{
 # fields code-size
 1    6263
 21   61767
 41  173623
 61  347503
 81  583367
 101  881231
 121 1241087
 141 1662959
 161 2146815
 181 2692679
 201 3300543
 221 3970407
 241 4702263
 261 5496135
 281 6351991
 }}}

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