Opened 16 months ago

Last modified 16 months ago

#15151 new feature request

Better Interaction Between Specialization and GND

Reported by: andrewthad Owned by:
Priority: normal Milestone: Research needed
Component: Compiler Version: 8.4.2
Keywords: deriving Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Change History (7)

comment:1 Changed 16 months ago by andrewthad

Summary: Better Interaction Specialization and GNDBetter Interaction Between Specialization and GND

comment:2 Changed 16 months ago 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?

comment:3 Changed 16 months ago by RyanGlScott

Status: newinfoneeded

comment:4 Changed 16 months ago 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.

comment:5 Changed 16 months ago by simonpj

Keywords: deriving added

comment:6 Changed 16 months ago by RyanGlScott

Milestone: 8.6.1Research needed
Status: infoneedednew

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:

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.

comment:7 Changed 16 months ago by andrewthad

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.

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.

Note: See TracTickets for help on using tickets.