Opened 7 years ago

Last modified 7 months ago

#6070 new bug

Fun with the demand analyser

Reported by: simonpj Owned by: simonpj
Priority: normal Milestone:
Component: Compiler Version: 7.4.1
Keywords: DemandAnalysis Cc: stefan@…, carter.schonwald@…
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 (last modified by simonpj)

Max writes: I've been trying to speed up the supercompiler, and in the process I've noticed some infelicities in the demand analyser that might be worth looking at. One is #5949. The other is:

Infelicity 2: a case where demand summarisation hurts us

I found practical examples where summarising the demand transfomer of a function as a single strictness signature hurt us. The examples were code like:

h :: (Int, Int) -> Int -> (Int, Int)
h x y = if y > 10
         then x
         else h (case h x 0 of (y1, y2) -> (y2, y1)) (y + 1)

If, at the innermost use of h, we re-analyse h in the demand C(C(U(LL))) rather than just unleashing the vanilla DmdSig computed from the demand C(C(S)) then we can unbox the pair argument. Currently GHC just gives h the DmdType SU(L) which doesn't eliminate the allocation of the pair at all.

This situation occurs in practice with code like:

c :: M.Map Int Int -> (Int, Int)
c m = M.foldrWithKey (\k v (a, b) -> if k + v > 2 then (a, b) else (b,
a)) (0, 1) m

The difference from my earlier example d is that I'm using the version of foldrWithKey that doesn't call seq. Current GHC generates this inner loop:

Rec {
CPR2.c_go2 [Occ=LoopBreaker]
  :: (GHC.Types.Int, GHC.Types.Int)
     -> Data.Map.Base.Map GHC.Types.Int GHC.Types.Int
     -> (GHC.Types.Int, GHC.Types.Int)
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType U(L*)S,
 Unf=OtherCon []]
CPR2.c_go2 =
  \ (z_spW :: (GHC.Types.Int, GHC.Types.Int))
    (ds_spU :: Data.Map.Base.Map GHC.Types.Int GHC.Types.Int) ->
    case ds_spU of _ {
      Data.Map.Base.Tip -> z_spW;
      Data.Map.Base.Bin rb_sqq kx_sq2 x_sq9 l_sqj r_sq5 ->
        case kx_sq2 of _ { GHC.Types.I# x1_sqc ->
        case CPR2.c_go2 z_spW r_sq5 of wild2_sqk { (a_sqh, b_sqg) ->
        case x_sq9 of _ { GHC.Types.I# y_sqd ->
        case GHC.Prim.+# x1_sqc y_sqd of sat_sqp { __DEFAULT ->
        case GHC.Prim.># sat_sqp 2 of _ {
          GHC.Types.False ->
            let {
              sat_sqo :: (GHC.Types.Int, GHC.Types.Int)
              [LclId]
              sat_sqo = (b_sqg, a_sqh) } in
            CPR2.c_go2 sat_sqo l_sqj;
          GHC.Types.True -> CPR2.c_go2 wild2_sqk l_sqj
        }
        }
        }
        }
        }
    }
end Rec }

I implemented this but the overhead of reanalysing a function at each occurrence site is prohibitive (with my changes paraffins took 2.5s to compile instead of 0.3s). It does fix the problem though.

A scheme like in "stricterness more relevant" but with let-binding that is polymorphic in the use-site demand might be able to detect the extra strictness here. I think Stefan Holdermanns has a paper describing such a system. But this is anyway much harder to fix than my first infelicity.

Change History (10)

comment:1 Changed 7 years ago by stefan

Cc: stefan@… added

comment:2 Changed 7 years ago by igloo

Milestone: 7.8.1
Owner: set to simonpj

comment:3 Changed 7 years ago by carter

Cc: carter.schonwald@… added

comment:4 Changed 6 years ago by nomeata

The first issue is also reported as #5949. So I guess this ticket should track the second infelicity. Unfortunately, I am not able to edit the ticket description, otherwise I’d remove it here.

comment:5 Changed 6 years ago by simonpj

Description: modified (diff)

comment:6 Changed 5 years ago by thoughtpolice

Milestone: 7.8.37.10.1

Moving to 7.10.1.

comment:7 Changed 5 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:8 Changed 4 years ago by thomie

Milestone: 7.12.1
Type of failure: None/UnknownRuntime performance bug

comment:9 Changed 18 months ago by osa1

Just tried with GHC HEAD, unused arg in join point in Unboxed.hs vanishes with late demand analysis.

let-no-escape {
  $j_s4wc [Occ=Once*!T[2], Dmd=<C(C(S)),1*C1(C1(U(U,U)))>]
    :: GHC.Prim.Int#
       -> GHC.Types.Int
       -> (# Unboxed.FingerTree
               Unboxed.Size (Unboxed.Node Unboxed.Size c_s44z),
             Unboxed.FingerTree
               Unboxed.Size (Unboxed.Node Unboxed.Size c_s44z) #)
  [LclId[JoinId(2)], Arity=2, Str=<S,U><L,A>, Unf=OtherCon []] = ...

After:

let-no-escape {
  $w$j_s4BK [InlPrag=NOUSERINLINE[0],
             Occ=Once*!T[1],
             Dmd=<C(S),1*C1(U(U,U))>]
    :: GHC.Prim.Int#
       -> (# Unboxed.FingerTree
               Unboxed.Size (Unboxed.Node Unboxed.Size c_s45o),
             Unboxed.FingerTree
               Unboxed.Size (Unboxed.Node Unboxed.Size c_s45o) #)
  [LclId[JoinId(1)], Arity=1, Str=<S,U>, Unf=OtherCon []] = ...
Version 0, edited 18 months ago by osa1 (next)

comment:10 Changed 7 months ago by simonpj

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