haskell - 如何原子地修改可变数组中的值？

Question

我在 ST monad 中有这个可变数组。我有这个循环功能。

 runST $ do
    myarray <- newMArray (Sz 10) 0
    loopM_ 0 (<10) (+1) (\j ->
      loopM_ 0 (<10) (+1) (\i ->
        when (mytruthcheck j i)
             (modifyM_ myarray (pure . (+1)) ((funcofji j i) :: Int)
     )))

我想使用 forkST_ 像这样并行运行外循环。

runST $ do
   myarray <- newMArray (Sz 10) 0
   loopM_ 0 (<10) (+1) (\j ->
     void (forkST_ (loopM_ 0 (<10) (+1) (\i ->
       when (mytruthcheck j i)
            (Data.Massiv.Array.Mutable.modifyM_
                 myarray (pure . (+1)) ((funcofji j i) :: Int)
    ))))

但我猜这会导致线程冲突，但我真的不知道，虽然我知道 funcofji 可以为 j< 的不同值输出相同的值 因此循环可以为不同的 j 修改 myarray 的相同索引。有没有办法确保这是自动完成的，或者已经是这样了？

顺便说一句，这是 loopM_ 函数

loopM_ :: Monad m => Int -> (Int -> Bool) -> (Int -> Int) -> (Int -> m a) -> m ()
loopM_ !init' condition increment f = go init'
  where
    go !step
      | condition step = f step >> go (increment step)
      | otherwise = pure ()

Answer 1

评论中提到，原子修改只对并发有用 ，这里好像不需要。您需要的是并行性。 ，可用于 Int 的 massiv:atomicAddIntArray

在 massiv 中还有一种内置的方法可以非常有效地进行并行处理，因此绝对不需要重新发明轮子:

  createArray_ Par (Sz 10) $ \scheduler myarray ->
    loopM_ 0 (<10) (+1) $ \j ->
      loopM_ 0 (<10) (+1) $ \i ->
        when (mytruthcheck j i) $ 
          scheduleWork_ scheduler $ 
            void $ atomicAddIntArray myarray ((funcofji j i) :: Int) 1

也不要骗自己，ST(状态线程)不是为多线程构建的，而是使用 IO。但是，如果您可以保证，尽管设置了多线程，但最终产生的结果仍然是确定性的，那么使用 unsafePerformIO 就可以了。

编辑

我刚刚注意到这条评论:

The loop size of j is close to 100,000 and the loop size of i is close to 1 Billion.

这让我相信以这种方式并行化它会更好:

  createArray_ Par (Sz 10) $ \scheduler myarray ->
    iforSchedulerM_ scheduler (0 ..: (100000 :. 1000000000)) $ \_ (j :. i) ->
      when (mytruthcheck j i) $ 
        void $ atomicAddIntArray myarray ((funcofji j i) :: Int) 1

这将确保您只安排几个作业，而不是数十亿个。查看iforSchedulerM_如果您对每个 i 和 j 工作负载有更深入的了解，则可以自定义并行化。