#5642: Deriving Generic of a big type takes a long time and lots of space
---------------------------------+------------------------------------------
Reporter: basvandijk | Owner: dimitris
Type: bug | Status: new
Priority: high | Milestone: 7.4.1
Component: Compiler | Version: 7.3
Keywords: | Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: Compile-time performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
---------------------------------+------------------------------------------
Comment(by basvandijk):
Replying to [comment:8 simonpj]:
> I think this is going to be a difficult one to solve. The underlying
problem is that the types grow non-linearly with the program size. Why?
Look at Section 2.3 of [http://research.microsoft.com/en-
us/um/people/simonpj/papers/variant-f/index.htm Scrap your type
applications].
Got it: N-ary data constructors like (`C e1 e2 e3 e4 e5`) are translated
to nested pairs (`Pair : ∀a,b. a → b → (a, b)`). This causes a quadratic
blow-up in size:
{{{
Pair σ1 (σ2,(σ3,(σ4,σ5))) e1
(Pair σ2 (σ3,(σ4,σ5)) e2
(Pair σ3 (σ4,σ5) e3
(Pair σ4 σ5 e4
e5)))
}}}
> This is a fundamental problem with System F, so it's not easy for GHC to
get around it. It shows up especially with deeply-nested sums and
products, which is exactly what is generated by the generic stuff. I'm
not sure what to do here.
So if I understand the paper correctly System IF would solve this by
removing the redundant type applications using:
{{{
Pair ψ τ s t → Pair ψ s τ t by (ξ2)
→ Pair s τ t by (ξ1)
→ Pair s t by (ξ1)
}}}
Of course the question is: is it worth implementing System IF for only
solving this problem? (I understand System IF did not significantly
improve compile times for the `base` library).
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5642#comment:10>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
