Deriving Read instance from datatype with N fields leads to N^2 code size growth
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:
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
Trac metadata
Trac field | Value |
---|---|
Version | 7.10.2 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |