1{-# LANGUAGE UnboxedTuples #-}
6-- Module : Streamly.Internal.Data.Array.Foreign
7-- Copyright : (c) 2019 Composewell Technologies
10-- Maintainer : streamly@composewell.com
11-- Stability : experimental
16-- * Arrays are finite and fixed in size
17-- * provide /O(1)/ access to elements
18-- * store only data and not functions
19-- * provide efficient IO interfacing
21-- 'Foldable' instance is not provided because the implementation would be much
22-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
23-- instances should be used with care; concatenating arrays using binary
24-- operations can be highly inefficient. Instead, use
25-- 'Streamly.Internal.Data.Array.Stream.Foreign.toArray' to concatenate N
28-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
29-- single byte) are only as good as holding those elements in a Haskell list.
30-- However, small arrays can be compacted into large ones to reduce the
31-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
32-- if we use one array for each chunk. This is still significant to add
35module Streamly.Internal.Data.Array.Foreign
43 -- Pure, From Static Memory (Unsafe)
44 -- We can use fromPtrM#, fromCStringM# and fromAddrM# to create arrays from
45 -- a dynamic memory address which requires a finalizer.
60 , A.writeN -- drop new
62 , A.write -- full buffer
63 -- , writeLastN -- drop old (ring buffer)
85 -- , readFrom -- read from a given position to the end of file
86 -- , readFromRev -- read from a given position to the beginning of file
87 -- , readTo -- read from beginning up to the given position
88 -- , readToRev -- read from end to the given position in file
96 -- , writeFrom -- start writing at the given position
98 -- , writeTo -- write from beginning up to the given position
103 -- , writeChunksOfFrom
117 -- -- * In-pace mutation (for Mutable Array type)
123 -- * Immutable Transformations
137 -- * Folds with Array as the container
142import Control.Monad (when)
143import Control.Monad.IO.Class (MonadIO(..))
144#if !(MIN_VERSION_base(4,11,0))
145import Data.Semigroup ((<>))
147import Data.Word (Word8)
148-- import Data.Functor.Identity (Identity)
149import Foreign.C.String (CString)
150import Foreign.ForeignPtr (withForeignPtr, castForeignPtr)
151import Foreign.Ptr (plusPtr, castPtr)
152import Foreign.Storable (Storable(..))
153import Prelude hiding (length, null, last, map, (!!), read, concat)
155import GHC.ForeignPtr (ForeignPtr(..))
156import GHC.Ptr (Ptr(..))
157import GHC.Prim (touch#)
158import GHC.IO (IO(..))
160import Streamly.Internal.Data.Array.Foreign.Types (Array(..), length)
161import Streamly.Internal.Data.Fold.Types (Fold(..))
162import Streamly.Internal.Data.Stream.Serial (SerialT)
163import Streamly.Internal.Data.Tuple.Strict (Tuple3'(..))
164import Streamly.Internal.Data.Unfold.Types (Unfold(..))
166import qualified Streamly.Internal.Data.Array.Foreign.Mut.Types as MA
167import qualified Streamly.Internal.Data.Array.Foreign.Types as A
168import qualified Streamly.Internal.Data.Fold as FL
169import qualified Streamly.Internal.Data.Stream.Prelude as P
170import qualified Streamly.Internal.Data.Stream.Serial as Serial
171import qualified Streamly.Internal.Data.Stream.StreamD as D
172import qualified Streamly.Internal.Data.Unfold as Unfold
173import qualified Streamly.Internal.Ring.Foreign as RB
175-------------------------------------------------------------------------------
177-------------------------------------------------------------------------------
179-- | Create an 'Array' from the first N elements of a stream. The array is
180-- allocated to size N, if the stream terminates before N elements then the
181-- array may hold less than N elements.
184{-# INLINE fromStreamN #-}
185fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
187 when (n < 0) $ error "writeN: negative write count specified"
188 A.fromStreamDN n $ D.toStreamD m
190-- | Create an 'Array' from a stream. This is useful when we want to create a
191-- single array from a stream of unknown size. 'writeN' is at least twice
192-- as efficient when the size is already known.
194-- Note that if the input stream is too large memory allocation for the array
195-- may fail. When the stream size is not known, `arraysOf` followed by
196-- processing of indvidual arrays in the resulting stream should be preferred.
199{-# INLINE fromStream #-}
200fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
201fromStream = P.foldOnce A.write
202-- write m = A.fromStreamD $ D.toStreamD m
204-------------------------------------------------------------------------------
206-------------------------------------------------------------------------------
208-- | Unfold an array into a stream.
211{-# INLINE_NORMAL read #-}
212read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
213read = Unfold.lmap A.unsafeThaw MA.read
215-- | Unfold an array into a stream, does not check the end of the array, the
216-- user is responsible for terminating the stream within the array bounds. For
217-- high performance application where the end condition can be determined by
218-- a terminating fold.
220-- Written in the hope that it may be faster than "read", however, in the case
221-- for which this was written, "read" proves to be faster even though the core
222-- generated with unsafeRead looks simpler.
226{-# INLINE_NORMAL unsafeRead #-}
227unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
228unsafeRead = Unfold step inject
231 inject (Array fp _) = return fp
233 {-# INLINE_LATE step #-}
234 step (ForeignPtr p contents) = do
235 -- unsafeInlineIO allows us to run this in Identity monad for pure
236 -- toList/foldr case which makes them much faster due to not
237 -- accumulating the list and fusing better with the pure consumers.
239 -- This should be safe as the array contents are guaranteed to be
240 -- evaluated/written to before we peek at them.
241 let !x = A.unsafeInlineIO $ do
245 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
246 return $ D.Yield x (ForeignPtr p1 contents)
248 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
250-- | > null arr = length arr == 0
254null :: Storable a => Array a -> Bool
255null arr = length arr == 0
257-- | > last arr = readIndex arr (length arr - 1)
261last :: Storable a => Array a -> Maybe a
262last arr = readIndex arr (length arr - 1)
264-------------------------------------------------------------------------------
265-- Folds with Array as the container
266-------------------------------------------------------------------------------
268-- | Take last 'n' elements from the stream and discard the rest.
270lastN :: (Storable a, MonadIO m) => Int -> Fold m a (Array a)
272 | n <= 0 = fmap (const mempty) FL.drain
273 | otherwise = A.unsafeFreeze <$> Fold step initial done
275 step (Tuple3' rb rh i) a = do
276 rh1 <- liftIO $ RB.unsafeInsert rb rh a
277 return $ FL.Partial $ Tuple3' rb rh1 (i + 1)
279 let f (a, b) = FL.Partial $ Tuple3' a b (0 :: Int)
280 in fmap f $ liftIO $ RB.new n
281 done (Tuple3' rb rh i) = do
282 arr <- liftIO $ MA.newArray n
283 foldFunc i rh snoc' arr rb
284 snoc' b a = liftIO $ MA.unsafeSnoc b a
286 | i < n = RB.unsafeFoldRingM
287 | otherwise = RB.unsafeFoldRingFullM
289-------------------------------------------------------------------------------
291-------------------------------------------------------------------------------
293-------------------------------------------------------------------------------
295-------------------------------------------------------------------------------
298-- | Perform a binary search in the array to find an element.
299bsearch :: a -> Array a -> Maybe Bool
302-- | Perform a binary search in the array to find an element index.
303{-# INLINE elemIndex #-}
304bsearchIndex :: a -> Array a -> Maybe Int
305bsearchIndex elem arr = undefined
307-- find/findIndex etc can potentially be implemented more efficiently on arrays
308-- compared to streams by using SIMD instructions.
310find :: (a -> Bool) -> Array a -> Bool
313findIndex :: (a -> Bool) -> Array a -> Maybe Int
316findIndices :: (a -> Bool) -> Array a -> Array Int
317findIndices = undefined
320-------------------------------------------------------------------------------
322-------------------------------------------------------------------------------
324-- XXX We can potentially use SIMD instructions on arrays to fold faster.
326-------------------------------------------------------------------------------
328-------------------------------------------------------------------------------
331slice :: Int -> Int -> Array a
332slice begin end arr = undefined
334splitAt :: Int -> Array a -> (Array a, Array a)
335splitAt i arr = undefined
337-- XXX This operation can be performed efficiently via streams.
338-- | Append two arrays together to create a single array.
339splice :: Array a -> Array a -> Array a
340splice arr1 arr2 = undefined
342-------------------------------------------------------------------------------
343-- In-place mutation APIs
344-------------------------------------------------------------------------------
346-- | Partition an array into two halves using a partitioning predicate. The
347-- first half retains values where the predicate is 'False' and the second half
348-- retains values where the predicate is 'True'.
349{-# INLINE partitionBy #-}
350partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
351partitionBy f arr = undefined
353-- | Shuffle corresponding elements from two arrays using a shuffle function.
354-- If the shuffle function returns 'False' then do nothing otherwise swap the
355-- elements. This can be used in a bottom up fold to shuffle or reorder the
357shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
358shuffleBy f arr1 arr2 = undefined
360-- XXX we can also make the folds partial by stopping at a certain level.
362-- | Perform a top down hierarchical recursive partitioning fold of items in
363-- the container using the given function as the partition function.
365-- This will perform a quick sort if the partition function is
366-- 'partitionBy (< pivot)'.
369{-# INLINABLE foldtWith #-}
370foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
371foldtWith level f = undefined
373-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
374-- indicates the level in the tree where the fold would stop.
376-- This will perform a random shuffle if the shuffle function is random.
377-- If we stop at level 0 and repeatedly apply the function then we can do a
379foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
380foldbWith level f = undefined
383-- XXX consider the bulk update/accumulation/permutation APIs from vector.
385-------------------------------------------------------------------------------
386-- Random reads and writes
387-------------------------------------------------------------------------------
389-- | /O(1)/ Lookup the element at the given index, starting from 0.
392{-# INLINE readIndex #-}
393readIndex :: Storable a => Array a -> Int -> Maybe a
395 if i < 0 || i > length arr - 1
397 else A.unsafeInlineIO $
398 withForeignPtr (aStart arr) $ \p -> Just <$> peekElemOff p i
401-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
402-- at index @i@ and reading up to @count@ elements in the forward direction
403-- ending at the index @i + count - 1@.
406{-# INLINE readSlice #-}
407readSlice :: (IsStream t, Monad m, Storable a)
408 => Array a -> Int -> Int -> t m a
409readSlice arr i len = undefined
411-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
412-- index @i@ and reading up to @count@ elements in the reverse direction ending
413-- at the index @i - count + 1@.
416{-# INLINE readSliceRev #-}
417readSliceRev :: (IsStream t, Monad m, Storable a)
418 => Array a -> Int -> Int -> t m a
419readSliceRev arr i len = undefined
422-- | /O(1)/ Write the given element at the given index in the array.
423-- Performs in-place mutation of the array.
426{-# INLINE writeIndex #-}
427writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
428writeIndex arr i a = do
429 let maxIndex = length arr - 1
431 then error "writeIndex: negative array index"
433 then error $ "writeIndex: specified array index " ++ show i
434 ++ " is beyond the maximum index " ++ show maxIndex
436 liftIO $ withForeignPtr (aStart arr) $ \p ->
440-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
441-- starting at index @i@ and writing up to @count@ elements in the forward
442-- direction ending at the index @i + count - 1@.
445{-# INLINE writeSlice #-}
446writeSlice :: (IsStream t, Monad m, Storable a)
447 => Array a -> Int -> Int -> t m a -> m (Array a)
448writeSlice arr i len s = undefined
450-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
451-- starting at index @i@ and writing up to @count@ elements in the reverse
452-- direction ending at the index @i - count + 1@.
455{-# INLINE writeSliceRev #-}
456writeSliceRev :: (IsStream t, Monad m, Storable a)
457 => Array a -> Int -> Int -> t m a -> m (Array a)
458writeSliceRev arr i len s = undefined
461-------------------------------------------------------------------------------
462-- Transform via stream operations
463-------------------------------------------------------------------------------
465-- for non-length changing operations we can use the original length for
466-- allocation. If we can predict the length then we can use the prediction for
467-- new allocation. Otherwise we can use a hint and adjust dynamically.
470-- | Transform an array into another array using a pipe transformation
474{-# INLINE runPipe #-}
475runPipe :: (MonadIO m, Storable a, Storable b)
476 => Pipe m a b -> Array a -> m (Array b)
477runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
480-- | Transform an array into another array using a stream transformation
484{-# INLINE streamTransform #-}
485streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
486 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
487streamTransform f arr =
488 P.foldOnce (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
491-------------------------------------------------------------------------------
493-------------------------------------------------------------------------------
495-- | Cast an array having elements of type @a@ into an array having elements of
496-- type @b@. The array size must be a multiple of the size of type @b@
497-- otherwise accessing the last element of the array may result into a crash or
507unsafeCast (Array start end) = Array (castForeignPtr start) (castPtr end)
509-- | Cast an array into a Word8 array
513asByteArray :: Array a -> Array Word8
514asByteArray = unsafeCast
516-- | Cast an array having elements of type @a@ into an array having elements of
517-- type @b@. The length of the array should be a multiple of the size of the
518-- target element otherwise 'Nothing' is returned.
522cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
524 let len = A.byteLength arr
525 r = len `mod` sizeOf (undefined :: b)
528 else Just $ unsafeCast arr
530-- | Use an @Array a@ as @Ptr b@.
536asPtr :: Array a -> (Ptr b -> IO c) -> IO c
537asPtr Array{..} act = do
538 withForeignPtr aStart $ \ptr -> act (castPtr ptr)
540-- | Convert an array of any type into a null terminated CString Ptr.
544-- /O(n) Time: (creates a copy of the array)/
548asCString :: Array a -> (CString -> IO b) -> IO b
549asCString arr act = do
550 let Array{..} = asByteArray arr <> A.fromList [0]
551 withForeignPtr aStart $ \ptr -> act (castPtr ptr)
553-------------------------------------------------------------------------------
555-------------------------------------------------------------------------------
557-- | Fold an array using a 'Fold'.
561fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
562fold f arr = P.foldOnce f (A.toStream arr :: Serial.SerialT m a)
564-- | Fold an array using a stream fold operation.
567{-# INLINE streamFold #-}
568streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
569streamFold f arr = f (A.toStream arr)
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list