compact-mutable-vector (empty) → 0.0.0.1

raw patch · 6 files changed

+233/−0 lines, 6 filesdep +basedep +compactdep +compact-mutable-vectorsetup-changed

Dependencies added: base, compact, compact-mutable-vector, ghc-prim, hspec, primitive, vector

Files

LICENSE +27/−0
Setup.hs +2/−0
compact-mutable-vector.cabal +66/−0
src/Data/Vector/Mutable/Compact.hs +108/−0
test/Data/Vector/Mutable/CompactSpec.hs +29/−0
test/Main.hs +1/−0

+ LICENSE view

@@ -0,0 +1,27 @@+Copyright 2019 rightfold++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++1. Redistributions of source code must retain the above copyright notice,+   this list of conditions and the following disclaimer.++2. 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.++3. 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.

+ Setup.hs view

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

+ compact-mutable-vector.cabal view

@@ -0,0 +1,66 @@+build-type: Simple+cabal-version: >= 1.8++name: compact-mutable-vector+version: 0.0.0.1++category: Data+license: BSD3+license-file: LICENSE+author: rightfold+maintainer: rightfold <rightfold@gmail.com>+bug-reports: https://github.com/rightfold/compact-mutable-vector/issues++synopsis: Mutable vector with different GC characteristics+description:+  Library for avoiding excessive mutable array traversals by the garbage+  collector when you use compact regions for your elements.+  .+  See Haddock for more information.++source-repository head+  type: git+  location: https://github.com/rightfold/compact-mutable-vector.git++library+  build-depends:+    base          >= 4.12 && < 5,+    compact,+    ghc-prim,+    primitive     >= 0.5.0.1 && < 0.8,+    vector        >= 0.12 && < 0.13++  exposed-modules:+    Data.Vector.Mutable.Compact++  ghc-options:+    -Wall+    -Wincomplete-record-updates+    -Wincomplete-uni-patterns++  hs-source-dirs:+    src++test-suite test+  build-depends:+    base,+    compact,+    compact-mutable-vector,+    hspec++  ghc-options:+    -Wall+    -Wincomplete-record-updates+    -Wincomplete-uni-patterns++  hs-source-dirs:+    test++  main-is:+    Main.hs++  other-modules:+    Data.Vector.Mutable.CompactSpec++  type:+    exitcode-stdio-1.0

+ src/Data/Vector/Mutable/Compact.hs view

@@ -0,0 +1,108 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE UnboxedTuples #-}++-- |+-- When you use normal mutable vectors, the garbage collector will traverse+-- them on every garbage collection, because they may point to data that is+-- newer than them. If you want to store your elements on a compact region+-- anyway, but also need to point to them from a mutable vector, you can+-- exploit the stability of the elements' addresses after adding them to the+-- compact region, to avoid these expensive traversals when collecting garbage.+--+-- This library offers a data type for mutable vectors where all elements are+-- stored in a compact region, using an unspeakable pointer casting hack.+module Data.Vector.Mutable.Compact+  ( -- * Basic operations+    CVector+  , replicate+  , read+  , write++    -- * Shape querying+  , length+  , null+  ) where++import Prelude hiding (length, null, read, replicate)++import Data.Primitive.Addr (Addr (..))+import Data.Compact (Compact)+import Data.Vector.Primitive.Mutable (MVector)+import GHC.IO (IO (..))+import GHC.Prim (RealWorld)++import qualified Data.Compact as Compact+import qualified Data.Vector.Primitive.Mutable as MVector+import qualified GHC.Prim as Prim++--------------------------------------------------------------------------------+-- Basic operations++-- |+-- Store the elements of the vector in a compact region, and use an unboxed+-- vector of pointers to the elements. Values in a compact region will not be+-- moved by the garbage collector, so their addresses are stable, and can hence+-- be stored in a mutable byte array. This avoids garbage collection overhead+-- if you store your elements in a compact region anyway, because the garbage+-- collector will not traverse byte arrays.+--+-- The elements must be able to be stored in a compact region. See+-- "Data.Compact" for a list of restrictions. The vector itself cannot itself+-- be stored in a compact region, because it is mutable.+--+-- Elements can never be bottom, because they are added to a compact region.+data CVector a =+  CVector+    !(Compact ())+    {-# UNPACK #-} !(MVector RealWorld Addr)++-- |+-- Create a new mutable vector of the given length, with each element set to+-- the given value. The given compact region will be used for all future+-- elements inserted into this vector.+replicate :: Compact () -> Int -> b -> IO (CVector b)+replicate c n x = do+  -- TODO: Should we add the element with sharing?+  xC <- Compact.getCompact <$> Compact.compactAdd c x+  xA <- IO $ \s -> let !(# s', xA #) = Prim.anyToAddr# xC s in+                   (# s', Addr xA #)+  v  <- MVector.replicate n xA+  pure $ CVector c v++-- |+-- Read the element at the given zero-based position. If the position is out of+-- bounds, crash.+read :: CVector a -> Int -> IO a+read (CVector _ v) i = do+  Addr xA <- MVector.read v i+  let (# xC #) = Prim.addrToAny# xA+  pure xC++-- |+-- Write an element at the given zero-based position. If the position is out of+-- bounds, crash.+--+-- The element will be added to the compact region.+write :: CVector a -> Int -> a -> IO ()+write (CVector c v) i x = do+  -- TODO: Should we add the element with sharing?+  xC <- Compact.getCompact <$> Compact.compactAdd c x+  xA <- IO $ \s -> let !(# s', xA #) = Prim.anyToAddr# xC s in+                   (# s', Addr xA #)+  MVector.write v i xA++--------------------------------------------------------------------------------+-- Shape querying++-- |+-- How many elements are in the vector?+{-# INLINE length #-}+length :: CVector a -> Int+length (CVector _ v) = MVector.length v++-- |+-- Is the vector empty?+{-# INLINE null #-}+null :: CVector a -> Bool+null (CVector _ v) = MVector.null v

+ test/Data/Vector/Mutable/CompactSpec.hs view

@@ -0,0 +1,29 @@+module Data.Vector.Mutable.CompactSpec+  ( spec+  ) where++import Data.Foldable (for_)+import Test.Hspec (Spec, it, shouldBe)+import System.Mem (performGC)++import qualified Data.Compact as Compact+import qualified Data.Vector.Mutable.Compact as CVector++spec :: Spec+spec =+  for_ [0 .. 63] $ \n ->+    it (show n) $ do+      c <- Compact.compact ()+      v <- CVector.replicate c n "ABC"+      for_ [0 .. n - 1] $ \i -> do++        performGC++        abc <- CVector.read v i+        abc `shouldBe` "ABC"++        performGC++        CVector.write v i (show i)+        def <- CVector.read v i+        def `shouldBe` (show i)

+ test/Main.hs view

@@ -0,0 +1,1 @@+{-# OPTIONS_GHC -F -pgmF hspec-discover #-}