1{-# OPTIONS_HADDOCK hide #-}
2{-# LANGUAGE BangPatterns #-}
4{-# LANGUAGE MagicHash #-}
5{-# LANGUAGE RecordWildCards #-}
6{-# LANGUAGE UnboxedTuples #-}
7{-# LANGUAGE ScopedTypeVariables #-}
12-- Module : Streamly.Internal.Memory.Array
13-- Copyright : (c) 2019 Composewell Technologies
16-- Maintainer : streamly@composewell.com
17-- Stability : experimental
22-- * Arrays are finite and fixed in size
23-- * provide /O(1)/ access to elements
24-- * store only data and not functions
25-- * provide efficient IO interfacing
27-- 'Foldable' instance is not provided because the implementation would be much
28-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
29-- instances should be used with care; concatenating arrays using binary
30-- operations can be highly inefficient. Instead, use
31-- 'Streamly.Internal.Memory.ArrayStream.toArray' to concatenate N arrays at
34-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
35-- single byte) are only as good as holding those elements in a Haskell list.
36-- However, small arrays can be compacted into large ones to reduce the
37-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
38-- if we use one array for each chunk. This is still significant to add
41module Streamly.Internal.Memory.Array
59 , A.writeN -- drop new
61 , A.write -- full buffer
62 -- , writeLastN -- drop old (ring buffer)
83 -- , readFrom -- read from a given position to the end of file
84 -- , readFromRev -- read from a given position to the beginning of file
85 -- , readTo -- read from beginning up to the given position
86 -- , readToRev -- read from end to the given position in file
94 -- , writeFrom -- start writing at the given position
96 -- , writeTo -- write from beginning up to the given position
101 -- , writeChunksOfFrom
115 -- -- * In-pace mutation (for Mutable Array type)
121 -- * Immutable Transformations
128 -- * Folds with Array as the container
133import Control.Monad.IO.Class (MonadIO(..))
134-- import Data.Functor.Identity (Identity)
135import Foreign.ForeignPtr (withForeignPtr, touchForeignPtr)
136import Foreign.Ptr (plusPtr)
137import Foreign.Storable (Storable(..))
138import Prelude hiding (length, null, last, map, (!!), read, concat)
140import GHC.ForeignPtr (ForeignPtr(..))
141import GHC.Ptr (Ptr(..))
142import GHC.Prim (touch#)
143import GHC.IO (IO(..))
145import Streamly.Internal.Data.Fold.Types (Fold(..))
146import Streamly.Internal.Data.Unfold.Types (Unfold(..))
147import Streamly.Internal.Memory.Array.Types (Array(..), length)
148import Streamly.Internal.Data.Stream.Serial (SerialT)
149import Streamly.Internal.Data.Stream.StreamK.Type (IsStream)
151import qualified Streamly.Internal.Memory.Array.Types as A
152import qualified Streamly.Internal.Data.Stream.Prelude as P
153import qualified Streamly.Internal.Data.Stream.Serial as Serial
154import qualified Streamly.Internal.Data.Stream.StreamD as D
155import qualified Streamly.Internal.Data.Stream.StreamK as K
157-------------------------------------------------------------------------------
159-------------------------------------------------------------------------------
162-- | Create a new uninitialized array of given length.
165newArray :: (MonadIO m, Storable a) => Int -> m (Array a)
166newArray len = undefined
169-- | Create an 'Array' from the first N elements of a stream. The array is
170-- allocated to size N, if the stream terminates before N elements then the
171-- array may hold less than N elements.
174{-# INLINE fromStreamN #-}
175fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
177 if n < 0 then error "writeN: negative write count specified" else return ()
178 A.fromStreamDN n $ D.toStreamD m
180-- | Create an 'Array' from a stream. This is useful when we want to create a
181-- single array from a stream of unknown size. 'writeN' is at least twice
182-- as efficient when the size is already known.
184-- Note that if the input stream is too large memory allocation for the array
185-- may fail. When the stream size is not known, `arraysOf` followed by
186-- processing of indvidual arrays in the resulting stream should be preferred.
189{-# INLINE fromStream #-}
190fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
191fromStream = P.runFold A.write
192-- write m = A.fromStreamD $ D.toStreamD m
194-------------------------------------------------------------------------------
196-------------------------------------------------------------------------------
198-- | Convert an 'Array' into a stream.
201{-# INLINE_EARLY toStream #-}
202toStream :: (Monad m, K.IsStream t, Storable a) => Array a -> t m a
203toStream = D.fromStreamD . A.toStreamD
204-- XXX add fallback to StreamK rule
205-- {-# RULES "Streamly.Array.read fallback to StreamK" [1]
206-- forall a. S.readK (read a) = K.fromArray a #-}
208-- | Convert an 'Array' into a stream in reverse order.
211{-# INLINE_EARLY toStreamRev #-}
212toStreamRev :: (Monad m, IsStream t, Storable a) => Array a -> t m a
213toStreamRev = D.fromStreamD . A.toStreamDRev
214-- XXX add fallback to StreamK rule
215-- {-# RULES "Streamly.Array.readRev fallback to StreamK" [1]
216-- forall a. S.toStreamK (readRev a) = K.revFromArray a #-}
218data ReadUState a = ReadUState
219 {-# UNPACK #-} !(ForeignPtr a) -- foreign ptr with end of array pointer
220 {-# UNPACK #-} !(Ptr a) -- current pointer
222-- | Unfold an array into a stream.
225{-# INLINE_NORMAL read #-}
226read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
227read = Unfold step inject
230 inject (Array (ForeignPtr start contents) (Ptr end) _) =
231 return $ ReadUState (ForeignPtr end contents) (Ptr start)
233 {-# INLINE_LATE step #-}
234 step (ReadUState fp@(ForeignPtr end _) p) | p == (Ptr end) =
235 let x = A.unsafeInlineIO $ touchForeignPtr fp
236 in x `seq` return D.Stop
237 step (ReadUState fp p) = do
238 -- unsafeInlineIO allows us to run this in Identity monad for pure
239 -- toList/foldr case which makes them much faster due to not
240 -- accumulating the list and fusing better with the pure consumers.
242 -- This should be safe as the array contents are guaranteed to be
243 -- evaluated/written to before we peek at them.
244 let !x = A.unsafeInlineIO $ peek p
246 (ReadUState fp (p `plusPtr` (sizeOf (undefined :: a))))
248-- | Unfold an array into a stream, does not check the end of the array, the
249-- user is responsible for terminating the stream within the array bounds. For
250-- high performance application where the end condition can be determined by
251-- a terminating fold.
253-- Written in the hope that it may be faster than "read", however, in the case
254-- for which this was written, "read" proves to be faster even though the core
255-- generated with unsafeRead looks simpler.
259{-# INLINE_NORMAL unsafeRead #-}
260unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
261unsafeRead = Unfold step inject
264 inject (Array fp _ _) = return fp
266 {-# INLINE_LATE step #-}
267 step (ForeignPtr p contents) = do
268 -- unsafeInlineIO allows us to run this in Identity monad for pure
269 -- toList/foldr case which makes them much faster due to not
270 -- accumulating the list and fusing better with the pure consumers.
272 -- This should be safe as the array contents are guaranteed to be
273 -- evaluated/written to before we peek at them.
274 let !x = A.unsafeInlineIO $ do
278 let !(Ptr p1) = Ptr p `plusPtr` (sizeOf (undefined :: a))
279 return $ D.Yield x (ForeignPtr p1 contents)
281 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
283-- | > null arr = length arr == 0
287null :: Storable a => Array a -> Bool
288null arr = length arr == 0
290-- | > last arr = readIndex arr (length arr - 1)
294last :: Storable a => Array a -> Maybe a
295last arr = readIndex arr (length arr - 1)
297-------------------------------------------------------------------------------
299-------------------------------------------------------------------------------
301-------------------------------------------------------------------------------
303-------------------------------------------------------------------------------
306-- | Perform a binary search in the array to find an element.
307bsearch :: a -> Array a -> Maybe Bool
310-- | Perform a binary search in the array to find an element index.
311{-# INLINE elemIndex #-}
312bsearchIndex :: a -> Array a -> Maybe Int
313bsearchIndex elem arr = undefined
315-- find/findIndex etc can potentially be implemented more efficiently on arrays
316-- compared to streams by using SIMD instructions.
318find :: (a -> Bool) -> Array a -> Bool
321findIndex :: (a -> Bool) -> Array a -> Maybe Int
324findIndices :: (a -> Bool) -> Array a -> Array Int
325findIndices = undefined
328-------------------------------------------------------------------------------
330-------------------------------------------------------------------------------
332-- XXX We can potentially use SIMD instructions on arrays to fold faster.
334-------------------------------------------------------------------------------
336-------------------------------------------------------------------------------
339slice :: Int -> Int -> Array a
340slice begin end arr = undefined
342splitAt :: Int -> Array a -> (Array a, Array a)
343splitAt i arr = undefined
345-- XXX This operation can be performed efficiently via streams.
346-- | Append two arrays together to create a single array.
347splice :: Array a -> Array a -> Array a
348splice arr1 arr2 = undefined
350-------------------------------------------------------------------------------
351-- In-place mutation APIs
352-------------------------------------------------------------------------------
354-- | Partition an array into two halves using a partitioning predicate. The
355-- first half retains values where the predicate is 'False' and the second half
356-- retains values where the predicate is 'True'.
357{-# INLINE partitionBy #-}
358partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
359partitionBy f arr = undefined
361-- | Shuffle corresponding elements from two arrays using a shuffle function.
362-- If the shuffle function returns 'False' then do nothing otherwise swap the
363-- elements. This can be used in a bottom up fold to shuffle or reorder the
365shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
366shuffleBy f arr1 arr2 = undefined
368-- XXX we can also make the folds partial by stopping at a certain level.
370-- | Perform a top down hierarchical recursive partitioning fold of items in
371-- the container using the given function as the partition function.
373-- This will perform a quick sort if the partition function is
374-- 'partitionBy (< pivot)'.
377{-# INLINABLE foldtWith #-}
378foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
379foldtWith level f = undefined
381-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
382-- indicates the level in the tree where the fold would stop.
384-- This will perform a random shuffle if the shuffle function is random.
385-- If we stop at level 0 and repeatedly apply the function then we can do a
387foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
388foldbWith level f = undefined
391-- XXX consider the bulk update/accumulation/permutation APIs from vector.
393-------------------------------------------------------------------------------
394-- Random reads and writes
395-------------------------------------------------------------------------------
397-- | /O(1)/ Lookup the element at the given index, starting from 0.
400{-# INLINE readIndex #-}
401readIndex :: Storable a => Array a -> Int -> Maybe a
403 if i < 0 || i > length arr - 1
405 else A.unsafeInlineIO $
406 withForeignPtr (aStart arr) $ \p -> fmap Just $ peekElemOff p i
409-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
410-- at index @i@ and reading up to @count@ elements in the forward direction
411-- ending at the index @i + count - 1@.
414{-# INLINE readSlice #-}
415readSlice :: (IsStream t, Monad m, Storable a)
416 => Array a -> Int -> Int -> t m a
417readSlice arr i len = undefined
419-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
420-- index @i@ and reading up to @count@ elements in the reverse direction ending
421-- at the index @i - count + 1@.
424{-# INLINE readSliceRev #-}
425readSliceRev :: (IsStream t, Monad m, Storable a)
426 => Array a -> Int -> Int -> t m a
427readSliceRev arr i len = undefined
430-- | /O(1)/ Write the given element at the given index in the array.
431-- Performs in-place mutation of the array.
434{-# INLINE writeIndex #-}
435writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
436writeIndex arr i a = do
437 let maxIndex = length arr - 1
439 then error "writeIndex: negative array index"
441 then error $ "writeIndex: specified array index " ++ show i
442 ++ " is beyond the maximum index " ++ show maxIndex
444 liftIO $ withForeignPtr (aStart arr) $ \p ->
448-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
449-- starting at index @i@ and writing up to @count@ elements in the forward
450-- direction ending at the index @i + count - 1@.
453{-# INLINE writeSlice #-}
454writeSlice :: (IsStream t, Monad m, Storable a)
455 => Array a -> Int -> Int -> t m a -> m ()
456writeSlice arr i len s = undefined
458-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
459-- starting at index @i@ and writing up to @count@ elements in the reverse
460-- direction ending at the index @i - count + 1@.
463{-# INLINE writeSliceRev #-}
464writeSliceRev :: (IsStream t, Monad m, Storable a)
465 => Array a -> Int -> Int -> t m a -> m ()
466writeSliceRev arr i len s = undefined
469-------------------------------------------------------------------------------
470-- Transform via stream operations
471-------------------------------------------------------------------------------
473-- for non-length changing operations we can use the original length for
474-- allocation. If we can predict the length then we can use the prediction for
475-- new allocation. Otherwise we can use a hint and adjust dynamically.
478-- | Transform an array into another array using a pipe transformation
482{-# INLINE runPipe #-}
483runPipe :: (MonadIO m, Storable a, Storable b)
484 => Pipe m a b -> Array a -> m (Array b)
485runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
488-- | Transform an array into another array using a stream transformation
492{-# INLINE streamTransform #-}
493streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
494 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
495streamTransform f arr =
496 P.runFold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
499-- | Fold an array using a 'Fold'.
503fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
504fold f arr = P.runFold f $ (toStream arr :: Serial.SerialT m a)
506-- | Fold an array using a stream fold operation.
509{-# INLINE streamFold #-}
510streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
511streamFold 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