[GHC] #9805: Use TrieMaps to speed up type class instance lookup

[GHC]

#9805: Use TrieMaps to speed up type class instance lookup
-------------------------------------+-------------------------------------
        Reporter:  ezyang            |                   Owner:  ezyang
            Type:  task              |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler (Type    |                 Version:  7.9
  checker)                           |                Keywords:
      Resolution:                    |            Architecture:
Operating System:  Unknown/Multiple  |  Unknown/Multiple
 Type of failure:  None/Unknown      |               Test Case:
      Blocked By:                    |                Blocking:
 Related Tickets:                    |  Differential Revisions:
-------------------------------------+-------------------------------------

Comment (by ezyang):

 So, I finished the `InstMap` implementation, and was about to wire up it
 with `InstEnv` when I realized there is one more thing to implement.

 You see, if the template variable doesn't match, the instance lookup code
 will TRY AGAIN to unify, this time properly unifying all variables and not
 just matching template variables, in order to provide the list of non-
 matching but unifying instances. So it looks like we'll need to implement
 this too, because otherwise the TrieMap lookup won't provide enough
 candidates.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9805#comment:10>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler