memory - 加速 Haskell 并发

Question

MVar, TVar, IORef, ... 我无法加速 thunk 问题(我认为)。

(我原来的问题是线程代码，我做了 n 次“forkIO”调用“addMany”；但我认为我的问题出在“shW”函数上)

让下一个代码:

{-# LANGUAGE BangPatterns #-}
import Control.Concurrent
import Control.Monad
import System.Environment(getArgs)
import Data.Int
import Data.IORef

-- "i" times, add "n" for each IORef (in "a")
addMany :: [IORef Int64] -> Int64 -> Int64 -> IO ()
addMany !a !n !i =
  forM_ [1..i] (\_ ->
    forM_ a (shW n))

-- MVar, TVar, IORef, ... read/write (x' = x + k)
shR = readIORef
shW !k !r = atomicModifyIORef r (\ !x' -> (x' + k, ()))

main = do
  (n':i':_) <- getArgs
  let (n, i) = (read n', read i')
  v <- forM [1..n] (\_ -> newIORef 0)
  addMany v 1 i
  mapM shR v >>= (putStrLn.show.sum)

然后，配置文件结果显示:

MUT     time    3.12s  (  3.12s elapsed)
GC      time    6.96s  (  6.96s elapsed)
...

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

MAIN         MAIN                     47           0    0.0    0.0   100.0  100.0
 main        Main                     95           0    0.0    0.0   100.0  100.0
  main.i     Main                    100           1    0.0    0.0     0.0    0.0
  addMany    Main                     99           1    0.4    0.5   100.0  100.0
   addMany.\ Main                    101       15000    6.6    0.0    99.6   99.5
    shW      Main                    102     2250000   92.7   99.5    93.0   99.5
     shW.\   Main                    104     2250000    0.3    0.0     0.3    0.0

我无法删除“shW”调用上的 thunk(而且内存使用量很大)。怎么了？

类似的 C# 代码运行得更快(很多):

class Node { 
    private object m; 
    private int n; 

    public Node() {n = 0; m = new object();} 
    public void Inc() {lock(m) n++;} 
    public int Read() {return n;} 
} 

class MainClass { 

    public static void Main(string[] args) { 

        var nitems = 1000; 
        var nthreads = 6; 
        var niters = 100000; 

        var g = Enumerable.Range(0, nitems).Select(i => new Node()).ToArray(); 
        Task.WaitAll(Enumerable.Range(0, nthreads).Select(q => Task.Factory.StartNew(() => { 
            var z = niters; 
            while(z-- > 0) 
                foreach(var i in g) 
                    i.Inc(); 
        })).ToArray()); 

        Console.WriteLine("Sum node values: {0}", g.Sum(i => i.Read())); 

    } 
} 

非常感谢!

更新

解决了原始问题:https://gist.github.com/3742897

非常感谢唐·斯图尔特!

Answer 1

当你查看堆和 GC 时间时，很明显存在泄漏:

USDGHTVVH1$ time ./A 1000 10000 +RTS -s
10000000
   1,208,298,840 bytes allocated in the heap
   1,352,861,868 bytes copied during GC
     280,181,684 bytes maximum residency (9 sample(s))
       4,688,680 bytes maximum slop
             545 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0      1677 colls,     0 par    2.27s    2.22s     0.0013s    0.0063s
  Gen  1         9 colls,     0 par    1.66s    1.77s     0.1969s    1.0273s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.70s  (  0.77s elapsed)
  GC      time    3.92s  (  4.00s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    4.62s  (  4.77s elapsed)

  %GC     time      84.8%  (83.8% elapsed)

  Alloc rate    1,718,469,461 bytes per MUT second

  Productivity  15.2% of total user, 14.7% of total elapsed

  real    0m4.752s
  user    0m0.015s
  sys     0m0.046s

2.8 亿驻留和 89% GC。大量的 thunk 被分配和丢弃。

堆配置文件使这一点显而易见。

线索是这些是“stg_app*”的东西(即 STG 机器应用 thunk)。

modify 系列函数的一个微妙但显着的问题是这里的问题——当你有一个惰性 atomicModify 时，根本没有办法严格更新该字段，不要求值(value)。

所以你所有仔细使用 atomicModifyIORef r (\!x' -> (x' + k, ())) 所做的就是构建 (+) 的应用链 函数，这样链的结果(即单元格中的值)被观察到，每个加法都将在其参数中是严格的。不是你想要的! argument 上要修改IORef 的任何严格性注释都不会对单元格本身产生任何影响。现在，通常你想要一个惰性修改——它只是一个指针交换，所以你可以有非常短的原子部分。

但有时这不是你想要的。

(有关此问题的背景，请参阅 GHC 票证 #5926 ，但是，至少在 2007 年，当我编写 strict-concurrency 包以避免 MVars 出现此问题时，该问题已为人所知。它是 discussed in 2009 ，我们现在有了2012 年的严格版本)。

通过首先要求值(value)，您可以消除问题。例如。

shW !k !r = --atomicModifyIORef r (\x -> (x + k, ()))
    do x <- shR r
       writeIORef r $! (x+1)

注意这个问题现在是 documented in the libraries ，你可以使用 atomicModifyIORef' 来避免它。

我们得到:

USDGHTVVH1$ time ./A 1000 10000 +RTS -s
10000000
     120,738,836 bytes allocated in the heap
       3,758,476 bytes copied during GC
          73,020 bytes maximum residency (1 sample(s))
          16,348 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0       230 colls,     0 par    0.00s    0.01s     0.0000s    0.0001s
  Gen  1         1 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.17s  (  0.17s elapsed)
  GC      time    0.00s  (  0.01s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.19s  (  0.17s elapsed)

  %GC     time       0.0%  (3.9% elapsed)

  Alloc rate    643,940,458 bytes per MUT second

  Productivity 100.0% of total user, 108.3% of total elapsed


real    0m0.218s
user    0m0.000s
sys     0m0.015s

也就是说，速度提高了 22 倍，并且内存使用变得恒定。搞笑的是，这是新的堆配置文件: