typeRepKind can perform substantial amounts of allocation
I came up with a (rather contrived) test case to demonstrate that D4082 reduced big-O time complexity in pathological cases. But I expected it to increase space usage by a constant factor. What I found was very much the opposite: it dramatically reduced allocation. The reason for this is obvious in hindsight. Every time we call typeRepKind
, we recalculate the kind entirely from scratch. That recalculation is only a potential time problem for TrApp
, because we only need to walk down links, but it's also a space problem for TrTyCon
, because we're building up a TypeRep
from a KindRep
.
The solution, assuming we choose to keep typeRepKind
, seems fairly clear: whether or not we choose to cache the kind in TrApp
, we should almost certainly do so in TrTyCon
.
Trac metadata
Trac field | Value |
---|---|
Version | 8.2.1 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Core Libraries |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | bgamari |
Operating system | |
Architecture |