使用ST monad

Question

在博客文章http://galvanist.com/post/83741037068/adding-badly-under-python-julia-go中，作者使用一个简单的算法来比较各种语言(包括Haskell)的性能。在Haskell示例中，作者使用了一个递归函数。作为练习，我想使用ST monad来允许本地可变状态。这是可行的，但是递归函数比我使用ST monad的函数要快得多。

递归函数-

peanoAdd :: Int -> Int -> Int
peanoAdd 0 y = y
peanoAdd x y = peanoAdd (x - 1) (y + 1)

main :: IO ()
main = do
    let a = 64000000 :: Int
    let b = 64000000 :: Int
    let n = peanoAdd a b
    print n

128000000

real    0m0.583s
user    0m0.480s
sys     0m0.096s

用圣·莫纳德-

import Control.Monad.ST
import Data.STRef
import Control.Monad.Loops

peanoAdd :: Int -> Int -> Int
peanoAdd x y = runST $ do
    x' <- newSTRef x
    y' <- newSTRef y
    whileM_ (do x'' <- readSTRef x'
                return $ x'' /= 0)
            (do modifySTRef x' (subtract 1)
                modifySTRef y' (+1))
    readSTRef y'

main :: IO ()
main = do
    let a = 64000000 :: Int
    let b = 64000000 :: Int
    let n = peanoAdd a b
    print n

128000000

real    0m17.837s
user    0m16.412s
sys     0m1.424s

是否有什么事情是我做的明显的错误，这是损害的表现在ST单例？(PS. )我使用Stack和两个项目的简单模板。)

Answer 1

ST程序运行缓慢的原因之一是您使用的是, which is non-strict

请注意，modifySTRef没有严格应用该函数。这意味着，如果程序多次调用modifySTRef，但很少使用该值，那么内存中的块就会堆积，从而导致空间泄漏。当使用STRef作为计数器时，这是常见的错误。例如，以下内容将泄漏内存并可能产生堆栈溢出： 打印$ runST $ do <- newSTRef 0 replicateM_ 1000000 $ modifySTRef ref (+1) readSTRef ref

您的x'每个循环强制一次，但是直到print才强制使用y'，因此形成了一个巨大的块链。

在我的膝上型电脑上使用modifySTRef'对其进行基准测试表明，严格性可以改善运行时(尽管两者仍然输给了递归版本)。

benchmarking rec
time                 7.896 ms   (7.602 ms .. 8.269 ms)
                     0.992 R²   (0.988 R² .. 0.997 R²)
mean                 7.842 ms   (7.724 ms .. 8.001 ms)
std dev              404.5 μs   (303.9 μs .. 523.8 μs)
variance introduced by outliers: 25% (moderately inflated)

benchmarking st
time                 18.44 ms   (17.84 ms .. 19.01 ms)
                     0.996 R²   (0.993 R² .. 0.998 R²)
mean                 18.03 ms   (17.79 ms .. 18.41 ms)
std dev              750.4 μs   (528.0 μs .. 1.110 ms)
variance introduced by outliers: 16% (moderately inflated)

benchmarking st'
time                 9.191 ms   (9.028 ms .. 9.437 ms)
                     0.996 R²   (0.992 R² .. 0.999 R²)
mean                 9.317 ms   (9.175 ms .. 9.527 ms)
std dev              475.8 μs   (311.8 μs .. 677.9 μs)
variance introduced by outliers: 25% (moderately inflated)

基准代码：

import Criterion.Main
import Control.Monad.ST
import Data.STRef
import Control.Monad.Loops

peanoAddST :: Int -> Int -> Int
peanoAddST x y = runST $ do
    x' <- newSTRef x
    y' <- newSTRef y
    whileM_ (do x'' <- readSTRef x'
                return $ x'' /= 0)
            (do modifySTRef x' (subtract 1)
                modifySTRef y' (+1))
    readSTRef y'

peanoAddST' :: Int -> Int -> Int
peanoAddST' x y = runST $ do
    x' <- newSTRef x
    y' <- newSTRef y
    whileM_ (do x'' <- readSTRef x'
                return $ x'' /= 0)
            (do modifySTRef' x' (subtract 1)
                modifySTRef' y' (+1))
    readSTRef y'

peanoAddRec :: Int -> Int -> Int
peanoAddRec 0 y = y
peanoAddRec x y = peanoAddRec (x - 1) (y + 1)

main =
  let n = 64000 in
  defaultMain
  [ bench "rec" $ whnf (peanoAddRec n) n
  , bench "st" $ whnf (peanoAddST n) n
  , bench "st'" $ whnf (peanoAddST' n) n
  ]