-
Edward Z. Yang authored
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
da64ab53