haskell - 在 Haskell 中并发读写 IOArray

Question

我开始在 Haskell 中使用 GHC 为多核机器编写并发程序。作为第一步，我决定编写一个同时读取和写入 IOArray 的程序。我的印象是对 IOArray 的读写不涉及同步。我这样做是为了建立一个基线，以与其他使用适当同步机制的数据结构的性能进行比较。我遇到了一些令人惊讶的结果，即在许多情况下，我根本没有得到任何加速。这让我想知道在 ghc 运行时是否发生了一些低级别的同步，例如，同步和阻塞评估 thunk(即“黑洞”)。以下是详细信息...

我在一个程序上写了几个变体。主要思想是我写了一个 DirectAddressTable 数据结构，它只是一个 IOArray 的包装器，提供插入和查找方法:

-- file DirectAddressTable.hs
module DirectAddressTable 
       ( DAT
       , newDAT
       , lookupDAT
       , insertDAT
       , getAssocsDAT
       )
       where

import Data.Array.IO
import Data.Array.MArray

newtype DAT = DAT (IOArray Int Char)

-- create a fixed size array; missing keys have value '-'.
newDAT :: Int -> IO DAT
newDAT n = do a <- newArray (0, n - 1) '-'
              return (DAT a)

-- lookup an item.
lookupDAT :: DAT -> Int -> IO (Maybe Char)
lookupDAT (DAT a) i = do c <- readArray a i 
                         return (if c=='-' then Nothing else Just c)

-- insert an item
insertDAT :: DAT -> Int -> Char -> IO ()
insertDAT (DAT a) i v = writeArray a i v

-- get all associations (exclude missing items, i.e. those whose value is '-').
getAssocsDAT :: DAT -> IO [(Int,Char)]
getAssocsDAT (DAT a) = 
  do assocs <- getAssocs a
     return [ (k,c) | (k,c) <- assocs, c /= '-' ]

然后我有一个主程序，它初始化一个新表， fork 一些线程，每个线程向刚刚初始化的表写入和读取一些固定数量的值。要写入的元素总数是固定的。要使用的线程数取自命令行参数，要处理的元素在线程之间平均分配。

-- file DirectTableTest.hs
import DirectAddressTable
import Control.Concurrent
import Control.Parallel
import System.Environment

main = 
  do args <- getArgs
     let numThreads = read (args !! 0)
     vs <- sequence (replicate numThreads newEmptyMVar)
     a <- newDAT arraySize     
     sequence_ [ forkIO (doLotsOfStuff numThreads i a >>= putMVar v) 
               | (i,v) <- zip [1..] vs]
     sequence_ [ takeMVar v >>= \a -> getAssocsDAT a >>= \xs -> print (last xs)  
               | v <- vs]     

doLotsOfStuff :: Int -> Int -> DAT -> IO DAT
doLotsOfStuff numThreads i a = 
  do let p j c = (c `seq` insertDAT a j c) >> 
                 lookupDAT a j >>= \v -> 
                 v `pseq` return ()  
     sequence_ [ p j c | (j,c) <- bunchOfKeys i ]
     return a
  where  bunchOfKeys i = take numElems $ zip cyclicIndices $ drop i cyclicChars
         numElems      = numberOfElems `div` numThreads

cyclicIndices = cycle [0..highestIndex]
cyclicChars   = cycle chars
chars         = ['a'..'z']

-- Parameters
arraySize :: Int
arraySize     = 100
highestIndex  = arraySize - 1
numberOfElems = 10 * 1000 * 1000     

我使用 ghc 7.2.1(与 7.0.3 的结果相似)和“ghc --make -rtsopts -threaded -fforce-recomp -O2 DirectTableTest.hs”编译了这个。
运行“time ./DirectTableTest 1 +RTS -N1”大约需要 1.4 秒，运行“time ./DirectTableTest 2 +RTS -N2”大约需要 2.0 秒!使用比工作线程多一个内核会更好一些，“time ./DirectTableTest 1 +RTS -N1”大约需要 1.4 秒，运行“time ./DirectTableTest 1 +RTS -N2”和“time ./DirectTableTest 2 +RTS” -N3"都需要大约 1.4 秒。
使用“-N2 -s”选项运行显示生产率为 95.4%，GC 为 4.3%。用 ThreadScope 查看程序的运行，我没有看到任何太令人震惊的地方。当 GC 发生时，每个 HEC 每毫秒产生一次。使用 4 核运行大约需要 1.2 秒，这至少比 1 核好一点。更多的核心并没有改善这一点。

我发现将 DirectAddressTable 实现中使用的数组类型从 IOArray 更改为 IOUArray 可以解决此问题。通过这一更改，“time ./DirectTableTest 1 +RTS -N1”的运行时间约为 1.4 秒，而“time ./DirectTableTest 2 +RTS -N2”的运行时间约为 1.0 秒。增加到 4 个内核可提供 0.55 秒的运行时间。使用“-s”运行显示 %3.9% 的 GC 时间。在 ThreadScope 下，我可以看到两个线程每 0.4 毫秒产生一次，比之前的程序更频繁。

最后，我尝试了另一种变体。我没有让线程在同一个共享数组上工作，而是让每个线程在自己的数组上工作。这可以很好地扩展(如您所料)，或多或少像第二个程序，IOArray 或 IOUArray 实现 DirectAddressTable 数据结构。

我理解为什么 IOUArray 可能比 IOArray 性能更好，但我不知道为什么它可以更好地扩展到多个线程和内核。有谁知道为什么会发生这种情况，或者我可以做些什么来找出发生了什么？我想知道这个问题是否可能是由于在评估相同的 thunk 时多个线程阻塞以及它是否与此有关: http://hackage.haskell.org/trac/ghc/ticket/3838 .

Answer 1

Running "time ./DirectTableTest 1 +RTS -N1" takes about 1.4 seconds and running "time ./DirectTableTest 2 +RTS -N2" take about 2.0 seconds!

我无法重现您的结果:

$ time ./so2 1 +RTS -N1
(99,'k')

real    0m0.950s
user    0m0.932s
sys     0m0.016s
tommd@Mavlo:Test$ time ./so2 2 +RTS -N2
(99,'s')
(99,'s')

real    0m0.589s
user    0m1.136s
sys     0m0.024s

随着轻量级线程数量的增加，这似乎按预期扩展:

ghc -O2 so2.hs -threaded -rtsopts
[1 of 2] Compiling DirectAddressTable2 ( DirectAddressTable2.hs, DirectAddressTable2.o )
[2 of 2] Compiling Main             ( so2.hs, so2.o )
Linking so2 ...
tommd@Mavlo:Test$ time ./so2 4
(99,'n')
(99,'z')
(99,'y')
(99,'y')

real    0m1.538s
user    0m1.320s
sys     0m0.216s
tommd@Mavlo:Test$ time ./so2 4 +RTS -N2
(99,'z')
(99,'x')
(99,'y')
(99,'y')

real    0m0.600s
user    0m1.156s
sys     0m0.020s

你真的有2个CPU吗？如果您运行的 GHC 线程 ( -Nx) 比可用 CPU 多，那么您的结果将非常糟糕。我想我真正要问的是:您确定您的系统上没有其他 CPU 密集型进程正在运行吗？

至于 IOUArray (通过编辑)

I understand why IOUArray might perform better than IOArray, but I don't know why it scales better to multiple threads and cores

未装箱的数组将是连续的，因此从缓存中受益更多。位于堆上任意位置的装箱值可能会导致内核之间的缓存失效大量增加。