シンプルな 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
れると、サンクで値が交換されます。次に、のIntMap
下でを使用しようとするIORef
と、複数のミューテーターが値を WHNF に強制しようとします。その結果、作業が重複するか、「ブラックホール」でスレッドがブロックされます。どちらにしても悪いことです。
私が探しているのは、new
、get
、およびdelete
影響を受けない型を残した代替実装です。1 つの可能性は、ロックの競合を減らすために、ロック ストライピングを使用することです。snap フレームワークでのこの HashMap 実装は、キーまたはハッシュ空間を N 個のパーティション (つまりVector (MVar (HashTable k v))
) に分割し、ミューテックス ロックでそれぞれを保護することにより、ロック ストライピングを実装します。new
タイプを変更せずに、この HashMap を使用するモジュールでget
を再実装する方法が明確ではありませんdelete
(それを使用する多くのモジュールが壊れる可能性があります)。
- API を再実装するために使用できる、スレッドセーフな Haskell 並行オブジェクト ストアまたは HashMap ライブラリはありますか?
- を削除したいと思い
unsafePerformIO
ます。 - 私は自分の API のために IO モナド内にとどまりたいと思っています。