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 |