packages feed

psqueues 0.2.2.0 → 0.2.2.1

raw patch · 8 files changed

+314/−1 lines, 8 files

Files

CHANGELOG view
@@ -1,3 +1,6 @@+- 0.2.2.1+    * Fix benchmark compilation with stack+ - 0.2.2.0     * Fix import of Traversable on GHC 7.8
+ benchmarks/BenchmarkTypes.hs view
@@ -0,0 +1,28 @@++module BenchmarkTypes where++import Criterion++type BElem = (Int, Int, ())++data BenchmarkSet = BenchmarkSet+    { bGroupName        :: String+    , bMinView          :: Benchmarkable+    , bLookup           :: Benchmarkable+    , bInsertEmpty      :: Benchmarkable+    , bInsertNew        :: Benchmarkable+    , bInsertDuplicates :: Benchmarkable+    , bDelete           :: Benchmarkable+    }++runBenchmark :: [BenchmarkSet] -> [Benchmark]+runBenchmark bset =+    [ bgroup "minView"          $ map (bench' bMinView)          bset+    , bgroup "lookup"           $ map (bench' bLookup)           bset+    , bgroup "insertEmpty"      $ map (bench' bInsertEmpty)      bset+    , bgroup "insertNew"        $ map (bench' bInsertNew)        bset+    , bgroup "insertDuplicates" $ map (bench' bInsertDuplicates) bset+    , bgroup "delete"           $ map (bench' bDelete)           bset+    ]+  where+   bench' f x = bench (bGroupName x) (f x)
+ benchmarks/Data/FingerTree/PSQueue/Benchmark.hs view
@@ -0,0 +1,61 @@+{-# LANGUAGE BangPatterns #-}++-- | This module contains benchmarks for the 'PSQueue' type from the+-- `fingertree-psqueue` package.+module Data.FingerTree.PSQueue.Benchmark+    ( benchmark+    ) where++import           Data.List (foldl')+import           Data.FingerTree.PSQueue (Binding (..))+import qualified Data.FingerTree.PSQueue as PSQueue+import           Criterion.Main+import           Prelude hiding (lookup)+import           BenchmarkTypes+import           Data.Maybe (fromMaybe)++benchmark :: String -> [BElem] -> BenchmarkSet+benchmark name elems = BenchmarkSet+    { bGroupName        = name+    , bMinView          = whnf bench_minView              initialPSQ+    , bLookup           = whnf (bench_lookup keys)        initialPSQ+    , bInsertEmpty      = nf'  (bench_insert firstElems)  PSQueue.empty+    , bInsertNew        = nf'  (bench_insert secondElems) initialPSQ+    , bInsertDuplicates = nf'  (bench_insert firstElems)  initialPSQ+    , bDelete           = nf'  (bench_delete firstKeys)   initialPSQ+    }+  where+    (firstElems, secondElems) = splitAt (numElems `div` 2) elems+    numElems  = length elems+    keys      = map (\(x, _, _) -> x) elems+    firstKeys = map (\(x, _, _) -> x) firstElems++    initialPSQ :: PSQueue.PSQ Int Int+    initialPSQ = PSQueue.fromList $ map toBinding firstElems++    toBinding :: BElem -> Binding Int Int+    toBinding (k, p, _) = k :-> p++    -- Get the size of the resulting PSQs, since there's no NFData instance+    nf' f x = whnf (PSQueue.size . f) x++bench_lookup :: [Int] -> PSQueue.PSQ Int Int -> Int+bench_lookup xs m = foldl' (\n k -> fromMaybe n (PSQueue.lookup k m)) 0 xs++bench_insert :: [BElem] -> PSQueue.PSQ Int Int -> PSQueue.PSQ Int Int+bench_insert xs m0 = foldl' (\m (k, p, _) -> fingerInsert k p m) m0 xs+  where+    fingerInsert+        :: (Ord k, Ord v) => k -> v -> PSQueue.PSQ k v -> PSQueue.PSQ k v+    fingerInsert k v m = PSQueue.alter (const $ Just v) k m++bench_minView :: PSQueue.PSQ Int Int -> Int+bench_minView = go 0+  where+    go !n t = case PSQueue.minView t of+      Nothing              -> n+      Just ((k :-> x), t') -> go (n + k + x) t'++-- Empty a queue by sequentially removing all elements+bench_delete :: [Int] -> PSQueue.PSQ Int Int -> PSQueue.PSQ Int Int+bench_delete keys t0 = foldl' (\t k -> PSQueue.delete k t) t0 keys
+ benchmarks/Data/HashPSQ/Benchmark.hs view
@@ -0,0 +1,53 @@+{-# LANGUAGE BangPatterns #-}++module Data.HashPSQ.Benchmark+    ( benchmark+    ) where++import           Data.List (foldl')+import qualified Data.HashPSQ as HashPSQ+import           Criterion.Main+import           Prelude hiding (lookup)+import           BenchmarkTypes++benchmark :: String -> [BElem] -> BenchmarkSet+benchmark name elems = BenchmarkSet+    { bGroupName        = name+    , bMinView          = whnf bench_minView              initialPSQ+    , bLookup           = whnf (bench_lookup keys)        initialPSQ+    , bInsertEmpty      = nf   (bench_insert firstElems)  HashPSQ.empty+    , bInsertNew        = nf   (bench_insert secondElems) initialPSQ+    , bInsertDuplicates = nf   (bench_insert firstElems)  initialPSQ+    , bDelete           = nf   (bench_delete firstKeys)   initialPSQ+    }+  where+    (firstElems, secondElems) = splitAt (numElems `div` 2) elems+    numElems  = length elems+    keys      = map (\(x, _, _) -> x) elems+    firstKeys = map (\(x, _, _) -> x) firstElems++    initialPSQ = HashPSQ.fromList firstElems :: HashPSQ.HashPSQ Int Int ()+++-- Get the sum of all priorities by getting all elements using 'lookup'+bench_lookup :: [Int] -> HashPSQ.HashPSQ Int Int () -> Int+bench_lookup xs m = foldl' (\n k -> maybe n fst (HashPSQ.lookup k m)) 0 xs++-- Insert a list of elements one-by-one into a PSQ+bench_insert+    :: [BElem] -> HashPSQ.HashPSQ Int Int () -> HashPSQ.HashPSQ Int Int ()+bench_insert xs m0 = foldl' (\m (k, p, v) -> HashPSQ.insert k p v m) m0 xs++-- Get the sum of all priorities by sequentially popping all elements using+-- 'minView'+bench_minView :: HashPSQ.HashPSQ Int Int () -> Int+bench_minView = go 0+  where+    go !n t = case HashPSQ.minView t of+      Nothing             -> n+      Just (k, x, _,  t') -> go (n + k + x) t'++-- Empty a queue by sequentially removing all elements+bench_delete+    :: [Int] -> HashPSQ.HashPSQ Int Int () -> HashPSQ.HashPSQ Int Int ()+bench_delete keys t0 = foldl' (\t k -> HashPSQ.delete k t) t0 keys
+ benchmarks/Data/IntPSQ/Benchmark.hs view
@@ -0,0 +1,50 @@+{-# LANGUAGE BangPatterns #-}+module Data.IntPSQ.Benchmark+    ( benchmark+    ) where++import           Data.List (foldl')+import qualified Data.IntPSQ as IntPSQ+import           Criterion.Main+import           Prelude hiding (lookup)+import           BenchmarkTypes++benchmark :: String -> [BElem] -> BenchmarkSet+benchmark name elems = BenchmarkSet+    { bGroupName        = name+    , bMinView          = whnf bench_minView              initialPSQ+    , bLookup           = whnf (bench_lookup keys)        initialPSQ+    , bInsertEmpty      = nf   (bench_insert firstElems)  IntPSQ.empty+    , bInsertNew        = nf   (bench_insert secondElems) initialPSQ+    , bInsertDuplicates = nf   (bench_insert firstElems)  initialPSQ+    , bDelete           = nf   (bench_delete firstKeys)   initialPSQ+    }+  where+    (firstElems, secondElems) = splitAt (numElems `div` 2) elems+    numElems  = length elems+    keys      = map (\(x, _, _) -> x) elems+    firstKeys = map (\(x, _, _) -> x) firstElems++    initialPSQ = IntPSQ.fromList firstElems :: IntPSQ.IntPSQ Int ()++-- Get the sum of all priorities by getting all elements using 'lookup'+bench_lookup :: [Int] -> IntPSQ.IntPSQ Int () -> Int+bench_lookup xs m = foldl' (\n k -> maybe n fst (IntPSQ.lookup k m)) 0 xs++-- Insert a list of elements one-by-one into a PSQ+bench_insert+    :: [(Int, Int, ())] -> IntPSQ.IntPSQ Int () -> IntPSQ.IntPSQ Int ()+bench_insert xs m0 = foldl' (\m (k, p, v) -> IntPSQ.insert k p v m) m0 xs++-- Get the sum of all priorities by sequentially popping all elements using+-- 'minView'+bench_minView :: IntPSQ.IntPSQ Int () -> Int+bench_minView = go 0+  where+    go !n t = case IntPSQ.minView t of+      Nothing            -> n+      Just (k, p, _, t') -> go (n + k + p) t'++-- Empty a queue by sequentially removing all elements+bench_delete :: [Int] -> IntPSQ.IntPSQ Int () -> IntPSQ.IntPSQ Int ()+bench_delete keys t0 = foldl' (\t k -> IntPSQ.delete k t) t0 keys
+ benchmarks/Data/OrdPSQ/Benchmark.hs view
@@ -0,0 +1,49 @@+{-# LANGUAGE BangPatterns #-}+module Data.OrdPSQ.Benchmark+    ( benchmark+    ) where++import           Data.List (foldl')+import qualified Data.OrdPSQ as OrdPSQ+import           Criterion.Main+import           Prelude hiding (lookup)+import           BenchmarkTypes++benchmark :: String -> [BElem] -> BenchmarkSet+benchmark name elems = BenchmarkSet+    { bGroupName        = name+    , bMinView          = whnf bench_minView              initialPSQ+    , bLookup           = whnf (bench_lookup keys)        initialPSQ+    , bInsertEmpty      = nf   (bench_insert firstElems)  OrdPSQ.empty+    , bInsertNew        = nf   (bench_insert secondElems) initialPSQ+    , bInsertDuplicates = nf   (bench_insert firstElems)  initialPSQ+    , bDelete           = nf   (bench_delete firstKeys)   initialPSQ+    }+  where+    (firstElems, secondElems) = splitAt (numElems `div` 2) elems+    numElems  = length elems+    keys      = map (\(x, _, _) -> x) elems+    firstKeys = map (\(x, _, _) -> x) firstElems++    initialPSQ = OrdPSQ.fromList firstElems :: OrdPSQ.OrdPSQ Int Int ()++-- Get the sum of all priorities by getting all elements using 'lookup'+bench_lookup :: [Int] -> OrdPSQ.OrdPSQ Int Int () -> Int+bench_lookup xs m = foldl' (\n k -> maybe n fst (OrdPSQ.lookup k m)) 0 xs++-- Insert a list of elements one-by-one into a PSQ+bench_insert :: [BElem] -> OrdPSQ.OrdPSQ Int Int () -> OrdPSQ.OrdPSQ Int Int ()+bench_insert xs m0 = foldl' (\m (k, p, v) -> OrdPSQ.insert k p v m) m0 xs++-- Get the sum of all priorities by sequentially popping all elements using+-- 'minView'+bench_minView :: OrdPSQ.OrdPSQ Int Int () -> Int+bench_minView = go 0+  where+    go !n t = case OrdPSQ.minView t of+      Nothing            -> n+      Just (k, x, _, t') -> go (n + k + x) t'++-- Empty a queue by sequentially removing all elements+bench_delete :: [Int] -> OrdPSQ.OrdPSQ Int Int () -> OrdPSQ.OrdPSQ Int Int ()+bench_delete keys t0 = foldl' (\t k -> OrdPSQ.delete k t) t0 keys
+ benchmarks/Data/PSQueue/Benchmark.hs view
@@ -0,0 +1,60 @@+{-# LANGUAGE BangPatterns #-}++-- | This module provides benchmarks for the 'PSQueue' type from the PSQueue+-- package.+module Data.PSQueue.Benchmark+    ( benchmark+    ) where++import           Data.List (foldl')+import qualified Data.PSQueue as PSQueue+import           Criterion.Main+import           Prelude hiding (lookup)+import           BenchmarkTypes+import           Data.Maybe (fromMaybe)++benchmark :: String -> [BElem] -> BenchmarkSet+benchmark name elems = BenchmarkSet+    { bGroupName        = name+    , bMinView          = whnf bench_minView              initialPSQ+    , bLookup           = whnf (bench_lookup keys)        initialPSQ+    , bInsertEmpty      = nf'  (bench_insert firstElems)  PSQueue.empty+    , bInsertNew        = nf'  (bench_insert secondElems) initialPSQ+    , bInsertDuplicates = nf'  (bench_insert firstElems)  initialPSQ+    , bDelete           = nf'  (bench_delete firstKeys)   initialPSQ+    }+  where+    (firstElems, secondElems) = splitAt (numElems `div` 2) elems+    numElems  = length elems+    keys      = map (\(x, _, _) -> x) elems+    firstKeys = map (\(x, _, _) -> x) firstElems++    initialPSQ+        = PSQueue.fromList $ map toBinding firstElems :: PSQueue.PSQ Int Int++    toBinding :: BElem -> PSQueue.Binding Int Int+    toBinding (k, p, _) = k PSQueue.:-> p++    -- Get the size of the resulting PSQ, since there's no NFData instance.+    nf' f x = whnf (PSQueue.size . f) x++-- Get the sum of all priorities by getting all elements using 'lookup'+bench_lookup :: [Int] -> PSQueue.PSQ Int Int -> Int+bench_lookup xs m = foldl' (\n k -> fromMaybe n (PSQueue.lookup k m)) 0 xs++-- Insert a list of elements one-by-one into a PSQ+bench_insert :: [BElem] -> PSQueue.PSQ Int Int -> PSQueue.PSQ Int Int+bench_insert xs m0 = foldl' (\m (k, p, _) -> PSQueue.insert k p m) m0 xs++-- Get the sum of all priorities by sequentially popping all elements using+-- 'minView'+bench_minView :: PSQueue.PSQ Int Int -> Int+bench_minView = go 0+  where+    go !n t = case PSQueue.minView t of+      Nothing           -> n+      Just ((k PSQueue.:-> x), t') -> go (n + k + x) t'++-- Empty a queue by sequentially removing all elements+bench_delete :: [Int] -> PSQueue.PSQ Int Int -> PSQueue.PSQ Int Int+bench_delete keys t0 = foldl' (\t k -> PSQueue.delete k t) t0 keys
psqueues.cabal view
@@ -1,5 +1,5 @@ Name:          psqueues-Version:       0.2.2.0+Version:       0.2.2.1 License:       BSD3 License-file:  LICENSE Maintainer:    Jasper Van der Jeugt <jaspervdj@gmail.com>@@ -85,6 +85,15 @@     Type:           exitcode-stdio-1.0     Hs-source-dirs: src benchmarks     Main-is:        Main.hs++    Other-modules:+        BenchmarkTypes+        Data.FingerTree.PSQueue.Benchmark+        Data.HashPSQ.Benchmark+        Data.IntPSQ.Benchmark+        Data.OrdPSQ.Benchmark+        Data.PSQueue.Benchmark+     Ghc-options:    -Wall      Build-depends: