mutable-containers 0.1.0.0 → 0.1.1.0

raw patch · 13 files changed

+280/−83 lines, 13 filesdep ~basePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• ChangeLog.md +4/−0
• Data/Mutable/Class.hs +30/−11
• Data/Mutable/DList.hs +0/−1
• Data/Mutable/Deque.hs +9/−6
• Data/Mutable/SRef.hs +3/−6
• Data/Mutable/URef.hs +3/−7
• Data/Mutable/VRef.hs +47/−0
• README.md +84/−0
• bench/bench.hs +0/−35
• bench/deque.hs +41/−0
• bench/ref.hs +32/−0
• mutable-containers.cabal +15/−4
• test/Spec.hs +12/−13

@@ -0,0 +1,4 @@+## 0.1.1.0++* Added reference benchmark.+* Added boxed deque and references.

@@ -1,18 +1,37 @@-{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE ConstraintKinds   #-}+{-# LANGUAGE FlexibleContexts  #-} {-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE TypeFamilies      #-} -- | Various typeclasses for mutable containers. module Data.Mutable.Class-    where+    ( PrimMonad+    , PrimState+    , RealWorld+    , MutableStack+    , MutableDeque+    , IORef+    , asIORef+    , STRef+    , asSTRef+    , MutVar+    , asMutVar+    , MutableContainer (..)+    , MutableRef (..)+    , MutableAtomicRef (..)+    , MutableCollection (..)+    , MutablePushFront (..)+    , MutablePushBack (..)+    , MutablePopFront (..)+    , MutablePopBack (..)+    ) where -import Control.Monad.Primitive-import Data.IORef-import Data.STRef-import Data.Primitive.MutVar-import Data.Monoid-import Data.MonoTraversable (Element)-import qualified Data.Sequences as Seqs+import           Control.Monad.Primitive+import           Data.IORef+import           Data.Monoid+import           Data.MonoTraversable    (Element)+import           Data.Primitive.MutVar+import qualified Data.Sequences          as Seqs+import           Data.STRef  class MutableContainer c where     type MCState c

@@ -7,7 +7,6 @@     ) where  import Data.Mutable.Class-import Data.Primitive.MutVar  data Node s a = Node     a

@@ -3,16 +3,16 @@     ( Deque     , asUDeque     , asSDeque+    , asBDeque     , module Data.Mutable.Class     ) where -import Data.Mutable.Class-import qualified Data.Vector.Generic.Mutable as V-import Control.Monad-import Control.Monad.Primitive (PrimState, PrimMonad)-import Data.Primitive.MutVar (MutVar)-import qualified Data.Vector.Unboxed.Mutable as U+import           Control.Monad                (liftM)+import           Data.Mutable.Class+import qualified Data.Vector.Generic.Mutable  as V+import qualified Data.Vector.Mutable          as B import qualified Data.Vector.Storable.Mutable as S+import qualified Data.Vector.Unboxed.Mutable  as U  data DequeState v s a = DequeState     (v s a)@@ -26,6 +26,9 @@  asSDeque :: Deque S.MVector s a -> Deque S.MVector s a asSDeque = id++asBDeque :: Deque B.MVector s a -> Deque B.MVector s a+asBDeque = id  instance MutableContainer (Deque v s a) where     type MCState (Deque v s a) = s

@@ -11,13 +11,10 @@     , MutableRef (..)     ) where -import Data.Mutable.Class-import Control.Monad.Primitive (PrimMonad, PrimState)-import Control.Monad.ST (ST)-import Control.Monad (liftM)+import           Control.Monad                (liftM)+import           Data.Mutable.Class+import qualified Data.Vector.Generic.Mutable  as V import qualified Data.Vector.Storable.Mutable as VS-import qualified Data.Vector.Mutable as VB-import qualified Data.Vector.Generic.Mutable as V  -- | A storable vector reference, supporting any monad. newtype SRef s a = SRef (VS.MVector s a)

@@ -11,14 +11,10 @@     , MutableRef (..)     ) where -import Data.Mutable.Class-import Control.Monad.Primitive (PrimMonad, PrimState)-import Control.Monad.ST (ST)-import Control.Monad (liftM)-import qualified Data.Vector.Unboxed.Mutable as VU-import qualified Data.Vector.Storable.Mutable as VS-import qualified Data.Vector.Mutable as VB+import           Control.Monad               (liftM)+import           Data.Mutable.Class import qualified Data.Vector.Generic.Mutable as V+import qualified Data.Vector.Unboxed.Mutable as VU  -- | An unboxed vector reference, supporting any monad. newtype URef s a = URef (VU.MVector s a)

@@ -0,0 +1,47 @@+{-# LANGUAGE TypeFamilies #-}+-- | Use 1-length mutable boxed vectors for mutable references.+--+-- Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.+module Data.Mutable.VRef+    ( -- * Types+      VRef+    , IOVRef+      -- * Functions+    , asVRef+    , MutableRef (..)+    ) where++import           Control.Monad               (liftM)+import           Data.Mutable.Class+import qualified Data.Vector.Generic.Mutable as V+import qualified Data.Vector.Mutable         as VB++-- | A boxed vector reference, supporting any monad.+newtype VRef s a = VRef (VB.MVector s a)++asVRef :: VRef s a -> VRef s a+asVRef x = x+{-# INLINE asVRef #-}++-- | A boxed IO vector reference.+type IOVRef = VRef (PrimState IO)++instance MutableContainer (VRef s a) where+    type MCState (VRef s a) = s+instance MutableRef (VRef s a) where+    type RefElement (VRef s a) = a++    newRef = liftM VRef . V.replicate 1+    {-# INLINE newRef#-}++    readRef (VRef v) = V.unsafeRead v 0+    {-# INLINE readRef #-}++    writeRef (VRef v) = V.unsafeWrite v 0+    {-# INLINE writeRef #-}++    modifyRef (VRef v) f = V.unsafeRead v 0 >>= V.unsafeWrite v 0 . f+    {-# INLINE modifyRef #-}++    modifyRef' = modifyRef+    {-# INLINE modifyRef' #-}

@@ -5,3 +5,87 @@ Note that this library should be considered extremely experimental. That said, it currently has 100% test coverage and has some performance tuning, though the API is expected to change significantly.++## Benchmark results++The following benchmarks were performed on January 4, 2015, against version 0.1.1.0.++### Deque benchmark++```+benchmarking IORef [Int]+time                 8.355 ms   (8.350 ms .. 8.362 ms)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 8.353 ms   (8.348 ms .. 8.358 ms)+std dev              15.89 μs   (11.83 μs .. 23.66 μs)++benchmarking IORef (Seq Int)+time                 140.5 μs   (140.4 μs .. 140.6 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 140.5 μs   (140.4 μs .. 140.6 μs)+std dev              313.3 ns   (239.0 ns .. 404.1 ns)++benchmarking UDeque+time                 101.2 μs   (101.2 μs .. 101.2 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 101.2 μs   (101.2 μs .. 101.2 μs)+std dev              16.11 ns   (13.38 ns .. 21.34 ns)++benchmarking SDeque+time                 97.86 μs   (97.85 μs .. 97.88 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 97.88 μs   (97.87 μs .. 97.89 μs)+std dev              38.61 ns   (31.34 ns .. 50.52 ns)++benchmarking BDeque+time                 113.7 μs   (113.7 μs .. 113.7 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 113.7 μs   (113.7 μs .. 113.7 μs)+std dev              29.87 ns   (22.98 ns .. 39.57 ns)++benchmarking DList+time                 160.8 μs   (160.7 μs .. 160.9 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 160.9 μs   (160.8 μs .. 161.0 μs)+std dev              331.8 ns   (277.0 ns .. 401.2 ns)+```++### Ref benchmark++```+benchmarking IORef+time                 4.321 μs   (4.320 μs .. 4.322 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 4.322 μs   (4.321 μs .. 4.323 μs)+std dev              4.840 ns   (3.746 ns .. 6.242 ns)++benchmarking STRef+time                 4.481 μs   (4.480 μs .. 4.481 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 4.481 μs   (4.481 μs .. 4.481 μs)+std dev              1.127 ns   (805.5 ps .. 1.758 ns)++benchmarking MutVar+time                 4.478 μs   (4.476 μs .. 4.481 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 4.479 μs   (4.477 μs .. 4.481 μs)+std dev              6.500 ns   (5.199 ns .. 8.246 ns)++benchmarking URef+time                 2.019 μs   (2.019 μs .. 2.020 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 2.020 μs   (2.019 μs .. 2.020 μs)+std dev              471.2 ps   (371.2 ps .. 671.9 ps)++benchmarking SRef+time                 2.175 μs   (2.174 μs .. 2.176 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 2.172 μs   (2.170 μs .. 2.173 μs)+std dev              5.106 ns   (4.054 ns .. 6.660 ns)++benchmarking VRef+time                 4.280 μs   (4.279 μs .. 4.280 μs)+                     1.000 R²   (1.000 R² .. 1.000 R²)+mean                 4.281 μs   (4.280 μs .. 4.283 μs)+std dev              4.552 ns   (1.911 ns .. 8.892 ns)+```

@@ -1,35 +0,0 @@-import Criterion.Main-import Data.Mutable.Class-import Control.Monad-import Data.IORef (IORef)-import Data.Sequence (Seq)-import Data.Mutable.Deque-import Data.Mutable.DList--test name forceType = bench name $ whnfIO $ do-    let x = 5 :: Int-    coll <- fmap forceType newColl-    replicateM_ 500 $ pushFront coll x-    replicateM_ 500 $ pushBack coll x-    replicateM_ 200 $ void $ popFront coll-    replicateM_ 200 $ void $ popBack coll-    replicateM_ 500 $ do-        pushBack coll x-        pushFront coll x-        void $ popFront coll-    replicateM_ 500 $ do-        pushBack coll x-        pushFront coll x-    replicateM_ 500 $ do-        pushBack coll x-        void $ popFront coll-{-# INLINE test #-}--main :: IO ()-main = defaultMain-    [ test "IORef [Int]" (id :: IORef [Int] -> IORef [Int])-    , test "IORef (Seq Int)" (id :: IORef (Seq Int) -> IORef (Seq Int))-    , test "UDeque" asUDeque-    , test "SDeque" asSDeque-    , test "DList" asDList-    ]

@@ -0,0 +1,41 @@+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE TypeFamilies    #-}+import Control.Monad+import Criterion.Main+import Data.Mutable.Class+import Data.Mutable.Deque+import Data.Mutable.DList+import Data.Sequence      (Seq)++test :: (MCState c ~ PrimState IO, CollElement c ~ Int, MutableDeque c)+     => String+     -> (c -> c)+     -> Benchmark+test name forceType = bench name $ whnfIO $ do+    let x = 5 :: Int+    coll <- fmap forceType newColl+    replicateM_ 500 $ pushFront coll x+    replicateM_ 500 $ pushBack coll x+    replicateM_ 200 $ void $ popFront coll+    replicateM_ 200 $ void $ popBack coll+    replicateM_ 500 $ do+        pushBack coll x+        pushFront coll x+        void $ popFront coll+    replicateM_ 500 $ do+        pushBack coll x+        pushFront coll x+    replicateM_ 500 $ do+        pushBack coll x+        void $ popFront coll+{-# INLINE test #-}++main :: IO ()+main = defaultMain+    [ test "IORef [Int]" (id :: IORef [Int] -> IORef [Int])+    , test "IORef (Seq Int)" (id :: IORef (Seq Int) -> IORef (Seq Int))+    , test "UDeque" asUDeque+    , test "SDeque" asSDeque+    , test "BDeque" asBDeque+    , test "DList" asDList+    ]

@@ -0,0 +1,32 @@+{-# LANGUAGE TypeFamilies #-}+import Control.Monad+import Criterion.Main+import Data.Mutable.Class+import Data.Mutable.SRef+import Data.Mutable.URef+import Data.Mutable.VRef++test :: (MCState c ~ PrimState IO, RefElement c ~ Int, MutableRef c)+     => String+     -> (c -> c)+     -> Benchmark+test name forceType = bench name $ whnfIO $ do+    ref <- fmap forceType $ newRef (5 :: Int)+    replicateM_ 500 $ do+        modifyRef' ref (+ 1)+        modifyRef' ref (subtract 1)+        void $ readRef ref+    replicateM_ 500 $ do+        writeRef ref (5 :: Int)+        void $ readRef ref+{-# INLINE test #-}++main :: IO ()+main = defaultMain+    [ test "IORef" asIORef+    , test "STRef" asSTRef+    , test "MutVar" asMutVar+    , test "URef" asURef+    , test "SRef" asSRef+    , test "VRef" asVRef+    ]

@@ -1,5 +1,5 @@ name:                mutable-containers-version:             0.1.0.0+version:             0.1.1.0 synopsis:            Abstactions and concrete implementations of mutable containers description:         See docs and README at <http://www.stackage.org/package/mutable-containers> homepage:            https://github.com/fpco/mutable-containers@@ -9,13 +9,14 @@ maintainer:          michael@fpcomplete.com category:            Data build-type:          Simple-extra-source-files:  README.md+extra-source-files:  README.md ChangeLog.md cabal-version:       >=1.10  library   exposed-modules:     Data.Mutable.SRef                        Data.Mutable.Class                        Data.Mutable.URef+                       Data.Mutable.VRef                        Data.Mutable.DList                        Data.Mutable.Deque   build-depends:       base >= 4.7 && < 5@@ -38,14 +39,24 @@                      , containers   default-language:    Haskell2010 -benchmark bench+benchmark deque   type:                exitcode-stdio-1.0   hs-source-dirs:      bench-  main-is:             bench.hs+  main-is:             deque.hs   build-depends:       base                      , mutable-containers                      , criterion                      , containers+  ghc-options:         -Wall -O2 -rtsopts+  default-language:    Haskell2010++benchmark ref+  type:                exitcode-stdio-1.0+  hs-source-dirs:      bench+  main-is:             ref.hs+  build-depends:       base+                     , mutable-containers+                     , criterion   ghc-options:         -Wall -O2 -rtsopts   default-language:    Haskell2010 

@@ -1,19 +1,16 @@ {-# LANGUAGE TypeFamilies #-}+import Control.Monad             (forM_)+import Data.Mutable.Deque+import Data.Mutable.DList+import Data.Mutable.SRef+import Data.Mutable.URef+import Data.Mutable.VRef+import Data.Sequence             (Seq)+import Data.Vector               (Vector) import Test.Hspec import Test.Hspec.QuickCheck import Test.QuickCheck.Arbitrary import Test.QuickCheck.Gen-import Data.Mutable.Deque-import Control.Monad (forM_)-import Data.IORef-import Data.Primitive.MutVar (MutVar)-import Control.Monad.Primitive (PrimState)-import Data.Sequence (Seq)-import Data.STRef (STRef)-import Data.Vector (Vector)-import Data.Mutable.URef-import Data.Mutable.SRef-import Data.Mutable.DList  main :: IO () main = hspec spec@@ -79,6 +76,7 @@                 drain         test "UDeque" asUDeque         test "SDeque" asSDeque+        test "BDeque" asBDeque         test "DList" asDList         test "MutVar Seq" (id :: MutVar (PrimState IO) (Seq Int) -> MutVar (PrimState IO) (Seq Int))         test "STRef Vector" (id :: STRef (PrimState IO) (Vector Int) -> STRef (PrimState IO) (Vector Int))@@ -106,14 +104,15 @@                     AtomicModifyRef i -> do                         let f x = (x + i, ())                         atomicModifyRef base f-                        atomic tested f+                        _ <- atomic tested f                         check                     AtomicModifyRef' i -> do                         atomicModifyRef' base $ \x -> (x - i, ())-                        atomic' tested $ \x -> (x - i, ())+                        _ <- atomic' tested $ \x -> (x - i, ())                         check         test "URef" asURef modifyRefHelper modifyRefHelper'         test "SRef" asSRef modifyRefHelper modifyRefHelper'+        test "VRef" asVRef modifyRefHelper modifyRefHelper'         test "STRef" asSTRef modifyRefHelper modifyRefHelper'         test "MutVar" asMutVar atomicModifyRef atomicModifyRef'