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
53 , A.writeN -- drop new
55 , A.write -- full buffer
56 -- , writeLastN -- drop old (ring buffer)
77 -- , readFrom -- read from a given position to the end of file
78 -- , readFromRev -- read from a given position to the beginning of file
79 -- , readTo -- read from beginning up to the given position
80 -- , readToRev -- read from end to the given position in file
88 -- , writeFrom -- start writing at the given position
90 -- , writeTo -- write from beginning up to the given position
95 -- , writeChunksOfFrom
109 -- -- * In-pace mutation (for Mutable Array type)
115 -- * Immutable Transformations
122 -- * Folds with Array as the container
127import Control.Monad (when)
128import Control.Monad.IO.Class (MonadIO(..))
129-- import Data.Functor.Identity (Identity)
130import Foreign.ForeignPtr (withForeignPtr, touchForeignPtr)
131import Foreign.Ptr (plusPtr)
132import Foreign.Storable (Storable(..))
133import Prelude hiding (length, null, last, map, (!!), read, concat)
135import GHC.ForeignPtr (ForeignPtr(..))
136import GHC.Ptr (Ptr(..))
137import GHC.Prim (touch#)
138import GHC.IO (IO(..))
140import Streamly.Internal.Data.Fold.Types (Fold(..))
141import Streamly.Internal.Data.Unfold.Types (Unfold(..))
142import Streamly.Internal.Memory.Array.Types (Array(..), length)
143import Streamly.Internal.Data.Stream.Serial (SerialT)
144import Streamly.Internal.Data.Stream.StreamK.Type (IsStream)
146import qualified Streamly.Internal.Memory.Array.Types as A
147import qualified Streamly.Internal.Data.Stream.Prelude as P
148import qualified Streamly.Internal.Data.Stream.Serial as Serial
149import qualified Streamly.Internal.Data.Stream.StreamD as D
150import qualified Streamly.Internal.Data.Stream.StreamK as K
152-------------------------------------------------------------------------------
154-------------------------------------------------------------------------------
157-- | Create a new uninitialized array of given length.
160newArray :: (MonadIO m, Storable a) => Int -> m (Array a)
161newArray len = undefined
164-- | Create an 'Array' from the first N elements of a stream. The array is
165-- allocated to size N, if the stream terminates before N elements then the
166-- array may hold less than N elements.
169{-# INLINE fromStreamN #-}
170fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
172 when (n < 0) $ error "writeN: negative write count specified"
173 A.fromStreamDN n $ D.toStreamD m
175-- | Create an 'Array' from a stream. This is useful when we want to create a
176-- single array from a stream of unknown size. 'writeN' is at least twice
177-- as efficient when the size is already known.
179-- Note that if the input stream is too large memory allocation for the array
180-- may fail. When the stream size is not known, `arraysOf` followed by
181-- processing of indvidual arrays in the resulting stream should be preferred.
184{-# INLINE fromStream #-}
185fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
186fromStream = P.runFold A.write
187-- write m = A.fromStreamD $ D.toStreamD m
189-------------------------------------------------------------------------------
191-------------------------------------------------------------------------------
193-- | Convert an 'Array' into a stream.
196{-# INLINE_EARLY toStream #-}
197toStream :: (Monad m, K.IsStream t, Storable a) => Array a -> t m a
198toStream = D.fromStreamD . A.toStreamD
199-- XXX add fallback to StreamK rule
200-- {-# RULES "Streamly.Array.read fallback to StreamK" [1]
201-- forall a. S.readK (read a) = K.fromArray a #-}
203-- | Convert an 'Array' into a stream in reverse order.
206{-# INLINE_EARLY toStreamRev #-}
207toStreamRev :: (Monad m, IsStream t, Storable a) => Array a -> t m a
208toStreamRev = D.fromStreamD . A.toStreamDRev
209-- XXX add fallback to StreamK rule
210-- {-# RULES "Streamly.Array.readRev fallback to StreamK" [1]
211-- forall a. S.toStreamK (readRev a) = K.revFromArray a #-}
213data ReadUState a = ReadUState
214 {-# UNPACK #-} !(ForeignPtr a) -- foreign ptr with end of array pointer
215 {-# UNPACK #-} !(Ptr a) -- current pointer
217-- | Unfold an array into a stream.
220{-# INLINE_NORMAL read #-}
221read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
222read = Unfold step inject
225 inject (Array (ForeignPtr start contents) (Ptr end) _) =
226 return $ ReadUState (ForeignPtr end contents) (Ptr start)
228 {-# INLINE_LATE step #-}
229 step (ReadUState fp@(ForeignPtr end _) p) | p == Ptr end =
230 let x = A.unsafeInlineIO $ touchForeignPtr fp
231 in x `seq` return D.Stop
232 step (ReadUState fp p) = do
233 -- unsafeInlineIO allows us to run this in Identity monad for pure
234 -- toList/foldr case which makes them much faster due to not
235 -- accumulating the list and fusing better with the pure consumers.
237 -- This should be safe as the array contents are guaranteed to be
238 -- evaluated/written to before we peek at them.
239 let !x = A.unsafeInlineIO $ peek p
241 (ReadUState fp (p `plusPtr` sizeOf (undefined :: a)))
243-- | Unfold an array into a stream, does not check the end of the array, the
244-- user is responsible for terminating the stream within the array bounds. For
245-- high performance application where the end condition can be determined by
246-- a terminating fold.
248-- Written in the hope that it may be faster than "read", however, in the case
249-- for which this was written, "read" proves to be faster even though the core
250-- generated with unsafeRead looks simpler.
254{-# INLINE_NORMAL unsafeRead #-}
255unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
256unsafeRead = Unfold step inject
259 inject (Array fp _ _) = return fp
261 {-# INLINE_LATE step #-}
262 step (ForeignPtr p contents) = do
263 -- unsafeInlineIO allows us to run this in Identity monad for pure
264 -- toList/foldr case which makes them much faster due to not
265 -- accumulating the list and fusing better with the pure consumers.
267 -- This should be safe as the array contents are guaranteed to be
268 -- evaluated/written to before we peek at them.
269 let !x = A.unsafeInlineIO $ do
273 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
274 return $ D.Yield x (ForeignPtr p1 contents)
276 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
278-- | > null arr = length arr == 0
282null :: Storable a => Array a -> Bool
283null arr = length arr == 0
285-- | > last arr = readIndex arr (length arr - 1)
289last :: Storable a => Array a -> Maybe a
290last arr = readIndex arr (length arr - 1)
292-------------------------------------------------------------------------------
294-------------------------------------------------------------------------------
296-------------------------------------------------------------------------------
298-------------------------------------------------------------------------------
301-- | Perform a binary search in the array to find an element.
302bsearch :: a -> Array a -> Maybe Bool
305-- | Perform a binary search in the array to find an element index.
306{-# INLINE elemIndex #-}
307bsearchIndex :: a -> Array a -> Maybe Int
308bsearchIndex elem arr = undefined
310-- find/findIndex etc can potentially be implemented more efficiently on arrays
311-- compared to streams by using SIMD instructions.
313find :: (a -> Bool) -> Array a -> Bool
316findIndex :: (a -> Bool) -> Array a -> Maybe Int
319findIndices :: (a -> Bool) -> Array a -> Array Int
320findIndices = undefined
323-------------------------------------------------------------------------------
325-------------------------------------------------------------------------------
327-- XXX We can potentially use SIMD instructions on arrays to fold faster.
329-------------------------------------------------------------------------------
331-------------------------------------------------------------------------------
334slice :: Int -> Int -> Array a
335slice begin end arr = undefined
337splitAt :: Int -> Array a -> (Array a, Array a)
338splitAt i arr = undefined
340-- XXX This operation can be performed efficiently via streams.
341-- | Append two arrays together to create a single array.
342splice :: Array a -> Array a -> Array a
343splice arr1 arr2 = undefined
345-------------------------------------------------------------------------------
346-- In-place mutation APIs
347-------------------------------------------------------------------------------
349-- | Partition an array into two halves using a partitioning predicate. The
350-- first half retains values where the predicate is 'False' and the second half
351-- retains values where the predicate is 'True'.
352{-# INLINE partitionBy #-}
353partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
354partitionBy f arr = undefined
356-- | Shuffle corresponding elements from two arrays using a shuffle function.
357-- If the shuffle function returns 'False' then do nothing otherwise swap the
358-- elements. This can be used in a bottom up fold to shuffle or reorder the
360shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
361shuffleBy f arr1 arr2 = undefined
363-- XXX we can also make the folds partial by stopping at a certain level.
365-- | Perform a top down hierarchical recursive partitioning fold of items in
366-- the container using the given function as the partition function.
368-- This will perform a quick sort if the partition function is
369-- 'partitionBy (< pivot)'.
372{-# INLINABLE foldtWith #-}
373foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
374foldtWith level f = undefined
376-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
377-- indicates the level in the tree where the fold would stop.
379-- This will perform a random shuffle if the shuffle function is random.
380-- If we stop at level 0 and repeatedly apply the function then we can do a
382foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
383foldbWith level f = undefined
386-- XXX consider the bulk update/accumulation/permutation APIs from vector.
388-------------------------------------------------------------------------------
389-- Random reads and writes
390-------------------------------------------------------------------------------
392-- | /O(1)/ Lookup the element at the given index, starting from 0.
395{-# INLINE readIndex #-}
396readIndex :: Storable a => Array a -> Int -> Maybe a
398 if i < 0 || i > length arr - 1
400 else A.unsafeInlineIO $
401 withForeignPtr (aStart arr) $ \p -> Just <$> peekElemOff p i
404-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
405-- at index @i@ and reading up to @count@ elements in the forward direction
406-- ending at the index @i + count - 1@.
409{-# INLINE readSlice #-}
410readSlice :: (IsStream t, Monad m, Storable a)
411 => Array a -> Int -> Int -> t m a
412readSlice arr i len = undefined
414-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
415-- index @i@ and reading up to @count@ elements in the reverse direction ending
416-- at the index @i - count + 1@.
419{-# INLINE readSliceRev #-}
420readSliceRev :: (IsStream t, Monad m, Storable a)
421 => Array a -> Int -> Int -> t m a
422readSliceRev arr i len = undefined
425-- | /O(1)/ Write the given element at the given index in the array.
426-- Performs in-place mutation of the array.
429{-# INLINE writeIndex #-}
430writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
431writeIndex arr i a = do
432 let maxIndex = length arr - 1
434 then error "writeIndex: negative array index"
436 then error $ "writeIndex: specified array index " ++ show i
437 ++ " is beyond the maximum index " ++ show maxIndex
439 liftIO $ withForeignPtr (aStart arr) $ \p ->
443-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
444-- starting at index @i@ and writing up to @count@ elements in the forward
445-- direction ending at the index @i + count - 1@.
448{-# INLINE writeSlice #-}
449writeSlice :: (IsStream t, Monad m, Storable a)
450 => Array a -> Int -> Int -> t m a -> m ()
451writeSlice arr i len s = undefined
453-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
454-- starting at index @i@ and writing up to @count@ elements in the reverse
455-- direction ending at the index @i - count + 1@.
458{-# INLINE writeSliceRev #-}
459writeSliceRev :: (IsStream t, Monad m, Storable a)
460 => Array a -> Int -> Int -> t m a -> m ()
461writeSliceRev arr i len s = undefined
464-------------------------------------------------------------------------------
465-- Transform via stream operations
466-------------------------------------------------------------------------------
468-- for non-length changing operations we can use the original length for
469-- allocation. If we can predict the length then we can use the prediction for
470-- new allocation. Otherwise we can use a hint and adjust dynamically.
473-- | Transform an array into another array using a pipe transformation
477{-# INLINE runPipe #-}
478runPipe :: (MonadIO m, Storable a, Storable b)
479 => Pipe m a b -> Array a -> m (Array b)
480runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
483-- | Transform an array into another array using a stream transformation
487{-# INLINE streamTransform #-}
488streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
489 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
490streamTransform f arr =
491 P.runFold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
494-- | Fold an array using a 'Fold'.
498fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
499fold f arr = P.runFold f (toStream arr :: Serial.SerialT m a)
501-- | Fold an array using a stream fold operation.
504{-# INLINE streamFold #-}
505streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
506streamFold 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