foldl as foldr to get list fusion

Daniel Fischer daniel.is.fischer at googlemail.com
Fri Oct 14 19:33:08 CEST 2011


On Friday 14 October 2011, 02:00:39, Bas van Dijk wrote:
> Hello,
> 
> Is there any reason other than history that foldl and foldl' are not
> defined in terms of foldr?

Worst-case efficiency.

> 
> If we define them in terms of foldr like:
> 
> foldl f z xs = foldr (\x y -> \z' -> let z'' = z' `f` x in y z'') id xs
> z {-# INLINE foldl #-}
> 
> foldl' f z xs = foldr (\x y -> \z' -> let !z'' = z' `f` x in y z'') id
> xs z {-# INLINE foldl' #-}
> 
> we can benefit from list fusion.

But if it doesn't happen, we get terrible code.

> 
> For example if we define sum as:
> 
> sum :: Num a => [a] -> a
> sum = foldl (+) 0
> 
> then building the following program with -O2:
> 
> fuse = sum (replicate 1000000 1 ++ replicate 5000 1 :: [Int])
> 
> yields the following totally fused core:
> 
> fuse :: Int
> fuse = case $wxs 1000000 0 of ww_ssn {
>          __DEFAULT -> I# ww_ssn
>        }
> 
> $wxs :: Int# -> Int# -> Int#
> $wxs =
>   \ (w_ssg :: Int#) (ww_ssj :: Int#) ->
>     case <=# w_ssg 1 of _ {
>       False -> $wxs (-# w_ssg 1) (+# ww_ssj 1);
>       True  -> $wxs1_rsB 5000 (+# ww_ssj 1)
>     }
> 
> $wxs1_rsB :: Int# -> Int# -> Int#
> $wxs1_rsB =
>   \ (w_ss5 :: Int#) (ww_ss8 :: Int#) ->
>     case <=# w_ss5 1 of _ {
>       False -> $wxs1_rsB (-# w_ss5 1) (+# ww_ss8 1);
>       True  -> +# ww_ss8 1
>     }

If you try something less transparent than replicate and use a less 
convenient type than Int, you get core like

===================================
FuseL.fuse_wild :: GHC.Integer.Type.Integer
[GblId,
 Caf=NoCafRefs,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [] 10 110}]
FuseL.fuse_wild = GHC.Integer.Type.S# 1

Rec {
go_rwH
  :: GHC.Integer.Type.Integer
     -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType S]
go_rwH =
  \ (x_avj :: GHC.Integer.Type.Integer) ->
    let {
      y_abw [Dmd=Just L]
        :: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
      [LclId, Str=DmdType]
      y_abw = go_rwH (GHC.Integer.plusInteger x_avj FuseL.fuse_wild) } in
    case x_avj of wild_dvr {
      GHC.Integer.Type.S# i_dvt ->
        case GHC.Prim.># i_dvt 5000 of _ {
          GHC.Types.False ->
            \ (z'_abx :: GHC.Integer.Type.Integer) ->
              y_abw (GHC.Integer.plusInteger z'_abx wild_dvr);
          GHC.Types.True -> GHC.Base.id @ GHC.Integer.Type.Integer
        };
      GHC.Integer.Type.J# s_dvG d_dvH ->
        case {__pkg_ccall_GC integer-gmp integer_cmm_cmpIntegerIntzh 
GHC.Prim.Int#
                                                        -> 
GHC.Prim.ByteArray#
                                                        -> GHC.Prim.Int#
                                                        -> 
GHC.Prim.Int#}_dvL
               s_dvG d_dvH 5000
        of wild2_dvO { __DEFAULT ->
        case GHC.Prim.># wild2_dvO 0 of _ {
          GHC.Types.False ->
            \ (z'_abx :: GHC.Integer.Type.Integer) ->
              y_abw (GHC.Integer.plusInteger z'_abx wild_dvr);
          GHC.Types.True -> GHC.Base.id @ GHC.Integer.Type.Integer
        }
        }
    }
end Rec }

n_rwI :: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
[GblId, Str=DmdType]
n_rwI = go_rwH FuseL.fuse_wild

Rec {
FuseL.fuse_go [Occ=LoopBreaker]
  :: GHC.Integer.Type.Integer
     -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
[GblId, Arity=1, Str=DmdType S]
FuseL.fuse_go =
  \ (x_avj :: GHC.Integer.Type.Integer) ->
    let {
      y_abw [Dmd=Just L]
        :: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
      [LclId, Str=DmdType]
      y_abw =
        FuseL.fuse_go (GHC.Integer.plusInteger x_avj FuseL.fuse_wild) } in
    case x_avj of wild_dvr {
      GHC.Integer.Type.S# i_dvt ->
        case GHC.Prim.># i_dvt 1000000 of _ {
          GHC.Types.False ->
            \ (z'_abx :: GHC.Integer.Type.Integer) ->
              y_abw (GHC.Integer.plusInteger z'_abx wild_dvr);
          GHC.Types.True -> n_rwI
        };
      GHC.Integer.Type.J# s_dvG d_dvH ->
        case {__pkg_ccall_GC integer-gmp integer_cmm_cmpIntegerIntzh 
GHC.Prim.Int#
                                                        -> 
GHC.Prim.ByteArray#
                                                        -> GHC.Prim.Int#
                                                        -> 
GHC.Prim.Int#}_dvL
               s_dvG d_dvH 1000000
        of wild2_dvO { __DEFAULT ->
        case GHC.Prim.># wild2_dvO 0 of _ {
          GHC.Types.False ->
            \ (z'_abx :: GHC.Integer.Type.Integer) ->
              y_abw (GHC.Integer.plusInteger z'_abx wild_dvr);
          GHC.Types.True -> n_rwI
        }
        }
    }
end Rec }

FuseL.fuse2 :: GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 20 0}]
FuseL.fuse2 = FuseL.fuse_go FuseL.fuse_wild

FuseL.fuse :: GHC.Integer.Type.Integer
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 20 0}]
FuseL.fuse = FuseL.fuse2 FuseL.fuse1
===================================

for

fuse = sum ([1 .. 1000000] ++ [1 .. 5000] :: [Integer])

You do NOT want that.

Incidentally, the core generated for foldl and foldl' as defined above is 
fine, it's the inlining and failure to fuse well that wreaks havoc.




More information about the Libraries mailing list