3

我已经用一个简单的 API 实现了一个线程安全的可变对象存储。直观地说，它有性能限制，即与多个并发写入者的锁争用。首先，这里是 API：

new :: String -> IO Int
get :: Int -> IO (Maybe String)
delete :: Int -> IO ()

隐藏在实现中的是一个全局可访问IORef的持有一个纯数据结构Ref，用unsafePerformIO. 它是一个IntMap, 和一个递增的插槽号。当一个元素被添加到 时IntMap，槽会增加并作为对条目的引用返回。这是实现：

module MyModule (new,get,delete) where

import Control.Monad (liftM)
import Data.IORef
import qualified Data.IntMap as Map
import Data.Functor ((<$>))
import Data.Maybe
import System.IO.Unsafe (unsafePerformIO)

new :: String -> IO Int
new = atomicModifyIORef ref . createEntry

get :: Int -> IO (Maybe String)
get i = liftM (Map.lookup i) (table <$> readIORef ref)

delete :: Int -> IO ()
delete = atomicModifyIORef ref . deleteEntry

---------------
-- IORef mutation

data Ref = Ref { lastSlot :: !Int , table :: Map.IntMap String }

{-# NOINLINE ref #-}
ref :: IORef Ref
ref = unsafePerformIO $
        newIORef Ref { lastSlot = 0, table = Map.empty }

createEntry :: String -> Ref -> (Ref, Int)
createEntry val reg =
  ref `seq` (reg', newSlot) where
    newSlot = lastSlot reg + 1
    reg' = reg { lastSlot = newSlot,
                 table    = Map.insert newSlot val (table reg) }

deleteEntry :: Int -> Ref -> (Ref, ())
deleteEntry slot reg = (reg { table = Map.delete slot (table reg) }, ())

一个使用示例是：

test :: IO ()
test = do
    x <- new "foo"
    y <- new "bar"
    fromJust <$> get y >>= print -- prints "bar"
    fromJust <$> get x >>= print -- prints "foo"
    delete x >> delete y

这是线程安全的，例如new可以在单独的线程中调用。这有效。正如Gregory Collins所指出的，问题在于争用。当在多并发作者的情况下添加了 100k+ 个条目时，atomicModifyIORef将用 thunk 交换值。然后，当我尝试使用IntMap下面的IORef时，多个 mutator 将尝试将值强制为 WHNF，从而导致重复工作或线程阻塞在“黑洞”上，这两种方式都很糟糕。

我正在寻找的是一种替代实现，使 、 和 的new类型get不受影响delete。一种可能性是使用锁分条，以减少锁争用。snap 框架中的这个 HashMap 实现实现了 lock-striping，通过将键或散列空间划分为 N 个分区（即Vector (MVar (HashTable k v))），然后用互斥锁保护每个分区。我不清楚我将如何重新实现new，get并delete在我的模块中使用这个 HashMap，而不修改类型（这会破坏很多使用它的模块）。

  • 是否有任何线程安全的 Haskell 并发对象存储或 HashMap 库可用于重新实现我的 API？
  • 我想删除unsafePerformIO.
  • 对于我的 API，我更愿意留在 IO Monad 中。
4

0 回答 0