#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable 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: | -------------------------------------+------------------------------------- Description changed by dfeuer: Old description:

In particular, `get` uses `getSomeTypeRep`. `getSomeTypeRep`, in turn, calls `typeRepKind` through its recursion. But `typeRepKind` is itself recursive, fully inspecting the spine of its argument. That smells quadratic to me. The solution, I believe, is to change the type of `getSomeTypeRep` to `BinHandle -> IO (SomeTypeRep, TypeRep Type)`.

New description: In particular, `get` uses `getSomeTypeRep`. `getSomeTypeRep`, in turn, calls `typeRepKind` through its recursion. But `typeRepKind` is itself recursive, fully inspecting the spine of its argument. That smells quadratic to me. The solution, I believe, is to change the type of `getSomeTypeRep` to `BinHandle -> IO (SomeTypeRep, SomeTypeRep)`. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable 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:D3998 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch * differential: => Phab:D3998 * milestone: => 8.4.1 Comment: Very good observation. I think Phab:D3998 should greatly improve the situation. We also need to get a fix into `binary` when an approach has been decided. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable 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:D3998 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): I think you need to define what your cost model is; it's not clear that anyone expects `dynApply` to be as cheap as a static application. The same goes for serialisation; it's going to be expensive even if you cache the kind. This is why packages like `distributed-process` go to some lengths to avoid serialising unnecessarily. On the other hand, packages like `vault` really don't care how expensive kind computation is, so optimizing for this case may be counterproductive from their perspective. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable 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:D3998 Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): We could, perhaps, consider a representation like I describe in comment:1:ticket:14263 for `TypeRep` to avoid these performance problems. Doing so would, at the least, be a nice stress test for `TypeInType`. :) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable 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:D3998, Wiki Page: | Phab:D4078, Phab:D4082 -------------------------------------+------------------------------------- Changes (by dfeuer): * differential: Phab:D3998 => Phab:D3998, Phab:D4078, Phab:D4082 Comment: I believe the simplest thing right now that will actually make deserialization linear is Phab:D4082. If at some point GHC allows unlifted types in kinds (which Richard thinks is probably not hard), then it will get even simpler and even cheaper. Phab:D4078 implements Richard's idea of starting off by digging down to the constructor, and as a side effect reduces the number of tags needed to express deeply nested applications. But I very much doubt the complexity/benefit ratio supports that approach, unless we change the structure of `TypeRep` to match. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable 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:D3998, Wiki Page: | Phab:D4078, Phab:D4082 -------------------------------------+------------------------------------- Changes (by dfeuer): * Attachment "Big.hs" added. Test case -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable 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:D3998, Wiki Page: | Phab:D4078, Phab:D4082 -------------------------------------+------------------------------------- Comment (by dfeuer): One more thing: while I don't think it's a good idea, we ''could'' go with a version of Phab:D4085 that only caches kind typereps in `TrTyCon` constructors. That would eliminate the allocation problem and alleviate but not eliminate the time problem. The reason I favor the fully cached version is that it doesn't strike me as really that expensive to add one more pointer to a constructor that already has four words of payload (two for the `Fingerprint`, one for the function, and one for the argument). However, that's somewhat conditional on being able to eliminate the extra laziness. It seems there's a knot that needs tying for `Type :: Type`, which makes things a tad fussy. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #14337 | Differential Rev(s): Phab:D3998, Wiki Page: | Phab:D4082, Phab:D4085 -------------------------------------+------------------------------------- Comment (by simonpj): Re the loop, `Type` = `TYPE Lifted`. So the `TypeRep` for `Type` is a `TrApp`, with a cached kind. So {{{ TYPE Lifted :: TYPE Lifted }}} But that kind has a cached kind: {{{ TYPE Lifted :: TYPE Lifted :: TYPE Lifted }}} and if the cache field is strict you build an infinite data structure. The only way out of this I can see is to * define a top level definition the `TypeRep` for `TYPE Lifted` * in that definition, do not use `mkTrApp`; instead build an explicit loop {{{ trTYPELifted = TrApp fpr trTYPE trLifted trTYPELifted }}} note that `trTYPELifted mentions itself directly. * In `mkTrApp` spot that case, and return `trTYPELifted`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Typeable Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #14337 | Differential Rev(s): Phab:D3998, Wiki Page: | Phab:D4082, Phab:D4085 -------------------------------------+------------------------------------- Comment (by simonpj): All this is re Phab:D4085.

I don't need the cache field to be strict. I just need to force values before installing them in that field,

Right: and that happens in the "smart constructor", `mkTrApp`. Doesn't the plan in comment:14 work? Just spot the special case in `mkTrApp`; and call `mkTrApp` whenever constructing a `TrApp`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14254: The Binary instance for TypeRep smells a bit expensive -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: fixed | Keywords: Typeable Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #14337 | Differential Rev(s): Phab:D3998, Wiki Page: | Phab:D4082, Phab:D4085 -------------------------------------+------------------------------------- Changes (by dfeuer): * status: patch => closed * resolution: => fixed Comment: Fixed by bc761ad9c65c7aa62d38db39c59a6c0ae59c8ab8. We now cache the `TypeRep` of the kind in each `TrTyCon` and `TrApp` constructor. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14254#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler