haskell 当一个函数被多次调用时，GHC什么时候会缓存局部定义的计算

dbf7pr2w 于 2023-03-30 发布在其他

关注(0)|答案(1)|浏览(125)

考虑以下定义：

--------------------------------------------------------------------------------
-- Computing the sum inside, without lambdas
--------------------------------------------------------------------------------

in_no_lambda :: [Int] -> [Int] -> [Int]
in_no_lambda xs = fmap (aux_in_no_lambda xs)

aux_in_no_lambda :: [Int] -> Int -> Int
aux_in_no_lambda xs i = let sum_xs = {-# SCC "sum_in_no_lambda" #-} sum xs
                        in sum_xs + i

--------------------------------------------------------------------------------
-- Computing the sum inside, using lambdas
--------------------------------------------------------------------------------
in_lambda :: [Int] -> [Int] -> [Int]
in_lambda xs = fmap (aux_in_lambda xs)

aux_in_lambda :: [Int] -> Int -> Int
aux_in_lambda xs = let sum_xs = {-# SCC "sum_in_lambda" #-} sum xs
                   in \i -> sum_xs + i

--------------------------------------------------------------------------------
-- Computing the sum outside
--------------------------------------------------------------------------------
out :: [Int] -> [Int] -> [Int]
out xs = fmap (aux_out sum_xs)
  where sum_xs = {-# SCC "sum_out" #-} sum xs

aux_out :: Int -> Int -> Int
aux_out sum_xs i = sum_xs + i

虽然这些都是等效的，但它们的运行时性能（显然）不是：

COST CENTRE          MODULE                SRC                       no.     entries  %time %alloc   %time %alloc

MAIN                 MAIN                  <built-in>                122           0   14.1    0.0   100.0  100.0
 CAF                 Main                  <entire-module>           243           0    0.0    0.0    85.9  100.0
  main               Main                  app/Main.hs:(6,1)-(12,22) 244           1   11.8   18.7    85.9  100.0
   in_lambda         Lib                   src/Lib.hs:26:1-38        248           1   20.6   27.1    26.3   27.1
    sum_in_lambda    Lib                   src/Lib.hs:29:61-66       249           1    5.7    0.0     5.7    0.0
   in_no_lambda      Lib                   src/Lib.hs:16:1-44        246           1   22.2   27.1    22.9   27.1
    sum_in_no_lambda Lib                   src/Lib.hs:19:69-74       247    10000001    0.8    0.0     0.8    0.0
   out               Lib                   src/Lib.hs:(36,1)-(37,45) 250           1   19.2   27.1    24.9   27.1
    sum_out          Lib                   src/Lib.hs:37:40-45       251           1    5.7    0.0     5.7    0.0

上面的配置文件数据提出了两个主要问题：
1.编译器是否在in_no_lambda和in_lambda中应用了不同的规则，导致sum_xs在后一种情况下只计算一次？如果是，这些规则是什么？（以及什么是经验验证的简单方法）
1.多次输入成本中心sum_in_no_lambda，但在此成本中心花费的%time似乎低于仅输入一次的sum_in_lambda和sum_in_lambda！如何解释？

haskell

来源：https://stackoverflow.com/questions/75838460/when-would-ghc-cache-the-computation-of-a-local-definition-in-a-function-when-ca

1条答案

按热度按时间

gev0vcfq1#

1.不，in_no_lambda和in_lambda都被GHC优化，以计算fmap“外部”的总和。即使对于in_no_lambda也会发生这种情况，这是因为完全的惰性优化。
1.我不是很熟悉成本中心的内部工作原理，但看看它的行为，我相信它只是计算一次总和，然后计算结果被查找了多少次，所以所有这些条目中只有一个进行了真实的的计算。
我认为当你看到简化的Core时，运行时间的实际差异会变得更加清晰（我已经清理了一点，几乎是真实的Haskell代码）：

go w ww =
  case w of
    [] -> I# ww
    y : ys -> case y of I# y1 -> go ys (ww +# y1)

in_lambda xs =
  map (let sum_xs = go xs 0# in \i -> $fNumInt_$c+ sum_xs i)

in_no_lambda xs eta
  let lvl = go xs 0# in
  map
    (\i -> case lvl of I# x -> case i of I# y -> I# (x +# y))
    eta

主要区别似乎是in_lambda包含对$fNumInt_$c+的调用（$fNumInt_$c+是专用于Int类型的+函数），而in_no_lambda直接使用原语+#，这节省了一次函数调用的开销。
我原以为这可以解释性能差异，但事实证明这一定是其他原因。我们可以通过手动使用+#原语来证明这不能解释性能差异：

import GHC.Exts

[..]

aux_in_lambda :: [Int] -> Int -> Int
aux_in_lambda xs = let sum_xs = {-# SCC "sum_in_lambda" #-} sum xs
                   in \i -> case sum_xs of I# x -> case i of I# y -> I# (x +# y)

这不会加快in_lambda函数的速度。
实际上，我可以在STG转储中使其完全等同于in_no_lambda，并且运行时间的差异仍然显示在配置文件中。在这一点上，我非常确定它一定是成本中心配置机制本身的某种奇怪之处。我确信这种时间差异不会出现在真实的的基准测试中。
你可能也注意到了一件事，in_lambda在map的参数中有let sum_xs = ...。然而，这根本不是问题，因为它不是在lambda下，因此只会被计算一次。你可以在STG表示中更清楚地看到这一点（这次我没有修改代码）：

in_lambda =
    CCS_DONT_CARE \r [xs]
        let { sum_xs = CCCS \u [] $wgo1 xs 0#; } in
        let { sat = CCCS \r [i] $fNumInt_$c+ sum_xs i; } in  map sat;

它首先分配sum_xs值，然后是sat函数，最后作为第一个参数传递给map（我也不知道这些CCS_DONT_CARE和CCCS到底是什么，除了它们与成本中心机制有关。

赞(0）回复(0）举报 2023-03-30

我来回答

haskell 当一个函数被多次调用时，GHC什么时候会缓存局部定义的计算

1条答案

相关问题

热门标签

最新问答