#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by goldfire): * priority: normal => highest * version: 7.10.2 => 7.11 * milestone: => 8.0.1 Old description:

This ticket is to track the handful of performance regressions seen with the addition of `TypeInType`. It is quite possibly a good idea to break these out into separate tickets, but until we investigate, they're all bundled here.

The regressions are: * T3064, bytes allocated up by 14.9%

(will update description)

New description: This ticket is to track the handful of performance regressions seen with the addition of `TypeInType`. It is quite possibly a good idea to break these out into separate tickets, but until we investigate, they're all bundled here. The regressions are: * T3064, bytes allocated up by 14.9% * T5030, up by 61.8% * T5837, up by 13% * T5321Fun, up by 11% * T5631, up by 39% * T9872d, '''down''' by 91.8% (see below) * T9872a, up by 33.6% * T9872c, up by 59.4% * T9872b, up by 49.4% * T9675, up by 29.7%, and peak megabytes allocated up by 28.4% * haddock.base, up by 12.4% * haddock.Cabal, up by 9.5% I did add an optimization around type family reduction (the function `zonk_eq_types` in !TcCanonical) that could cause such a drastic reduction. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Richard Eisenberg ): In [changeset:"6746549772c5cc0ac66c0fce562f297f4d4b80a2/ghc" 67465497/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="6746549772c5cc0ac66c0fce562f297f4d4b80a2" Add kind equalities to GHC. This implements the ideas originally put forward in "System FC with Explicit Kind Equality" (ICFP'13). There are several noteworthy changes with this patch: * We now have casts in types. These change the kind of a type. See new constructor `CastTy`. * All types and all constructors can be promoted. This includes GADT constructors. GADT pattern matches take place in type family equations. In Core, types can now be applied to coercions via the `CoercionTy` constructor. * Coercions can now be heterogeneous, relating types of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2` proves both that `t1` and `t2` are the same and also that `k1` and `k2` are the same. * The `Coercion` type has been significantly enhanced. The documentation in `docs/core-spec/core-spec.pdf` reflects the new reality. * The type of `*` is now `*`. No more `BOX`. * Users can write explicit kind variables in their code, anywhere they can write type variables. For backward compatibility, automatic inference of kind-variable binding is still permitted. * The new extension `TypeInType` turns on the new user-facing features. * Type families and synonyms are now promoted to kinds. This causes trouble with parsing `*`, leading to the somewhat awkward new `HsAppsTy` constructor for `HsType`. This is dispatched with in the renamer, where the kind `*` can be told apart from a type-level multiplication operator. Without `-XTypeInType` the old behavior persists. With `-XTypeInType`, you need to import `Data.Kind` to get `*`, also known as `Type`. * The kind-checking algorithms in TcHsType have been significantly rewritten to allow for enhanced kinds. * The new features are still quite experimental and may be in flux. * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203. * TODO: Update user manual. Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142. Updates Haddock submodule. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => TypeInType -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: goldfire Type: bug | Status: new Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Richard, this is marked as "highest" priority for 8.0.1 Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: highest | Milestone: 8.0.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by goldfire): * owner: goldfire => Comment: I'm afraid I have to declare defeat against this ticket. :( I've spent the better part of the last few days trying to understand what's going on here, but failed utterly. I simply cannot find the source of the slowdown. It just seems like ''everything'' is doing more allocation, making it rather hard to find a culprit. I tried putting SCCs on low-level functions, too, but to no avail. The one moment of glory was finding that `tcMatchTys` was taking up 25% of the allocations on T9872c. I identified that the cause was a check to make sure that we don't match with a local, forall-bound variable. Of course, local forall-bound variables are rare, so I optimized the check by seeing if there are any forall-bound variables. This led to a whopping improvement of 20%! But then, inexplicably, when I turn off profiling, the exact same optimization led to no improvement. My tinkering led to a few tiny optimizations, leading to 5% reduction in two test cases. This is a small victory, but doesn't really undo the sting of defeat. (Optimizations to land in the next day or so.) My best guess is that the extra variables due to runtime polymorphism are what's gumming up the works. Previously, every binder without a type signature (including all local ones) were given a type `alpha :: OpenKind`. Now, every binder is given `alpha :: TYPE rho`; two metavariables where there was once one. And even when the type is solved, the kind now takes up more space than it did previously. But I have no data to back this up. I'm very happy to advise someone who wants to take this on. As usual with performance problems, the devil is in the data collecting and pinpointing -- the fix (if there is one) is usually quite easy. But I'm sad to say that I'm formally giving up on this one. I have simply timed out if I am to graduate. I will say that I don't believe this ticket needs to be a release blocker. * T5631 still is worse by 30% in bytes allocated. This is a happy- generated file with lots of mutually-recursive functions with no type signatures, exactly the pathological case for representation polymorphism. I doubt we can bring this one back to 7.10 levels. * T5837 is off from before `TypeInType`. But it's still better than 7.10 was! * T9675 has regressed in peak memory usage, but not allocations. This one doesn't seem to be representation polymorphism. But I couldn't nail it. * T9872 is an utter abuse of type families and looks nothing like a typical Haskell program. And those are the only cases that are worse than before `TypeInType`. Work between when this ticket was posted and now cleared up the others. I'll leave it to someone else to agree with me that this needn't be a release blocker before changing the priority. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: high | Milestone: 8.0.2 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I just thought of a way to make forward progress on here: I still have the very long and very tortuous commit history of my development of `TypeInType`. (It's at [https://github.com/goldfirere/ghc/tree/nokinds the nokinds branch of my github fork].) Someone (including perhaps a future me) could just bisect. This would be complicated by the fact that many commits in there do not compile. But git's bisect mechanism has a way of dealing with that (`git bisect skip`). So this process would be quite long, but it also seems quite likely to lead to a solution. Unlike my previous attempts. If anyone has written a script for use with `git bisect run` that might aid in this process, do post! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: high | Milestone: 8.0.2 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Richard Eisenberg ): In [changeset:"0706a103ae8c9c61e6bbaadd16b32da76aa5a749/ghc" 0706a103/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="0706a103ae8c9c61e6bbaadd16b32da76aa5a749" Add two small optimizations. (#11196) - Optimize zonking * to avoid allocation. - Try to avoid looking at the free variables of a type in the pure unifier. We need look at the variables only in the case of a forall. The performance results updates included in this also include a regression, but the regression is not due to this patch. When validating previous patches, the test case failed, but I was unable to reproduce outside of validation, so I let it go by, thinking the failure was spurious. Upon closer inspection, the perf number was right at the line, and the wibble between a valiation environment and a regular test run was enough to make the difference. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

With the forthcoming support for pattern synonyms in TH (not for 8.0! but likely for 8.2) Given how quickly osa1 seems to be moving on unboxed sums it's entirely

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: high | Milestone: 8.0.2 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): possible that we will have proper unpacking by 8.2 (at least I have my fingers crossed). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: bug | Status: new Priority: high | Milestone: 8.0.2 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType 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 bgamari): For the record, `FunTy` was reintroduced by 77bb09270c70455bbd547470c4e995707d19f37d. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType 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 bgamari): * milestone: 8.2.1 => 8.4.1 Comment: It seems unlikely that anything will happen on this for 8.2. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11196: TypeInType performance regressions -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 7.11 Resolution: | Keywords: TypeInType 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 bgamari): I have not. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11196#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler