Significant compilation time blowup when refactoring singletons-heavy code

At ICFP, I griped to Ben about some code I'm writing (which makes use of singletons to the nth degree) that takes absolutely forever to compile with optimizations. I suspected that type families (i.e., coercions) were the culprit, but Ben requested that I put the code on Trac anyways, so here it is.

I've attached two modules (Lib.hs and Lib2.hs). You'll need GHC 8.6.1 or later to compile it. To compile it, run:

$ time /opt/ghc/8.6.1/bin/ghc -O1 -fforce-recomp Lib.hs
[1 of 2] Compiling Lib2             ( Lib2.hs, Lib2.o )
[2 of 2] Compiling Lib              ( Lib.hs, Lib.o )

real    3m28.367s
user    3m28.512s
sys     0m0.212s

Note that if you compile without optimizations, it'll finish almost immediately:

$ time /opt/ghc/8.6.1/bin/ghc -O0 -fforce-recomp Lib.hs
[1 of 2] Compiling Lib2             ( Lib2.hs, Lib2.o )
[2 of 2] Compiling Lib              ( Lib.hs, Lib.o )

real    0m0.528s
user    0m0.480s
sys     0m0.036s

Also, if you look at the source code for Lib.hs, you'll notice some code which says:

instance SApplicative f => SApplicative (M1 i c f) where
  sPure x = singFun3 @(.@#@$) (%.) @@ singFun1 @M1Sym0 SM1 @@ (singFun1 @PureSym0 sPure) @@ x
  -- If I change the implementation of sPure above to be this:
  --
  --   sPure x = SM1 (sPure x)
  --
  -- Then Lib.hs compiles quickly again (< 1 second) with -O1.

  SM1 f %<*> SM1 x = SM1 (f %<*> x)

If you apply this suggested change, then you can see the difference when you compile it with optimizations again:

$ time /opt/ghc/8.6.1/bin/ghc -O1 -fforce-recomp Lib.hs
[1 of 2] Compiling Lib2             ( Lib2.hs, Lib2.o )
[2 of 2] Compiling Lib              ( Lib.hs, Lib.o )

real    0m0.986s
user    0m0.940s
sys     0m0.040s

Given that this particular change of code causes such a dramatic increase in compilation, I have to wonder if there's more going on here than just the usual type-family slowness.

Trac metadata

Trac field	Value
Version	8.6.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC	bgamari
Operating system
Architecture