#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by simonpj): * cc: goldfire, cactus, dimitris@… (added) Old description:

Gergo reports, prompted by [http://stackoverflow.com/questions/26538595/more-efficient-type-level- computations-using-type-families this question on Stack Overflow].

I wrote some code today using closed type families and datakinds. Also, as a baseline, I typechecked the code using open type families from the original question.

The two files are attached as slow1.hs and slow2.hs below.

On GHC 7.8.3, typechecking took about 45 seconds for each. However, on a 'perf' build of GHC 7.9 d8c437b3, with ghc-stage2, the first one took 1m3s and the second one 1m12s. A 40% and 60% increase in typechecking time, respectively!

Is this some known regression, something surprising, or is 'perf' simply not the right build flavour for this kind of comparison?

New description: Gergo reports, prompted by [http://stackoverflow.com/questions/26538595 /more-efficient-type-level-computations-using-type-families this question on Stack Overflow]. I wrote some code today using closed type families and datakinds. Also, as a baseline, I typechecked the code using open type families from the original question. The two files are attached as slow1.hs and slow2.hs below. On GHC 7.8.3, typechecking took about 45 seconds for each. However, on a 'perf' build of GHC 7.9 d8c437b3, with ghc-stage2, the first one took 1m3s and the second one 1m12s. A 40% and 60% increase in typechecking time, respectively! Is this some known regression, something surprising, or is 'perf' simply not the right build flavour for this kind of comparison? -- Comment: Very helpful examples. Working on them. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by goldfire): This all begs a question I've wondered several times: Flattening in the solver is great when we have bits of a type that are unknown, like `F (Int, a)`. But, it seems like an awful lot of work to do when a type is fully known, such as `F Bool`. In the latter case, is there a reason we don't use `normaliseType`? It would seem to me that this all would get more efficient if we just called `normaliseType` as an early step in the process, say in `flattenFamApp`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"37c2ed4bc3d4ff0a4681e9d27c7f748886e413f6/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="37c2ed4bc3d4ff0a4681e9d27c7f748886e413f6" Optimise partitionFunEqs for the 'false' case In the examples from Trac #9872 we were getting a large set of inert CFunEqCans, and partitioning them was taking ages. This patch improves it somewhat by optimising the partition for the case where the predicat is false. The ticket has more info. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by goldfire): Recall that `normaliseType` does "deep" normalisation, not just at top level -- it recursively tries to normalise all arguments. And, I don't think it would take long for it to try. If `normaliseType` doesn't remove a top-level type function, then flatten as normal, but it's still possible some good progress was made below top level. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"13b0b460d365828c7d41b39d2ce7d5bbe4c69f98/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="13b0b460d365828c7d41b39d2ce7d5bbe4c69f98" Reorganise the work list, so that flattening goals are treated in the right order Trac #9872 showed the importance of processing goals in depth-first, so that we do not build up a huge pool of suspended function calls, waiting for their children to fire. There is a detailed explanation in Note [The flattening work list] in TcFlatten The effect for Trac #9872 (slow1.hs) is dramatic. We go from too long to wait down to 28Gbyte allocation. GHC 7.8.3 did 116Gbyte allocation! }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by simonpj): * status: new => closed * resolution: => fixed Comment: Actually with the other changes I've made in the last day or two, allocation in HEAD for T9872a is down to 5.5Gbytes. Thanks for these examples, Gergo. I claim victory. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): yes, both tests are in commit fca85c9b1617417a6170f3591a29d1fe36d35da5/ghc -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): Oh ok. Do you think it's significantly different? Or just different? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"7256213843b80d75a86f033be77516a62d56044a/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="7256213843b80d75a86f033be77516a62d56044a" Add a third test variant to Trac #9872 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by jstolarek): I mentioned on ghc-devs that I witnessed exponential compile times for type families. I just built the latest HEAD and I see that the problem is gone. With my test case I get the following dependency between input size and compile time: ||= Input size =||= GHC 7.8.4 RC1 =||= GHC HEAD || || 64 || 1.2s || 0.6s || || 128 || 11.1s || 1.3s || || 256 || 1m41s || 3.7s || Compiling with GHC 7.8.4 required passing `-ftype-function-depth=1000` (perhaps a smaller value would work, but the default one was too low). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by jstolarek): Attached. It's generated automatically using Template Haskell so it's a bit messy. I was planning to clean it up a but that required more time that I had at my disposal :-( -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by goldfire): I have some work-in-progress [https://github.com/goldfirere/ghc/tree/wip /opt-flatten here] that cuts allocation amounts for the T9872x cases by half. I'm still twiddling knobs to find the best combination of settings, but the high-order bit is this: try to reduce a type family (in `flatten_exact_fam_app_fully`) '''before''' flattening the arguments. Only if that fails do we flatten the arguments. This works well if we have something like {{{ type family F a where F a = G a type family G a type family H a where H Bool = Char }}} and we call `F (H Bool)`. The current (HEAD) flattener will flatten `H Bool`, then reduce `F Char` to `G Char`, then flatten `Char` ''again'', then try to reduce `G Char`. With my patch, it just reduces `F (H Bool)` to `G (H Bool)`, then tries to reduce `G`, fails, and then reduces `H Bool` to `Char`. This saves one flattening. But, you can imagine it saving a lot more (and it does, in practice). On current tests, it works better not to use the flat-cache (which amounts to memoization of type-level functions) for this very-eager reduction. I'll look forward to trying Janek's tests, which satisfies a direct need: I've been worried that I'm overspecializing to the existing tests, and fresh tests will help. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by goldfire): In thinking about this issue, the Right Way to get type families to be faster is to optimize them properly. By this, I mean taking the type family definitions and performing an optimization pass on them during type-checking/desugaring. We've essentially just implemented a tiny interpreter inside of !TcFlatten, and the whole thing could be more principled in approach. I'm not making a concrete proposal, just musing on the fact that we have here a classic problem -- how to write a fast interpreter for a given programming language. It just happens to be the language of type families. I suppose there is a body of research and experience on this very issue, and if we want to be serious about fast compilation times in the presence of heavy type-level computation, it would do well to use that body of knowledge. In any case, I'm done dwelling on performance for a while, but I'm quite pleased with my end result. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by jstolarek): I've been chasing memory leak on my injective type families branch and it seems that these tests are the culprit. When run separately they are harmless and finish in a matter of seconds. However each of them allocates a lot of memory: T9872a: {{{ 2,680,443,384 bytes allocated in the heap 1,341,144,448 bytes copied during GC 230,497,136 bytes maximum residency (10 sample(s)) 1,651,136 bytes maximum slop 465 MB total memory in use (0 MB lost due to fragmentation) Productivity 34.5% of total user, 34.5% of total elapsed }}} T9872b: {{{ 3,480,475,896 bytes allocated in the heap 2,049,027,512 bytes copied during GC 466,737,240 bytes maximum residency (12 sample(s)) 2,234,096 bytes maximum slop 912 MB total memory in use (0 MB lost due to fragmentation) Productivity 33.2% of total user, 33.1% of total elapsed }}} T9872c: {{{ 2,963,257,224 bytes allocated in the heap 1,905,496,768 bytes copied during GC 454,512,352 bytes maximum residency (11 sample(s)) 2,104,512 bytes maximum slop 889 MB total memory in use (0 MB lost due to fragmentation) Productivity 31.2% of total user, 31.2% of total elapsed }}} T9872d: {{{ 740,175,432 bytes allocated in the heap 564,712,136 bytes copied during GC 68,077,728 bytes maximum residency (11 sample(s)) 904,080 bytes maximum slop 174 MB total memory in use (0 MB lost due to fragmentation) Productivity 26.1% of total user, 26.3% of total elapsed }}} So when these tests are run concurrently during validation they eat up ~2,5GB of RAM and that, in conjunction with other things running in the background, is too much for my machine. Note also the productivity: between to 2/3rd and 3/4th of running time is spent on garbage collection. These numbers don't look good. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by jstolarek): Let me only remark that these numbers were taken in a separate runs, not parallel ones. Richard, so you're seeing similar numbers for these tests? GC time actually looks pretty bad and I think it deserves a bug report, not just a feature request. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9872: Runing type functions is too slow -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.3 Resolution: fixed | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by goldfire): I don't have anything in particular in mind -- just that we happen to have some expertise on taking a functional program and executing it quickly, and perhaps we can apply that knowledge to this problem. It seems to me that the algorithm used to reduce type families evolved out of a constraint-solving process, and taking a more direct tack might prove fruitful, while still retaining the ability to work with programs where bits (skolem type variables) aren't -- and can't be -- known. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9872#comment:31 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler