1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE FlexibleContexts #-}
module Main where
import qualified Data.HashTable.Class as C
import Data.HashTable.IO
import Data.HashTable.Test.Common
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM
import Statistics.Quantile (continuousBy, cadpw)
import Statistics.Sample
import System.Environment
import System.Random.MWC
overhead :: C.HashTable h =>
FixedTableType h ->
GenIO ->
IO Double
overhead dummy rng = do
size <- uniformR (1000,50000) rng
!v <- replicateM' size $ uniform rng
let _ = v :: [(Int,Int)]
!ht <- fromList v
forceType dummy ht
x <- computeOverhead ht
return x
where
replicateM' :: Int -> IO a -> IO [a]
replicateM' !sz f = go sz []
where
go !i !l | i == 0 = return l
| otherwise = do
!x <- f
go (i-1) (x:l)
-- Returns mean / stddev
runTrials :: C.HashTable h =>
FixedTableType h
-> GenIO
-> Int
-> IO (Double, Double, Double, Double)
runTrials dummy rng ntrials = do
sample <- rep ntrials $ overhead dummy rng
let (m, v) = meanVarianceUnb sample
return (m, sqrt v, p95 sample, pMax sample)
where
p95 sample = continuousBy cadpw 19 20 sample
pMax sample = V.foldl' max (-1) sample
rep !n !f = do
mv <- VM.new n
go mv
where
go !mv = go' 0
where
go' !i | i >= n = V.unsafeFreeze mv
| otherwise = do
!d <- f
VM.unsafeWrite mv i d
go' $ i+1
main :: IO ()
main = do
rng <- do
args <- getArgs
if null args
then withSystemRandom (\x -> (return x) :: IO GenIO)
else initialize $ V.fromList [read $ head args]
runTrials dummyLinearTable rng nTrials >>= report "linear hash table"
runTrials dummyBasicTable rng nTrials >>= report "basic hash table"
runTrials dummyCuckooTable rng nTrials >>= report "cuckoo hash table"
where
nTrials = 200
report name md = putStrLn msg
where msg = concat [ "\n(Mean,StdDev,95%,Max) for overhead of "
, name
, " ("
, show nTrials
, " trials): "
, show md
, "\n" ]
dummyBasicTable = dummyTable
:: forall k v . BasicHashTable k v
dummyLinearTable = dummyTable
:: forall k v . LinearHashTable k v
dummyCuckooTable = dummyTable
:: forall k v . CuckooHashTable k v
|
