haskell - 为什么添加INLINE会使我的程序变慢

我一直在寻找一种可以在无限列表上使用的foldl的情况，这种情况下您无法获得 protected 递归，但可能取决于第一个参数而第二个参数可能无法使用。

例如乘法，通常需要参数和 protected 递归的乘法不起作用，但是如果第一个参数为0，则可能会短路。

所以我写了以下函数:

foldlp :: (b -> a -> b) -> (b -> Bool) -> b -> [a] -> b
foldlp f p = go where
    go b [] = b
    go b (x : xs)
        | p b = go (f b x) xs
        | otherwise = b

并使用我的自定义短路乘法功能对其进行了测试:

 mult :: Integer -> Integer -> Integer
 mult 0 _ = 0
 mult x y = x * y

 main :: IO ()
 main = print . <test_function>

我通过-prof -fprof-auto -O2，+RTS -p获得的结果是:

foldlp mult (/= 0) 1 $ replicate (10 ^ 7) 1
total time = 0.40 secs
total alloc = 480,049,336 bytes

foldlp mult (`seq` True) 1 $ replicate (10 ^ 7) 1
total time = 0.37 secs
total alloc = 480,049,336 bytes

foldl' mult 1 $ replicate (10 ^ 7) 1
total time = 0.37 secs
total alloc = 480,049,352 bytes

foldl mult 1 $ replicate (10 ^ 7) 1
total time = 0.74 secs
total alloc = 880,049,352 bytes

foldr mult 1 $ replicate (10 ^ 7) 1
total time = 0.87 secs
total alloc = 880,049,336 bytes

这是非常有前途的，因为我的自定义函数允许灵活的严格性类型，并且还可以在无限列表上使用

第一个示例一旦击中0，就会终止，foldr也会终止，但是foldr慢得多。

它避免了元组中的重击之类的问题，因为((1 + 2) + 3, (10 + 20) + 30)从技术上讲是WHNF中的对象，打破了foldl'。

您可以使用foldl重新获得flip foldl (const True)，使用foldl' seq flip foldl (重新获得True)。这样做似乎可以重新获得原始受限功能的性能特征。

因此，作为旁注，我认为foldlp将是Foldable的一个有值(value)的补充。

但是我的实际问题是，为什么当我添加{-# INLINE foldlp #-}时，函数的性能显着下降，给了我:

foldlp mult (/= 0) 1 $ replicate (10 ^ 7) 1
total time = 0.67 secs
total alloc = 800,049,336 bytes

所以我真正的问题是为什么会这样。我认为内联的缺点是代码膨胀，对运行时性能和增加的内存使用没有明显的负面影响。

最佳答案

根据the GHC docs的指示，INLINE编译指示阻止其他编译器优化，以使重写规则仍然生效。

所以我的猜测是，通过使用INLINE删除了一些优化，GHC就会应用来使您的代码更快。

经过一番探索(在编译中使用-ddump-simpl)，我发现了GHC执行的优化。为此，我研究了带内联和不带内联的foldlp的核心:

内联:

foldlp =
  \ (@ b_a10N)
    (@ a_a10O)
    (eta_B2 :: b_a10N -> a_a10O -> b_a10N)
    (eta1_B1 :: b_a10N -> Bool)
    (eta2_X3 :: b_a10N)
    (eta3_X5 :: [a_a10O]) ->
    letrec {
      go_s1Ao [Occ=LoopBreaker] :: b_a10N -> [a_a10O] -> b_a10N
      [LclId, Arity=2, Str=DmdType <L,U><S,1*U>]
      go_s1Ao =
        \ (b1_avT :: b_a10N) (ds_d1xQ :: [a_a10O]) ->
        -- Removed the actual definition of go for brevity,
        -- it's the same in both cases
          }; } in
    go_s1Ao eta2_X3 eta3_X5

非内联:

foldlp =
  \ (@ b_a10N)
    (@ a_a10O)
    (f_avQ :: b_a10N -> a_a10O -> b_a10N)
    (p_avR :: b_a10N -> Bool) ->
    letrec {
      go_s1Am [Occ=LoopBreaker] :: b_a10N -> [a_a10O] -> b_a10N
      [LclId, Arity=2, Str=DmdType <L,U><S,1*U>]
      go_s1Am =
        \ (b1_avT :: b_a10N) (ds_d1xQ :: [a_a10O]) ->
        -- Removed the actual definition of go for brevity,
        -- it's the same in both cases
          }; } in
    go_s1Am

相关的区别在最后一行。优化器取消了实际上必须调用foldlp来调用go的步骤，并且只是从foldlp中创建了一个带有两个参数的函数，该函数返回了一个带有两个参数的函数。使用内联时，不会执行此优化，并且内核看起来与您编写的代码完全相同。

我通过编写foldlp的三个变体来验证这一点:

module Main where

foldlp :: (b -> a -> b) -> (b -> Bool) -> b -> [a] -> b
foldlp f p = go where
      go b [] = b
      go b (x : xs)
        | p b = go (f b x) xs
        | otherwise = b

{-# INLINE foldlpInline #-}
foldlpInline :: (b -> a -> b) -> (b -> Bool) -> b -> [a] -> b
foldlpInline f p = go where
      go b [] = b
      go b (x : xs)
        | p b = go (f b x) xs
        | otherwise = b


{-# INLINE foldlp' #-} -- So that the code is not optimized
foldlp' b [] = b
foldlp' b (x : xs)
        | (/= 0) b = foldlp' (mult b x) xs
        | otherwise = b

mult :: Integer -> Integer -> Integer
mult 0 _ = 0
mult x y = x * y

--main = print $ foldlp mult (/= 0) 1 $ replicate (10 ^ 7) 1
--main = print $ foldlpInline mult (/= 0) 1 $ replicate (10 ^ 7) 1
main = print $ foldlp' 1 $ replicate (10 ^ 7) 1

结果是:

第一种情况(正常的非内联):

./test  0,42s user 0,01s system 96% cpu 0,446 total

第二种情况(内联):

./test  0,83s user 0,02s system 98% cpu 0,862 total

第三种情况(编译器为非内联程序生成的内容)

./test  0,42s user 0,01s system 99% cpu 0,432 total

关于haskell - 为什么添加INLINE会使我的程序变慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39991318/