1{-# LANGUAGE UnboxedTuples #-}
6-- Module : Streamly.Internal.Memory.Array
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.Memory.ArrayStream.toArray' to concatenate N arrays at
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.Memory.Array
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, touchForeignPtr, 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.Fold.Types (Fold(..))
161import Streamly.Internal.Data.Unfold.Types (Unfold(..))
162import Streamly.Internal.Memory.Array.Types (Array(..), length)
163import Streamly.Internal.Data.Stream.Serial (SerialT)
164import Streamly.Internal.Data.Stream.StreamK.Type (IsStream)
166import qualified Streamly.Internal.Memory.Array.Types as A
167import qualified Streamly.Internal.Data.Stream.Prelude as P
168import qualified Streamly.Internal.Data.Stream.Serial as Serial
169import qualified Streamly.Internal.Data.Stream.StreamD as D
170import qualified Streamly.Internal.Data.Stream.StreamK as K
172-------------------------------------------------------------------------------
174-------------------------------------------------------------------------------
176-- | Create an 'Array' from the first N elements of a stream. The array is
177-- allocated to size N, if the stream terminates before N elements then the
178-- array may hold less than N elements.
181{-# INLINE fromStreamN #-}
182fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
184 when (n < 0) $ error "writeN: negative write count specified"
185 A.fromStreamDN n $ D.toStreamD m
187-- | Create an 'Array' from a stream. This is useful when we want to create a
188-- single array from a stream of unknown size. 'writeN' is at least twice
189-- as efficient when the size is already known.
191-- Note that if the input stream is too large memory allocation for the array
192-- may fail. When the stream size is not known, `arraysOf` followed by
193-- processing of indvidual arrays in the resulting stream should be preferred.
196{-# INLINE fromStream #-}
197fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
198fromStream = P.runFold A.write
199-- write m = A.fromStreamD $ D.toStreamD m
201-------------------------------------------------------------------------------
203-------------------------------------------------------------------------------
205-- | Convert an 'Array' into a stream.
208{-# INLINE_EARLY toStream #-}
209toStream :: (Monad m, K.IsStream t, Storable a) => Array a -> t m a
210toStream = D.fromStreamD . A.toStreamD
211-- XXX add fallback to StreamK rule
212-- {-# RULES "Streamly.Array.read fallback to StreamK" [1]
213-- forall a. S.readK (read a) = K.fromArray a #-}
215-- | Convert an 'Array' into a stream in reverse order.
218{-# INLINE_EARLY toStreamRev #-}
219toStreamRev :: (Monad m, IsStream t, Storable a) => Array a -> t m a
220toStreamRev = D.fromStreamD . A.toStreamDRev
221-- XXX add fallback to StreamK rule
222-- {-# RULES "Streamly.Array.readRev fallback to StreamK" [1]
223-- forall a. S.toStreamK (readRev a) = K.revFromArray a #-}
225data ReadUState a = ReadUState
226 {-# UNPACK #-} !(ForeignPtr a) -- foreign ptr with end of array pointer
227 {-# UNPACK #-} !(Ptr a) -- current pointer
229-- | Unfold an array into a stream.
232{-# INLINE_NORMAL read #-}
233read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
234read = Unfold step inject
237 inject (Array (ForeignPtr start contents) (Ptr end)) =
238 return $ ReadUState (ForeignPtr end contents) (Ptr start)
240 {-# INLINE_LATE step #-}
241 step (ReadUState fp@(ForeignPtr end _) p) | p == Ptr end =
242 let x = A.unsafeInlineIO $ touchForeignPtr fp
243 in x `seq` return D.Stop
244 step (ReadUState fp p) = do
245 -- unsafeInlineIO allows us to run this in Identity monad for pure
246 -- toList/foldr case which makes them much faster due to not
247 -- accumulating the list and fusing better with the pure consumers.
249 -- This should be safe as the array contents are guaranteed to be
250 -- evaluated/written to before we peek at them.
251 let !x = A.unsafeInlineIO $ peek p
253 (ReadUState fp (p `plusPtr` sizeOf (undefined :: a)))
255-- | Unfold an array into a stream, does not check the end of the array, the
256-- user is responsible for terminating the stream within the array bounds. For
257-- high performance application where the end condition can be determined by
258-- a terminating fold.
260-- Written in the hope that it may be faster than "read", however, in the case
261-- for which this was written, "read" proves to be faster even though the core
262-- generated with unsafeRead looks simpler.
266{-# INLINE_NORMAL unsafeRead #-}
267unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
268unsafeRead = Unfold step inject
271 inject (Array fp _) = return fp
273 {-# INLINE_LATE step #-}
274 step (ForeignPtr p contents) = do
275 -- unsafeInlineIO allows us to run this in Identity monad for pure
276 -- toList/foldr case which makes them much faster due to not
277 -- accumulating the list and fusing better with the pure consumers.
279 -- This should be safe as the array contents are guaranteed to be
280 -- evaluated/written to before we peek at them.
281 let !x = A.unsafeInlineIO $ do
285 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
286 return $ D.Yield x (ForeignPtr p1 contents)
288 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
290-- | > null arr = length arr == 0
294null :: Storable a => Array a -> Bool
295null arr = length arr == 0
297-- | > last arr = readIndex arr (length arr - 1)
301last :: Storable a => Array a -> Maybe a
302last arr = readIndex arr (length arr - 1)
304-------------------------------------------------------------------------------
306-------------------------------------------------------------------------------
308-------------------------------------------------------------------------------
310-------------------------------------------------------------------------------
313-- | Perform a binary search in the array to find an element.
314bsearch :: a -> Array a -> Maybe Bool
317-- | Perform a binary search in the array to find an element index.
318{-# INLINE elemIndex #-}
319bsearchIndex :: a -> Array a -> Maybe Int
320bsearchIndex elem arr = undefined
322-- find/findIndex etc can potentially be implemented more efficiently on arrays
323-- compared to streams by using SIMD instructions.
325find :: (a -> Bool) -> Array a -> Bool
328findIndex :: (a -> Bool) -> Array a -> Maybe Int
331findIndices :: (a -> Bool) -> Array a -> Array Int
332findIndices = undefined
335-------------------------------------------------------------------------------
337-------------------------------------------------------------------------------
339-- XXX We can potentially use SIMD instructions on arrays to fold faster.
341-------------------------------------------------------------------------------
343-------------------------------------------------------------------------------
346slice :: Int -> Int -> Array a
347slice begin end arr = undefined
349splitAt :: Int -> Array a -> (Array a, Array a)
350splitAt i arr = undefined
352-- XXX This operation can be performed efficiently via streams.
353-- | Append two arrays together to create a single array.
354splice :: Array a -> Array a -> Array a
355splice arr1 arr2 = undefined
357-------------------------------------------------------------------------------
358-- In-place mutation APIs
359-------------------------------------------------------------------------------
361-- | Partition an array into two halves using a partitioning predicate. The
362-- first half retains values where the predicate is 'False' and the second half
363-- retains values where the predicate is 'True'.
364{-# INLINE partitionBy #-}
365partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
366partitionBy f arr = undefined
368-- | Shuffle corresponding elements from two arrays using a shuffle function.
369-- If the shuffle function returns 'False' then do nothing otherwise swap the
370-- elements. This can be used in a bottom up fold to shuffle or reorder the
372shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
373shuffleBy f arr1 arr2 = undefined
375-- XXX we can also make the folds partial by stopping at a certain level.
377-- | Perform a top down hierarchical recursive partitioning fold of items in
378-- the container using the given function as the partition function.
380-- This will perform a quick sort if the partition function is
381-- 'partitionBy (< pivot)'.
384{-# INLINABLE foldtWith #-}
385foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
386foldtWith level f = undefined
388-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
389-- indicates the level in the tree where the fold would stop.
391-- This will perform a random shuffle if the shuffle function is random.
392-- If we stop at level 0 and repeatedly apply the function then we can do a
394foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
395foldbWith level f = undefined
398-- XXX consider the bulk update/accumulation/permutation APIs from vector.
400-------------------------------------------------------------------------------
401-- Random reads and writes
402-------------------------------------------------------------------------------
404-- | /O(1)/ Lookup the element at the given index, starting from 0.
407{-# INLINE readIndex #-}
408readIndex :: Storable a => Array a -> Int -> Maybe a
410 if i < 0 || i > length arr - 1
412 else A.unsafeInlineIO $
413 withForeignPtr (aStart arr) $ \p -> Just <$> peekElemOff p i
416-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
417-- at index @i@ and reading up to @count@ elements in the forward direction
418-- ending at the index @i + count - 1@.
421{-# INLINE readSlice #-}
422readSlice :: (IsStream t, Monad m, Storable a)
423 => Array a -> Int -> Int -> t m a
424readSlice arr i len = undefined
426-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
427-- index @i@ and reading up to @count@ elements in the reverse direction ending
428-- at the index @i - count + 1@.
431{-# INLINE readSliceRev #-}
432readSliceRev :: (IsStream t, Monad m, Storable a)
433 => Array a -> Int -> Int -> t m a
434readSliceRev arr i len = undefined
437-- | /O(1)/ Write the given element at the given index in the array.
438-- Performs in-place mutation of the array.
441{-# INLINE writeIndex #-}
442writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
443writeIndex arr i a = do
444 let maxIndex = length arr - 1
446 then error "writeIndex: negative array index"
448 then error $ "writeIndex: specified array index " ++ show i
449 ++ " is beyond the maximum index " ++ show maxIndex
451 liftIO $ withForeignPtr (aStart arr) $ \p ->
455-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
456-- starting at index @i@ and writing up to @count@ elements in the forward
457-- direction ending at the index @i + count - 1@.
460{-# INLINE writeSlice #-}
461writeSlice :: (IsStream t, Monad m, Storable a)
462 => Array a -> Int -> Int -> t m a -> m (Array a)
463writeSlice arr i len s = undefined
465-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
466-- starting at index @i@ and writing up to @count@ elements in the reverse
467-- direction ending at the index @i - count + 1@.
470{-# INLINE writeSliceRev #-}
471writeSliceRev :: (IsStream t, Monad m, Storable a)
472 => Array a -> Int -> Int -> t m a -> m (Array a)
473writeSliceRev arr i len s = undefined
476-------------------------------------------------------------------------------
477-- Transform via stream operations
478-------------------------------------------------------------------------------
480-- for non-length changing operations we can use the original length for
481-- allocation. If we can predict the length then we can use the prediction for
482-- new allocation. Otherwise we can use a hint and adjust dynamically.
485-- | Transform an array into another array using a pipe transformation
489{-# INLINE runPipe #-}
490runPipe :: (MonadIO m, Storable a, Storable b)
491 => Pipe m a b -> Array a -> m (Array b)
492runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
495-- | Transform an array into another array using a stream transformation
499{-# INLINE streamTransform #-}
500streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
501 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
502streamTransform f arr =
503 P.runFold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
506-------------------------------------------------------------------------------
508-------------------------------------------------------------------------------
510-- | Cast an array having elements of type @a@ into an array having elements of
511-- type @b@. The array size must be a multiple of the size of type @b@
512-- otherwise accessing the last element of the array may result into a crash or
517unsafeCast :: Array a -> Array b
518unsafeCast (Array start end) = Array (castForeignPtr start) (castPtr end)
520-- | Cast an array into a Word8 array
524asByteArray :: Array a -> Array Word8
525asByteArray = unsafeCast
527-- | Cast an array having elements of type @a@ into an array having elements of
528-- type @b@. The length of the array should be a multiple of the size of the
529-- target element otherwise 'Nothing' is returned.
533cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
535 let len = A.byteLength arr
536 r = len `mod` sizeOf (undefined :: b)
539 else Just $ unsafeCast arr
541-- | Use an @Array a@ as @Ptr b@.
547asPtr :: Array a -> (Ptr b -> IO c) -> IO c
548asPtr Array{..} act = do
549 withForeignPtr aStart $ \ptr -> act (castPtr ptr)
551-- | Convert an array of any type into a null terminated CString Ptr.
555-- /O(n) Time: (creates a copy of the array)/
559asCString :: Array a -> (CString -> IO b) -> IO b
560asCString arr act = do
561 let Array{..} = asByteArray arr <> A.fromList [0]
562 withForeignPtr aStart $ \ptr -> act (castPtr ptr)
564-------------------------------------------------------------------------------
566-------------------------------------------------------------------------------
568-- | Fold an array using a 'Fold'.
572fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
573fold f arr = P.runFold f (toStream arr :: Serial.SerialT m a)
575-- | Fold an array using a stream fold operation.
578{-# INLINE streamFold #-}
579streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
580streamFold f arr = f (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