#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Compile- | Blocked By: time performance bug | Related Tickets: #9583 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dreixel): What makes you think it's due to Generics? Not much changed there since 7.8... -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 7.10.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Compile- | Blocked By: time performance bug | Related Tickets: #9583 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by hvr): * priority: normal => high Comment: increasing priority, as Phab:D183 has landed and therefore is starting to affect buildbots and developers working on GHC HEAD -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 7.10.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Compile- | Blocked By: time performance bug | Related Tickets: #9583 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dreixel): I'm happy to investigate the problem, but it will take a few days, so we might need some temporary workaround. In fact, I can't even build HEAD at the moment (my VM runs out of memory), because of this. Can the Binary instances be disabled in Cabal for a while? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 7.10.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Compile- | Blocked By: time performance bug | Related Tickets: #9583 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): Might it be worth leaving a few comments in the `GBInary` class to highlight that innocently inlining those methods is dangerous? And we still don't really understand why, I think. `gget` looks as if it has lots of cpp-generated code, but the others look small. Unless the things they call are in turn INLINE. So, a good fix, but it might be worth more investigation to figure out the best way to solve this in the end. I think Pedro's goal was to eliminate all the intermediate structure. Simon -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 7.12.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583 | Differential Revisions: -------------------------------------+------------------------------------- Comment (by darchon): I have another data-point for this performance bug: http://hackage.haskell.org/package/unbound-generics. Compiling the following example: https://github.com/lambdageek/unbound- generics/blob/master/examples/F.hs {{{ $ uname -a Darwin wlan022084.mobiel.utwente.nl 14.1.0 Darwin Kernel Version 14.1.0: Thu Feb 26 19:26:47 PST 2015; root:xnu-2782.10.73~1/RELEASE_X86_64 x86_64 ############################################################################# $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.8.4 $ ghc -O -c -Rghc-timing -fforce-recomp -Wnot F.hs <<ghc: 1721650904 bytes, 3317 GCs, 16624472/43436104 avg/max bytes residency (12 samples), 112M in use, 0.00 INIT (0.00 elapsed), 1.85 MUT (2.22 elapsed), 1.52 GC (2.03 elapsed) :ghc>> ############################################################################# $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.10.0.20150323 $ ghc -O -c -Rghc-timing -fforce-recomp -Wnot F.hs <<ghc: 13422435616 bytes, 21356 GCs, 46569528/80396192 avg/max bytes residency (25 samples), 221M in use, 0.000 INIT (0.001 elapsed), 11.911 MUT (12.895 elapsed), 10.298 GC (10.973 elapsed) :ghc>> }}} The interesting parts of running with -v2 are: {{{ $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.8.4 $ ghc -O -c -Rghc-timing -fforce-recomp -Wnot -v2 F.hs [...] Result size of Simplifier = {terms: 2,583, types: 8,513, coercions: 1,371} *** Specialise: Result size of Specialise = {terms: 2,583, types: 8,513, coercions: 1,371} *** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}): Result size of Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}) = {terms: 2,923, types: 9,081, coercions: 1,371} *** Float inwards: Result size of Float inwards = {terms: 2,923, types: 9,081, coercions: 1,371} *** Simplifier: Result size of Simplifier iteration=1 = {terms: 6,490, types: 31,862, coercions: 17,447} [...] ############################################################################# $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.10.0.20150323 $ ghc -O -c -Rghc-timing -fforce-recomp -Wnot -v2 F.hs [...] Result size of Simplifier = {terms: 2,028, types: 5,759, coercions: 1,207} *** Specialise: Result size of Specialise = {terms: 11,945, types: 48,810, coercions: 9,282} *** Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = False}): Result size of Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = False}) = {terms: 14,293, types: 68,412, coercions: 9,282} *** Simplifier: Result size of Simplifier iteration=1 = {terms: 22,244, types: 103,329, coercions: 35,450} [...] }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 7.12.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583 | Differential Revisions: -------------------------------------+------------------------------------- Comment (by goldfire): Here is some relevant data (thanks to Michal Terepeta). These numbers were gotten while compiling haskell-src-exts: (I'm choosing the `-fno-call-arity` results here for better comparison against 7.8, which lacked the `-fcall-arity` feature.) {{{ ** HEAD with -fno-call-arity Sun Apr 12 18:16 2015 Time and Allocation Profiling Report (Final) ghc +RTS -p -RTS [...] -fno-call-arity total time = 113.71 secs (113714 ticks @ 1000 us, 1 processor) total alloc = 121,884,896,720 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc SimplTopBinds SimplCore 37.2 36.6 CoreTidy HscMain 6.0 7.3 lintAnnots CoreLint 5.8 6.5 pprNativeCode AsmCodeGen 4.1 4.8 OccAnal SimplCore 3.6 3.8 occAnalBind.assoc OccurAnal 2.9 3.2 StgCmm HscMain 2.9 2.6 RegAlloc AsmCodeGen 2.6 3.4 FloatOutwards SimplCore 2.6 2.3 regLiveness AsmCodeGen 2.5 2.8 tc_rn_src_decls TcRnDriver 2.4 1.9 Simplify SimplCore 2.4 0.3 sink CmmPipeline 2.1 2.2 NewStranal SimplCore 1.7 2.1 genMachCode AsmCodeGen 1.4 1.4 layoutStack CmmPipeline 1.4 1.4 NativeCodeGen CodeOutput 1.1 1.2 FloatInwards SimplCore 1.1 1.4 do_block Hoopl.Dataflow 1.0 0.6 Digraph.scc Digraph 0.8 1.3 }}} {{{ ** 7.8.4 Sun Apr 12 15:41 2015 Time and Allocation Profiling Report (Final) ghc +RTS -p -RTS [...] total time = 93.11 secs (93112 ticks @ 1000 us, 1 processor) total alloc = 103,135,975,120 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc SimplTopBinds SimplCore 38.5 37.4 pprNativeCode AsmCodeGen 6.2 7.2 StgCmm HscMain 3.9 4.2 RegAlloc AsmCodeGen 3.7 5.1 occAnalBind.assoc OccurAnal 3.3 3.6 OccAnal SimplCore 3.3 3.6 regLiveness AsmCodeGen 3.1 3.4 FloatOutwards SimplCore 2.9 2.4 sink CmmPipeline 2.8 2.8 Simplify SimplCore 2.6 0.3 tc_rn_src_decls TcRnDriver 2.4 2.1 genMachCode AsmCodeGen 1.9 2.0 NewStranal SimplCore 1.8 2.1 layoutStack CmmPipeline 1.8 1.8 Core2Core HscMain 1.3 1.2 deSugar HscMain 1.1 1.1 do_block Hoopl.Dataflow 1.1 0.7 CoreTidy HscMain 1.0 1.1 CorePrep HscMain 1.0 1.1 Digraph.scc Digraph 0.9 1.5 versioninfo MkIface 0.9 1.0 zonkEvBndr_zonkTcTypeToType TcHsSyn 0.6 1.4 }}} HEAD with `-fno-specialise` and `-fno-call-arity`: {{{ ghc +RTS -p -RTS [...] -fno-specialise -fno-call-arity total time = 89.93 secs (89928 ticks @ 1000 us, 1 processor) total alloc = 93,495,685,792 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc SimplTopBinds SimplCore 38.7 38.6 pprNativeCode AsmCodeGen 5.1 5.9 StgCmm HscMain 3.7 3.3 occAnalBind.assoc OccurAnal 3.2 3.6 OccAnal SimplCore 3.2 3.6 tc_rn_src_decls TcRnDriver 3.1 2.5 RegAlloc AsmCodeGen 3.1 4.2 regLiveness AsmCodeGen 3.0 3.5 FloatOutwards SimplCore 2.7 2.4 sink CmmPipeline 2.6 2.7 Simplify SimplCore 2.5 0.1 NewStranal SimplCore 1.9 2.3 genMachCode AsmCodeGen 1.8 1.7 layoutStack CmmPipeline 1.6 1.7 NativeCodeGen CodeOutput 1.4 1.5 FloatInwards SimplCore 1.2 1.6 CoreTidy HscMain 1.2 1.2 deSugar HscMain 1.2 1.2 do_block Hoopl.Dataflow 1.1 0.7 CorePrep HscMain 1.0 1.1 versioninfo MkIface 0.9 1.0 Parser HscMain 0.9 1.2 Digraph.scc Digraph 0.9 1.5 canEvVar TcCanonical 0.7 1.0 }}} And now with only `-fno-specialise`: {{{ ghc +RTS -p -RTS [...] -fno-specialise total time = 109.78 secs (109784 ticks @ 1000 us, 1 processor) total alloc = 124,469,615,048 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc SimplTopBinds SimplCore 35.4 32.4 CallArity SimplCore 13.4 20.7 pprNativeCode AsmCodeGen 4.1 4.5 OccAnal SimplCore 3.1 3.1 StgCmm HscMain 3.0 2.5 occAnalBind.assoc OccurAnal 3.0 3.1 RegAlloc AsmCodeGen 2.6 3.2 tc_rn_src_decls TcRnDriver 2.5 1.8 regLiveness AsmCodeGen 2.4 2.6 Simplify SimplCore 2.3 0.1 FloatOutwards SimplCore 2.3 1.8 sink CmmPipeline 2.2 2.0 genMachCode AsmCodeGen 1.5 1.3 NewStranal SimplCore 1.5 1.7 layoutStack CmmPipeline 1.3 1.3 NativeCodeGen CodeOutput 1.2 1.1 FloatInwards SimplCore 1.0 1.2 Digraph.scc Digraph 0.8 1.2 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 7.12.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293 | Differential Revisions: -------------------------------------+------------------------------------- Comment (by goldfire): Michal describes how he got the numbers pasted in comment:12: build GHC HEAD/7.8.4 with build flavor `prof` then get the haskell-src- exts sources, install the dependencies and finally add `+RTS -p -RTS` to the cabal file and compile it, the resulting `ghc.prof` contains the profiling information. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:14> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 7.12.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293 | Differential Revisions: -------------------------------------+------------------------------------- Changes (by gidyn): * cc: gidyn (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:16> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 8.0.1 Component: Compiler | Version: 7.9 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: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by ezyang): * keywords: => deriving-perf -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:19> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 8.0.1 Component: Compiler | Version: 7.9 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: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ezyang): I did some investigation related to this bug on GHC 7.10.3-ish and binary 0.7.5.0 (yes it's old, but I didn't see any more recent relevant commits; and it's what GHC is bootstrapping with). Here are some partial findings: 1. I can trigger bad constant factors this data type: {{{ {-# LANGUAGE DeriveGeneric #-} module A where import Data.Binary import GHC.Generics data T = T () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () deriving Generic instance Binary T }}} {{{ ezyang@sabre:~/Dev/labs$ time $DEV/ghc-7.10-frontend-plugins/usr/bin/ghc --make Bin.hs -O2 -fforce-recomp -fliberate-case-threshold=1000 [1 of 1] Compiling A ( Bin.hs, Bin.o ) real 0m7.369s user 0m6.408s sys 0m0.224s ezyang@sabre:~/Dev/labs$ time $DEV/ghc-7.10-frontend-plugins/usr/bin/ghc --make Bin.hs -O0 -fforce-recomp -fliberate-case-threshold=1000 [1 of 1] Compiling A ( Bin.hs, Bin.o ) real 0m0.881s user 0m0.776s sys 0m0.080s }}} 2. The problem gets worse if you have explicit field names, something like a x2 factor. {{{ data T = T () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () () deriving Generic -- versus data T = T { f0 :: (), f1 :: (), f2 :: (), f3 :: (), f4 :: (), f5 :: (), f6 :: (), f7 :: (), f8 :: (), f9 :: (), f10 :: (), f11 :: (), f12 :: (), f13 :: (), f14 :: (), f15 :: (), f16 :: (), f17 :: (), f18 :: (), f19 :: (), f20 :: (), f21 :: (), f22 :: (), f23 :: (), f24 :: (), f25 :: (), f26 :: (), f27 :: (), f28 :: (), f29 :: (), f30 :: (), f31 :: (), f32 :: (), f33 :: (), f34 :: (), f35 :: (), f36 :: (), f37 :: (), f38 :: (), f39 :: () } deriving (Generic) }}} {{{ ezyang@sabre:~/Dev/labs$ time $DEV/ghc-7.10-frontend-plugins/usr/bin/ghc --make Bin.hs -O -fforce-recomp -fliberate-case-threshold=1000 [1 of 1] Compiling A ( Bin.hs, Bin.o ) real 0m2.649s user 0m2.520s sys 0m0.080s ezyang@sabre:~/Dev/labs$ time $DEV/ghc-7.10-frontend-plugins/usr/bin/ghc --make Bin.hs -O -fforce-recomp -fliberate-case-threshold=1000 [1 of 1] Compiling A ( Bin.hs, Bin.o ) real 0m4.990s user 0m4.824s sys 0m0.144s }}} It's NOT just generic deriving; the generic deriving is still pretty speedy, honestly. 3. If you inline all of Binary's class definitions into the same file, things speed up. Comparing the two cases, it seems that when we cross- module compile, GHC does more inlining and more optimization, and it takes longer. This is something like a 30% factor. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:21> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: new Priority: high | Milestone: 8.0.1 Component: Compiler | Version: 7.9 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: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ezyang): I managed to massively speed up Binary by applying (3). So I think we have our culprit. Here's the PR: https://github.com/kolmodin/binary/pull/95 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:23> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: patch Priority: high | Milestone: 8.0.1 Component: Compiler | Version: 7.9 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: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Thank you for helping to characterise this. More please! Eg is it the type checker, or all the way down the pipeline? Do terms get big? Why does putting Binary's classes in the file help? Why does removing `not- used` help. One possible reason: see [http://research.microsoft.com/en- us/um/people/simonpj/papers/variant-f/index.htm Scrap your type applications] Section 2.3. Generics, I suspect, uses lots of nested types! -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:25> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: simonpj Type: bug | Status: patch Priority: high | Milestone: 8.0.1 Component: Compiler | Version: 7.9 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: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ezyang): Yes, comment:22 gives a standalone case of how making a type class only have one method improves time. I can try to characterize this further. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:27> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: 8.0.1 => 8.2.1 Comment: Punting to 8.2. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:30> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by michalt): * cc: michalt (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:32> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by thoughtpolice): Just as an aside, I also applied the trick from comment:23 to cereal, and the results were almost unbelievable. The example given (comment:22) actually completely exhausts the simplifier tickets, so it essentially turns a non-compiling program into a compiling one that works in less than a second. https://github.com/GaloisInc/cereal/commit/94c87592d010fdb381c6a2dc963bbfcef... The result on the `binary-serialise-cbor` suite with this change is incredible. Just another data point - it would be useful to minimize `cereal` akin to `binary` in comment:22 and see the difference. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:34> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonmar): In case any more motivation is needed here: we have had to stop using `deriving Generic` and find alternative methods due to this problem, so it's an actual blocker for some use cases of `deriving Generic`. Do we know what the problem is? Is it fixable? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:36> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: 8.2.1 => 8.4.1 Comment: Sadly we seem to have lost steam on this. Bumping off to 8.4. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:38> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: dfeuer (added) * related: #9583, #10293, #13059 => #9583, #10293, #13059, #10818 Comment: It appears that much or all of the regression in the original example occurred in b9e49d3e9580e13d89efd1f779cb76f610e0d6e0. Before, I get {{{ dfeuer@squirrel:~/src/cabal> ~/src/ghc-iproute-before/inplace/bin/ghc- stage2 -Rghc-timing -O -c Cabal/Language/Haskell/Extension.hs <<ghc: 5795390224 bytes, 640 GCs, 37133197/104324936 avg/max bytes residency (16 samples), 248M in use, 0.001 INIT (0.001 elapsed), 3.981 MUT (4.258 elapsed), 2.622 GC (2.639 elapsed) :ghc>> }}} After, {{{ dfeuer@squirrel:~/src/cabal> ~/src/ghc-iproute-after/inplace/bin/ghc- stage2 -Rghc-timing -O -c Cabal/Language/Haskell/Extension.hs <<ghc: 126972407680 bytes, 3337 GCs, 340164097/914871104 avg/max bytes residency (36 samples), 2652M in use, 0.001 INIT (0.001 elapsed), 82.951 MUT (118.315 elapsed), 52.254 GC (52.317 elapsed) :ghc>> }}} Jeepers! -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:40> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):

1024 specialization rules to -ddump-rules for this module.

Really? I compiled the module in comment:22 with HEAD and got no rules at all! What am I doing wrong? {{{ Result size of Tidy Core = {terms: 2,582, types: 63,214, coercions: 20,656, joins: 0/34} }}} Simon -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:42> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): OK, so is there now a regression wrt 7.8 or not? If not let's close. If so, let's investigate. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:44> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * owner: (none) => dfeuer Comment: How is this going, David? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:46> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): I think the original issue is fixed. To be extra clear, the original issue was that it was very slow to compile `Language.Haskell.Extension` from `Cabal`. I was able to reproduce this using Cabal at commit [https://github.com/haskell/cabal/commit/eaf2aae18603965ff668384b391fcaa14de1... eaf2aae18603965ff668384b391fcaa14de19823]. The problem there appeared in GHC commit b9e49d3e9580e13d89efd1f779cb76f610e0d6e0, which added 1024 specialization rules for said module. The problem is now gone. It looks to me as though ezyang's test case in comment:22 doesn't actually relate to the regression; I don't see it moving terribly much from 7.8 to 7.10 or from 7.10 to 8.2. It seems to be looking at other issues. I will try to see how those have shifted. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:48> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): OK, so we conclude that the original problem is now fixed? (Albeit we don't quite know how.) If so, great; but let's add a regression test. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:50> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):

Are we hoping to be able to reintroduce the inlines and merge the classes?

Well, the original Description says that compiling Cabal with GHC 8.0 was 26x slower than compiling with GHC 7.8. That's a big difference. How long does it take to compile (the same) Cabal with GHC 8.2? That's the question at hand. If it's still 26x slower (and your comment suggests that it is, albeit maybe not 26x), I'd love to dig a bit into why. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:52> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Nope, nope, nope. Actually, there still seems to be a problem, but I think it's been masked by the early inline patch. Specifically, ''removing'' the `INLINE`s makes the merged class problematic. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:54> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Here's a truly bare-bones, Haskell 98 reproduction: {{{#!hs module Duh where class Duh a where duh :: Integer -> a noDuh :: a -> Integer class GenDuh a where gduh :: Integer -> a gnoDuh :: a -> Integer instance GenDuh () where gduh = const () gnoDuh = const 1 instance GenDuh a => GenDuh (Maybe a) where gduh 0 = Nothing gduh n = Just (gduh (n - 1)) gnoDuh Nothing = 0 gnoDuh (Just x) = 1 + gnoDuh x data T = T (Maybe (Maybe ())) instance Duh T where duh i = T (gduh i) noDuh (T m) = gnoDuh m }}} GHC 8.2.1rc2 with `-O2 -ddump-ds` produces {{{ -- RHS size: {terms: 13, types: 18, coercions: 0, joins: 0/2} $cnoDuh_aRo :: T -> Integer [LclId] $cnoDuh_aRo = let { $dGenDuh_a2nn :: GenDuh (Maybe ()) [LclId] $dGenDuh_a2nn = Duh.$fGenDuhMaybe @ () Duh.$fGenDuh() } in let { $dGenDuh_aRs :: GenDuh (Maybe (Maybe ())) [LclId] $dGenDuh_aRs = Duh.$fGenDuhMaybe @ (Maybe ()) $dGenDuh_a2nn } in \ (ds_d2ow :: T) -> case ds_d2ow of { T m_azN -> gnoDuh @ (Maybe (Maybe ())) $dGenDuh_aRs m_azN } -- RHS size: {terms: 11, types: 14, coercions: 0, joins: 0/2} $cduh_aRi :: Integer -> T [LclId] $cduh_aRi = let { $dGenDuh_a2nl :: GenDuh (Maybe ()) [LclId] $dGenDuh_a2nl = Duh.$fGenDuhMaybe @ () Duh.$fGenDuh() } in let { $dGenDuh_aRm :: GenDuh (Maybe (Maybe ())) [LclId] $dGenDuh_aRm = Duh.$fGenDuhMaybe @ (Maybe ()) $dGenDuh_a2nl } in \ (i_azM :: Integer) -> Duh.T (gduh @ (Maybe (Maybe ())) $dGenDuh_aRm i_azM) }}} We solve the `GenDuh (Maybe (Maybe ()))` constraint twice, and build its dictionary twice. I'll attach `-ddump-tc-trace`. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:56> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * Attachment "tracecsduh" added. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by RyanGlScott): I've confirmed this as well. Before that commit, this is the `-ddump-ds` output: {{{ $cnoDuh_axu :: T -> Integer [LclId, Str=DmdType] $cnoDuh_axu = \ (ds_dTM :: T) -> case ds_dTM of _ [Occ=Dead] { T m_avB -> gnoDuh @ (Maybe (Maybe ())) $dGenDuh_axt m_avB } $cduh_axo :: Integer -> T [LclId, Str=DmdType] $cduh_axo = \ (i_avA :: Integer) -> Duh.T (gduh @ (Maybe (Maybe ())) $dGenDuh_axt i_avA) }}} But after that commit: {{{ $cnoDuh_axw :: T -> Integer [LclId, Str=DmdType] $cnoDuh_axw = let { $dGenDuh_aNk :: GenDuh (Maybe ()) [LclId, Str=DmdType] $dGenDuh_aNk = Duh.$fGenDuhMaybe @ () Duh.$fGenDuh() } in let { $dGenDuh_axC :: GenDuh (Maybe (Maybe ())) [LclId, Str=DmdType] $dGenDuh_axC = Duh.$fGenDuhMaybe @ (Maybe ()) $dGenDuh_aNk } in \ (ds_dTV :: T) -> case ds_dTV of _ [Occ=Dead] { T m_avB -> gnoDuh @ (Maybe (Maybe ())) $dGenDuh_axC m_avB } $cduh_axp :: Integer -> T [LclId, Str=DmdType] $cduh_axp = let { $dGenDuh_aNi :: GenDuh (Maybe ()) [LclId, Str=DmdType] $dGenDuh_aNi = Duh.$fGenDuhMaybe @ () Duh.$fGenDuh() } in let { $dGenDuh_axv :: GenDuh (Maybe (Maybe ())) [LclId, Str=DmdType] $dGenDuh_axv = Duh.$fGenDuhMaybe @ (Maybe ()) $dGenDuh_aNi } in \ (i_avA :: Integer) -> Duh.T (gduh @ (Maybe (Maybe ())) $dGenDuh_axv i_avA) }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:58> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:59 simonpj]:

I can see that you get two copies of the same code, which CSE will presumably get rid of. That might be worth trying to fix.

But why does it lead to a 26x increase in compilation time? I'd expect it to be un-noticeable.

Well, it's not always going to cause serious problems, and I think this ticket touches several underlying issues, but it bet it ''can'' cause serious trouble. Suppose you have a class with ten methods, and use generic defaults. Now you'll end up with ten dictionaries of ten methods each. Depending on how inlining goes, I suspect that could be quite bad. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:60> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Hmmmm... While 2b74bd9d8b4c6b20f3e8d9ada12e7db645cc3c19 seems to improve matters considerably, it doesn't fix the whole issue. ezyang's reproduction in comment:22 can be modified to make things blow up after the commit, and as far back as 7.8 at least. Specifically: * Increase the size of the definition of `T`, leaving it in the `Gen` module. * Move the definition of `tput` to a separate `GenSpec` module. This will lead to simplifier tick exhaustion. If the definition of `T` (or even just the derivation of `Generic T`) is moved to `GenSpec`, then compilation succeeds. The number of terms seems to blow up several simplifier passes after specialization. I don't yet know why, but it smells like inlining. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:62> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): Phab:D3656 #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * differential: => Phab:D3656 Comment: I've added a test demonstrating improvement from the specializer change. It's not as precise as I'd like. A variation (moving the definition of `T` into the `T9630a` module while leaving the specialization in `T9630`) has more dramatic effects, with simplifier tick exhaustion in the older GHC. But as mentioned, a similar modification of Edward's test case does ''not'' see any improvement. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:64> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler

#9630: compile-time performance regression (probably due to Generics) -------------------------------------+------------------------------------- Reporter: hvr | Owner: dfeuer Type: bug | Status: closed Priority: high | Milestone: 8.2.1 Component: Compiler | Version: 7.9 Resolution: fixed | Keywords: deriving- | perf, Generics Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9583, #10293, | Differential Rev(s): Phab:D3656 #13059, #10818 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: new => closed * resolution: => fixed Comment: As the regression ''seems'' to be fixed, I've opened #13993 to address the longer-standing issue and am closing this ticket. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9630#comment:66> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler