-
Notifications
You must be signed in to change notification settings - Fork 0
/
Bench.hs
167 lines (152 loc) · 8.54 KB
/
Bench.hs
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import Control.Exception
import Control.Monad
import Control.Monad.IO.Class (liftIO)
import Control.Monad.State.Strict
import Criterion.Main
import Data.Word
import Data.Vector (Vector)
import qualified Data.Vector as V
import qualified Data.HashSet as HashSet
import qualified Data.IntSet as Containers
import qualified Data.IntSet.FFI as FFI
import qualified Data.IntSet.GHC as ISGHC
import qualified Data.IntSet.Native as Native
import qualified Data.IntSet.NativeDiv as NativeDiv
import qualified Data.IntSet.NativeUS as NativeUS
import qualified Data.Set as Set
import System.Random
main :: IO ()
main = defaultMain [
bgroup "ffi" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetFFI 0 n v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetFFI 0 n v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetFFI 0 n v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetFFI 0 n v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetFFI 0 n v)
]
, bgroup "native" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNative 0 n v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNative 0 n v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNative 0 n v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNative 0 n v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNative 0 n v)
]
, bgroup "native-us" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeUS 0 n v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeUS 0 n v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeUS 0 n v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeUS 0 n v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeUS 0 n v)
]
, bgroup "native-div" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeDiv 0 n v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeDiv 0 n v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeDiv 0 n v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeDiv 0 n v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetNativeDiv 0 n v)
]
, bgroup "ghc" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetGHC 0 n v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetGHC 0 n v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetGHC 0 n v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetGHC 0 n v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetGHC 0 n v)
]
, bgroup "containers" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetContainers v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetContainers v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetContainers v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetContainers v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetContainers v)
]
, bgroup "set" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetSet v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetSet v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetSet v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetSet v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetSet v)
]
, bgroup "hashset" [ let n = 1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetHashSet v)
, let n = 10*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetHashSet v)
, let n = 100*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetHashSet v)
, let n = 1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetHashSet v)
, let n = 10*1000*1000; !v = generateInts 0 n (fromIntegral n) in bench (show n) $ whnfIO (intsetHashSet v)
]
]
intsetFFI :: Word64
-> Word64
-> Vector Word64
-> IO ()
intsetFFI minB maxB xs = bracket (FFI.new minB maxB 100) FFI.free $ \s ->
forM_ xs $ \i -> do
FFI.add s i
f <- FFI.check s i
unless f $
throwIO $ userError "implementation errors"
intsetNativeDiv :: Word64
-> Word64
-> Vector Word64
-> IO ()
intsetNativeDiv minB maxB xs = do
s <- NativeDiv.new minB maxB
forM_ xs $ \i -> do
NativeDiv.add s i
f <- NativeDiv.check s i
unless f $
throwIO $ userError "implementation errors"
intsetNative :: Word64
-> Word64
-> Vector Word64
-> IO ()
intsetNative minB maxB xs = do
s <- Native.new minB maxB
forM_ xs $ \i -> do
Native.add s i
f <- Native.check s i
unless f $
throwIO $ userError "implementation errors"
intsetNativeUS :: Word64
-> Word64
-> Vector Word64
-> IO ()
intsetNativeUS minB maxB xs = do
s <- NativeUS.new minB maxB
forM_ xs $ \i -> do
NativeUS.add s i
f <- NativeUS.check s i
unless f $
throwIO $ userError "implementation errors"
intsetGHC :: Word64
-> Word64
-> Vector Word64
-> IO ()
intsetGHC minB maxB xs = do
s <- ISGHC.new minB maxB
forM_ xs $ \i -> do
ISGHC.add s i
f <- ISGHC.check s i
unless f $
throwIO $ userError "implementation errors"
intsetContainers :: Vector Word64 -> IO Containers.IntSet
intsetContainers xs = execStateT go Containers.empty
where
go = forM xs $ \i -> do
modify' $ Containers.insert (fromIntegral i)
f <- gets $ Containers.member (fromIntegral i)
unless f $
liftIO . throwIO $ userError "implementation errors"
intsetSet :: Vector Word64 -> IO (Set.Set Word64)
intsetSet xs = execStateT go Set.empty
where
go = forM xs $ \i -> do
modify' $ Set.insert i
f <- gets $ Set.member i
unless f $
liftIO . throwIO $ userError "implementation errors"
intsetHashSet :: Vector Word64 -> IO (HashSet.HashSet Word64)
intsetHashSet xs = execStateT go HashSet.empty
where
go = forM xs $ \i -> do
modify' $ HashSet.insert i
f <- gets $ HashSet.member i
unless f $
liftIO . throwIO $ userError "implementation errors"
generateInts :: Word64
-> Word64
-> Int
-> Vector Word64
generateInts minB maxB n =
V.fromList . take n $ randomRs (minB, maxB) (mkStdGen 0x214f36c9)