algorithm - Haskell 中惰性求值和严格求值的比较

Question

我在 Haskell 上实现了 Winograd 算法，由于计算严格，试图加快算法速度。在这一点上我成功了，但我完全不明白为什么增加严格性后它开始工作得更快。由于我的这个算法的代码足够大，我写了两个小函数来演示这个问题。

module Main where
import qualified Data.Vector as V
import qualified Data.Matrix as M

import Control.DeepSeq
import Control.Exception
import System.Clock
import Data.Time

matrixCtor x y size = M.matrix size size $ \(i,j) -> x*i+y*j

group v s = foldl (\acc i ->acc + V.unsafeIndex v i * V.unsafeIndex v (i+1)) 0 [0,2..s-1]

size = 3000 :: Int

testWithForce :: IO ()
testWithForce = do
  let a = matrixCtor 2 1 size
  evaluate $ force a

  start <- getCurrentTime

  let c = V.generate size $ \j -> M.getCol (j+1) a
  evaluate $ force c
  let d = foldl (\acc i ->acc + group (V.unsafeIndex c i) size) 0 [0,1..(size-1)]
  evaluate $ force d

  end <- getCurrentTime
  print (diffUTCTime end start)


testWithoutForce :: IO ()
testWithoutForce = do
  let a = matrixCtor (-2) 1 size
  evaluate $ force a

  start <- getCurrentTime

  let c = V.generate size $ \j -> M.getCol (j+1) a
  let d = foldl (\acc i ->acc + group (V.unsafeIndex c i) size) 0 [0,1..(size-1)]
  evaluate $ force d

  end <- getCurrentTime
  print (diffUTCTime end start)

main :: IO ()
main = do
  testWithForce
  testWithoutForce

在算法的实现中，矩阵在使用前被计算，就像这里一样。在函数 testWithForce 中，我在使用它之前计算值 c。在这种情况下，函数 testWithForce 比函数 testWithoutForce 运行得更快。我得到了以下结果:

0.945078s --testWithForce
1.785158s --testWithoutForce

我只是不明白为什么在这种情况下严格会加快工作速度。

Answer 1

请原谅没有回答，但一定要控制 GC:看起来第二个函数可能会承受前一个函数的 GC，从而扩大差异。

我可以重现您所看到的:

$ ghc -O3 --make foo.hs && ./foo
[1 of 1] Compiling Main             ( foo.hs, foo.o )
Linking foo ...
1.471109207s
2.001165795s

然而，当我翻转测试的顺序时，结果是不同的:

main = do
  testWithoutForce 
  testWithForce

$  ghc -O3 --make foo.hs && ./foo
1.626452918s
1.609818958s

所以我在每次测试之间进行了 main GC:

import System.Mem

main = do
  performMajorGC
  testWithForce
  performMajorGC
  testWithoutForce

强制的仍然更快，但差异大大减小了:

1.460686986s
1.581715988s