Performance problem with TrieMap
Looking at #9805 (closed) reminded me. When investigating the performance of #9872 (closed) I found a major performance hole in TrieMap
.
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).
This is pretty bad. In test T9872
I found that 90% of compile time was spent in TrieMap
as we repeatedly built, folded, and then rebuilt TrieMap
s. I fixed that by keeping smaller TrieMap
s, but the underlying problem remains.
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. So I think that TypeMap
, say, should look like
data TypeMap a
= EmptyTM
| SingletonTM Type a
| TM { tm_var :: VarMap a
, tm_app :: TypeMap (TypeMap a)
, tm_fun :: TypeMap (TypeMap a)
, tm_tc_app :: NameEnv (ListMap TypeMap a)
, tm_forall :: TypeMap (BndrMap a)
, tm_tylit :: TyLitMap a
}
The SingletonTM
means that, once you are down to a single (key,value) pair, you stop and
just use SingletonTM
.
Tiresomely, because of the deBruijn thing, it'd need to be
...
| SingletonTM (CMEnv, Type) a
...
and we'd need an auxiliary function for equality:
eqTypeModuloDeBruijn :: (CMEnv, Type) -> (CEnv, Type) -> Bool
But that's not hard. Very similar to the way RnEnv2
works.
Trac metadata
Trac field | Value |
---|---|
Version | 7.8.4 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |