Opened 2 years ago

Last modified 9 months ago

#14337 new bug

typeRepKind can perform substantial amounts of allocation

Reported by: dfeuer Owned by:
Priority: normal Milestone: 8.10.1
Component: Core Libraries Version: 8.2.1
Keywords: Typeable Cc: bgamari
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #14254 Differential Rev(s):
Wiki Page:

Description

I came up with a (rather contrived) test case to demonstrate that Phab: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.

Change History (5)

comment:1 Changed 2 years ago by simonpj

Is this something to do with #14254, perhaps?

I came up with a (rather contrived) test case

Did you perhaps fail to attach it?

comment:2 Changed 2 years ago by dfeuer

I've attached it now, to #14254.

comment:3 Changed 20 months ago by bgamari

Milestone: 8.4.18.6.1

This ticket won't be resolved in 8.4; remilestoning for 8.6. Do holler if you are affected by this or would otherwise like to work on it.

comment:4 Changed 15 months ago by bgamari

Milestone: 8.6.18.8.1

These won't be addressed in GHC 8.6.

comment:5 Changed 9 months ago by osa1

Milestone: 8.8.18.10.1

Bumping milestones of low-priority tickets.

Note: See TracTickets for help on using tickets.