Opened 9 years ago

Last modified 7 months ago

#2598 new feature request

Avoid excessive specialisation in SpecConstr

Reported by: simonpj Owned by:
Priority: lowest Milestone:
Component: Compiler Version: 6.8.3
Keywords: SpecConstr Cc: ndmitchell@…, rl@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

This ticket captures an email thread so it doesn't get lost.

Consider this (from haddock/src/Haddock/Backends/Hoogle.hs):

dropComment (' ':'-':'-':' ':_) = []
dropComment (x:xs) = x : dropComment xs
dropComment [] = []

This desugars thus:

dropComment xs
  = case xs of
      (C# x1 : xs1) ->
        case x1 of
          ' '# ->
             case xs1 of
               (C# x2:xs2) ->
                 case x2 of
                   '-' -> ....
                   DEFAULT -> dropComment (C# x2 : xs2)
          DEFAULT -> ...
       [] -> ...

I have elided the branches that are less interesting, and I have done a bit of multi-level pattern matching to save space.

The thing to notice is this: at the recursive call, we know that the argument is a cons, with C# at the front. So SpecConstr dutifully creates a specialized version. And similarly for each subsequent character! Indeed, if the match fails after matching (' ': '-' : ) prefix, the recursive call even knows that the first char is '-'!

Hence we get as many specializations as we have characters in the input match.

So SpecConstr is behaving as expected. Can anyone think of a heuristic to squash this behavior? At the moment we take the first N specializations and then stop. One heuristic might be "if there are lots of recursive calls, don't specialize". But that is very close to "if there are lots of specializations, drop some". Mind you, perhaps we should be more vigorous still: "if there are more than N, don't do any" on the grounds that randomly choosing the first few is unlikely to be useful.

Any thoughts?

Attachments (1)

DropComment.hs (124 bytes) - added by morabbin 5 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 9 years ago by simonpj

Neil has a good suggestion: One possible heuristic would be to never specialise down recursive components. That way you would only ever obtain the specialisations:

[]
_:_
' ':_
'-':_

Which seems like a sensible set. By using a size bound as well, your definition of recursive components can be very weak - directly recursive should catch most examples. I'm not sure how this work with other examples - it seems sufficient for the classic 'last' example though.

comment:2 Changed 9 years ago by NeilMitchell

Cc: ndmitchell@… added

comment:3 Changed 9 years ago by simonpj

Cc: rl@… added

Roman says: Yes, as long as the definition of recursive doesn't include things like

   data T a where
     Pair :: T a -> T b -> T (a,b)
     ...

and similar constructs for indexed types. I'm not really convinced about this idea, though. What is so special about recursive constructors? And why is generating all specialisations in this particular case bad at all? In the end, all but the one for dropComment (x:xs) are eliminated which roughly doubles the code size. There are a couple more tiny leftovers but that's only because GHC isn't even trying to get rid of them. To be honest, I don't quite see the problem here.

In fact, in this example SpecConstr actually performs a fairly complex optimisation which, unfortunately, doesn't bring much (I think; benchmarking the lexer with and without SpecConstr would be useful).

> dropComment (' ':'-':'-':' ':_) = []
> dropComment (x:xs) = x : dropComment xs
> dropComment [] = []

Without SpecConstr, we have:

    dropComment (' ':'-':'a':...)
-> dropComment ('-':'a':...)
-> dropComment ('a':...)

SpecConstr skips the second step (i.e., saves a recursive call) because it knows that the argument won't match the first equation. For Haddock, this isn't a big win unless the input file contains a lot of space/dash sequences. However, I can easily imagine programs where this optimisation would be very desirable.

Roman

comment:4 Changed 9 years ago by simonpj

Hmm. I just compiled dropComment all by itself, and sure enough you get two dropComment itself, one similar-sized specialisation --- together with another FIVE smaller specialisations that look like

Foo.$sdropComment3 :: [GHC.Types.Char] -> GHC.Prim.Char# -> [GHC.Types.Char]
Foo.$sdropComment3 xs c = '-' : Foo.$sdropComment2 xs c

and similar ones. I'd expected lots of big specialisations, so this was a surprise to me.

The full output follows. Still there a big bloat in the middle. Discarding the recursive components is just a slightly-random heuristic, and I expect you're right that there might be cases where it matters.

Simon

==================== Tidy Core ====================
Foo.a :: GHC.Types.Char
[GlobalId]
[NoCafRefs]
Foo.a = GHC.Types.C# '-'

Foo.a1 :: GHC.Types.Char
[GlobalId]
[NoCafRefs]
Foo.a1 = GHC.Types.C# '-'

Foo.$sdropComment :: [GHC.Types.Char]
[GlobalId]
[NoCafRefs]
Foo.$sdropComment =
  GHC.Types.: @ GHC.Types.Char Foo.a (GHC.Types.[] @ GHC.Types.Char)

Foo.$sdropComment1 :: [GHC.Types.Char]
[GlobalId]
[NoCafRefs]
Foo.$sdropComment1 =
  GHC.Types.: @ GHC.Types.Char Foo.a1 Foo.$sdropComment

Rec {
Foo.$sdropComment2 :: [GHC.Types.Char]
                      -> GHC.Prim.Char#
                      -> [GHC.Types.Char]
[GlobalId]
[Arity 2
 NoCafRefs]
Foo.$sdropComment2 =
  \ (sc_sgz :: [GHC.Types.Char]) (sc1_sgA :: GHC.Prim.Char#) ->
    GHC.Types.:
      @ GHC.Types.Char
      (GHC.Types.C# '-')
      (Foo.$sdropComment4 sc_sgz sc1_sgA)
Foo.$sdropComment3 :: [GHC.Types.Char]
                      -> GHC.Prim.Char#
                      -> [GHC.Types.Char]
[GlobalId]
[Arity 2
 NoCafRefs]
Foo.$sdropComment3 =
  \ (sc_sgD :: [GHC.Types.Char]) (sc1_sgE :: GHC.Prim.Char#) ->
    GHC.Types.:
      @ GHC.Types.Char
      (GHC.Types.C# '-')
      (Foo.$sdropComment2 sc_sgD sc1_sgE)
Foo.$sdropComment4 :: [GHC.Types.Char]
                      -> GHC.Prim.Char#
                      -> [GHC.Types.Char]
[GlobalId]
[Arity 2
 NoCafRefs]
Foo.$sdropComment4 =
  \ (sc_sgv :: [GHC.Types.Char]) (sc1_sgw :: GHC.Prim.Char#) ->
    case sc1_sgw of ds_Xfu {
      __DEFAULT ->
        GHC.Types.:
          @ GHC.Types.Char (GHC.Types.C# ds_Xfu) (Foo.dropComment sc_sgv);
      ' ' ->
        case sc_sgv of wild_Xo {
          [] ->
            GHC.Types.:
              @ GHC.Types.Char
              (GHC.Types.C# ' ')
              (GHC.Types.[] @ GHC.Types.Char);
          : ds1_dfc ds2_dfd ->
            case ds1_dfc of wild1_Xu { GHC.Types.C# ds3_dfe ->
            case ds3_dfe of ds4_XfM {
              __DEFAULT ->
                GHC.Types.:
                  @ GHC.Types.Char
                  (GHC.Types.C# ' ')
                  (Foo.$sdropComment4 ds2_dfd ds4_XfM);
              '-' ->
                case ds2_dfd of wild2_XD {
                  [] ->
                    GHC.Types.: @ GHC.Types.Char (GHC.Types.C# ' ') Foo.$sdropComment;
                  : ds5_dff ds6_dfg ->
                    case ds5_dff of wild3_XJ { GHC.Types.C# ds7_dfh ->
                    case ds7_dfh of ds8_Xg4 {
                      __DEFAULT ->
                        GHC.Types.:
                          @ GHC.Types.Char
                          (GHC.Types.C# ' ')
                          (GHC.Types.:
                             @ GHC.Types.Char
                             (GHC.Types.C# '-')
                             (Foo.$sdropComment4 ds6_dfg ds8_Xg4));
                      '-' ->
                        case ds6_dfg of wild4_XS {
                          [] ->
                            GHC.Types.: @ GHC.Types.Char (GHC.Types.C# ' ') Foo.$sdropComment1;
                          : ds9_dfi ds10_dfj ->
                            case ds9_dfi of wild5_XY { GHC.Types.C# ds11_dfk ->
                            case ds11_dfk of ds12_Xgm {
                              __DEFAULT ->
                                GHC.Types.:
                                  @ GHC.Types.Char
                                  (GHC.Types.C# ' ')
                                  (GHC.Types.:
                                     @ GHC.Types.Char
                                     (GHC.Types.C# '-')
                                     (GHC.Types.:
                                        @ GHC.Types.Char
                                        (GHC.Types.C# '-')
                                        (Foo.$sdropComment4 ds10_dfj ds12_Xgm)));
                              ' ' -> GHC.Types.[] @ GHC.Types.Char
                            }}}}}}}}}
 
Foo.dropComment :: [GHC.Types.Char] -> [GHC.Types.Char]
[GlobalId]
[Arity 1
 NoCafRefs
 Str: DmdType S]
Foo.dropComment =
  \ (ds_df8 :: [GHC.Types.Char]) ->
    case ds_df8 of wild_B1 {
      [] -> GHC.Types.[] @ GHC.Types.Char;
      : ds1_df9 ds2_dfa ->
        case ds1_df9 of wild1_Xf { GHC.Types.C# ds3_dfb ->
        case ds3_dfb of ds4_Xfu {
          __DEFAULT ->
            GHC.Types.: @ GHC.Types.Char wild1_Xf (Foo.dropComment ds2_dfa);
          ' ' ->
            case ds2_dfa of wild2_Xo {
              [] ->
                GHC.Types.:
                  @ GHC.Types.Char wild1_Xf (GHC.Types.[] @ GHC.Types.Char);
              : ds5_dfc ds6_dfd ->
                case ds5_dfc of wild3_Xu { GHC.Types.C# ds7_dfe ->
                case ds7_dfe of ds8_XfM {
                  __DEFAULT ->
                    GHC.Types.:
                      @ GHC.Types.Char wild1_Xf (Foo.$sdropComment4 ds6_dfd ds8_XfM);
                  '-' ->
                    case ds6_dfd of wild4_XD {
                      [] -> GHC.Types.: @ GHC.Types.Char wild1_Xf Foo.$sdropComment;
                      : ds9_dff ds10_dfg ->
                        case ds9_dff of wild5_XJ { GHC.Types.C# ds11_dfh ->
                        case ds11_dfh of ds12_Xg4 {
                          __DEFAULT ->
                            GHC.Types.:
                              @ GHC.Types.Char
                              wild1_Xf
                              (GHC.Types.:
                                 @ GHC.Types.Char
                                 (GHC.Types.C# '-')
                                 (Foo.$sdropComment4 ds10_dfg ds12_Xg4));
                          '-' ->
                            case ds10_dfg of wild6_XS {
                              [] -> GHC.Types.: @ GHC.Types.Char wild1_Xf Foo.$sdropComment1;
                              : ds13_dfi ds14_dfj ->
                                case ds13_dfi of wild7_XY { GHC.Types.C# ds15_dfk ->
                                case ds15_dfk of ds16_Xgm {
                                  __DEFAULT ->
                                    GHC.Types.:
                                      @ GHC.Types.Char
                                      wild1_Xf
                                      (GHC.Types.:
                                         @ GHC.Types.Char
                                         (GHC.Types.C# '-')
                                         (GHC.Types.:
                                            @ GHC.Types.Char
                                            (GHC.Types.C# '-')
                                            (Foo.$sdropComment4 ds14_dfj ds16_Xgm)));
                                  ' ' -> GHC.Types.[] @ GHC.Types.Char
                                }}}}}}}}}}}
end Rec }

comment:5 Changed 9 years ago by rl

It might actually be better to decide whether to specialise or not depending on how an argument is used in the function instead of what it is bound to in a call. So for dropComment we'd see:

dropComment xs = case xs of
                   []   -> []
                   x:xs -> <big chunk of code>

Now, we might decide that specialising for dropComment (x:xs) isn't worth it because we will only get rid of the one case which doesn't buy us much. I have no idea what the exact heuristic should be but since we are worried about code size that should probably be the main criterion.

BTW, the five tiny specialisations are only kept alive by rules. For instance:

$sdropComment3 xs c = '-' : dropComment2 xs c

"SC:dropComment5" forall xs c.
  dropComment ('-' : '-': c : xs) = dropComment3 xs c

Since dropComment3 is very small and the only reference to it is on the rhs of the rule, I can easily imagine a pass which simply inlines it there and drops the binding.

comment:6 Changed 9 years ago by igloo

Milestone: 6.10 branch

comment:7 Changed 9 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:8 Changed 9 years ago by simonmar

Operating System: UnknownUnknown/Multiple

comment:9 Changed 9 years ago by igloo

Milestone: 6.10 branch6.12 branch

comment:10 Changed 7 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:11 Changed 7 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:12 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:13 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:14 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:15 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:16 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

Changed 5 years ago by morabbin

Attachment: DropComment.hs added

comment:17 Changed 5 years ago by morabbin

Type of failure: None/Unknown

Is this moot now? With GHC 7.6.2:

ghc --make -fforce-recomp -c -ddverbose-core2core -dshow-passes -O2 DropComment.hs

on the attached DropComment.hs produces (among other things):

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 70, types: 50, coercions: 0}

Rec {
lvl_rid :: [GHC.Types.Char]
[GblId]
lvl_rid = DropComment.dropComment (GHC.Types.[] @ GHC.Types.Char)

DropComment.dropComment [Occ=LoopBreaker]
  :: [GHC.Types.Char] -> [GHC.Types.Char]
[GblId, Arity=1, Str=DmdType S]
DropComment.dropComment =
  \ (ds_deO :: [GHC.Types.Char]) ->
    case ds_deO of _ {
      [] -> GHC.Types.[] @ GHC.Types.Char;
      : ds1_deP ds2_deQ ->
        case ds1_deP of wild1_X7 { GHC.Types.C# ds3_deR ->
        case ds3_deR of _ {
          __DEFAULT ->
            GHC.Types.:
              @ GHC.Types.Char wild1_X7 (DropComment.dropComment ds2_deQ);
          ' ' ->
            case ds2_deQ of wild2_Xa {
              [] -> GHC.Types.: @ GHC.Types.Char wild1_X7 lvl_rid;
              : ds5_deS ds6_deT ->
                case ds5_deS of _ { GHC.Types.C# ds7_deU ->
                case ds7_deU of _ {
                  __DEFAULT ->
                    GHC.Types.:
                      @ GHC.Types.Char wild1_X7 (DropComment.dropComment wild2_Xa);
                  '-' ->
                    case ds6_deT of _ {
                      [] ->
                        GHC.Types.:
                          @ GHC.Types.Char wild1_X7 (DropComment.dropComment wild2_Xa);
                      : ds9_deV ds10_deW ->
                        case ds9_deV of _ { GHC.Types.C# ds11_deX ->
                        case ds11_deX of _ {
                          __DEFAULT ->
                            GHC.Types.:
                              @ GHC.Types.Char wild1_X7 (DropComment.dropComment wild2_Xa);
                          '-' ->
                            case ds10_deW of _ {
                              [] ->
                                GHC.Types.:
                                  @ GHC.Types.Char wild1_X7 (DropComment.dropComment wild2_Xa);
                              : ds13_deY ds14_deZ ->
                                case ds13_deY of _ { GHC.Types.C# ds15_df0 ->
                                case ds15_df0 of _ {
                                  __DEFAULT ->
                                    GHC.Types.:
                                      @ GHC.Types.Char wild1_X7 (DropComment.dropComment wild2_Xa);
                                  ' ' -> GHC.Types.[] @ GHC.Types.Char
                                }
                                }
                            }
                        }
                        }
                    }
                }
                }
            }
        }
        }
    }
end Rec }

comment:18 Changed 3 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:19 in reply to:  17 Changed 3 years ago by thomie

Replying to morabbin:

Is this moot now?

The excessive specializations still show up with -fspec-constr-count greater than 5. The default is 3, and was introduced in commit e5adcaf845207c73da65cb44cff4ef83b76dd4a9. I believe this ticket is about coming up with a better heuristic.

Author: simonpj@microsoft.com <unknown>
Date:   Thu Mar 6 12:00:04 2008 +0000

    Improve SpecConstr for local bindings: seed specialisation from the calls

    ...    

      * New flag -fspec-constr-count=N sets the maximum number of specialisations
        for any single function to N.  -fno-spec-constr-count removes the limit.

    ...

This is the command I used to test:

ghc DropComment.hs -O -fspec-constr -ddump-simpl -fspec-constr-count=6

comment:20 Changed 3 years ago by thomie

Type of failure: None/UnknownRuntime performance bug

comment:21 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:22 Changed 3 years ago by thoughtpolice

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:23 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:24 Changed 21 months ago by thomie

Milestone: 8.0.1

comment:25 Changed 7 months ago by simonpj

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