Opened 8 years ago

Closed 4 years ago

#3698 closed bug (fixed)

Bad code generated for zip/filter/filter loop

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 the program:

zip_filter :: (Num a, Ord a) => a -> [a] -> [a] -> [a]
zip_filter x as bs = zipWith (+) (filter (<x) as) (filter (<x) bs)

GHC generates this:

poly_z_smp = \ (@ a_aiz) _ -> GHC.Types.[] @ a_aiz

T.zip_filter =
  \ (@ a_aiz) $dNum_ajm $dOrd_ajn eta_B3 eta_B2 eta_B1 ->
    letrec {
      go_smr :: [a_aiz] -> [a_aiz] -> [a_aiz]
      go_smr =
        \ (ds_ak5 :: [a_aiz]) ->
          case ds_ak5 of _ {
            [] -> poly_z_smp @ a_aiz;
            : y_aka ys_akb ->
              let {
                r_smt :: [a_aiz] -> [a_aiz]
                r_smt = go_smr ys_akb } in
              case GHC.Classes.< @ a_aiz $dOrd_ajn y_aka eta_B3 of _ {
                GHC.Bool.False -> r_smt;
                GHC.Bool.True ->
                  \ (ds_alR :: [a_aiz]) ->
                    case ds_alR of _ {
                      [] -> GHC.Types.[] @ a_aiz;
                      : y_alW ys_alX ->
                        GHC.Types.:
                          @ a_aiz (GHC.Num.+ @ a_aiz $dNum_ajm y_aka y_alW) (r_smt ys_alX)
                    }
              }
          }; } in
    go_smr
      eta_B2
      (GHC.List.filter
         @ a_aiz
         (\ (ds_djz :: a_aiz) ->
            GHC.Classes.< @ a_aiz $dOrd_ajn ds_djz eta_B3)
         eta_B1)

Eta-expanding go_smr would result in much better code.

Change History (10)

comment:1 Changed 8 years ago by guest

Another instance of the irritating arity fixpoint thing. See also #2762, #2902 and stuff at the top of http://hackage.haskell.org/trac/ghc/wiki/Status/SLPJ-Tickets

However, even if we had arity fixpoint detection, your function won't get eta-expanded. Reason: GHC.Classes.< might select an expensive operation from the dictionary. If this is the case then you might repeat tons of work. So to eta-expand safely you would need to also detect that go_smr is only ever used applied with a particular ds_ak5.

comment:2 Changed 8 years ago by rl

Hmm, yes, I guess it would be good to detect that, too. FWIW, essentially the same code is generated if we make zip_filter monomorphic:

zip_filter :: Double -> [Double] -> [Double] -> [Double]

Here, we know what (<) is so we don't have to detect this.

comment:3 Changed 8 years ago by igloo

Milestone: 6.14 branch

comment:4 Changed 7 years ago by igloo

Milestone: 6.14 branch6.14.1

comment:5 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:6 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:7 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:8 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: normallow

comment:9 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:10 Changed 4 years ago by nomeata

difficulty: Unknown
Resolution: fixed
Status: newclosed

The new callarity analysis successfully eta-expands the monomorphic code. For the polymorphic code, there is nothing we can do, as guest mentions in comment:1. So I guess this can be closed.

(I did not create a test case for this because these things are hard to test, and it is a standard application fo the callarity analysis, nothing tricky going on here.)

Note: See TracTickets for help on using tickets.