我怎么记忆？

Question

我编写了这个函数来计算Collat​​z序列,我看到执行的时间差别很大,这取决于我给它的旋转.显然它与"memoization"有关,但我很难理解它是什么以及它是如何工作的,不幸的是,关于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.

- 然后它只需要大约4秒钟ghc -O2,但我不会活得足够长,看不到它完整ghc -O2.

通过查看成本中心的详细信息可以ghc -prof -fprof-auto -O2看出,第一个版本进入了collatz大约一亿次,而修补后的版本只进行了大约一百五十万次.这一定是加速的原因,但我很难理解这种魔法的内在运作.我最好的想法是我们用O(log n)映射查找替换一部分昂贵的递归调用,但我不知道它是否为真,为什么它在很大程度上取决于一些被遗忘的编译器标志,而我认为,这种表演波动应该完全遵循语言.

我可以解释这里发生的事情,以及为什么性能与ghc -O2普通ghc版本之间的差异如此之大？

---

PS Stack Overflow上其他地方突出显示的自动备忘有两个要求:

• 使功能被记忆为顶级名称.

• 使一个函数被记忆为一个单形的函数.

根据这些要求,我重建remocollatz如下:

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

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

现在它是顶级和单态的.运行时间大约是11秒,而类似的单形table版本:

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这里第一种情况下应该执行的memoization 几乎比我的哑桌慢3倍.

Answer 1

我可以解释一下这里发生了什么,以及为什么ghc -O2和普通ghc构建之间的性能差异很大？

免责声明:这是猜测,未通过查看GHC核心输出进行验证.仔细回答这样做是为了验证下面概述的猜想.您可以尝试自己查看:添加-ddump-simpl到您的编译行,您将获得丰富的输出,详细说明GHC对您的代码所做的工作.

你写:

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

表达table mutate实际上并不依赖于x; 但它出现在方程式的右侧,x作为一个参数.因此,在没有优化的情况下,每次remocollatz调用时都会重新计算该表(大概甚至可以从计算内部table mutate).

通过优化,GHC通知table mutate不依赖于x,并将其浮动到自己的定义,有效地产生:

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

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

因此,对于整个程序运行,该表仅计算一次.

不知道为什么它[性能]在很大程度上取决于一些被遗忘的编译器标志,而我认为,这样的性能波动应该完全取决于语言.

对不起,但Haskell并没有这样做.语言定义清楚地说明了给定Haskell术语的含义,但没有说明计算该含义所需的运行时或内存性能.