Opened 8 years ago

Closed 4 years ago

#3697 closed bug (fixed)

Method selectors aren't floated out of loops

Reported by: rl Owned by:
Priority: low Milestone: 7.6.2
Component: Compiler Version: 6.13
Keywords: Cc:
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

Here is a small example:

foo :: Num a => [a] -> [a]
foo as = filter (/=0) (map (\x -> x-x) as)

Here is the code that the current HEAD generates for the loop:

go_smy =
  \ (ds_akN :: [a_aiw]) ->
    case ds_akN of _ {
      [] -> GHC.Types.[] @ a_aiw;
      : y_akS ys_akT ->
        let {
          x_smA :: a_aiw
          x_smA = GHC.Num.- @ a_aiw $dNum_ajk y_akS y_akS } in
        case GHC.Classes./= @ a_aiw lvl_smu x_smA lit_smw of _ {
          GHC.Bool.False -> go_smy ys_akT;
          GHC.Bool.True -> GHC.Types.: @ a_aiw x_smA (go_smy ys_akT)
        }

Note that the Eq dictionary is inspected by (/=) in every loop iteration. Floating out GHC.Classes./= @ a_aiw lvl_smu (and, perhaps, GHC.Num.- @ a_aiw $dNum_ajk) should solve this. In fact, I wonder why that isn't happening already. Do method selectors have a wrong arity?

FWIW, in GHC 6.10 LiberateCase moves the method selection out of the loop (not ideal, but it gets the job done) so NoSlow shows this as a slight performance regression.

Change History (9)

comment:1 Changed 8 years ago by simonpj

It's hard to know what the right thing to do here is. At the moment GHC treats (op d) as cheap, where op is a class operation and d is a dictionary. If we don't, we get lots of

f = \d. let h1 = op1 d in \x. ...(h1 x)...

So 'f' gets arity 1. And indeed there is some sharing that would be gotten if you had map (f dInt) xs, because the selection from dInt would happen just once. But in general it's much better to have one function with arity 2 rather than two functions of arity 1.

Same thing for a recursive function. If method selection isn't cheap you get lots of

f = \d. let h1 = op1 d
        in letrec fr = \x. ...(h1 x)...fr x'...
        in fr

If you inline h1, we can make f have arity 2.

So it's a hard call. I suppose that what we ultimately want is: share the method selection if doing so doesn't decrease arity. That could be done by running float-out near the end of optimisation (which it is) with a few twiddles to seek out those method selections. Worth thinking about.

Simon

comment:2 Changed 8 years ago by igloo

Milestone: 6.14 branch

comment:3 Changed 8 years ago by igloo

Milestone: 6.14 branch6.14.1

comment:4 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:5 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:6 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:7 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: normallow

comment:8 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:9 Changed 4 years ago by nomeata

difficulty: Unknown
Resolution: fixed
Status: newclosed

With todays HEAD, I get good code:

T3697.foo =
  \ (@ a)
    ($dEq :: GHC.Classes.Eq a)
    ($dNum :: GHC.Num.Num a)
    (as :: [a]) ->
    let {
      ds :: a
      [LclId, Str=DmdType]
      ds = GHC.Num.fromInteger @ a $dNum T3697.foo1 } in
    let {
      lvl :: a -> a -> GHC.Types.Bool
      [LclId, Str=DmdType]
      lvl = GHC.Classes./= @ a $dEq } in
    let {
      lvl1 :: a -> a -> a
      [LclId, Str=DmdType]
      lvl1 = GHC.Num.- @ a $dNum } in
    letrec {
      go [Occ=LoopBreaker] :: [a] -> [a]
      [LclId, Arity=1, Str=DmdType <S,1*U>]
      go =
        \ (ds1 :: [a]) ->
          case ds1 of _ [Occ=Dead] {
            [] -> GHC.Types.[] @ a;
            : y ys ->
              let {
                x :: a
                [LclId, Str=DmdType]
                x = lvl1 y y } in
              case lvl x ds of _ [Occ=Dead] {
                GHC.Types.False -> go ys;
                GHC.Types.True -> GHC.Types.: @ a x (go ys)
              }
          }; } in
    go as

Given the age of the bug, I don’t dare to guess what has fixed this. Also, hard to make a useful testcase here.

Note: See TracTickets for help on using tickets.