#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:"da64ab530512c36acd17c1dbcd3b5fcc681d128b/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="da64ab530512c36acd17c1dbcd3b5fcc681d128b" Compress TypeMap TrieMap leaves with singleton constructor. Suppose we have a handful H of entries in a TrieMap, each with a very large key, size K. If you fold over such a TrieMap you'd expect time O(H). That would certainly be true of an association list! But with TrieMap we actually have to navigate down a long singleton structure to get to the elements, so it takes time O(K*H). The point of a TrieMap is that you need to navigate to the point where only one key remains, and then things should be fast. This is a starting point: we can improve the patch by generalizing the singleton constructor so it applies to CoercionMap and CoreMap; I'll do this in a later commit. Summary: Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: simonpj, austin Subscribers: carter, thomie Differential Revision: https://phabricator.haskell.org/D606 GHC Trac Issues: #9960 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9960#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler