8

MVar、TVar、IORef、... サンク問題を高速化できません (と思います)。

(私の元の問題はスレッド化されたコードです。「forkIO」を n 回呼び出して「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」呼び出しでサンクを削除できません (メモリ使用量が膨大です)。どうしたの？

同様の 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

どうもありがとうドン・スチュワート！

4

1 に答える 1

27

ヒープと 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 億 8000 万のレジデンシーと 89% の GC。たくさんのサンクが割り当てられ、捨てられています。

ヒープ プロファイルは、これを明白にします。

ここに画像の説明を入力

手がかりは、これらが「stg_app*」のもの (つまり、STG マシン適用サンク) であるということです。

関数の変更ファミリに関する微妙ではあるが注目に値する問題は、ここでの問題です。レイジーなatomicModifyがある場合、値を要求せずにフィールドを厳密に更新する方法はありません。

したがって、dos を慎重に使用することは、チェーンの結果 (つまり、セルの値) が観察されるようにatomicModifyIORef r (\ !x' -> (x' + k, ()))、関数のアプリケーションのチェーンを構築することであり、各追加はその引数で厳密になります。(+)あなたが望むものではありません！modifyIORef への引数の厳密性注釈は、セル自体には影響しません。さて、通常は遅延変更が必要です。これは単なるポインタ スワップであるため、非常に短いアトミック セクションを使用できます。

しかし、時にはそれはあなたが望むものではありません.

(この問題の背景については、GHC チケット#5926を参照してください。ただし、少なくとも 2007 年には、MVar でこの問題を回避するためにstrict-concurrencyパッケージを作成したときに、この問題は知られていました。2009 年に議論され、現在では strict があります。 2012 年版）。

最初に値を要求することで、問題を解決できます。例えば

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

この問題はライブラリに記載されており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 倍のスピードアップであり、メモリ使用量は一定になります。笑いのために、これが新しいヒーププロファイルです:

ここに画像の説明を入力

于 2012-09-18T12:12:17.230 に答える