#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 dreixel):
Replying to [comment:10 basvandijk]:
> 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)))
}}}
No; we balance the sums and the products, so it grows with logarithmic
complexity. See the second column of the 4th page of
[http://dreixel.net/research/pdf/gdmh.pdf the original paper].
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5642#comment:11>
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
