Opened 2 years ago

Last modified 9 months ago

#13647 new bug

Tidy up TcTypeable

Reported by: simonpj Owned by:
Priority: normal Milestone: 8.10.1
Component: Compiler Version: 8.0.1
Keywords: Typeable Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

There is code in TcTypeable that generates a KindRep for each TyCon (see Note [Representing TyCon kinds: KindRep]). There's nothing actually wrong with it.

But it's pretty hard to understand. And it generates a staggering amount of data structure, when compiling GHC.Types.

Result size of Tidy Core
  = {terms: 74,615, types: 41,335, coercions: 2, joins: 0/0}

Why? Well, it injects a TyCon binding for each unboxed tuple size. For example, here is the code for pairs (#,#)

$tc(#,#)
  = TyCon 16533601304077481746##
          7902994497850328874##
          tr$ModuleGHCPrim
          $tc(#,#)2
          2#
          $tc(#,#)1

-- TYPE #0 -> TYPE #1 -> TYPE (TupleRep (': RuntimeRep #0 (': RuntimeRep #1 ('[] RuntimeRep))))
$tc(#,#)1 :: KindRep
$tc(#,#)1       = KindRepFun $krep2115_r6ji $krep18009_rarE

$krep18009_rarE = KindRepFun $krep2117_r6jk $krep18008_rarD

-- TYPE (TupleRep (': RuntimeRep #0 (': RuntimeRep #1 ('[] RuntimeRep))))
$krep18008_rarD = KindRepTyConApp $tcTYPE $krep18007_rarC
$krep18007_rarC = : @ KindRep $krep18006_rarB ([] @ KindRep)

-- TupleRep (': RuntimeRep #0 (': RuntimeRep #1 ('[] RuntimeRep)))
$krep18006_rarB = KindRepTyConApp $tc'TupleRep $krep18005_rarA
$krep18005_rarA = : @ KindRep $krep2283_r6m0 ([] @ KindRep)

-- ': RuntimeRep #0 (': RuntimeRep #1 ('[] RuntimeRep))
$krep2283_r6m0  = KindRepTyConApp $tc': $krep2282_r6lZ
$krep2282_r6lZ  = : @ KindRep $tc'AddrRep1 $krep2281_r6lY
$krep2281_r6lY  = : @ KindRep $krep61_r5Ma           $krep2280_r6lX
$krep2280_r6lX  = : @ KindRep $krep2279_r6lW         ([] @ KindRep)

-- ': RuntimeRep #1 ('[] RuntimeRep)
$krep2279_r6lW = KindRepTyConApp $tc': $krep2278_r6lV
$krep2278_r6lV = : @ KindRep $tc'AddrRep1 $krep2277_r6lU
$krep2277_r6lU = : @ KindRep $krep60_r5M9           $krep2276_r6lT
$krep2276_r6lT = : @ KindRep $krep2274_r6lR          ([] @ KindRep)

-- '[] RuntimeRep
$krep2274_r6lR = KindRepTyConApp $tc'[] $krep2273_r6lQ
$krep2273_r6lQ = : @ KindRep $tc'AddrRep1 ([] @ KindRep)

-- RuntimeRep
$tc'AddrRep1 = KindRepTyConApp $tcRuntimeRep ([] @ KindRep)

-------------- TYPE #0
$krep2115_r6ji = KindRepTyConApp $tcTYPE $krep2114_r6jh
$krep2114_r6jh = : @ KindRep $krep61_r5Ma ([] @ KindRep)
$krep61_r5Ma   = KindRepVar 0#

-------------- TYPE #1
$krep2117_r6jk = KindRepTyConApp $tcTYPE $krep2116_r6jj
$krep2116_r6jj = : @ KindRep $krep60_r5M9 ([] @ KindRep)
$krep60_r5M9   = KindRepVar 1#

That's a lot, and it's only for pairs. We generate all this up to 62-tuples!

Suggestions (read Note [Representing TyCon kinds: KindRep] first)

  • KindRep is a description of a polykind; an interpreter, called instantiateKindRep turns it into a kind. So we can add whatever constructors we like to KindRep.
  • One good one would be UnboxedTupleRep n, which instantiateKindRep can instantiate to the kind of an unboxed tuple. It just moves the work somewhere else, of course, but it will make the generated code dramatically smaller.
  • We have a few canned kind-reps, via TcTypeable.builtInKindReps. It'd be simpler and easier instead to make each of them into a data constructor of KindRep.
  • Once that is done, I suspect that the entire machinery of tyring to share KindReps (which makes my head hurt) would be unnecessary

None of this is essential, but I think that matters can be improved.

Change History (5)

comment:1 Changed 2 years ago by bgamari

Indeed I had considered giving tuple KindReps special treatment, but was reluctant to implement a solution that would only target GHC.Types. Yes, GHC.Types does get larger,

Once that is done, I suspect that the entire machinery of tyring to share KindReps (which makes my head hurt) would be unnecessary

I am not convinced it would be wise to drop the sharing. Afterall, the problem that you describe above above does not affect only GHC.Types. There were some programs in nofib whose compiler allocations increased drastically due to TTypeable as well. The patches introducing sharing (a694cee77b64235b42029fea248453ddf6b17d17) and "canned" KindReps (c1dacb8a9c18677495bbe7e41391f8ca7a573070) both helped immensely.

comment:2 Changed 20 months ago by bgamari

Milestone: 8.4.18.6.1

On re-reading Simon's suggestions they actually sound quite plausible. We should certainly give this a try. Not for 8.4, however.

comment:3 Changed 20 months ago by simonpj

Keywords: Typeable added

comment:4 Changed 15 months ago by bgamari

Milestone: 8.6.18.8.1

These will not 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.