构建昂贵的密钥映射时正确利用并行性吗？

Question

我正在Haskell中编写彩虹表的玩具实现。主要数据结构是严格的Map h c，包含大量从随机值生成的对c：

import qualified Data.Map as M
import System.Random

table :: (RandomGen g, Random c) => Int -> g -> Map h c
table n = M.fromList . map (\c -> (chain c, c)) . take n . randoms

在哪里chain计算非常昂贵。占主导地位的计算时间部分令人尴尬地是并行的，因此，如果并行运行，我希望内核数量获得准线性加速。

但是，我希望将计算对立即添加到表中，而不是累积在内存中的列表中。应当注意，可能会发生冲突，在这种情况下，应尽快丢弃冗余链。堆分析确认是这种情况。

我parMap从找到了Control.Parallel.Strategies，并尝试将其应用于我的表构建功能：

table n = M.fromList . parMap (evalTuple2 rseq rseq) (\c -> (chain c, c)) . take n . randoms

但是，运行时-N，充其量只能达到1.3核心使用率。堆分析至少表明中间列表不驻留在内存中，但是“ -s”还报告创建了0个火花。我的用法怎么可能parMap？这样做的正确方法是什么？

编辑：chain定义为：

chain :: (c -> h) -> [h -> c] -> c -> h
chain h = h . flip (foldl' (flip (.h)))

where (c -> h)是目标哈希函数（从明文到哈希），并且[h -> c]是reduce函数的系列。我想执行留在通用c和h，但基准我用两个严格的字节串。

Answer 1

这是我想出的。让我知道基准是如何计算的：

#!/usr/bin/env stack
{- stack --resolver lts-14.1 script --optimize
  --package scheduler
  --package containers
  --package random
  --package splitmix
  --package deepseq
-}
{-# LANGUAGE BangPatterns #-}

import Control.DeepSeq
import Control.Scheduler
import Data.Foldable as F
import Data.IORef
import Data.List (unfoldr)
import Data.Map.Strict as M
import System.Environment (getArgs)
import System.Random as R
import System.Random.SplitMix


-- for simplicity
chain :: Show a => a -> String
chain = show

makeTable :: Int -> SMGen -> (SMGen, M.Map String Int)
makeTable = go M.empty
  where go !acc i gen
          | i > 0 =
            let (c, gen') = R.random gen
            in go (M.insert (chain c) c acc) (i - 1) gen'
          | otherwise = (gen,  acc)

makeTablePar :: Int -> SMGen -> IO (M.Map String Int)
makeTablePar n0 gen0 = do
  let gens = unfoldr (Just . splitSMGen) gen0
  gensState <- initWorkerStates Par (\(WorkerId wid) -> newIORef (gens !! wid))
  tables <-
    withSchedulerWS gensState $ \scheduler -> do
      let k = numWorkers (unwrapSchedulerWS scheduler)
          (q, r) = n0 `quotRem` k
      forM_ ((if r == 0 then [] else [r]) ++ replicate k q) $ \n ->
        scheduleWorkState scheduler $ \genRef -> do
          gen <- readIORef genRef
          let (gen', table) = makeTable n gen
          writeIORef genRef gen'
          table `deepseq` pure table
  pure $ F.foldl' M.union M.empty tables

main :: IO ()
main = do
  [n] <- fmap read <$> getArgs
  gen <- initSMGen
  print =<< makeTablePar n gen

关于实施的一些注意事项：

• 不要使用 的生成器random，它非常慢，但splitmix速度快了 200 倍
• 在 中makeTable，如果您希望立即丢弃重复结果，则需要手动循环或展开。但由于我们需要返回生成器，所以我选择了手动循环。
• 为了最大限度地减少线程之间的同步，将为每个线程构建独立的映射，并在最终将结果映射合并在一起时删除重复项。