[GHC] #15151: Better Interaction Specialization and GND
#15151: Better Interaction Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.4.2 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Let us consider the following code: {{{ -- Sort.hs sort :: (Prim a, Ord a) => MutablePrimArray s a -> ST s () sort mutArr = ... {-# SPECIALIZE sort :: MutablePrimArray s Int -> ST s () -#} {-# SPECIALIZE sort :: MutablePrimArray s Int8 -> ST s () -#} {-# SPECIALIZE sort :: MutablePrimArray s Word8 -> ST s () -#} ... }}} For reference, a `MutablePrimArray` is a `MutableByteArray` with a phantom type variable to tag the element type. This sorting algorithm may be implemented in any number of ways, and the implementation is unimportant here. The specialize pragmas are intended to capture a number of common use cases. Here's where a problem arises: {{{ -- Example.hs newtype PersonId = PersonId Int deriving (Eq,Ord,Prim) sortPeople :: MutablePrimArray s PersonId -> MutablePrimArray s PersonId sortPeople x = sort x }}} There isn't a rewrite rule that specializes the `sort` function when we are dealing with `PersonId`. So, we end up with a slower version of the code that explicitly passes all the dictionaries. One solution would be to just use `INLINABLE` instead. Then we don't have to try to list every type, and we just let the specialization be generate at the call site. But this isn't totally satisfying. There are a lot of types that are just newtype wrappers around `Int`. Why should we have an extra copy of the same code for each of them? (Even without newtypes, `INLINABLE` can still result in duplication if neither of the modules that needs a specialization transitively imports the other). What I'm suggesting is that rewrite rules (like those generated by `SPECIALIZE`) could target not just the given type but also any newtype around it, provided that all typeclass instances required by the function were the result of GND. The only situations where this is unsound are situations where the user was already doing something unsound with rewrite rules. There are several implementation difficulties: * In core, there is no good way to tell that a typeclass instance dictionary was the result of GND. I'm not sure how to work around this. * `Eq` and `Ord` usually aren't handled by the `newtype` deriving strategy. They are handled by the `stock` strategy, which produces code with equivalent behavior but is nevertheless different code. * The rewrite rule would need to look at additional arguments beyond the type arguments. I suspect that these difficulties would make such this feature difficult to implement, but this feature would help me with some of my libraries and applications. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15151: Better Interaction Between Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.4.2 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: | -------------------------------------+------------------------------------- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15151: Better Interaction Between Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.4.2 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 RyanGlScott): I'm afraid I don't quite understand what you're proposing. Can you provide an example of the code that is currently generated, and an example of the code you wish would be generated? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15151: Better Interaction Between Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature request | Status: infoneeded Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.4.2 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 RyanGlScott): * status: new => infoneeded -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15151: Better Interaction Between Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature request | Status: infoneeded Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.4.2 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 simonpj): What Andrew means is that the desired machine-code for `sortPeople` is bit-for-bit identical with that of `sortInt`; and the SPECIALISE pragma in `Sort.hs` has already made a nice specialised copy of the latter. He just wants to reuse it. Of course, the reason for creating the `PersonId` newtype might be precisely the have a ''different'' `Ord` instance that the underlying `Int` type. Then it would be wrong to use `sortInt`. But if the `Ord` instance is derived, esp via GND, then it ''is'' sound to use `sortInt`. I don't see an easy way to achieve exactly what you want. But there are two workarounds. * As you say, use INLINABLE on `sort`; and specialise (even with an explicit SPECIALISE pragma) in the module where `PersonId` is defined. * Define `sortPeople` like this {{{ sortPeople :: MutablePrimArray s PersonId -> MutablePrimArray s PersonId sortPeople = coerce (sort @Int) }}} The `sort @Int` will get the efficient specialised version you want; and the `coerce` will lift it to the type you want. And if you want GHC to use `sortPeople` you'd have to add {{{ {-# RULES "sort/PersonId" sort @PersonId = sortPeople #-} }}} Interestingly, this would ''completely ignore'' any `Ord` instance for `PersonId`; indeed it doesn't need to have one. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15151: Better Interaction Between Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature request | Status: infoneeded Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.4.2 Resolution: | Keywords: deriving 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: => deriving -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15151: Better Interaction Between Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Research | needed Component: Compiler | Version: 8.4.2 Resolution: | Keywords: deriving 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 RyanGlScott): * status: infoneeded => new * milestone: 8.6.1 => Research needed Comment: OK. I think I'm inclined to agree with Simon here that isn't at all simple to achieve. GHC doesn't track whether an instance was derived or not (let alone whether it was GND'd or not), and moreover, it's questionable that we'd even want to do this. After all, why should a GND'd instance receive special privileges? If I defined this instance manually: {{{#!hs instance Eq PersonId where (==) = coerce @Int @PersonId (==) }}} Then why shouldn't GHC be able to recognize that that instance has the same representation the `Eq Int` instance? A similar problem arises when you try to `coerce` from a `Map Int ()` to a `Map PersonId ()`. The nominal role on `Map`'s first type argument prevents this from typechecking, which is rather unsatisfying, since the `Ord PersonId` instance has the same representation as the `Ord Int` instance. Again, folks have asked if there is a way we could carve out an exception here to allow this to typecheck if `Ord PersonId` was GND'd, but I have similar reservations about that idea as I do the one proposed in this ticket. In short, it feels like there ought to be a more general guiding principle here to determine whether two instance dictionaries are representationally equivalent. I'm not sure what that would be, though. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
In short, it feels like there ought to be a more general guiding
#15151: Better Interaction Between Specialization and GND -------------------------------------+------------------------------------- Reporter: andrewthad | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Research | needed Component: Compiler | Version: 8.4.2 Resolution: | Keywords: deriving 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 andrewthad): principle here to determine whether two instance dictionaries are representationally equivalent. I'm not sure what that would be, though. That seems to sum up the difficulty pretty well. I agree that giving GNDed instances special standing would be bad (and difficult, since that's currently not even tracked). I have no idea what a good way to check instance equality would be. I don't expect that this will be doable in the immediate or even in the far future, but maybe it's a research problem someone may try to tackle one day. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15151#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC