git.iko.soy/streamly
on df8de8d help sign in
streamly/benchmark/Linear.hs
430 lines 19 kB history raw
1{-# LANGUAGE CPP #-}
2#if __GLASGOW_HASKELL__ >= 800
3{-# OPTIONS_GHC -Wno-orphans #-}
4#endif
6-- |
7-- Module : Main
8-- Copyright : (c) 2018 Harendra Kumar
9--
10-- License : BSD3
11-- Maintainer : harendra.kumar@gmail.com
13import Control.DeepSeq (NFData(..), deepseq)
14import Data.Functor.Identity (Identity, runIdentity)
15import System.Random (randomRIO)
16import Data.Monoid (Last(..))
18import qualified GHC.Exts as GHC
19import qualified Streamly.Benchmark.Prelude as Ops
21import Streamly
22import qualified Streamly.Data.Fold as FL
23import qualified Streamly.Memory.Array as A
24import qualified Streamly.Prelude as S
25import qualified Streamly.Internal.Data.Sink as Sink
27import qualified Streamly.Internal.Data.Fold as IFL
28import qualified Streamly.Internal.Prelude as IP
29import qualified Streamly.Internal.Data.Pipe as Pipe
31import Gauge
33-------------------------------------------------------------------------------
34--
35-------------------------------------------------------------------------------
37#if !MIN_VERSION_deepseq(1,4,3)
38instance NFData Ordering where rnf = (`seq` ())
39#endif
41-- We need a monadic bind here to make sure that the function f does not get
42-- completely optimized out by the compiler in some cases.
44-- | Takes a fold method, and uses it with a default source.
45{-# INLINE benchIOSink #-}
46benchIOSink
47 :: (IsStream t, NFData b)
48 => String -> (t IO Int -> IO b) -> Benchmark
49benchIOSink name f = bench name $ nfIO $ randomRIO (1,1) >>= f . Ops.source
51-- XXX once we convert all the functions to use this we can rename this to
52-- benchIOSink
53{-# INLINE benchIOSink1 #-}
54benchIOSink1 :: NFData b => String -> (Int -> IO b) -> Benchmark
55benchIOSink1 name f = bench name $ nfIO $ randomRIO (1,1) >>= f
57-- XXX We should be using sourceUnfoldrM for fair comparison with IO monad, but
58-- we can't use it as it requires MonadAsync constraint.
59{-# INLINE benchIdentitySink #-}
60benchIdentitySink
61 :: (IsStream t, NFData b)
62 => String -> (t Identity Int -> Identity b) -> Benchmark
63benchIdentitySink name f = bench name $ nf (f . Ops.sourceUnfoldr) 1
65-- | Takes a source, and uses it with a default drain/fold method.
66{-# INLINE benchIOSrc #-}
67benchIOSrc
68 :: (t IO a -> SerialT IO a)
69 -> String
70 -> (Int -> t IO a)
71 -> Benchmark
72benchIOSrc t name f =
73 bench name $ nfIO $ randomRIO (1,1) >>= Ops.toNull t . f
75{-# INLINE benchIOSrc1 #-}
76benchIOSrc1 :: String -> (Int -> IO ()) -> Benchmark
77benchIOSrc1 name f = bench name $ nfIO $ randomRIO (1,1) >>= f
79{-# INLINE benchPure #-}
80benchPure :: NFData b => String -> (Int -> a) -> (a -> b) -> Benchmark
81benchPure name src f = bench name $ nfIO $ randomRIO (1,1) >>= return . f . src
83{-# INLINE benchPureSink #-}
84benchPureSink :: NFData b => String -> (SerialT Identity Int -> b) -> Benchmark
85benchPureSink name f = benchPure name Ops.sourceUnfoldr f
87-- XXX once we convert all the functions to use this we can rename this to
88-- benchPureSink
89{-# INLINE benchPureSink1 #-}
90benchPureSink1 :: NFData b => String -> (Int -> Identity b) -> Benchmark
91benchPureSink1 name f =
92 bench name $ nfIO $ randomRIO (1,1) >>= return . runIdentity . f
94{-# INLINE benchPureSinkIO #-}
95benchPureSinkIO
96 :: NFData b
97 => String -> (SerialT Identity Int -> IO b) -> Benchmark
98benchPureSinkIO name f =
99 bench name $ nfIO $ randomRIO (1, 1) >>= f . Ops.sourceUnfoldr
101{-# INLINE benchPureSrc #-}
102benchPureSrc :: String -> (Int -> SerialT Identity a) -> Benchmark
103benchPureSrc name src = benchPure name src (runIdentity . S.drain)
105mkString :: String
106mkString = "fromList [1" ++ concat (replicate Ops.value ",1") ++ "]"
108mkListString :: String
109mkListString = "[1" ++ concat (replicate Ops.value ",1") ++ "]"
111mkList :: [Int]
112mkList = [1..Ops.value]
114main :: IO ()
115main =
116 defaultMain
117 [ bgroup "serially"
118 [ bgroup "pure"
119 [ benchPureSink "id" id
120 , benchPureSink1 "eqBy" Ops.eqByPure
121 , benchPureSink "==" Ops.eqInstance
122 , benchPureSink "/=" Ops.eqInstanceNotEq
123 , benchPureSink1 "cmpBy" Ops.cmpByPure
124 , benchPureSink "<" Ops.ordInstance
125 , benchPureSink "min" Ops.ordInstanceMin
126 , benchPureSrc "IsList.fromList" Ops.sourceIsList
127 , benchPureSink "IsList.toList" GHC.toList
128 , benchPureSrc "IsString.fromString" Ops.sourceIsString
129 , mkString `deepseq` (bench "readsPrec pure streams" $
130 nf Ops.readInstance mkString)
131 , mkString `deepseq` (bench "readsPrec Haskell lists" $
132 nf Ops.readInstanceList mkListString)
133 , benchPureSink "showsPrec pure streams" Ops.showInstance
134 , mkList `deepseq` (bench "showPrec Haskell lists" $
135 nf Ops.showInstanceList mkList)
136 , benchPureSink "foldl'" Ops.pureFoldl'
137 , benchPureSink "foldable/foldl'" Ops.foldableFoldl'
138 , benchPureSink "foldable/sum" Ops.foldableSum
139 , benchPureSinkIO "traversable/mapM" Ops.traversableMapM
140 ]
141 , bgroup "generation"
142 [ -- Most basic, barely stream continuations running
143 benchIOSrc serially "unfoldr" Ops.sourceUnfoldr
144 , benchIOSrc serially "unfoldrM" Ops.sourceUnfoldrM
145 , benchIOSrc serially "intFromTo" Ops.sourceIntFromTo
146 , benchIOSrc serially "intFromThenTo" Ops.sourceIntFromThenTo
147 , benchIOSrc serially "integerFromStep" Ops.sourceIntegerFromStep
148 , benchIOSrc serially "fracFromThenTo" Ops.sourceFracFromThenTo
149 , benchIOSrc serially "fracFromTo" Ops.sourceFracFromTo
150 , benchIOSrc serially "fromList" Ops.sourceFromList
151 , benchIOSrc serially "fromListM" Ops.sourceFromListM
152 -- These are essentially cons and consM
153 , benchIOSrc serially "fromFoldable" Ops.sourceFromFoldable
154 , benchIOSrc serially "fromFoldableM" Ops.sourceFromFoldableM
155 ]
156 , bgroup "elimination"
157 [ bgroup "reduce"
158 [ bgroup "IO"
159 [ benchIOSink "foldrM" Ops.foldrMReduce
160 , benchIOSink "foldl'" Ops.foldl'Reduce
161 , benchIOSink "foldl1'" Ops.foldl1'Reduce
162 , benchIOSink "foldlM'" Ops.foldlM'Reduce
163 ]
164 , bgroup "Identity"
165 [ benchIdentitySink "foldrM" Ops.foldrMReduce
166 , benchIdentitySink "foldl'" Ops.foldl'Reduce
167 , benchIdentitySink "foldl1'" Ops.foldl1'Reduce
168 , benchIdentitySink "foldlM'" Ops.foldlM'Reduce
169 ]
170 ]
172 , bgroup "build"
173 [ bgroup "IO"
174 [ benchIOSink "foldrM" Ops.foldrMBuild
175 , benchIOSink "foldl'" Ops.foldl'Build
176 , benchIOSink "foldlM'" Ops.foldlM'Build
177 ]
178 , bgroup "Identity"
179 [ benchIdentitySink "foldrM" Ops.foldrMBuild
180 , benchIdentitySink "foldl'" Ops.foldl'Build
181 , benchIdentitySink "foldlM'" Ops.foldlM'Build
182 ]
183 ]
184 , benchIOSink "uncons" Ops.uncons
185 , benchIOSink "toNull" $ Ops.toNull serially
186 , benchIOSink "mapM_" Ops.mapM_
188 , benchIOSink "init" Ops.init
189 , benchIOSink "tail" Ops.tail
190 , benchIOSink "nullHeadTail" Ops.nullHeadTail
192 -- this is too low and causes all benchmarks reported in ns
193 -- , benchIOSink "head" Ops.head
194 , benchIOSink "last" Ops.last
195 -- , benchIOSink "lookup" Ops.lookup
196 , benchIOSink "find" Ops.find
197 , benchIOSink "findIndex" Ops.findIndex
198 , benchIOSink "elemIndex" Ops.elemIndex
200 -- this is too low and causes all benchmarks reported in ns
201 -- , benchIOSink "null" Ops.null
202 , benchIOSink "elem" Ops.elem
203 , benchIOSink "notElem" Ops.notElem
204 , benchIOSink "all" Ops.all
205 , benchIOSink "any" Ops.any
206 , benchIOSink "and" Ops.and
207 , benchIOSink "or" Ops.or
209 , benchIOSink "length" Ops.length
210 , benchIOSink "sum" Ops.sum
211 , benchIOSink "product" Ops.product
213 , benchIOSink "maximumBy" Ops.maximumBy
214 , benchIOSink "maximum" Ops.maximum
215 , benchIOSink "minimumBy" Ops.minimumBy
216 , benchIOSink "minimum" Ops.minimum
218 , benchIOSink "toList" Ops.toList
219 , benchIOSink "toListRev" Ops.toListRev
220 ]
221 , bgroup "folds"
222 [ benchIOSink "drain" (S.fold FL.drain)
223 , benchIOSink "sink" (S.fold $ Sink.toFold Sink.drain)
224 , benchIOSink "last" (S.fold FL.last)
225 , benchIOSink "length" (S.fold FL.length)
226 , benchIOSink "sum" (S.fold FL.sum)
227 , benchIOSink "product" (S.fold FL.product)
228 , benchIOSink "maximumBy" (S.fold (FL.maximumBy compare))
229 , benchIOSink "maximum" (S.fold FL.maximum)
230 , benchIOSink "minimumBy" (S.fold (FL.minimumBy compare))
231 , benchIOSink "minimum" (S.fold FL.minimum)
232 , benchIOSink "mean" (\s -> S.fold FL.mean (S.map (fromIntegral :: Int -> Double) s))
233 , benchIOSink "variance" (\s -> S.fold FL.variance (S.map (fromIntegral :: Int -> Double) s))
234 , benchIOSink "stdDev" (\s -> S.fold FL.stdDev (S.map (fromIntegral :: Int -> Double) s))
236 , benchIOSink "mconcat" (S.fold FL.mconcat . (S.map (Last . Just)))
237 , benchIOSink "foldMap" (S.fold (FL.foldMap (Last . Just)))
239 , benchIOSink "toList" (S.fold FL.toList)
240 , benchIOSink "toListRevF" (S.fold IFL.toListRevF)
241 , benchIOSink "toStream" (S.fold IP.toStream)
242 , benchIOSink "toStreamRev" (S.fold IP.toStreamRev)
243 , benchIOSink "writeN" (S.fold (A.writeN Ops.value))
245 , benchIOSink "index" (S.fold (FL.index Ops.maxValue))
246 , benchIOSink "head" (S.fold FL.head)
247 , benchIOSink "find" (S.fold (FL.find (== Ops.maxValue)))
248 , benchIOSink "findIndex" (S.fold (FL.findIndex (== Ops.maxValue)))
249 , benchIOSink "elemIndex" (S.fold (FL.elemIndex Ops.maxValue))
251 , benchIOSink "null" (S.fold FL.null)
252 , benchIOSink "elem" (S.fold (FL.elem Ops.maxValue))
253 , benchIOSink "notElem" (S.fold (FL.notElem Ops.maxValue))
254 , benchIOSink "all" (S.fold (FL.all (<= Ops.maxValue)))
255 , benchIOSink "any" (S.fold (FL.any (> Ops.maxValue)))
256 , benchIOSink "and" (\s -> S.fold FL.and (S.map (<= Ops.maxValue) s))
257 , benchIOSink "or" (\s -> S.fold FL.or (S.map (> Ops.maxValue) s))
258 ]
259 , bgroup "fold-multi-stream"
260 [ benchIOSink1 "eqBy" Ops.eqBy
261 , benchIOSink1 "cmpBy" Ops.cmpBy
262 , benchIOSink "isPrefixOf" Ops.isPrefixOf
263 , benchIOSink "isSubsequenceOf" Ops.isSubsequenceOf
264 , benchIOSink "stripPrefix" Ops.stripPrefix
265 ]
266 , bgroup "folds-transforms"
267 [ benchIOSink "drain" (S.fold FL.drain)
268 , benchIOSink "lmap" (S.fold (IFL.lmap (+1) FL.drain))
269 , benchIOSink "pipe-mapM"
270 (S.fold (IFL.transform (Pipe.mapM (\x -> return $ x + 1)) FL.drain))
271 ]
272 , bgroup "folds-compositions" -- Applicative
273 [
274 benchIOSink "all,any" (S.fold ((,) <$> FL.all (<= Ops.maxValue)
275 <*> FL.any (> Ops.maxValue)))
276 , benchIOSink "sum,length" (S.fold ((,) <$> FL.sum <*> FL.length))
277 ]
278 , bgroup "pipes"
279 [ benchIOSink "mapM" (Ops.transformMapM serially 1)
280 , benchIOSink "compose" (Ops.transformComposeMapM serially 1)
281 , benchIOSink "tee" (Ops.transformTeeMapM serially 1)
282 , benchIOSink "zip" (Ops.transformZipMapM serially 1)
283 ]
284 , bgroup "pipesX4"
285 [ benchIOSink "mapM" (Ops.transformMapM serially 4)
286 , benchIOSink "compose" (Ops.transformComposeMapM serially 4)
287 , benchIOSink "tee" (Ops.transformTeeMapM serially 4)
288 , benchIOSink "zip" (Ops.transformZipMapM serially 4)
289 ]
290 , bgroup "transformation"
291 [ benchIOSink "scanl" (Ops.scan 1)
292 , benchIOSink "scanl1'" (Ops.scanl1' 1)
293 , benchIOSink "map" (Ops.map 1)
294 , benchIOSink "fmap" (Ops.fmap 1)
295 , benchIOSink "mapM" (Ops.mapM serially 1)
296 , benchIOSink "mapMaybe" (Ops.mapMaybe 1)
297 , benchIOSink "mapMaybeM" (Ops.mapMaybeM 1)
298 , bench "sequence" $ nfIO $ randomRIO (1,1000) >>= \n ->
299 Ops.sequence serially (Ops.sourceUnfoldrMAction n)
300 , benchIOSink "findIndices" (Ops.findIndices 1)
301 , benchIOSink "elemIndices" (Ops.elemIndices 1)
302 , benchIOSink "reverse" (Ops.reverse 1)
303 , benchIOSink "reverse'" (Ops.reverse' 1)
304 , benchIOSink "foldrS" (Ops.foldrS 1)
305 , benchIOSink "foldrSMap" (Ops.foldrSMap 1)
306 , benchIOSink "foldrT" (Ops.foldrT 1)
307 , benchIOSink "foldrTMap" (Ops.foldrTMap 1)
308 ]
309 , bgroup "transformationX4"
310 [ benchIOSink "scan" (Ops.scan 4)
311 , benchIOSink "scanl1'" (Ops.scanl1' 4)
312 , benchIOSink "map" (Ops.map 4)
313 , benchIOSink "fmap" (Ops.fmap 4)
314 , benchIOSink "mapM" (Ops.mapM serially 4)
315 , benchIOSink "mapMaybe" (Ops.mapMaybe 4)
316 , benchIOSink "mapMaybeM" (Ops.mapMaybeM 4)
317 -- , bench "sequence" $ nfIO $ randomRIO (1,1000) >>= \n ->
318 -- Ops.sequence serially (Ops.sourceUnfoldrMAction n)
319 , benchIOSink "findIndices" (Ops.findIndices 4)
320 , benchIOSink "elemIndices" (Ops.elemIndices 4)
321 ]
322 , bgroup "filtering"
323 [ benchIOSink "filter-even" (Ops.filterEven 1)
324 , benchIOSink "filter-all-out" (Ops.filterAllOut 1)
325 , benchIOSink "filter-all-in" (Ops.filterAllIn 1)
326 , benchIOSink "take-all" (Ops.takeAll 1)
327 , benchIOSink "takeWhile-true" (Ops.takeWhileTrue 1)
328 --, benchIOSink "takeWhileM-true" (Ops.takeWhileMTrue 1)
329 , benchIOSink "drop-one" (Ops.dropOne 1)
330 , benchIOSink "drop-all" (Ops.dropAll 1)
331 , benchIOSink "dropWhile-true" (Ops.dropWhileTrue 1)
332 --, benchIOSink "dropWhileM-true" (Ops.dropWhileMTrue 1)
333 , benchIOSink "dropWhile-false" (Ops.dropWhileFalse 1)
334 , benchIOSink "deleteBy" (Ops.deleteBy 1)
335 , benchIOSink "intersperse" (Ops.intersperse 1)
336 , benchIOSink "insertBy" (Ops.insertBy 1)
337 ]
338 , bgroup "filteringX4"
339 [ benchIOSink "filter-even" (Ops.filterEven 4)
340 , benchIOSink "filter-all-out" (Ops.filterAllOut 4)
341 , benchIOSink "filter-all-in" (Ops.filterAllIn 4)
342 , benchIOSink "take-all" (Ops.takeAll 4)
343 , benchIOSink "takeWhile-true" (Ops.takeWhileTrue 4)
344 --, benchIOSink "takeWhileM-true" (Ops.takeWhileMTrue 4)
345 , benchIOSink "drop-one" (Ops.dropOne 4)
346 , benchIOSink "drop-all" (Ops.dropAll 4)
347 , benchIOSink "dropWhile-true" (Ops.dropWhileTrue 4)
348 --, benchIOSink "dropWhileM-true" (Ops.dropWhileMTrue 4)
349 , benchIOSink "dropWhile-false" (Ops.dropWhileFalse 4)
350 , benchIOSink "deleteBy" (Ops.deleteBy 4)
351 , benchIOSink "intersperse" (Ops.intersperse 4)
352 , benchIOSink "insertBy" (Ops.insertBy 4)
353 ]
354 , bgroup "joining"
355 [ benchIOSrc1 "zip (2x50K)" (Ops.zip 50000)
356 , benchIOSrc1 "zipM (2x50K)" (Ops.zipM 50000)
357 , benchIOSrc1 "mergeBy (2x50K)" (Ops.mergeBy 50000)
358 , benchIOSrc1 "serial (2x50K)" (Ops.serial2 50000)
359 , benchIOSrc1 "append (2x50K)" (Ops.append2 50000)
360 , benchIOSrc1 "serial (2x2x25K)" (Ops.serial4 25000)
361 , benchIOSrc1 "append (2x2x25K)" (Ops.append4 25000)
362 , benchIOSrc1 "wSerial (2x50K)" Ops.wSerial2
363 , benchIOSrc1 "interleave (2x50K)" Ops.interleave2
364 , benchIOSrc1 "roundRobin (2x50K)" Ops.roundRobin2
365 ]
366 , bgroup "concat-foldable"
367 [ benchIOSrc serially "foldMapWith (1x100K)" Ops.sourceFoldMapWith
368 , benchIOSrc serially "foldMapWithM (1x100K)" Ops.sourceFoldMapWithM
369 , benchIOSrc serially "foldMapM (1x100K)" Ops.sourceFoldMapM
370 , benchIOSrc serially "foldWithConcatMapId (1x100K)" Ops.sourceConcatMapId
371 ]
372 , bgroup "concat-serial"
373 [ benchIOSrc1 "concatMapPure (2x50K)" (Ops.concatMapPure 2 50000)
374 , benchIOSrc1 "concatMap (2x50K)" (Ops.concatMap 2 50000)
375 , benchIOSrc1 "concatMap (50Kx2)" (Ops.concatMap 50000 2)
376 , benchIOSrc1 "concatMapRepl (25Kx4)" Ops.concatMapRepl4xN
377 , benchIOSrc1 "concatUnfoldRepl (25Kx4)" Ops.concatUnfoldRepl4xN
379 , benchIOSrc1 "concatMapWithSerial (2x50K)"
380 (Ops.concatMapWithSerial 2 50000)
381 , benchIOSrc1 "concatMapWithSerial (50Kx2)"
382 (Ops.concatMapWithSerial 50000 2)
384 , benchIOSrc1 "concatMapWithAppend (2x50K)"
385 (Ops.concatMapWithAppend 2 50000)
386 ]
387 , bgroup "concat-interleave"
388 [ benchIOSrc1 "concatMapWithWSerial (2x50K)"
389 (Ops.concatMapWithWSerial 2 50000)
390 , benchIOSrc1 "concatMapWithWSerial (50Kx2)"
391 (Ops.concatMapWithWSerial 50000 2)
392 , benchIOSrc1 "concatUnfoldInterleaveRepl (25Kx4)"
393 Ops.concatUnfoldInterleaveRepl4xN
394 , benchIOSrc1 "concatUnfoldRoundrobinRepl (25Kx4)"
395 Ops.concatUnfoldRoundrobinRepl4xN
396 ]
397 -- scanl-map and foldl-map are equivalent to the scan and fold in the foldl
398 -- library. If scan/fold followed by a map is efficient enough we may not
399 -- need monolithic implementations of these.
400 , bgroup "mixed"
401 [ benchIOSink "scanl-map" (Ops.scanMap 1)
402 , benchIOSink "foldl-map" Ops.foldl'ReduceMap
403 , benchIOSink "sum-product-fold" Ops.sumProductFold
404 , benchIOSink "sum-product-scan" Ops.sumProductScan
405 ]
406 , bgroup "mixedX4"
407 [ benchIOSink "scan-map" (Ops.scanMap 4)
408 , benchIOSink "drop-map" (Ops.dropMap 4)
409 , benchIOSink "drop-scan" (Ops.dropScan 4)
410 , benchIOSink "take-drop" (Ops.takeDrop 4)
411 , benchIOSink "take-scan" (Ops.takeScan 4)
412 , benchIOSink "take-map" (Ops.takeMap 4)
413 , benchIOSink "filter-drop" (Ops.filterDrop 4)
414 , benchIOSink "filter-take" (Ops.filterTake 4)
415 , benchIOSink "filter-scan" (Ops.filterScan 4)
416 , benchIOSink "filter-scanl1" (Ops.filterScanl1 4)
417 , benchIOSink "filter-map" (Ops.filterMap 4)
418 ]
419 , bgroup "iterated"
420 [ benchIOSrc serially "mapM" Ops.iterateMapM
421 , benchIOSrc serially "scan(1/100)" Ops.iterateScan
422 , benchIOSrc serially "scanl1(1/100)" Ops.iterateScanl1
423 , benchIOSrc serially "filterEven" Ops.iterateFilterEven
424 , benchIOSrc serially "takeAll" Ops.iterateTakeAll
425 , benchIOSrc serially "dropOne" Ops.iterateDropOne
426 , benchIOSrc serially "dropWhileFalse" Ops.iterateDropWhileFalse
427 , benchIOSrc serially "dropWhileTrue" Ops.iterateDropWhileTrue
428 ]
429 ]
430 ]