Opened 7 years ago

Closed 7 years ago

Last modified 2 years ago

#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 Changed 7 years ago by dreixel

Is this not related to #5224?

comment:2 in reply to:  1 Changed 7 years ago by simonmar

Replying to dreixel:

Is this not related to #5224?

No, this ticket is about compiling Data.Tuple itself, whereas #5224 concerns the performance of GHC when compiling other modules.

comment:3 Changed 7 years ago by simonpj

  • 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 derive Generic only up to 7-tuples. Could you try that?
  • 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 7 years ago by dreixel

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 7 years ago by dreixel

Resolution: fixed
Status: newclosed

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 2 years ago by RyanGlScott

Keywords: Generics added
Note: See TracTickets for help on using tickets.