Large space usage when deriving Generic
There's a large space leak when deriving Generic:
http://www.haskell.org/pipermail/cvs-ghc/2011-May/062484.html
It is not currently derived for tuples; see changeset 7fcfc880853fa399c9468049aeb14e6eadb9eae5 in libraries/ghc-prim.
Test GShow1 therefore fails at the moment.
Trac metadata
| Trac field | Value |
|---|---|
| Version | 7.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | high |
| Resolution | Unresolved |
| Component | Compiler |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture |
Activity
mentioned in issue #5224
changed milestone to %7.2.1
added Tbug Trac import labels
mentioned in commit 807f9c8e
Is this not related to #5224?
Replying to [ticket:5227#comment:51751 dreixel]:
Is this not related to #5224?
No, this ticket is about compiling
Data.Tupleitself, whereas #5224 concerns the performance of GHC when compiling other modules.mentioned in commit de57e6f9
- We only derive Eq, Ord etc for tuples up to 15-tuples (see
GHC.Base) and Data for tuples up to 7-tuples. I think it would be reasonable to deriveGenericonly up to 7-tuples. Could you try that? - I'm guessing (but I have not checked) that a big reason for the blow-up is the repetition of type arguments; see http://research.microsoft.com/en-us/um/people/simonpj/papers/variant-f/if.pdf, page 5. Indeed Section 2.3 explicitly mentions the derivable-type-classes stuff as provoking the bad behaviour.
- The paper mentions a quadratic blow-up, but I think it's actually only N*logN if the tuples are balanced. But the constant factor seems large: see the example below.
- At the moment every derived instance is totally independent of every other one. But there must be a lot of repetition. Could we generate more compact code by hand-writing the derived tuple instances?
For this innocent triple:
data T = MkT Int Int Int deriving( Generic )we get the following "from" function (omitting all type info):
ghc -c -XDeriveGeneric Foo.hs -ddump-simpl -dsuppress-all ... $cfrom_rjE = \ (@ x_af9) (ds_dj5 :: T) -> case ds_dj5 of _ { MkT g1_af0 g2_af1 g3_af2 -> (:*: (g1_af0 `cast` ...) (:*: (g2_af1 `cast` ...) (g3_af2 `cast` ...))) `cast` ... }Seems reasonable. But show the type info and it looks like this:
$cfrom_rjE :: forall x_af8. Foo.T -> GHC.Generics.Rep Foo.T x_af8 [GblId, Arity=1, Caf=NoCafRefs] $cfrom_rjE = \ (@ x_af9) (ds_dj5 :: Foo.T) -> case ds_dj5 of _ { Foo.MkT g1_af0 g2_af1 g3_af2 -> (GHC.Generics.:*: @ (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int)) @ (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) GHC.Generics.:*: GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int)) @ x_af9 (g1_af0 `cast` (Sym (GHC.Generics.NTCo:K1 <GHC.Generics.R> <GHC.Types.Int> <x_af9>) ; Sym (GHC.Generics.NTCo:M1 <GHC.Generics.S> <GHC.Generics.NoSelector> <GHC.Generics.K1 GHC.Generics.R GHC.Types.Int>) <x_af9> :: GHC.Types.Int ~ GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) x_af9)) (GHC.Generics.:*: @ (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int)) @ (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int)) @ x_af9 (g2_af1 `cast` (Sym (GHC.Generics.NTCo:K1 <GHC.Generics.R> <GHC.Types.Int> <x_af9>) ; Sym (GHC.Generics.NTCo:M1 <GHC.Generics.S> <GHC.Generics.NoSelector> <GHC.Generics.K1 GHC.Generics.R GHC.Types.Int>) <x_af9> :: GHC.Types.Int ~ GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) x_af9)) (g3_af2 `cast` (Sym (GHC.Generics.NTCo:K1 <GHC.Generics.R> <GHC.Types.Int> <x_af9>) ; Sym (GHC.Generics.NTCo:M1 <GHC.Generics.S> <GHC.Generics.NoSelector> <GHC.Generics.K1 GHC.Generics.R GHC.Types.Int>) <x_af9> :: GHC.Types.Int ~ GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) x_af9)))) `cast` (Sym (GHC.Generics.NTCo:M1 <GHC.Generics.C> <Foo.C1_0T> <GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) GHC.Generics.:*: (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) GHC.Generics.:*: GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int))>) ; (Sym (GHC.Generics.NTCo:M1 <GHC.Generics.D> <Foo.D1T> <GHC.Generics.M1 GHC.Generics.C Foo.C1_0T (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) GHC.Generics.:*: (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) GHC.Generics.:*: GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int)))>) ; Sym (Foo.TFCo:Rep_T)) <x_af9> :: (GHC.Generics.:*:) (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int)) (GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int) GHC.Generics.:*: GHC.Generics.M1 GHC.Generics.S GHC.Generics.NoSelector (GHC.Generics.K1 GHC.Generics.R GHC.Types.Int)) x_af9 ~ GHC.Generics.Rep Foo.T x_af9) }Lots and lots of repeated types. And that's for a triple. Try a 10-tuple!
I don't really have a good way to solve this, except by using System IF (the paper) or perhaps by let-binding types which would be a significant change.
Short term: just up to 7-tuples, like Data.
Simon
- We only derive Eq, Ord etc for tuples up to 15-tuples (see
mentioned in commit c1e88d86
mentioned in commit 3740b0ae
-
Done: http://hackage.haskell.org/trac/ghc/changeset/bca02fda94c406cc484a3bfbcb6d120d43439935
Heap profile now only goes up to 5M, Tuple.hi file is less than 10% in size compared to 7.0.
Trac metadata
Trac field Value Resolution Unresolved → ResolvedFixed mentioned in issue #14594
added Phigh label
