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れると、サンクで値が交換されます。次に、の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 モナド内にとどまりたいと思っています。
4

0 に答える 0