#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: 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: | -------------------------------------+------------------------------------- Changes (by mikhail.vorozhtsov): * Attachment "Regression.hs" added. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: 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 mikhail.vorozhtsov): The results of putting `NOINLINE` on `elemWitness`: {{{ $ time ~/Prefixes/ghc-7.10.3/bin/ghc -O -c -Rghc-timing TypeList.hs Regression.hs <> real 0m5.092s user 0m4.983s sys 0m0.097s $ time ~/Prefixes/ghc-8.0.1/bin/ghc -O -c -Rghc-timing TypeList.hs Regression.hs <> real 0m23.988s user 0m23.747s sys 0m0.190s }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining 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 mpickering): The interface file produced by both versions is absolutely huge (17mb). A very large number of coercions are generated by the instance declarations in Regression.hs. Interestingly, one way to improve the performance is marking `elemWitness` as inlinable.. This stops the unfoldings being optimised but it doesn't bring performance to the same level as omitting unfoldings completely. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining 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 mikhail.vorozhtsov): Here are some numbers from `-v4` logs: {{{ $ grep -E '(=====|^Result|coercions)' out-7_10.log | grep -v 'RHS size' | head -40 ==================== Parser ==================== ==================== Source Statistics ==================== ==================== Occurrence analysis ==================== ==================== Desugar (after optimization) ==================== Result size of Desugar (after optimization) = {terms: 2,144, types: 128,368, coercions: 415,496} ==================== Occurrence analysis ==================== Result size of Simplifier iteration=1 = {terms: 3,200, types: 173,424, coercions: 415,528} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 3,200, types: 173,424, coercions: 415,528} ==================== Specialise ==================== Result size of Specialise = {terms: 12,416, types: 658,320, coercions: 455,704} ==================== FloatOut stats: ==================== Result size of Float out(FOS {Lam = Just 0, = {terms: 13,472, types: 739,808, coercions: 455,704} ==================== Occurrence analysis ==================== Result size of Simplifier iteration=1 = {terms: 30,336, types: 1,848,096, coercions: 6,417,128} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 30,336, types: 1,848,096, coercions: 6,417,128} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 30,336, types: 1,848,096, coercions: 6,417,128} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 30,336, types: 1,848,096, coercions: 6,417,128} Result size of Float inwards = {terms: 30,336, types: 1,848,096, coercions: 6,417,128} ==================== Called arity analysis ==================== Result size of Called arity analysis = {terms: 30,336, types: 1,848,096, coercions: 6,417,128} ==================== Occurrence analysis ==================== }}} for 7.10.3 versus {{{ $ grep -E '(=====|^Result|coercions)' out-8_0.log | grep -v 'RHS size' | head -40 ==================== Parser ==================== ==================== Source Statistics ==================== ==================== Occurrence analysis ==================== ==================== Desugar (after optimization) ==================== Result size of Desugar (after optimization) = {terms: 3,835, types: 147,262, coercions: 549,848} ==================== Occurrence analysis ==================== Result size of Simplifier iteration=1 = {terms: 4,897, types: 161,681, coercions: 549,849} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 4,897, types: 161,681, coercions: 549,849} ==================== Specialise ==================== Result size of Specialise = {terms: 17,793, types: 899,977, coercions: 3,094,577} ==================== FloatOut stats: ==================== Result size of Float out(FOS {Lam = Just 0, = {terms: 20,769, types: 1,109,785, coercions: 3,094,577} ==================== Occurrence analysis ==================== Result size of Simplifier iteration=1 = {terms: 16,553, types: 871,953, coercions: 2,232,281} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 16,429, types: 864,761, coercions: 2,184,448} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 16,429, types: 864,761, coercions: 2,184,448} ==================== Occurrence analysis ==================== Result size of Simplifier iteration=1 = {terms: 87,357, types: 4,366,893, coercions: 10,008,352} ==================== Occurrence analysis ==================== Result size of Simplifier = {terms: 87,357, types: 4,366,893, coercions: 10,008,352} Result size of Float inwards = {terms: 87,357, types: 4,366,893, coercions: 10,008,352} ==================== Called arity analysis ==================== Result size of Called arity analysis = {terms: 87,357, types: 4,366,893, coercions: 10,008,352} ==================== Occurrence analysis ==================== }}} for 8.0.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: (none) mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining 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 RyanGlScott): A sizable chunk of the regression came from commit 6746549772c5cc0ac66c0fce562f297f4d4b80a2 (Add kind equalities to GHC.) {{{ Commit 6e56ac58a6905197412d58e32792a04a63b94d7e (Fix infix record field fixity (#11167 and #11173).) ----- $ time ghc4/inplace/bin/ghc-stage2 -fforce-recomp -O -c -Rghc-timing TypeList.hs Regression.hs <> real 0m12.829s user 0m12.688s sys 0m0.140s Commit 6746549772c5cc0ac66c0fce562f297f4d4b80a2 (Add kind equalities to GHC.) ----- $ time ghc4/inplace/bin/ghc-stage2 -fforce-recomp -O -c -Rghc-timing TypeList.hs Regression.hs <> real 0m34.744s user 0m34.572s sys 0m0.176s }}} But that's not the full story, since I get a realtime of `1m12.849s` with GHC 8.0.1. I'll try to figure out what other commit(s) are contributing. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: (none) mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining 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: | -------------------------------------+------------------------------------- Changes (by nh2): * cc: nh2 (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: (none) mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining 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 simonpj): See [https://mail.haskell.org/pipermail/ghc-devs/2017-May/014277.html this ghc-devs thread], and [https://mail.haskell.org/pipermail/ghc- devs/2017-June/014278.html this one]. There seem to be several issues: * Why does the small change identified by Ryan have such a huge effect? We need insight. * The change that Richard made to `CoreOpt.simple_opt_expr` actually fixed an outright bug. But it's ''still'' wrong now. See Trac #13798. * The fuss that is caused by this `map/coerce` rule is out of all proportion to its importance. We should think of a better way. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: (none) mikhail.vorozhtsov | Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining 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 RyanGlScott): Well hot dang. It turns out that commit 2b74bd9d8b4c6b20f3e8d9ada12e7db645cc3c19 (Stop the specialiser generating loopy code) is once again responsible for fixing the problem! {{{ Commit 92a4f908f2599150bec0530d688997f03780646e (Spelling typos) <> real 0m59.150s user 0m59.020s sys 0m0.224s Commit 2b74bd9d8b4c6b20f3e8d9ada12e7db645cc3c19 (Stop the specialiser generating loopy code) <> real 0m4.549s user 0m4.440s sys 0m0.096s }}} For reference, the time for GHC 7.10.3 was: {{{ <> real 0m13.477s user 0m13.128s sys 0m0.104s }}} So now it's even //better// than it used to be! That's pretty cool. I don't have any particular insight as to why that commit made things so much better, but sure enough, `TypeList.hs` contains some classes with significant superclasses: {{{#!hs class (FindElem 'HeadElem a l ~ 'Elem p) => ElemAt p (a :: k) (l :: [k]) where elemWitness :: Proxy a -> Proxy l -> ElemWitness p a l class IsElem t (ElemsOf a) => ElemOf a t where }}} So it's entirely possible that their corresponding dictionaries are just getting optimized better. It would be great to have someone verify this at the Core level. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: (none) mikhail.vorozhtsov | Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3632 Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * status: new => patch * differential: => Phab:D3632 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#12545: Compilation time/space regression in GHC 8.0/8.1 (search in type-level lists and -O) -------------------------------------+------------------------------------- Reporter: | Owner: (none) mikhail.vorozhtsov | Type: bug | Status: closed Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/compiler/T12545 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3632 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => closed * testcase: => perf/compiler/T12545 * resolution: => fixed * milestone: => 8.2.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12545#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler