haskell - 我该如何内存？

Question

我已经编写了这个计算 Collat​​z 序列的函数，并且我发现执行时间根据我给它的旋转而变化很大。显然它与一种叫做“记忆化”的东西有关，但我很难理解它是什么以及它是如何工作的，不幸的是，HaskellWiki 上的相关文章以及它链接到的论文都被证明不是是很容易克服的。他们讨论了高度外行人无法区分的树结构的相对性能的复杂细节，而我错过的一定是这些来源忽略提及的一些非常基本、非常琐碎的点。

这是代码。这是一个完整的程序，可以构建和执行。

module Main where

import Data.Function
import Data.List (maximumBy)

size :: (Integral a) => a
size = 10 ^ 6

-- Nail the basics.

collatz :: Integral a => a -> a
collatz n | even n = n `div` 2
          | otherwise = n * 3 + 1

recollatz :: Integral a => a -> a
recollatz = fix $ \f x -> if (x /= 1) 
                          then f (collatz x)
                          else x

-- Now, I want to do the counting with a tuple monad.

mocollatz :: Integral b => b -> ([b], b)
mocollatz n = ([n], collatz n)

remocollatz :: Integral a => a -> ([a], a)
remocollatz = fix $ \f x -> if x /= 1
                            then f =<< mocollatz x
                            else return x

-- Trivialities.

collatzLength :: Integral a => a -> Int
collatzLength x = (length . fst $ (remocollatz x)) + 1

collatzPairs :: Integral a => a -> [(a, Int)]
collatzPairs n = zip [1..n] (collatzLength <$> [1..n])

longestCollatz :: Integral a => a -> (a, Int)
longestCollatz n = maximumBy order $ collatzPairs n
  where
    order :: Ord b => (a, b) -> (a, b) -> Ordering
    order x y = snd x `compare` snd y

main :: IO ()
main = print $ longestCollatz size

使用 ghc -O2 大约需要 17 秒，没有 ghc -O2 大约需要 22 秒才能传递从 开始的最长 Collat​​z 序列的长度和种子任何低于 size 的点。

现在，如果我进行这些更改:

diff --git a/Main.hs b/Main.hs
index c78ad95..9607fe0 100644
--- a/Main.hs
+++ b/Main.hs
@@ -1,6 +1,7 @@
 module Main where

 import Data.Function
+import qualified Data.Map.Lazy as M
 import Data.List (maximumBy)

 size :: (Integral a) => a
@@ -22,10 +23,15 @@ recollatz = fix $ \f x -> if (x /= 1)
 mocollatz :: Integral b => b -> ([b], b)
 mocollatz n = ([n], collatz n)

-remocollatz :: Integral a => a -> ([a], a)
-remocollatz = fix $ \f x -> if x /= 1
-                            then f =<< mocollatz x
-                            else return x
+remocollatz :: (Num a, Integral b) => b -> ([b], a)
+remocollatz 1 = return 1
+remocollatz x = case M.lookup x (table mutate) of
+    Nothing -> mutate x
+    Just y  -> y
+  where mutate x = remocollatz =<< mocollatz x
+
+table :: (Ord a, Integral a) => (a -> b) -> M.Map a b
+table f = M.fromList [ (x, f x) | x <- [1..size] ]

 -- Trivialities.

-- 如果使用 ghc -O2，则只需大约 4 秒，但如果没有 ghc -O2，我就活不了多久看到它完成。

使用 ghc -prof -fprof-auto -O2 查看成本中心的详细信息，发现第一个版本进入 collat​​z 大约一亿次，而修补的版本则进入 collat​​z 大约一亿次一次——大约一百五十万次。这肯定是加速的原因，但我很难理解这个魔法的内部运作原理。我最好的想法是，我们用 O(log n) 映射查找替换一部分昂贵的递归调用，但我不知道这是否属实以及为什么它如此依赖于一些被遗弃的编译器标志，而正如我所见，这种性能波动应该完全由语言决定。

我能否解释一下这里发生的情况，以及为什么 ghc -O2 和普通 ghc 版本之间的性能差异如此之大？

<小时/>

附注Stack Overflow 上其他地方强调了实现自动记忆化的两个要求:

• 将要内存的函数设置为顶级名称。

• 将要内存的函数设为单态函数。

根据这些要求，我重建了 remocollat​​z，如下所示:

remocollatz :: Int -> ([Int], Int)
remocollatz 1 = return 1
remocollatz x = mutate x

mutate :: Int -> ([Int], Int)
mutate x = remocollatz =<< mocollatz x

现在它已经达到了最高级别和单态性。与类似的单态 table 版本相比，运行时间约为 11 秒:

remocollatz :: Int -> ([Int], Int)
remocollatz 1 = return 1
remocollatz x = case M.lookup x (table mutate) of
    Nothing -> mutate x
    Just y  -> y

mutate :: Int -> ([Int], Int)
mutate = \x -> remocollatz =<< mocollatz x

table :: (Int -> ([Int], Int)) -> M.Map Int ([Int], Int)
table f = M.fromList [ (x, f x) | x <- [1..size] ]

-- 运行时间不到 4 秒。

我想知道为什么内存 ghc 在第一种情况下的执行速度比我的哑表慢了近 3 倍。

Answer 1

Can I haz an explanation of what happens here, and why the performance differs so vastly between ghc -O2 and plain ghc builds?

免责声明:这是一个猜测，未通过查看 GHC 核心输出进行验证。仔细的回答将验证下面概述的猜想。您可以尝试自己查看它:将 -ddump-simpl 添加到您的编译行，您将获得大量输出，详细说明 GHC 对您的代码做了什么。

你写:

remocollatz x = {- ... -} table mutate {- ... -}
  where mutate x = remocollatz =<< mocollatz x

表达式table mutate实际上并不依赖于x；但它出现在以 x 作为参数的方程的右侧。因此，如果不进行优化，每次调用 remocollat​​z 时都会重新计算该表(可能甚至是在 table mutate 的计算内部)。

通过优化，GHC 注意到 table mutate 不依赖于 x，并将其 float 到自己的定义，从而有效地生成:

fresh_variable_name = table mutate
  where mutate x = remocollatz =<< mocollatz x

remocollatz x = case M.lookup x fresh_variable_name of
    {- ... -}

因此，在整个程序运行过程中，该表仅计算一次。

don't know why it [the performance] depends so much on some godforsaken compiler flags, while, as I see it, such performance swings should all follow solely from the language.

抱歉，Haskell 不是这样工作的。语言定义清楚地说明了给定 Haskell 术语的含义，但没有说明计算该含义所需的运行时或内存性能。