#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 ):
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
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
