hashtable-benchmark (empty) → 0.1

raw patch · 5 files changed

+207/−0 lines, 5 filesdep +QuickCheckdep +basedep +containerssetup-changed

Dependencies added: QuickCheck, base, containers, criterion, hashtables, unordered-containers

Files

• LICENSE +29/−0
• README.md +23/−0
• Setup.hs +2/−0
• hashtable-benchmark.cabal +30/−0
• src/Main.hs +123/−0

@@ -0,0 +1,29 @@+BSD 3-Clause License++Copyright (c) 2017, Hongchang Wu+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++* Redistributions of source code must retain the above copyright notice, this+  list of conditions and the following disclaimer.++* Redistributions in binary form must reproduce the above copyright notice,+  this list of conditions and the following disclaimer in the documentation+  and/or other materials provided with the distribution.++* Neither the name of the copyright holder nor the names of its+  contributors may be used to endorse or promote products derived from+  this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,+OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,23 @@+# Haskell Hash Table Benchmark++[![Build Status](https://travis-ci.org/hongchangwu/hashtable-benchmark.svg?branch=master)](https://travis-ci.org/hongchangwu/hashtable-benchmark)++Benchmark of hash table implementations in Haskell:++- `Data.Map`+- `Data.IntMap`+- `Data.HashMap`+- `Data.HashTable`++## Build++```+stack setup+stack build+```++## Run++```+stack exec benchmark+```

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,30 @@+name:                hashtable-benchmark+version:             0.1+synopsis:            Benchmark of hash table implementations in Haskell+Description:         Please see README.md+homepage:            https://github.com/hongchangwu/hashtable-benchmark#readme+license:             BSD3+license-file:        LICENSE+author:              Hongchang Wu+maintainer:          wuhc85@gmail.com+copyright:           Copyright (c) 2017 Hongchang Wu+category:            Benchmarking+build-type:          Simple+extra-source-files:  README.md+cabal-version:       >=1.10++executable benchmark+  hs-source-dirs:      src+  main-is:             Main.hs+  ghc-options:         -fno-full-laziness -threaded -rtsopts -with-rtsopts=-N -Wall+  build-depends:       base >=4.5 && <5+                     , containers+                     , criterion+                     , hashtables+                     , QuickCheck+                     , unordered-containers+  default-language:    Haskell2010++source-repository head+  type:     git+  location: https://github.com/hongchangwu/hashtable-benchmark

@@ -0,0 +1,123 @@+module Main (main) where++import           Criterion.Main+import           Data.HashMap.Lazy    (HashMap)+import qualified Data.HashMap.Lazy    as HashMap+import           Data.HashTable.Class (HashTable)+import           Data.HashTable.IO    (BasicHashTable, CuckooHashTable,+                                       IOHashTable, LinearHashTable)+import qualified Data.HashTable.IO    as IOHashTable+import           Data.IntMap          (IntMap)+import qualified Data.IntMap          as IntMap+import           Data.List            (foldl')+import           Data.Map             (Map)+import qualified Data.Map             as Map+import           Test.QuickCheck      (generate, vector)++size :: Int+size = 1000000++type InsertInput = ([Int], [Int])++generateInsertInput :: Int -> IO InsertInput+generateInsertInput k = (,) <$> return [1 .. k] <*> generate (vector k)++type LookupInput = [Int]++generateLookupInput :: Int -> IO LookupInput+generateLookupInput k = generate (vector k)++main :: IO ()+main =+  defaultMain+    [ env (generateInsertInput size) $+      \ ~(sorted, random) ->+         bgroup+           "insert"+           [ bgroup+               "Data.Map"+               [ bench "sorted" $ whnf insertMap sorted+               , bench "random" $ whnf insertMap random+               ]+           , bgroup+               "Data.IntMap"+               [ bench "sorted" $ whnf insertIntMap sorted+               , bench "random" $ whnf insertIntMap random+               ]+           , bgroup+               "Data.HashMap.Lazy"+               [ bench "sorted" $ whnf insertHashMap sorted+               , bench "random" $ whnf insertHashMap random+               ]+           , bgroup+               "Data.HashTable.ST.Basic"+               [ bench "sorted" $+                 whnfIO+                   (insertHashTableIO sorted :: IO (BasicHashTable Int Int))+               , bench "random" $+                 whnfIO+                   (insertHashTableIO random :: IO (BasicHashTable Int Int))+               ]+           , bgroup+               "Data.HashTable.ST.Cuckoo"+               [ bench "sorted" $+                 whnfIO+                   (insertHashTableIO sorted :: IO (CuckooHashTable Int Int))+               , bench "random" $+                 whnfIO+                   (insertHashTableIO random :: IO (CuckooHashTable Int Int))+               ]+           , bgroup+               "Data.HashTable.ST.Linear"+               [ bench "sorted" $+                 whnfIO+                   (insertHashTableIO sorted :: IO (LinearHashTable Int Int))+               , bench "random" $+                 whnfIO+                   (insertHashTableIO random :: IO (LinearHashTable Int Int))+               ]+           ]+    , env (generateLookupInput size) $+      \ks ->+         bgroup+           "lookup"+           [ bench "Data.Map" $ nf lookupMap ks+           , bench "Data.IntMap" $ nf lookupIntMap ks+           , bench "Data.HashMap.Lazy" $ nf lookupHashMap ks+           ]+    ]++insertMap :: [Int] -> Map Int Int+insertMap = foldl' (\m k -> Map.insert k 1 m) Map.empty++insertIntMap :: [Int] -> IntMap Int+insertIntMap = foldl' (\m k -> IntMap.insert k 1 m) IntMap.empty++insertHashMap :: [Int] -> HashMap Int Int+insertHashMap = foldl' (\m k -> HashMap.insert k 1 m) HashMap.empty++insertHashTableIO+  :: HashTable h+  => [Int] -> IO (IOHashTable h Int Int)+insertHashTableIO xs = do+  ht <- IOHashTable.new+  mapM_ (\k -> IOHashTable.insert ht k 1) xs+  return ht++aMap :: Map Int Int+aMap = Map.fromAscList [(k, 1) | k <- [1 .. size]]++lookupMap :: [Int] -> [Maybe Int]+lookupMap = map (`Map.lookup` aMap)++aIntMap :: IntMap Int+aIntMap = IntMap.fromAscList [(k, 1) | k <- [1 .. size]]++lookupIntMap :: [Int] -> [Maybe Int]+lookupIntMap = map (`IntMap.lookup` aIntMap)++aHashMap :: HashMap Int Int+aHashMap = HashMap.fromList [(k, 1) | k <- [1 .. size]]++lookupHashMap :: [Int] -> [Maybe Int]+lookupHashMap = map (`HashMap.lookup` aHashMap)