[GHC] #9960: Performance problem with TrieMap

[GHC]

#9960: Performance problem with TrieMap
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                   Owner:
            Type:  bug               |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler          |                 Version:  7.8.4
      Resolution:                    |                Keywords:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  None/Unknown      |  Unknown/Multiple
      Blocked By:                    |               Test Case:
 Related Tickets:                    |                Blocking:
                                     |  Differential Revisions:  Phab:D606
-------------------------------------+-------------------------------------

Comment (by Edward Z. Yang <ezyang@…>):

 In [changeset:"ccef01465366e11978fdad1bf28aeac2edde36c2/ghc"]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="ccef01465366e11978fdad1bf28aeac2edde36c2"
 Add 'DeBruijn' constructor, which generalizes "key modulo alpha-renaming."

 Summary:
 We need equality over Types, etc; and this equality has to be modulo alpha
 renaming. Previously, we baked CmEnv into the generic "empty, singleton,
 many"
 structure. This isn't great, really GenMap should be more generic than
 that.

 The insight: we've defined the key wrong: the key should be *equipped*
 with the alpha-renaming information (CmEnv) and a TrieMap queried with
 this.
 This is what the DeBruijn constructor does.

 Now, when we define TrieMap instances, we don't have to synthesize an
 emptyCME
 to pass to the helper functions: we have all the information we need. To
 make a
 recursive call, we construct a new DeBruijn with the updated CME and then
 call lookupTM on that. We can even define a plain old Eq instance on
 DeBruijn
 respecting alpha-renaming.  There are number of other good knock-on
 effects.

 This patch does add a bit of boxing and unboxing, but nothing the
 optimizer
 shouldn't be able to eliminate.

 Signed-off-by: Edward Z. Yang <ezyang at cs.stanford.edu>

 Test Plan: validate

 Reviewers: simonpj, austin

 Subscribers: carter, thomie

 Differential Revision: https://phabricator.haskell.org/D608

 GHC Trac Issues: #9960
 }}}

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