1{-# LANGUAGE BangPatterns #-}
3{-# LANGUAGE MagicHash #-}
4{-# LANGUAGE RecordWildCards #-}
5{-# LANGUAGE UnboxedTuples #-}
6{-# LANGUAGE ScopedTypeVariables #-}
11-- Module : Streamly.Internal.Memory.Array
12-- Copyright : (c) 2019 Composewell Technologies
15-- Maintainer : streamly@composewell.com
16-- Stability : experimental
21-- * Arrays are finite and fixed in size
22-- * provide /O(1)/ access to elements
23-- * store only data and not functions
24-- * provide efficient IO interfacing
26-- 'Foldable' instance is not provided because the implementation would be much
27-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
28-- instances should be used with care; concatenating arrays using binary
29-- operations can be highly inefficient. Instead, use
30-- 'Streamly.Internal.Memory.ArrayStream.toArray' to concatenate N arrays at
33-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
34-- single byte) are only as good as holding those elements in a Haskell list.
35-- However, small arrays can be compacted into large ones to reduce the
36-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
37-- if we use one array for each chunk. This is still significant to add
40module Streamly.Internal.Memory.Array
58 , A.writeN -- drop new
59 , A.write -- full buffer
60 -- , writeLastN -- drop old (ring buffer)
63 -- 'GHC.Exts.toList' from "GHC.Exts" can be used to convert an array to a
89 -- * Immutable Transformations
98import Control.Monad.IO.Class (MonadIO(..))
99-- import Data.Functor.Identity (Identity)
100import Foreign.ForeignPtr (withForeignPtr, touchForeignPtr)
101import Foreign.Ptr (plusPtr)
102import Foreign.Storable (Storable(..))
103import Prelude hiding (length, null, last, map, (!!), read, concat)
105import GHC.ForeignPtr (ForeignPtr(..))
106import GHC.Ptr (Ptr(..))
108import Streamly.Internal.Data.Fold.Types (Fold(..))
109import Streamly.Internal.Data.Unfold.Types (Unfold(..))
110import Streamly.Internal.Memory.Array.Types (Array(..), length)
111import Streamly.Streams.Serial (SerialT)
112import Streamly.Streams.StreamK.Type (IsStream)
114import qualified Streamly.Internal.Memory.Array.Types as A
115import qualified Streamly.Streams.Prelude as P
116import qualified Streamly.Streams.Serial as Serial
117import qualified Streamly.Streams.StreamD as D
118import qualified Streamly.Streams.StreamK as K
120-------------------------------------------------------------------------------
122-------------------------------------------------------------------------------
125-- | Create a new uninitialized array of given length.
128newArray :: (MonadIO m, Storable a) => Int -> m (Array a)
129newArray len = undefined
132-- | Create an 'Array' from the first N elements of a stream. The array is
133-- allocated to size N, if the stream terminates before N elements then the
134-- array may hold less than N elements.
137{-# INLINE fromStreamN #-}
138fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
140 if n < 0 then error "writeN: negative write count specified" else return ()
141 A.fromStreamDN n $ D.toStreamD m
143-- | Create an 'Array' from a stream. This is useful when we want to create a
144-- single array from a stream of unknown size. 'writeN' is at least twice
145-- as efficient when the size is already known.
147-- Note that if the input stream is too large memory allocation for the array
148-- may fail. When the stream size is not known, `arraysOf` followed by
149-- processing of indvidual arrays in the resulting stream should be preferred.
152{-# INLINE fromStream #-}
153fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
154fromStream = P.runFold A.write
155-- write m = A.fromStreamD $ D.toStreamD m
157-------------------------------------------------------------------------------
159-------------------------------------------------------------------------------
161-- | Convert an 'Array' into a stream.
164{-# INLINE_EARLY toStream #-}
165toStream :: (Monad m, K.IsStream t, Storable a) => Array a -> t m a
166toStream = D.fromStreamD . A.toStreamD
167-- XXX add fallback to StreamK rule
168-- {-# RULES "Streamly.Array.read fallback to StreamK" [1]
169-- forall a. S.readK (read a) = K.fromArray a #-}
171-- | Convert an 'Array' into a stream in reverse order.
174{-# INLINE_EARLY toStreamRev #-}
175toStreamRev :: (Monad m, IsStream t, Storable a) => Array a -> t m a
176toStreamRev = D.fromStreamD . A.toStreamDRev
177-- XXX add fallback to StreamK rule
178-- {-# RULES "Streamly.Array.readRev fallback to StreamK" [1]
179-- forall a. S.toStreamK (readRev a) = K.revFromArray a #-}
181data ReadUState a = ReadUState
182 {-# UNPACK #-} !(ForeignPtr a) -- foreign ptr with end of array pointer
183 {-# UNPACK #-} !(Ptr a) -- current pointer
185-- | Unfold an array into a stream.
188{-# INLINE_NORMAL read #-}
189read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
190read = Unfold step inject
193 inject (Array (ForeignPtr start contents) (Ptr end) _) =
194 return $ ReadUState (ForeignPtr end contents) (Ptr start)
196 {-# INLINE_LATE step #-}
197 step (ReadUState fp@(ForeignPtr end _) p) | p == (Ptr end) =
198 let x = A.unsafeInlineIO $ touchForeignPtr fp
199 in x `seq` return D.Stop
200 step (ReadUState fp p) = do
201 -- unsafeInlineIO allows us to run this in Identity monad for pure
202 -- toList/foldr case which makes them much faster due to not
203 -- accumulating the list and fusing better with the pure consumers.
205 -- This should be safe as the array contents are guaranteed to be
206 -- evaluated/written to before we peek at them.
207 let !x = A.unsafeInlineIO $ peek p
209 (ReadUState fp (p `plusPtr` (sizeOf (undefined :: a))))
211-- | > null arr = length arr == 0
215null :: Storable a => Array a -> Bool
216null arr = length arr == 0
218-- | > last arr = readIndex arr (length arr - 1)
222last :: Storable a => Array a -> Maybe a
223last arr = readIndex arr (length arr - 1)
225-------------------------------------------------------------------------------
227-------------------------------------------------------------------------------
229-------------------------------------------------------------------------------
231-------------------------------------------------------------------------------
234-- | Perform a binary search in the array to find an element.
235bsearch :: a -> Array a -> Maybe Bool
238-- | Perform a binary search in the array to find an element index.
239{-# INLINE elemIndex #-}
240bsearchIndex :: a -> Array a -> Maybe Int
241bsearchIndex elem arr = undefined
243-- find/findIndex etc can potentially be implemented more efficiently on arrays
244-- compared to streams by using SIMD instructions.
246find :: (a -> Bool) -> Array a -> Bool
249findIndex :: (a -> Bool) -> Array a -> Maybe Int
252findIndices :: (a -> Bool) -> Array a -> Array Int
253findIndices = undefined
256-------------------------------------------------------------------------------
258-------------------------------------------------------------------------------
260-- XXX We can potentially use SIMD instructions on arrays to fold faster.
262-------------------------------------------------------------------------------
264-------------------------------------------------------------------------------
267slice :: Int -> Int -> Array a
268slice begin end arr = undefined
270splitAt :: Int -> Array a -> (Array a, Array a)
271splitAt i arr = undefined
273-- XXX This operation can be performed efficiently via streams.
274-- | Append two arrays together to create a single array.
275splice :: Array a -> Array a -> Array a
276splice arr1 arr2 = undefined
278-------------------------------------------------------------------------------
279-- In-place mutation APIs
280-------------------------------------------------------------------------------
282-- | Partition an array into two halves using a partitioning predicate. The
283-- first half retains values where the predicate is 'False' and the second half
284-- retains values where the predicate is 'True'.
285{-# INLINE partitionBy #-}
286partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
287partitionBy f arr = undefined
289-- | Shuffle corresponding elements from two arrays using a shuffle function.
290-- If the shuffle function returns 'False' then do nothing otherwise swap the
291-- elements. This can be used in a bottom up fold to shuffle or reorder the
293shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
294shuffleBy f arr1 arr2 = undefined
296-- XXX we can also make the folds partial by stopping at a certain level.
298-- | Perform a top down hierarchical recursive partitioning fold of items in
299-- the container using the given function as the partition function.
301-- This will perform a quick sort if the partition function is
302-- 'partitionBy (< pivot)'.
305{-# INLINABLE foldtWith #-}
306foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
307foldtWith level f = undefined
309-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
310-- indicates the level in the tree where the fold would stop.
312-- This will perform a random shuffle if the shuffle function is random.
313-- If we stop at level 0 and repeatedly apply the function then we can do a
315foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
316foldbWith level f = undefined
319-- XXX consider the bulk update/accumulation/permutation APIs from vector.
321-------------------------------------------------------------------------------
322-- Random reads and writes
323-------------------------------------------------------------------------------
325-- | /O(1)/ Lookup the element at the given index, starting from 0.
328{-# INLINE readIndex #-}
329readIndex :: Storable a => Array a -> Int -> Maybe a
331 if i < 0 || i > length arr - 1
333 else A.unsafeInlineIO $
334 withForeignPtr (aStart arr) $ \p -> fmap Just $ peekElemOff p i
337-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
338-- at index @i@ and reading up to @count@ elements in the forward direction
339-- ending at the index @i + count - 1@.
342{-# INLINE readSlice #-}
343readSlice :: (IsStream t, Monad m, Storable a)
344 => Array a -> Int -> Int -> t m a
345readSlice arr i len = undefined
347-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
348-- index @i@ and reading up to @count@ elements in the reverse direction ending
349-- at the index @i - count + 1@.
352{-# INLINE readSliceRev #-}
353readSliceRev :: (IsStream t, Monad m, Storable a)
354 => Array a -> Int -> Int -> t m a
355readSliceRev arr i len = undefined
358-- | /O(1)/ Write the given element at the given index in the array.
359-- Performs in-place mutation of the array.
362{-# INLINE writeIndex #-}
363writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
364writeIndex arr i a = do
365 let maxIndex = length arr - 1
367 then error "writeIndex: negative array index"
369 then error $ "writeIndex: specified array index " ++ show i
370 ++ " is beyond the maximum index " ++ show maxIndex
372 liftIO $ withForeignPtr (aStart arr) $ \p ->
376-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
377-- starting at index @i@ and writing up to @count@ elements in the forward
378-- direction ending at the index @i + count - 1@.
381{-# INLINE writeSlice #-}
382writeSlice :: (IsStream t, Monad m, Storable a)
383 => Array a -> Int -> Int -> t m a -> m ()
384writeSlice arr i len s = undefined
386-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
387-- starting at index @i@ and writing up to @count@ elements in the reverse
388-- direction ending at the index @i - count + 1@.
391{-# INLINE writeSliceRev #-}
392writeSliceRev :: (IsStream t, Monad m, Storable a)
393 => Array a -> Int -> Int -> t m a -> m ()
394writeSliceRev arr i len s = undefined
397-------------------------------------------------------------------------------
398-- Transform via stream operations
399-------------------------------------------------------------------------------
401-- for non-length changing operations we can use the original length for
402-- allocation. If we can predict the length then we can use the prediction for
403-- new allocation. Otherwise we can use a hint and adjust dynamically.
406-- | Transform an array into another array using a pipe transformation
410{-# INLINE runPipe #-}
411runPipe :: (MonadIO m, Storable a, Storable b)
412 => Pipe m a b -> Array a -> m (Array b)
413runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
416-- | Transform an array into another array using a stream transformation
420{-# INLINE streamTransform #-}
421streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
422 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
423streamTransform f arr =
424 P.runFold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
427-- | Fold an array using a 'Fold'.
431fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
432fold f arr = P.runFold f $ (toStream arr :: Serial.SerialT m a)
434-- | Fold an array using a stream fold operation.
437{-# INLINE streamFold #-}
438streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
439streamFold 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