8fabda4bce615cf63ae8cfcde73514c7453a63cb
[packages/containers.git] / benchmarks / IntMap.hs
1 {-# LANGUAGE BangPatterns #-}
2 module Main where
3
4 import Control.DeepSeq (rnf)
5 import Control.Exception (evaluate)
6 import Criterion.Main (bench, defaultMain, whnf)
7 import Data.List (foldl')
8 import qualified Data.IntMap as M
9 import qualified Data.IntMap.Strict as MS
10 import Data.Maybe (fromMaybe)
11 import Prelude hiding (lookup)
12
13 main = do
14 let m = M.fromAscList elems :: M.IntMap Int
15 evaluate $ rnf [m]
16 defaultMain
17 [ bench "lookup" $ whnf (lookup keys) m
18 , bench "insert" $ whnf (ins elems) M.empty
19 , bench "insertWith empty" $ whnf (insWith elems) M.empty
20 , bench "insertWith update" $ whnf (insWith elems) m
21 , bench "insertWith' empty" $ whnf (insWith' elems) M.empty
22 , bench "insertWith' update" $ whnf (insWith' elems) m
23 , bench "insertWithKey empty" $ whnf (insWithKey elems) M.empty
24 , bench "insertWithKey update" $ whnf (insWithKey elems) m
25 , bench "insertWithKey' empty" $ whnf (insWithKey' elems) M.empty
26 , bench "insertWithKey' update" $ whnf (insWithKey' elems) m
27 , bench "insertLookupWithKey empty" $ whnf (insLookupWithKey elems) M.empty
28 , bench "insertLookupWithKey update" $ whnf (insLookupWithKey elems) m
29 , bench "map" $ whnf (M.map (+ 1)) m
30 , bench "mapWithKey" $ whnf (M.mapWithKey (+)) m
31 , bench "foldlWithKey" $ whnf (ins elems) m
32 , bench "foldlWithKey'" $ whnf (M.foldlWithKey' sum 0) m
33 , bench "foldrWithKey" $ whnf (M.foldrWithKey consPair []) m
34 , bench "delete" $ whnf (del keys) m
35 , bench "update" $ whnf (upd keys) m
36 , bench "updateLookupWithKey" $ whnf (upd' keys) m
37 , bench "alter" $ whnf (alt keys) m
38 , bench "mapMaybe" $ whnf (M.mapMaybe maybeDel) m
39 , bench "mapMaybeWithKey" $ whnf (M.mapMaybeWithKey (const maybeDel)) m
40 , bench "fromList" $ whnf M.fromList elems
41 , bench "fromAscList" $ whnf M.fromAscList elems
42 , bench "fromDistinctAscList" $ whnf M.fromDistinctAscList elems
43 ]
44 where
45 elems = zip keys values
46 keys = [1..2^12]
47 values = [1..2^12]
48 sum k v1 v2 = k + v1 + v2
49 consPair k v xs = (k, v) : xs
50
51 add3 :: Int -> Int -> Int -> Int
52 add3 x y z = x + y + z
53 {-# INLINE add3 #-}
54
55 lookup :: [Int] -> M.IntMap Int -> Int
56 lookup xs m = foldl' (\n k -> fromMaybe n (M.lookup k m)) 0 xs
57
58 ins :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
59 ins xs m = foldl' (\m (k, v) -> M.insert k v m) m xs
60
61 insWith :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
62 insWith xs m = foldl' (\m (k, v) -> M.insertWith (+) k v m) m xs
63
64 insWithKey :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
65 insWithKey xs m = foldl' (\m (k, v) -> M.insertWithKey add3 k v m) m xs
66
67 insWith' :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
68 insWith' xs m = foldl' (\m (k, v) -> MS.insertWith (+) k v m) m xs
69
70 insWithKey' :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
71 insWithKey' xs m = foldl' (\m (k, v) -> MS.insertWithKey add3 k v m) m xs
72
73 data PairS a b = PS !a !b
74
75 insLookupWithKey :: [(Int, Int)] -> M.IntMap Int -> (Int, M.IntMap Int)
76 insLookupWithKey xs m = let !(PS a b) = foldl' f (PS 0 m) xs in (a, b)
77 where
78 f (PS n m) (k, v) = let !(n', m') = M.insertLookupWithKey add3 k v m
79 in PS (fromMaybe 0 n' + n) m'
80
81 del :: [Int] -> M.IntMap Int -> M.IntMap Int
82 del xs m = foldl' (\m k -> M.delete k m) m xs
83
84 upd :: [Int] -> M.IntMap Int -> M.IntMap Int
85 upd xs m = foldl' (\m k -> M.update Just k m) m xs
86
87 upd' :: [Int] -> M.IntMap Int -> M.IntMap Int
88 upd' xs m = foldl' (\m k -> snd $ M.updateLookupWithKey (\_ a -> Just a) k m) m xs
89
90 alt :: [Int] -> M.IntMap Int -> M.IntMap Int
91 alt xs m = foldl' (\m k -> M.alter id k m) m xs
92
93 maybeDel :: Int -> Maybe Int
94 maybeDel n | n `mod` 3 == 0 = Nothing
95 | otherwise = Just n