ttrie 0.1 → 0.1.0.0
raw patch · 8 files changed
+223/−309 lines, 8 filesdep +criteriondep −criterion-plusdep ~atomic-primopsdep ~hashabledep ~primitive
Dependencies added: criterion
Dependencies removed: criterion-plus
Dependency ranges changed: atomic-primops, hashable, primitive
Files
- README.md +2/−10
- benchmarks/Bench.hs +0/−200
- benchmarks/Bench1.hs +26/−0
- benchmarks/BenchGen.hs +0/−4
- benchmarks/Common.hs +122/−0
- benchmarks/run.sh +52/−20
- src/Control/Concurrent/STM/Map.hs +6/−48
- ttrie.cabal +15/−27
README.md view
@@ -1,10 +1,2 @@-A contention-free STM hash map for Haskell.--"Contention-free" means that the map will never cause spurious conflicts.-A transaction operating on the map will only ever have to retry if-another transaction is operating on the same key at the same time.--This is an implementation of the *transactional trie*,-which is basically a *lock-free concurrent hash trie* lifted into STM.-For a detailed discussion, including an evaluation of its performance,-see Chapter 4 of [my master's thesis](https://github.com/mcschroeder/thesis).+# ttrie+A contention-free STM hash map for Haskell
− benchmarks/Bench.hs
@@ -1,200 +0,0 @@-{-# LANGUAGE DeriveGeneric #-}-{-# LANGUAGE OverloadedStrings #-}-module Main where--import BenchGen-import Control.Applicative-import Control.Concurrent.Async-import Control.Concurrent.STM-import Control.Concurrent.STM.Stats-import Control.DeepSeq-import Control.Exception (evaluate)-import Control.Monad-import Control.Monad.IO.Class-import CriterionPlus-import qualified Data.Map as Map-import Data.Text (Text)-import qualified Data.Text as T-import GHC.Generics-import GHC.Stats-import System.Environment-import System.Mem-import System.Random.MWC-import System.Random.MWC.CondensedTable-import Text.Printf--import qualified Control.Concurrent.STM.Map as TTrie-import qualified STMContainers.Map as STMCont-import qualified Data.HashMap.Strict as HashMap----------------------------------------------------------------------------------main :: IO ()-main = do- (arg1:arg2:arg3:arg4:arg5:args) <- getArgs- printf "threads = %s\n" arg1- printf "numTransactions = %s\n" arg2- printf "sizes = %s\n" arg3- printf "numPrefill = %s\n" arg4- printf "ops = %s\n" arg5- let threads = read arg1 :: [Int]- numTransactions = read arg2- sizes = mkTable $ read arg3- numPrefill = read arg4- (ins,upd,look,del) = read arg5- config = Config- { operations = mkTable [ (Insert, ins + upd)- , (Lookup, look)- , (Delete, del)- ]- , keys = \op -> case op of- Insert -> mkTable [(remember key, ins), (remember (reuse key), upd)]- Lookup -> mkTable [(reuse key, 1)]- Delete -> mkTable [(forget (reuse key), 1)]- }-- (ks,txs) <- genTransactions numPrefill numTransactions sizes config- withArgs args $ benchmark- $ standoff (T.pack arg5)- $ mapM_ (supergroup ks txs numTransactions)- $ threads--supergroup :: [Key] -> [Transaction] -> Int -> Int -> Standoff ()-supergroup ks txs numTransactions t =- group (T.pack $ printf "%d/%d" t n) $ do- runAll "unordered-containers" hashmapPrefill hashmapEval- runAll "stm-containers" stmcontPrefill stmcontEval- runAll "ttrie" ttriePrefill ttrieEval- where- n = numTransactions `div` t- ops = split n txs- runAll name prefill eval = do- runTime name prefill eval ks ops- liftIO $ runRetries (printf "%d/%d/%s" t n name) prefill eval ks ops- liftIO $ runAlloc prefill eval ks ops--split :: Int -> [a] -> [[a]]-split n [] = []-split n xs = let (ys,zs) = splitAt n xs in ys : split n zs----------------------------------------------------------------------------------type EvalFunc c = Op -> Key -> c -> STM ()-type PrefillFunc c = [Key] -> IO c--runTime :: String -> PrefillFunc c -> EvalFunc c -> [Key] -> [[Transaction]] -> Standoff ()-runTime name prefill eval ks ops = subject (T.pack name) $ do- pause- c <- liftIO $ prefill ks- continue- liftIO $ run_ atomically ops eval c--runRetries :: String -> PrefillFunc c -> EvalFunc c -> [Key] -> [[Transaction]] -> IO ()-runRetries name prefill eval ks ops = do- printf "commits: "- c <- prefill ks- let atomically' = trackSTMConf defaultTrackSTMConf- { tryThreshold = Nothing- , globalTheshold = Nothing- }- run_ (atomically' name) ops eval c- stats <- getSTMStats- let Just (commits, retries) = Map.lookup name stats- printf "%d\nretries: %d\n" commits retries--runAlloc :: PrefillFunc c -> EvalFunc c -> [Key] -> [[Transaction]] -> IO ()-runAlloc prefill eval ks ops = do- printf "allocated bytes: "- c <- prefill ks- performGC- before <- getGCStats- run_ atomically ops eval c- performGC- after <- getGCStats- let bytes = bytesAllocated after - bytesAllocated before- printf "%d\n" bytes--run_ :: (STM () -> IO ()) -> [[Transaction]] -> EvalFunc c -> c -> IO ()-run_ atom ops f c = void $ mapConcurrently (mapM_ txEval) ops- where txEval = atom . mapM_ (\(op,k) -> f op k c)----------------------------------------------------------------------------------type Key = Text-type Transaction = [(Op,Key)]--data Op = Lookup | Insert | Delete- deriving (Eq, Show, Generic)--instance NFData Op--key :: Generator IO k Key-key = do- n <- liftGen $ genFromTable length- T.pack <$> replicateM n (liftGen $ genFromTable alphabet)- where- length = mkTable $ zip [7..20] (repeat 1)- alphabet = mkTable $ zip ['a'..'z'] (repeat 1)--genTransactions :: Int -> Int -> CondensedTableV Int -> Config IO Op Key -> IO ([Key],[Transaction])-genTransactions numPrefill numTransactions sizes config = do- gen <- create- runGenerator gen $ do- liftIO $ printf "Generating %d random keys to prefill...\n" numPrefill- ks <- replicateM numPrefill (remember key)- liftIO $ printf "Generating %d random transactions...\n" numTransactions- txs <- replicateM numTransactions $ do- size <- liftGen $ genFromTable sizes- generateOperations config size- return (ks,txs)----------------------------------------------------------------------------------- Evaluation and Prefill functions--instance (NFData k, NFData v) => NFData (TTrie.Map k v)--ttriePrefill :: PrefillFunc (TTrie.Map Key ())-ttriePrefill ks = do- m <- atomically $ TTrie.empty- forM_ ks $ \k -> atomically $ TTrie.insert k () m- evaluate (rnf m)- return m--ttrieEval :: EvalFunc (TTrie.Map Key ())-ttrieEval Lookup k = void . TTrie.lookup k-ttrieEval Insert k = TTrie.insert k ()-ttrieEval Delete k = TTrie.delete k--instance (NFData k, NFData v) => NFData (STMCont.Map k v)--stmcontPrefill :: PrefillFunc (STMCont.Map Key ())-stmcontPrefill ks = do- m <- atomically $ STMCont.new- forM_ ks $ \k -> atomically $ STMCont.insert () k m- evaluate (rnf m)- return m--stmcontEval :: EvalFunc (STMCont.Map Key ())-stmcontEval Lookup k = void . STMCont.lookup k-stmcontEval Insert k = STMCont.insert () k-stmcontEval Delete k = STMCont.delete k--instance (NFData a) => NFData (TVar a)--hashmapPrefill :: PrefillFunc (TVar (HashMap.HashMap Key (TVar ())))-hashmapPrefill ks = do- elems <- forM ks (\k -> newTVarIO () >>= \v -> return (k,v))- m <- newTVarIO $ HashMap.fromList elems- evaluate (rnf m)- return m--hashmapEval :: EvalFunc (TVar (HashMap.HashMap Key (TVar ())))-hashmapEval Lookup k m = do- v <- HashMap.lookup k <$> readTVar m- case v of- Just v -> void $ readTVar v- Nothing -> return ()-hashmapEval Insert k m = do- v <- newTVar ()- modifyTVar' m (HashMap.insert k v)-hashmapEval Delete k m = modifyTVar' m (HashMap.delete k)
+ benchmarks/Bench1.hs view
@@ -0,0 +1,26 @@+module Main where++import BenchGen+import Common+import System.Environment+import Text.Printf++main :: IO ()+main = do+ (arg1:arg2:arg3:arg4:args) <- getArgs+ printf "threads = %s\nnumTransactions = %s\nsizes = %s\nops = %s\n" arg1 arg2 arg3 arg4+ let threads = read arg1+ numTransactions = read arg2+ sizes = mkTable $ read arg3+ (inserts,lookups,updates,deletes) = read arg4+ config = Config+ { operations = mkTable [ (Insert, inserts + updates)+ , (Lookup, lookups)+ , (Delete, deletes)+ ]+ , keys = \op -> case op of+ Insert -> mkTable [(remember key, inserts), (remember (reuse key), updates)]+ Lookup -> mkTable [(key, 0), (reuse key, 1)]+ Delete -> mkTable [(forget key, 0), (forget (reuse key), 1)]+ }+ withArgs args $ runAll threads numTransactions sizes config
benchmarks/BenchGen.hs view
@@ -4,7 +4,6 @@ import Control.Applicative import Control.Monad-import Control.Monad.IO.Class import Control.Monad.Primitive import Control.Monad.Trans.Class import Control.Monad.Trans.State.Strict@@ -19,9 +18,6 @@ newtype Generator m k a = Generator { unG :: StateT (Gen (PrimState m), Set k) m a } deriving (Functor, Applicative, Monad)--instance MonadIO m => MonadIO (Generator m k) where- liftIO = Generator . liftIO runGenerator :: PrimMonad m => Gen (PrimState m) -> Generator m k a -> m a runGenerator gen (Generator m) = evalStateT m (gen, Set.empty)
+ benchmarks/Common.hs view
@@ -0,0 +1,122 @@+{-# LANGUAGE DeriveGeneric #-}+module Common where++import BenchGen++import Control.Applicative+import Control.Concurrent.Async+import Control.Concurrent.STM+import Control.Concurrent.STM.Stats+import Control.DeepSeq+import Control.Monad+import Criterion.Main+import qualified Data.Map as Map+import Data.Text (Text)+import qualified Data.Text as T+import GHC.Generics+import System.Random.MWC+import System.Random.MWC.CondensedTable+import Text.Printf++import qualified Control.Concurrent.STM.Map as TTrie+import qualified STMContainers.Map as STMCont+import qualified Data.HashMap.Strict as HashMap++------------------------------------------------------------------------------++data Op = Lookup | Insert | Delete+ deriving (Eq, Show, Generic)++instance NFData Op++key :: Generator IO k Text+key = do+ n <- liftGen $ genFromTable length+ T.pack <$> replicateM n (liftGen $ genFromTable alphabet)+ where+ length = mkTable $ zip [7..20] (repeat 1)+ alphabet = mkTable $ zip ['a'..'z'] (repeat 1)++------------------------------------------------------------------------------++runAll :: [Int] -> Int -> CondensedTableV Int -> Config IO Op Text -> IO ()+runAll numThreads numTransactions sizes config = do+ txs <- genTransactions numTransactions sizes config+ runBenchmarks txs numTransactions numThreads+ collectRetryStats txs numTransactions numThreads++genTransactions :: Int -> CondensedTableV Int -> Config IO Op Text -> IO [[(Op, Text)]]+genTransactions numTransactions sizes config = do+ printf "Generating %d random transactions...\n" numTransactions+ gen <- create+ runGenerator gen $ do+ replicateM numTransactions $ do+ size <- liftGen $ genFromTable sizes+ generateOperations config size++runBenchmarks :: [[(Op, Text)]] -> Int -> [Int] -> IO ()+runBenchmarks txs numTransactions numThreads =+ defaultMain $! flip map numThreads+ $ \n -> env (return $! split (numTransactions `div` n) txs)+ $ \ ~ops -> bgroup (printf "%d/%d" n (numTransactions `div` n))+ [ bench "unordered-containers" $ whnfIO $ run ops hashmapEval =<< newTVarIO HashMap.empty+ , bench "unordered-containers2" $ whnfIO $ run ops hashmapEval2 =<< newTVarIO HashMap.empty+ , bench "stm-containers" $ whnfIO $ run ops stmcontEval =<< STMCont.newIO+ , bench "ttrie" $ whnfIO $ run ops ttrieEval =<< atomically TTrie.empty+ ]+ where+ run ops f c = mapConcurrently (mapM_ txEval) ops+ where txEval = atomically . mapM_ (\(op,k) -> f op k c)++collectRetryStats :: [[(Op, Text)]] -> Int -> [Int] -> IO ()+collectRetryStats txs numTransactions numThreads =+ flip mapM_ numThreads $ \n -> do+ let ops = split (numTransactions `div` n) txs+ str = printf "%d/%d" n (numTransactions `div` n)+ run (str++"/unordered-containers") ops hashmapEval =<< newTVarIO HashMap.empty+ run (str++"/unordered-containers2") ops hashmapEval2 =<< newTVarIO HashMap.empty+ run (str++"/stm-containers") ops stmcontEval =<< STMCont.newIO+ run (str++"/ttrie") ops ttrieEval =<< atomically TTrie.empty+ where+ run name ops f c = do+ printf "collecting retry statistics for %s\n" name+ mapConcurrently (mapM_ txEval) ops+ printStats name+ where+ txEval = atomically' name . mapM_ (\(op,k) -> f op k c)+ atomically' = trackSTMConf defaultTrackSTMConf+ { tryThreshold = Nothing+ , globalTheshold = Nothing+ }+ printStats name = do+ stats <- getSTMStats+ let Just (commits, retries) = Map.lookup name stats+ printf "Commits\t%d\nRetries\t%d\n\n" commits retries++split n [] = []+split n xs = let (ys,zs) = splitAt n xs in ys : split n zs++------------------------------------------------------------------------------+-- Evaluation functions++ttrieEval Lookup k = void . TTrie.lookup k+ttrieEval Insert k = TTrie.insert k ()+ttrieEval Delete k = TTrie.delete k++stmcontEval Lookup k = void . STMCont.lookup k+stmcontEval Insert k = STMCont.insert () k+stmcontEval Delete k = STMCont.delete k++hashmapEval Lookup k m = do+ v <- HashMap.lookup k <$> readTVar m+ case v of+ Nothing -> return ()+ Just v -> readTVar v >> return ()+hashmapEval Insert k m = do+ v <- newTVar ()+ modifyTVar' m (HashMap.insert k v)+hashmapEval Delete k m = modifyTVar' m (HashMap.delete k)++hashmapEval2 Lookup k m = HashMap.lookup k <$> readTVar m >> return ()+hashmapEval2 Insert k m = modifyTVar' m (HashMap.insert k ())+hashmapEval2 Delete k m = modifyTVar' m (HashMap.delete k)
benchmarks/run.sh view
@@ -1,30 +1,62 @@-#!/bin/bash+#!/bin/sh main() {- THREADS="[1,2,4,6,8,10,12,14,16]"- TX_SIZE="[(1,1),(2,1),(3,1),(4,1),(5,1)]"- NUM_TX="200000"- NUM_PREFILL="1000000"+ THREADS="[1,2,4,6,8,12,16,24,32,48,64,96,128]"+ NUM_TX="250000" - mkdir -p "results/1"- bench $THREADS $NUM_TX "[(1,1)]" 0 "(1,0,0,0)" "results/1/insert"- bench $THREADS $NUM_TX "[(1,1)]" $NUM_TX "(0,1,0,0)" "results/1/update"- bench $THREADS $NUM_TX "[(1,1)]" $NUM_TX "(0,0,1,0)" "results/1/lookup"- bench $THREADS $NUM_TX "[(1,1)]" $NUM_TX "(0,0,0,1)" "results/1/delete"+ # weights for the transaction's size distribution+ TX_SIZES[0]="[(1,5),(2,5),(3,4),(4,4),(5,3),(6,3),(7,2),(8,2),(9,1),(10,1)]"+ TX_SIZES[1]="[(1,2),(2,3),(3,4),(4,4),(5,5),(6,4),(7,3),(8,2),(9,1),(10,1)]"+ TX_SIZES[2]="[(1,1),(2,1),(3,2),(4,2),(5,3),(6,3),(7,4),(8,4),(9,5),(10,5)]" - mkdir -p "results/5"- bench $THREADS $NUM_TX $TX_SIZE 0 "(70,10,10,10)" "results/update/5/insert"- bench $THREADS $NUM_TX $TX_SIZE $NUM_PREFILL "(10,70,10,10)" "results/update/5/update"- bench $THREADS $NUM_TX $TX_SIZE $NUM_PREFILL "(10,10,70,10)" "results/update/5/lookup"- bench $THREADS $NUM_TX $TX_SIZE $NUM_PREFILL "(10,10,10,70)" "results/update/5/delete" - bench $THREADS $NUM_TX $TX_SIZE $NUM_PREFILL "(25,25,25,25)" "results/update/5/balanced-prefill"+ # distributions of (lookup,insert,update,delete)+ OP_DISTS[0]="(20,60,15,5)"+ OP_DISTS[1]="(20,15,60,5)"+ OP_DISTS[2]="(80,10,5,5)"+ OP_DISTS[3]="(40,20,15,5)" -# sudo shutdown -h now+ TX_SIZES_NAMES=("small" "medium" "large")+ OP_DISTS_NAMES=("insert" "update" "lookup" "balanced")++ for i in ${!TX_SIZES[@]}; do+ TX_SIZE=${TX_SIZES[$i]}+ for j in ${!OP_DISTS[@]}; do+ OP=${OP_DIST[$j]}++ mkdir -p "results"+ ni=${TX_SIZES_NAMES[$i]}+ nj=${OP_DISTS_NAMES[$j]}+ n="results/$ni-$nj"++ unbuffer cabal bench bench1 --benchmark-options="$THREADS $NUM_TX $TX_SIZE $OP_DIST --regress allocated:iters +RTS -T" | + tee "$n.txt"+ + cat "$n.txt" | extract_times | transpose > "$n-time.dat"+ cat "$n.txt" | extract_allocations | transpose > "$n-alloc.dat"+ cat "$n.txt" | extract_retries | transpose > "$n-retries.dat"+ done+ done } -bench() {- unbuffer cabal bench bench --benchmark-options="$1 $2 $3 $4 $5 +RTS -T" | tee "$6.txt"-# curl -F $6.txt=@$6.txt https://XXXXXXXXXXXXXXX@neocities.org/api/upload+extract_retries() {+ grep -E "collecting|Retries" | + sed -E 'N;s/[^0-9]*([0-9]+)\/[0-9]+\/(.*)\n[^0-9]*([0-9\.e]*)/\2 \1 \3/g'+}++extract_times() {+ grep -E "benchmarking|time" | + sed -E "s/time *([0-9\.]*) s.*/\1/g" | + sed -E "s/time *([0-9]*)\.([0-9]*) ms.*/0.\1\2/g" | + sed -E "N;s/[^0-9]*([0-9]+)\/[0-9]+\/(.*)\n(.*)/\2 \1 \3/g"+}++extract_allocations() {+ grep -E "benchmarking|iters" | + sed -E "N;s/[^0-9]*([0-9]+)\/[0-9]+\/(.*)\n[^0-9]*([0-9\.e]*).*/\2 \1 \3/g"+}++transpose() {+ awk '{names[$1]++; threads[0]=0; threads[$2]++; results[$1,0]="\""$1"\""; results[$1,$2]=$3}END{for (t in threads) { printf "%s",t; for (n in names) printf " %s",results[n,t]; printf "\n" }}' | sort -n } main "$@"
src/Control/Concurrent/STM/Map.hs view
@@ -1,27 +1,13 @@ {-# LANGUAGE PatternGuards #-} {-# OPTIONS_GHC -funbox-strict-fields #-}---------------------------------------------------------------------------- | A contention-free STM hash map.--- \"Contention-free\" means that the map will never cause spurious conflicts.--- A transaction operating on the map will only ever have to retry if--- another transaction is operating on the same key at the same time.------------------------------------------------------------------------- module Control.Concurrent.STM.Map ( Map-- -- * Construction , empty-- -- * Modification , insert- , delete- , unsafeDelete-- -- * Query , lookup+ , delete , phantomLookup+ , unsafeDelete ) where import Control.Applicative ((<$>))@@ -53,38 +39,27 @@ ----------------------------------------------------------------------- --- | /O(1)/. Construct an empty map.+-- | /O(1)/. The empty map. empty :: STM (Map k v) empty = unsafeIOToSTM $ Map <$> newIORef (Array emptyArray) {-# INLINE empty #-} --- | /O(log n)/. Associate the given value with the given key.--- If the key is already present in the map, the old value is replaced. insert :: (Eq k, Hashable k) => k -> v -> Map k v -> STM () insert k v m = do var <- getTVar k m writeTVar var (Just v)+ {-# INLINABLE insert #-} --- | /O(log n)/. Return the value associated with the given key, or 'Nothing'.------ __Note__: This might increase the map's memory consumption--- by putting the key into the map.--- If that is not acceptable, use 'phantomLookup'. lookup :: (Eq k, Hashable k) => k -> Map k v -> STM (Maybe v) lookup k m = do var <- getTVar k m readTVar var+ {-# INLINABLE lookup #-} --- | /O(log n)/. Remove the value associated with a given key from the map,--- if present.------ __Note__: This does not actually remove the key from the map.--- In fact, it might actually increase the map's memory consumption--- by putting the key into the map.--- To completely delete an entry, including its key, use 'unsafeDelete'. delete :: (Eq k, Hashable k) => k -> Map k v -> STM () delete k m = do var <- getTVar k m writeTVar var Nothing+ {-# INLINABLE delete #-} -----------------------------------------------------------------------@@ -137,20 +112,6 @@ {-# INLINE getTVar #-} --- | /O(log n)/. Return the value associated with the given key, or 'Nothing'.------ In contrast to 'lookup', this will never increase the map's memory consumption.--- However, it might allow /phantom reads/ to occur.--- Consider the following situation:------ > f = atomically $ do v1 <- phantomLookup k m--- > v2 <- phantomLookup k m--- > return (v1 == v2)------ Under certain circumstances @f@ might actually return @False@, in particular--- if the first @phantomLookup@ happens on an empty map--- and some other transaction inserts a value for @k@ before the second call--- to @phantomLookup@. phantomLookup :: (Eq k, Hashable k) => k -> Map k v -> STM (Maybe v) phantomLookup k (Map root) = go root 0 undefined where@@ -172,9 +133,6 @@ {-# INLINABLE phantomLookup #-} --- | /O(log n)/. This will completely remove a given key--- and its associated value from the map, if present.--- This is not an atomic operation, however. __Use with caution!__ unsafeDelete :: (Eq k, Hashable k) => k -> Map k v -> IO () unsafeDelete k m@(Map root) = do ok <- go root 0 undefined
ttrie.cabal view
@@ -1,16 +1,7 @@ name: ttrie-version: 0.1+version: 0.1.0.0 synopsis: Contention-free STM hash map-description:- A contention-free STM hash map.- \"Contention-free\" means that the map will never cause spurious conflicts.- A transaction operating on the map will only ever have to retry if- another transaction is operating on the same key at the same time.- .- This is an implementation of the /transactional trie/,- which is basically a /lock-free concurrent hash trie/ lifted into STM.- For a detailed discussion, including an evaluation of its performance,- see Chapter 4 of <https://github.com/mcschroeder/thesis my master's thesis>.+-- description: homepage: http://github.com/mcschroeder/ttrie bug-reports: http://github.com/mcschroeder/ttrie/issues license: MIT@@ -23,29 +14,26 @@ extra-source-files: README.md, benchmarks/run.sh cabal-version: >=1.10 -source-repository head- type: git- location: https://github.com/mcschroeder/ttrie.git- library hs-source-dirs: src exposed-modules: Control.Concurrent.STM.Map other-modules: Data.SparseArray- default-language: Haskell2010- ghc-options: -Wall+ build-depends: base >=4.7 && <4.8- , atomic-primops >=0.6- , hashable >=1.2- , primitive >=0.5+ , atomic-primops ==0.6.*+ , hashable ==1.2.*+ , primitive ==0.5.* , stm >=2 -benchmark bench+ default-language: Haskell2010+ ghc-options: -Wall+++benchmark bench1 hs-source-dirs: benchmarks- main-is: Bench.hs- other-modules: BenchGen+ main-is: Bench1.hs+ other-modules: BenchGen, Common type: exitcode-stdio-1.0- default-language: Haskell2010- ghc-options: -O2 -threaded -with-rtsopts=-N build-depends:- base, async, bifunctors, containers, criterion-plus, deepseq, mwc-random, primitive, stm, stm-containers, stm-stats, text, transformers, ttrie, unordered-containers, vector-+ base, async, criterion >= 1.0, deepseq, hashable, stm, stm-containers, stm-stats, text, ttrie, unordered-containers, mwc-random, containers, transformers, vector, primitive, bifunctors+ ghc-options: -O2 -threaded -with-rtsopts=-N