1{-# LANGUAGE BangPatterns #-}
3{-# LANGUAGE MagicHash #-}
4{-# LANGUAGE UnboxedTuples #-}
5{-# LANGUAGE ScopedTypeVariables #-}
10-- Module : Streamly.Internal.Memory.Array
11-- Copyright : (c) 2019 Composewell Technologies
14-- Maintainer : streamly@composewell.com
15-- Stability : experimental
20-- * Arrays are finite and fixed in size
21-- * provide /O(1)/ access to elements
22-- * store only data and not functions
23-- * provide efficient IO interfacing
25-- 'Foldable' instance is not provided because the implementation would be much
26-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
27-- instances should be used with care; concatenating arrays using binary
28-- operations can be highly inefficient. Instead, use
29-- 'Streamly.Internal.Memory.ArrayStream.toArray' to concatenate N arrays at
32-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
33-- single byte) are only as good as holding those elements in a Haskell list.
34-- However, small arrays can be compacted into large ones to reduce the
35-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
36-- if we use one array for each chunk. This is still significant to add
39module Streamly.Internal.Memory.Array
57 , A.writeN -- drop new
59 , A.write -- full buffer
60 -- , writeLastN -- drop old (ring buffer)
81 -- , readFrom -- read from a given position to the end of file
82 -- , readFromRev -- read from a given position to the beginning of file
83 -- , readTo -- read from beginning up to the given position
84 -- , readToRev -- read from end to the given position in file
92 -- , writeFrom -- start writing at the given position
94 -- , writeTo -- write from beginning up to the given position
99 -- , writeChunksOfFrom
113 -- -- * In-pace mutation (for Mutable Array type)
119 -- * Immutable Transformations
126 -- * Folds with Array as the container
131import Control.Monad (when)
132import Control.Monad.IO.Class (MonadIO(..))
133-- import Data.Functor.Identity (Identity)
134import Foreign.ForeignPtr (withForeignPtr, touchForeignPtr)
135import Foreign.Ptr (plusPtr)
136import Foreign.Storable (Storable(..))
137import Prelude hiding (length, null, last, map, (!!), read, concat)
139import GHC.ForeignPtr (ForeignPtr(..))
140import GHC.Ptr (Ptr(..))
141import GHC.Prim (touch#)
142import GHC.IO (IO(..))
144import Streamly.Internal.Data.Fold.Types (Fold(..))
145import Streamly.Internal.Data.Unfold.Types (Unfold(..))
146import Streamly.Internal.Memory.Array.Types (Array(..), length)
147import Streamly.Internal.Data.Stream.Serial (SerialT)
148import Streamly.Internal.Data.Stream.StreamK.Type (IsStream)
150import qualified Streamly.Internal.Memory.Array.Types as A
151import qualified Streamly.Internal.Data.Stream.Prelude as P
152import qualified Streamly.Internal.Data.Stream.Serial as Serial
153import qualified Streamly.Internal.Data.Stream.StreamD as D
154import qualified Streamly.Internal.Data.Stream.StreamK as K
156-------------------------------------------------------------------------------
158-------------------------------------------------------------------------------
161-- | Create a new uninitialized array of given length.
164newArray :: (MonadIO m, Storable a) => Int -> m (Array a)
165newArray len = undefined
168-- | Create an 'Array' from the first N elements of a stream. The array is
169-- allocated to size N, if the stream terminates before N elements then the
170-- array may hold less than N elements.
173{-# INLINE fromStreamN #-}
174fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
176 when (n < 0) $ error "writeN: negative write count specified"
177 A.fromStreamDN n $ D.toStreamD m
179-- | Create an 'Array' from a stream. This is useful when we want to create a
180-- single array from a stream of unknown size. 'writeN' is at least twice
181-- as efficient when the size is already known.
183-- Note that if the input stream is too large memory allocation for the array
184-- may fail. When the stream size is not known, `arraysOf` followed by
185-- processing of indvidual arrays in the resulting stream should be preferred.
188{-# INLINE fromStream #-}
189fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
190fromStream = P.runFold A.write
191-- write m = A.fromStreamD $ D.toStreamD m
193-------------------------------------------------------------------------------
195-------------------------------------------------------------------------------
197-- | Convert an 'Array' into a stream.
200{-# INLINE_EARLY toStream #-}
201toStream :: (Monad m, K.IsStream t, Storable a) => Array a -> t m a
202toStream = D.fromStreamD . A.toStreamD
203-- XXX add fallback to StreamK rule
204-- {-# RULES "Streamly.Array.read fallback to StreamK" [1]
205-- forall a. S.readK (read a) = K.fromArray a #-}
207-- | Convert an 'Array' into a stream in reverse order.
210{-# INLINE_EARLY toStreamRev #-}
211toStreamRev :: (Monad m, IsStream t, Storable a) => Array a -> t m a
212toStreamRev = D.fromStreamD . A.toStreamDRev
213-- XXX add fallback to StreamK rule
214-- {-# RULES "Streamly.Array.readRev fallback to StreamK" [1]
215-- forall a. S.toStreamK (readRev a) = K.revFromArray a #-}
217data ReadUState a = ReadUState
218 {-# UNPACK #-} !(ForeignPtr a) -- foreign ptr with end of array pointer
219 {-# UNPACK #-} !(Ptr a) -- current pointer
221-- | Unfold an array into a stream.
224{-# INLINE_NORMAL read #-}
225read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
226read = Unfold step inject
229 inject (Array (ForeignPtr start contents) (Ptr end) _) =
230 return $ ReadUState (ForeignPtr end contents) (Ptr start)
232 {-# INLINE_LATE step #-}
233 step (ReadUState fp@(ForeignPtr end _) p) | p == Ptr end =
234 let x = A.unsafeInlineIO $ touchForeignPtr fp
235 in x `seq` return D.Stop
236 step (ReadUState fp p) = do
237 -- unsafeInlineIO allows us to run this in Identity monad for pure
238 -- toList/foldr case which makes them much faster due to not
239 -- accumulating the list and fusing better with the pure consumers.
241 -- This should be safe as the array contents are guaranteed to be
242 -- evaluated/written to before we peek at them.
243 let !x = A.unsafeInlineIO $ peek p
245 (ReadUState fp (p `plusPtr` sizeOf (undefined :: a)))
247-- | Unfold an array into a stream, does not check the end of the array, the
248-- user is responsible for terminating the stream within the array bounds. For
249-- high performance application where the end condition can be determined by
250-- a terminating fold.
252-- Written in the hope that it may be faster than "read", however, in the case
253-- for which this was written, "read" proves to be faster even though the core
254-- generated with unsafeRead looks simpler.
258{-# INLINE_NORMAL unsafeRead #-}
259unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
260unsafeRead = Unfold step inject
263 inject (Array fp _ _) = return fp
265 {-# INLINE_LATE step #-}
266 step (ForeignPtr p contents) = do
267 -- unsafeInlineIO allows us to run this in Identity monad for pure
268 -- toList/foldr case which makes them much faster due to not
269 -- accumulating the list and fusing better with the pure consumers.
271 -- This should be safe as the array contents are guaranteed to be
272 -- evaluated/written to before we peek at them.
273 let !x = A.unsafeInlineIO $ do
277 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
278 return $ D.Yield x (ForeignPtr p1 contents)
280 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
282-- | > null arr = length arr == 0
286null :: Storable a => Array a -> Bool
287null arr = length arr == 0
289-- | > last arr = readIndex arr (length arr - 1)
293last :: Storable a => Array a -> Maybe a
294last arr = readIndex arr (length arr - 1)
296-------------------------------------------------------------------------------
298-------------------------------------------------------------------------------
300-------------------------------------------------------------------------------
302-------------------------------------------------------------------------------
305-- | Perform a binary search in the array to find an element.
306bsearch :: a -> Array a -> Maybe Bool
309-- | Perform a binary search in the array to find an element index.
310{-# INLINE elemIndex #-}
311bsearchIndex :: a -> Array a -> Maybe Int
312bsearchIndex elem arr = undefined
314-- find/findIndex etc can potentially be implemented more efficiently on arrays
315-- compared to streams by using SIMD instructions.
317find :: (a -> Bool) -> Array a -> Bool
320findIndex :: (a -> Bool) -> Array a -> Maybe Int
323findIndices :: (a -> Bool) -> Array a -> Array Int
324findIndices = undefined
327-------------------------------------------------------------------------------
329-------------------------------------------------------------------------------
331-- XXX We can potentially use SIMD instructions on arrays to fold faster.
333-------------------------------------------------------------------------------
335-------------------------------------------------------------------------------
338slice :: Int -> Int -> Array a
339slice begin end arr = undefined
341splitAt :: Int -> Array a -> (Array a, Array a)
342splitAt i arr = undefined
344-- XXX This operation can be performed efficiently via streams.
345-- | Append two arrays together to create a single array.
346splice :: Array a -> Array a -> Array a
347splice arr1 arr2 = undefined
349-------------------------------------------------------------------------------
350-- In-place mutation APIs
351-------------------------------------------------------------------------------
353-- | Partition an array into two halves using a partitioning predicate. The
354-- first half retains values where the predicate is 'False' and the second half
355-- retains values where the predicate is 'True'.
356{-# INLINE partitionBy #-}
357partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
358partitionBy f arr = undefined
360-- | Shuffle corresponding elements from two arrays using a shuffle function.
361-- If the shuffle function returns 'False' then do nothing otherwise swap the
362-- elements. This can be used in a bottom up fold to shuffle or reorder the
364shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
365shuffleBy f arr1 arr2 = undefined
367-- XXX we can also make the folds partial by stopping at a certain level.
369-- | Perform a top down hierarchical recursive partitioning fold of items in
370-- the container using the given function as the partition function.
372-- This will perform a quick sort if the partition function is
373-- 'partitionBy (< pivot)'.
376{-# INLINABLE foldtWith #-}
377foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
378foldtWith level f = undefined
380-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
381-- indicates the level in the tree where the fold would stop.
383-- This will perform a random shuffle if the shuffle function is random.
384-- If we stop at level 0 and repeatedly apply the function then we can do a
386foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
387foldbWith level f = undefined
390-- XXX consider the bulk update/accumulation/permutation APIs from vector.
392-------------------------------------------------------------------------------
393-- Random reads and writes
394-------------------------------------------------------------------------------
396-- | /O(1)/ Lookup the element at the given index, starting from 0.
399{-# INLINE readIndex #-}
400readIndex :: Storable a => Array a -> Int -> Maybe a
402 if i < 0 || i > length arr - 1
404 else A.unsafeInlineIO $
405 withForeignPtr (aStart arr) $ \p -> Just <$> peekElemOff p i
408-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
409-- at index @i@ and reading up to @count@ elements in the forward direction
410-- ending at the index @i + count - 1@.
413{-# INLINE readSlice #-}
414readSlice :: (IsStream t, Monad m, Storable a)
415 => Array a -> Int -> Int -> t m a
416readSlice arr i len = undefined
418-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
419-- index @i@ and reading up to @count@ elements in the reverse direction ending
420-- at the index @i - count + 1@.
423{-# INLINE readSliceRev #-}
424readSliceRev :: (IsStream t, Monad m, Storable a)
425 => Array a -> Int -> Int -> t m a
426readSliceRev arr i len = undefined
429-- | /O(1)/ Write the given element at the given index in the array.
430-- Performs in-place mutation of the array.
433{-# INLINE writeIndex #-}
434writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
435writeIndex arr i a = do
436 let maxIndex = length arr - 1
438 then error "writeIndex: negative array index"
440 then error $ "writeIndex: specified array index " ++ show i
441 ++ " is beyond the maximum index " ++ show maxIndex
443 liftIO $ withForeignPtr (aStart arr) $ \p ->
447-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
448-- starting at index @i@ and writing up to @count@ elements in the forward
449-- direction ending at the index @i + count - 1@.
452{-# INLINE writeSlice #-}
453writeSlice :: (IsStream t, Monad m, Storable a)
454 => Array a -> Int -> Int -> t m a -> m ()
455writeSlice arr i len s = undefined
457-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
458-- starting at index @i@ and writing up to @count@ elements in the reverse
459-- direction ending at the index @i - count + 1@.
462{-# INLINE writeSliceRev #-}
463writeSliceRev :: (IsStream t, Monad m, Storable a)
464 => Array a -> Int -> Int -> t m a -> m ()
465writeSliceRev arr i len s = undefined
468-------------------------------------------------------------------------------
469-- Transform via stream operations
470-------------------------------------------------------------------------------
472-- for non-length changing operations we can use the original length for
473-- allocation. If we can predict the length then we can use the prediction for
474-- new allocation. Otherwise we can use a hint and adjust dynamically.
477-- | Transform an array into another array using a pipe transformation
481{-# INLINE runPipe #-}
482runPipe :: (MonadIO m, Storable a, Storable b)
483 => Pipe m a b -> Array a -> m (Array b)
484runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
487-- | Transform an array into another array using a stream transformation
491{-# INLINE streamTransform #-}
492streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
493 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
494streamTransform f arr =
495 P.runFold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
498-- | Fold an array using a 'Fold'.
502fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
503fold f arr = P.runFold f (toStream arr :: Serial.SerialT m a)
505-- | Fold an array using a stream fold operation.
508{-# INLINE streamFold #-}
509streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
510streamFold 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