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