#5227 closed bug (fixed)
Large space usage when deriving Generic
Reported by: | igloo | Owned by: | dreixel |
---|---|---|---|
Priority: | high | Milestone: | 7.2.1 |
Component: | Compiler | Version: | 7.1 |
Keywords: | Generics | 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'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.
Change History (6)
comment:1 follow-up: 2 Changed 9 years ago by
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
- 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 deriveGeneric
only 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
comment:4 Changed 9 years ago by
Owner: | changed from jpm@… to dreixel |
---|
Ok, I'll see what happens when we only go up to 7-tuples and report here.
Fortunately users can always use standalone deriving for bigger tuples if necessary.
comment:5 Changed 9 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
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.
comment:6 Changed 4 years ago by
Keywords: | Generics added |
---|
Is this not related to #5224?