massiv 0.5.4.0 → 0.5.5.0

raw patch · 11 files changed

+205/−40 lines, 11 filesdep ~schedulerPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: scheduler

API changes (from Hackage documentation)

Files

• CHANGELOG.md +6/−0
• massiv.cabal +2/−2
• src/Data/Massiv/Array/Delayed/Pull.hs +2/−0
• src/Data/Massiv/Array/Manifest.hs +25/−3
• src/Data/Massiv/Array/Manifest/Internal.hs +5/−3
• src/Data/Massiv/Array/Mutable.hs +4/−3
• src/Data/Massiv/Array/Ops/Fold.hs +12/−10
• src/Data/Massiv/Array/Ops/Fold/Internal.hs +94/−7
• src/Data/Massiv/Array/Ops/Transform.hs +3/−3
• src/Data/Massiv/Core/Common.hs +13/−5
• src/Data/Massiv/Vector.hs +39/−4

@@ -1,3 +1,9 @@+# 0.5.5++* Add `takeWhile`, `dropWhile` and `findIndex`+* Improve performance of `any`, `and`, `or`, `all`+* Add `elem`+ # 0.5.4  * Addition of `unsafeTransformStencil`

@@ -1,5 +1,5 @@ name:                massiv-version:             0.5.4.0+version:             0.5.5.0 synopsis:            Massiv (Массив) is an Array Library. description:         Multi-dimensional Arrays with fusion, stencils and parallel computation. homepage:            https://github.com/lehins/massiv@@ -81,7 +81,7 @@                      , data-default-class                      , deepseq                      , exceptions-                     , scheduler >= 1.4.0+                     , scheduler >= 1.5.0                      , primitive                      , unliftio-core                      , vector

@@ -141,6 +141,8 @@   {-# INLINE null #-}   length = totalElem . size   {-# INLINE length #-}+  elem e = A.any (e ==)+  {-# INLINE elem #-}   toList arr = build (\ c n -> foldrFB c n arr)   {-# INLINE toList #-} 

@@ -1,10 +1,10 @@+{-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TypeFamilies #-}-{-# LANGUAGE TypeOperators #-} -- | -- Module      : Data.Massiv.Array.Manifest -- Copyright   : (c) Alexey Kuleshevich 2018-2019@@ -23,6 +23,8 @@   , B(..)   , N(..)   , Uninitialized(..)+  -- ** Access+  , findIndex   -- ** Conversion   -- $boxed_conversion_note   , unwrapNormalForm@@ -88,7 +90,8 @@   , castToBuilder   ) where -import Data.ByteString as S+import Control.Monad+import Data.ByteString as S hiding (findIndex) import Data.ByteString.Builder import Data.ByteString.Internal import Data.ByteString.Unsafe as SU@@ -101,7 +104,6 @@ import Data.Massiv.Core.Common import Data.Word (Word8) - -- | /O(1)/ - Convert a strict ByteString into a manifest array. Will return `Nothing` if length -- doesn't match the total number of elements of new array. --@@ -164,3 +166,23 @@ -- `Data.Primitive.Array.Array`, which holds the pointers to values isn't copied around, it is always -- kept as the same array. Conversion to Massiv boxed array will undergo evaluation during which -- computation strategies will be respected.++++-- | /O(n)/ - Perform a row-major search starting at @0@ for an element. Returns the index+-- of the first occurance of an element or `Nothing` if a predicate could not be satisifed+-- after it was applyied to all elements of the array.+--+-- @since 0.5.5+findIndex :: Manifest r ix e => (e -> Bool) -> Array r ix e -> Maybe ix+findIndex f arr = go 0+  where+    !sz = size arr+    !k = totalElem sz+    go !i = do+      guard (i < k)+      if f (unsafeLinearIndex arr i)+        then Just $ fromLinearIndex sz i+        else go (i + 1)+{-# INLINE findIndex #-}+

@@ -50,7 +50,7 @@ import qualified Data.Foldable as F (Foldable(..)) import Data.Massiv.Array.Delayed.Pull import Data.Massiv.Array.Mutable-import Data.Massiv.Array.Ops.Fold.Internal+import Data.Massiv.Array.Ops.Fold.Internal as A import Data.Massiv.Array.Mutable.Internal (unsafeCreateArray_) import Data.Massiv.Vector.Stream as S (steps, isteps) import Data.Massiv.Core.Common@@ -122,6 +122,8 @@   {-# INLINE null #-}   length = totalElem . size   {-# INLINE length #-}+  elem e = A.any (e ==)+  {-# INLINE elem #-}   toList arr = build (\ c n -> foldrFB c n arr)   {-# INLINE toList #-} @@ -361,8 +363,8 @@       unsafePerformIO $ do         marr <- unsafeNew sz         traverse (\_ -> unsafeFreeze (getComp arr) marr) =<<-          try (withScheduler_ (getComp arr) $ \scheduler ->-                  loadRagged (scheduleWork scheduler) (unsafeLinearWrite marr) 0 (totalElem sz) sz arr)+          try (withMassivScheduler_ (getComp arr) $ \scheduler ->+                 loadRagged (scheduleWork scheduler) (unsafeLinearWrite marr) 0 (totalElem sz) sz arr) {-# INLINE fromRaggedArrayM #-}  

@@ -162,7 +162,7 @@     let sz = size arr         totalLength = totalElem sz     marr <- unsafeNew sz-    withScheduler_ (getComp arr) $ \scheduler ->+    withMassivScheduler_ (getComp arr) $ \scheduler ->       splitLinearly (numWorkers scheduler) totalLength $ \chunkLength slackStart -> do         loopM_ 0 (< slackStart) (+ chunkLength) $ \ !start ->           scheduleWork_ scheduler $ unsafeArrayLinearCopy arr start marr start (SafeSz chunkLength)@@ -223,7 +223,7 @@     let sz = msize smarr         totalLength = totalElem sz     tmarr <- unsafeNew sz-    withScheduler_ comp $ \scheduler ->+    withMassivScheduler_ comp $ \scheduler ->       splitLinearly (numWorkers scheduler) totalLength $ \chunkLength slackStart -> do         loopM_ 0 (< slackStart) (+ chunkLength) $ \ !start ->           scheduleWork_ scheduler $ unsafeLinearCopy smarr start tmarr start (SafeSz chunkLength)@@ -298,7 +298,8 @@   liftIO $ do     unless (totalElem (msize mArr) == totalElem (size arr)) $       throwM $ SizeElementsMismatchException (msize mArr) (size arr)-    withScheduler_ (getComp arr) $ \scheduler -> loadArrayM scheduler arr (unsafeLinearWrite mArr)+    withMassivScheduler_ (getComp arr) $ \scheduler ->+      loadArrayM scheduler arr (unsafeLinearWrite mArr) {-# INLINE computeInto #-}  

@@ -35,6 +35,7 @@   , or   , all   , any+  , elem    -- ** Single dimension folds   -- *** Safe inner most@@ -102,8 +103,9 @@ import Data.Massiv.Array.Ops.Fold.Internal import Data.Massiv.Core import Data.Massiv.Core.Common-import Prelude hiding (all, and, any, foldl, foldr, map, maximum, minimum, or, product, sum)+import Prelude hiding (all, and, any, foldl, foldr, map, maximum, minimum, or, product, sum, elem) + -- | /O(n)/ - Monoidal fold over an array with an index aware function. Also known as reduce. -- -- @since 0.2.4@@ -459,7 +461,7 @@ -- -- @since 0.1.0 and :: Source r ix Bool => Array r ix Bool -> Bool-and = foldlInternal (&&) True (&&) True+and = all id {-# INLINE and #-}  @@ -467,23 +469,23 @@ -- -- @since 0.1.0 or :: Source r ix Bool => Array r ix Bool -> Bool-or = foldlInternal (||) False (||) False+or = any id {-# INLINE or #-}  --- | /O(n)/ - Determines whether all element of the array satisfy the predicate.+-- | /O(n)/ - Determines whether all elements of the array satisfy a predicate. -- -- @since 0.1.0 all :: Source r ix e => (e -> Bool) -> Array r ix e -> Bool-all f = foldlInternal (\acc e -> acc && f e) True (&&) True+all f = not . any (not . f) {-# INLINE all #-} --- | /O(n)/ - Determines whether any element of the array satisfies the predicate.+-- | /O(n)/ - Determines whether an element is present in the array. ----- @since 0.1.0-any :: Source r ix e => (e -> Bool) -> Array r ix e -> Bool-any f = foldlInternal (\acc e -> acc || f e) False (||) False-{-# INLINE any #-}+-- @since 0.5.5+elem :: (Eq e, Source r ix e) => e -> Array r ix e -> Bool+elem e = any (e ==)+{-# INLINE elem #-}   {- $unstruct_folds

@@ -42,6 +42,9 @@   , ifoldlIO   , ifoldrIO   -- , splitReduce+  , any+  , anySu+  , anyPu   ) where  import Control.Monad (void, when)@@ -49,7 +52,7 @@ import qualified Data.Foldable as F import Data.Functor.Identity (runIdentity) import Data.Massiv.Core.Common-import Prelude hiding (foldl, foldr)+import Prelude hiding (foldl, foldr, any) import System.IO.Unsafe (unsafePerformIO)  @@ -334,10 +337,10 @@ -- -- them. Number of chunks will depend on the computation strategy. Results of each action -- -- will be combined with a folding function. -- ----- -- @since 0.4.1+-- -- @since 0.6.0 -- splitReduce :: --      (MonadUnliftIO m, Source r ix e)---   => (Scheduler m a -> Array r Ix1 e -> m a)+--   => (Scheduler m a -> BatchId -> Array r Ix1 e -> m a) --   -> (b -> a -> m b) -- ^ Folding action that is applied to the results of a parallel fold --   -> b -- ^ Accumulator for chunks folding --   -> Array r ix e@@ -346,13 +349,15 @@ --   let !sz = size arr --       !totalLength = totalElem sz --   results <----     withScheduler (getComp arr) $ \scheduler ->+--     withScheduler (getComp arr) $ \scheduler -> do+--       batchId <- getCurrentBatchId scheduler --       splitLinearly (numWorkers scheduler) totalLength $ \chunkLength slackStart -> do --         loopM_ 0 (< slackStart) (+ chunkLength) $ \ !start ->---           scheduleWork scheduler $ f scheduler $ unsafeLinearSlice start (SafeSz chunkLength) arr+--           scheduleWork scheduler $ f scheduler batchId $+--             unsafeLinearSlice start (SafeSz chunkLength) arr --         when (slackStart < totalLength) $---           scheduleWork scheduler $---           f scheduler $ unsafeLinearSlice slackStart (SafeSz (totalLength - slackStart)) arr+--           scheduleWork scheduler $ f scheduler batchId $+--             unsafeLinearSlice slackStart (SafeSz (totalLength - slackStart)) arr --   F.foldlM g tAcc results -- {-# INLINE splitReduce #-} @@ -381,3 +386,85 @@                 f ix (unsafeLinearIndex arr i) acc     F.foldlM (flip g) tAcc results {-# INLINE ifoldrIO #-}++-- | Sequential implementation of `any` with unrolling+anySu :: Source r ix a => (a -> Bool) -> Array r ix a -> Bool+anySu f arr = go 0+  where+    !k = elemsCount arr+    !k4 = k - (k `rem` 4)+    go !i+      | i < k4 =+        f (unsafeLinearIndex arr i      ) ||+        f (unsafeLinearIndex arr (i + 1)) ||+        f (unsafeLinearIndex arr (i + 2)) ||+        f (unsafeLinearIndex arr (i + 3)) ||+        go (i + 4)+      | i < k = f (unsafeLinearIndex arr i) || go (i + 1)+      | otherwise = False+{-# INLINE anySu #-}+++-- | Implementaton of `any` on a slice of an array with short-circuiting using batch cancellation.+anySliceSuM ::+     Source r ix a+  => Batch IO Bool+  -> Ix1+  -> Sz1+  -> (a -> Bool)+  -> Array r ix a+  -> IO Bool+anySliceSuM batch ix0 (Sz k) f arr = go ix0+  where+    !k' = k - ix0+    !k4 = ix0 + (k' - (k' `rem` 4))+    go !i+      | i < k4 = do+        let r =+              f (unsafeLinearIndex arr i) ||+              f (unsafeLinearIndex arr (i + 1)) ||+              f (unsafeLinearIndex arr (i + 2)) ||+              f (unsafeLinearIndex arr (i + 3))+         in if r+              then cancelBatchWith batch True+              else do+                done <- hasBatchFinished batch+                if done+                  then pure True+                  else go (i + 4)+      | i < k =+        if f (unsafeLinearIndex arr i)+          then cancelBatchWith batch True+          else go (i + 1)+      | otherwise = pure False+{-# INLINE anySliceSuM #-}++++-- | Parallelizable implementation of `any` with unrolling+anyPu :: Source r ix e => (e -> Bool) -> Array r ix e -> IO Bool+anyPu f arr = do+  let !sz = size arr+      !totalLength = totalElem sz+  results <-+    withScheduler (getComp arr) $ \scheduler -> do+      batch <- getCurrentBatch scheduler+      splitLinearly (numWorkers scheduler) totalLength $ \chunkLength slackStart -> do+        loopM_ 0 (< slackStart) (+ chunkLength) $ \ !start ->+          scheduleWork scheduler $ anySliceSuM batch start (Sz (start + chunkLength)) f arr+        when (slackStart < totalLength) $+          scheduleWork scheduler $ anySliceSuM batch slackStart (Sz totalLength) f arr+  pure $ F.foldl' (||) False results+{-# INLINE anyPu #-}++++-- | /O(n)/ - Determines whether any element of the array satisfies a predicate.+--+-- @since 0.1.0+any :: Source r ix e => (e -> Bool) -> Array r ix e -> Bool+any f arr =+  case getComp arr of+    Seq -> anySu f arr+    _ -> unsafePerformIO $ anyPu f arr+{-# INLINE any #-}

@@ -606,7 +606,7 @@         DLArray {dlComp = foldMap getComp arrs, dlSize = newSz, dlDefault = Nothing, dlLoad = load} {-# INLINE stackSlicesM #-} --- | Specialized `stackOuterM` to handling stacking from the outside. It is the inverse of+-- | Specialized `stackSlicesM` to handling stacking from the outside. It is the inverse of -- `Data.Massiv.Array.outerSlices`. -- -- /__Exceptions__/: `SizeMismatchException`@@ -646,8 +646,8 @@ stackOuterSlicesM = stackSlicesM (dimensions (Proxy :: Proxy ix)) {-# INLINE stackOuterSlicesM #-} --- | Specialized `stackOuterM` to handling stacking from the inside. It is the inverse of--- `Data.Massiv.Array.outerSlices`.+-- | Specialized `stackSlicesM` to handling stacking from the inside. It is the inverse of+-- `Data.Massiv.Array.innerSlices`. -- -- /__Exceptions__/: `SizeMismatchException` --

@@ -38,6 +38,7 @@   , numWorkers   , scheduleWork   , scheduleWork_+  , withMassivScheduler_   , WorkerStates   , unsafeRead   , unsafeWrite@@ -95,6 +96,7 @@ import Control.Monad.Primitive import Control.Scheduler (Comp(..), Scheduler, WorkerStates, numWorkers,                           scheduleWork, scheduleWork_, withScheduler_, trivialScheduler_)+import Control.Scheduler.Global import Data.Massiv.Core.Exception import Data.Massiv.Core.Index import Data.Massiv.Core.Index.Internal (Sz(SafeSz))@@ -329,12 +331,11 @@     => MArray (PrimState m) r' ix e     -> Array r ix e     -> m (MArray (PrimState m) r' ix e)-  unsafeLoadIntoS marr arr = do-    loadArrayM trivialScheduler_ arr (unsafeLinearWrite marr)-    pure marr+  unsafeLoadIntoS marr arr =+    marr <$ loadArrayM trivialScheduler_ arr (unsafeLinearWrite marr)   {-# INLINE unsafeLoadIntoS #-} -  -- | Same as `unsafeLoadIntoS`, but with respect of computation startegy.+  -- | Same as `unsafeLoadIntoS`, but respecting computation strategy.   --   -- @since 0.5.0   unsafeLoadInto ::@@ -343,11 +344,18 @@     -> Array r ix e     -> m (MArray RealWorld r' ix e)   unsafeLoadInto marr arr = do-    liftIO $ withScheduler_ (getComp arr) $ \scheduler ->+    liftIO $ withMassivScheduler_ (getComp arr) $ \scheduler ->       loadArrayM scheduler arr (unsafeLinearWrite marr)     pure marr   {-# INLINE unsafeLoadInto #-} +-- | Selects an optimal scheduler for the supplied strategy, but it works only in `IO`+withMassivScheduler_ :: Comp -> (Scheduler IO () -> IO ()) -> IO ()+withMassivScheduler_ comp f =+  case comp of+    Par -> withGlobalScheduler_ globalScheduler f+    Seq -> f trivialScheduler_+    _ -> withScheduler_ comp f  class Load r ix e => StrideLoad r ix e where   -- | Load an array into memory with stride. Default implementation requires an instance of

@@ -53,9 +53,11 @@   , take   , take'   , takeM+  , takeWhile   , stake   -- *** Drop   , drop+  , dropWhile   , drop'   , dropM   , sdrop@@ -182,8 +184,8 @@   , scatMaybes   , simapMaybe   , simapMaybeM-  -- , takeWhile-  -- , dropWhile+  -- , stakeWhile+  -- , sdropWhile   -- -- ** Partitioning   -- , partition   -- , unstablePartition@@ -194,7 +196,7 @@   -- , elem   -- , notElem   -- , find-  -- , findIndex+  , findIndex   -- , findIndices   -- , elemIndex   -- , elemIndices@@ -309,7 +311,8 @@ import Data.Massiv.Core.Common import qualified Data.Massiv.Vector.Stream as S import Data.Massiv.Vector.Unsafe-import Prelude hiding (drop, init, length, null, replicate, splitAt, tail, take)+import Data.Maybe+import Prelude hiding (drop, init, length, null, replicate, splitAt, tail, take, takeWhile, dropWhile)  -- ========= -- -- Accessors --@@ -813,6 +816,23 @@ take k = fst . sliceAt k {-# INLINE take #-} ++-- | Slice a manifest vector in such a way that it will contain all initial elements that+-- satisfy the supplied predicate.+--+-- @since 0.5.5+takeWhile :: Manifest r Ix1 e => (e -> Bool) -> Vector r e -> Vector r e+takeWhile f v = take (go 0) v+  where+    !k = elemsCount v+    go !i+      | i < k && f (unsafeLinearIndex v i) = go (i + 1)+      | otherwise = SafeSz i+{-# INLINE takeWhile #-}++++ -- | /O(1)/ - Get the vector with the first @n@ elements. Throws an error size is less -- than @n@. --@@ -869,6 +889,21 @@ drop :: Source r Ix1 e => Sz1 -> Vector r e -> Vector r e drop k = snd . sliceAt k {-# INLINE drop #-}+++-- | Slice a manifest vector in such a way that it will not contain all initial elements+-- that satisfy the supplied predicate.+--+-- @since 0.5.5+dropWhile :: Manifest r Ix1 e => (e -> Bool) -> Vector r e -> Vector r e+dropWhile f v = drop (go 0) v+  where+    !k = elemsCount v+    go !i+      | i < k && f (unsafeLinearIndex v i) = go (i + 1)+      | otherwise = SafeSz i+{-# INLINE dropWhile #-}+  -- | Keep all but the first @n@ elements from the delayed stream vector. --