3-- Module : Streamly.Internal.Data.Array
4-- Copyright : (c) 2019 Composewell Technologies
7-- Maintainer : streamly@composewell.com
8-- Stability : experimental
11module Streamly.Internal.Data.Array
20 module Streamly.Internal.Data.Array.Type
36 , producer -- experimental
42 , last -- XXX getIndexLast?
44 , getIndicesFromThenTo
45 -- , getIndicesFrom -- read from a given position to the end of file
46 -- , getIndicesUpto -- read from beginning up to the given position
48 -- , getIndicesFromRev -- read from a given position to the beginning of file
49 -- , getIndicesUptoRev -- read from end to the given position in file
73 -- * Streaming Operations
83#include "ArrayMacros.h"
85import Control.Exception (assert)
86import Control.Monad (when)
87import Control.Monad.IO.Class (MonadIO(..))
88import Data.Functor.Identity (Identity)
89import Data.Proxy (Proxy(..))
90import Data.Word (Word8)
91import Foreign.C.String (CString)
92import Foreign.Ptr (castPtr)
93import Foreign.Storable (Storable)
94import Streamly.Internal.Data.Unbox (Unbox(..))
95import Prelude hiding (length, null, last, map, (!!), read, concat)
97import Streamly.Internal.Data.Fold.Type (Fold(..))
98import Streamly.Internal.Data.Producer.Type (Producer(..))
99import Streamly.Internal.Data.Stream (Stream)
100import Streamly.Internal.Data.Tuple.Strict (Tuple3Fused'(..))
101import Streamly.Internal.Data.Unfold.Type (Unfold(..))
102import Streamly.Internal.System.IO (unsafeInlineIO)
104import qualified Streamly.Internal.Data.MutArray.Type as MA
105import qualified Streamly.Internal.Data.MutArray as MA
106import qualified Streamly.Internal.Data.Array.Type as A
107import qualified Streamly.Internal.Data.Fold as FL
108import qualified Streamly.Internal.Data.Producer.Type as Producer
109import qualified Streamly.Internal.Data.Producer as Producer
110import qualified Streamly.Internal.Data.Ring as RB
111import qualified Streamly.Internal.Data.Stream as D
112import qualified Streamly.Internal.Data.Stream as Stream
113import qualified Streamly.Internal.Data.Unfold as Unfold
115import Streamly.Internal.Data.Array.Type
117#include "DocTestDataArray.hs"
123-- * Arrays are finite and fixed in size
124-- * provide /O(1)/ access to elements
125-- * store only data and not functions
126-- * provide efficient IO interfacing
128-- 'Foldable' instance is not provided because the implementation would be much
129-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
130-- instances should be used with care; concatenating arrays using binary
131-- operations can be highly inefficient. Instead, use
132-- 'Streamly.Internal.Data.Stream.Chunked.toArray' to concatenate N
135-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
136-- single byte) are only as good as holding those elements in a Haskell list.
137-- However, small arrays can be compacted into large ones to reduce the
138-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
139-- if we use one array for each chunk. This is still significant to add
142-------------------------------------------------------------------------------
144-------------------------------------------------------------------------------
146-- | Create an 'Array' from the first N elements of a stream. The array is
147-- allocated to size N, if the stream terminates before N elements then the
148-- array may hold less than N elements.
151{-# INLINE fromStreamN #-}
152fromStreamN :: (MonadIO m, Unbox a) => Int -> Stream m a -> m (Array a)
154 when (n < 0) $ error "writeN: negative write count specified"
157-- | Create an 'Array' from a stream. This is useful when we want to create a
158-- single array from a stream of unknown size. 'writeN' is at least twice
159-- as efficient when the size is already known.
161-- Note that if the input stream is too large memory allocation for the array
162-- may fail. When the stream size is not known, `chunksOf` followed by
163-- processing of indvidual arrays in the resulting stream should be preferred.
166{-# INLINE fromStream #-}
167fromStream :: (MonadIO m, Unbox a) => Stream m a -> m (Array a)
168fromStream = Stream.fold A.write
169-- write m = A.fromStreamD $ D.fromStreamK m
171-------------------------------------------------------------------------------
173-------------------------------------------------------------------------------
175{-# INLINE_NORMAL producer #-}
176producer :: forall m a. (Monad m, Unbox a) => Producer m (Array a) a
178 Producer.translate A.unsafeThaw A.unsafeFreeze
179 $ MA.producerWith (return . unsafeInlineIO)
181-- | Unfold an array into a stream.
183{-# INLINE_NORMAL reader #-}
184reader :: forall m a. (Monad m, Unbox a) => Unfold m (Array a) a
185reader = Producer.simplify producer
187-- | Unfold an array into a stream, does not check the end of the array, the
188-- user is responsible for terminating the stream within the array bounds. For
189-- high performance application where the end condition can be determined by
190-- a terminating fold.
192-- Written in the hope that it may be faster than "read", however, in the case
193-- for which this was written, "read" proves to be faster even though the core
194-- generated with unsafeRead looks simpler.
198{-# INLINE_NORMAL readerUnsafe #-}
199readerUnsafe :: forall m a. (Monad m, Unbox a) => Unfold m (Array a) a
200readerUnsafe = Unfold step inject
203 inject (Array contents start end) =
204 return (ArrayUnsafe contents end start)
206 {-# INLINE_LATE step #-}
207 step (ArrayUnsafe contents end p) = do
208 -- unsafeInlineIO allows us to run this in Identity monad for pure
209 -- toList/foldr case which makes them much faster due to not
210 -- accumulating the list and fusing better with the pure consumers.
212 -- This should be safe as the array contents are guaranteed to be
213 -- evaluated/written to before we peek at them.
214 let !x = unsafeInlineIO $ peekByteIndex p contents
215 let !p1 = INDEX_NEXT(p,a)
216 return $ D.Yield x (ArrayUnsafe contents end p1)
220-- >>> null arr = Array.byteLength arr == 0
224null :: Array a -> Bool
225null arr = A.byteLength arr == 0
227-- | Like 'getIndex' but indexes the array in reverse from the end.
230{-# INLINE getIndexRev #-}
231getIndexRev :: forall a. Unbox a => Int -> Array a -> Maybe a
235 let elemPtr = RINDEX_OF(arrEnd arr, i, a)
236 if i >= 0 && elemPtr >= arrStart arr
237 then Just <$> peekByteIndex elemPtr (arrContents arr)
242-- >>> last arr = Array.getIndexRev arr 0
246last :: Unbox a => Array a -> Maybe a
249-------------------------------------------------------------------------------
250-- Folds with Array as the container
251-------------------------------------------------------------------------------
253-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
254-- stream to an 'Array'.
256{-# INLINE writeLastN #-}
258 (Storable a, Unbox a, MonadIO m) => Int -> Fold m a (Array a)
260 | n <= 0 = fmap (const mempty) FL.drain
261 | otherwise = A.unsafeFreeze <$> Fold step initial done done
265 step (Tuple3Fused' rb rh i) a = do
266 rh1 <- liftIO $ RB.unsafeInsert rb rh a
267 return $ FL.Partial $ Tuple3Fused' rb rh1 (i + 1)
270 let f (a, b) = FL.Partial $ Tuple3Fused' a b (0 :: Int)
271 in fmap f $ liftIO $ RB.new n
273 done (Tuple3Fused' rb rh i) = do
274 arr <- liftIO $ MA.new n
275 foldFunc i rh snoc' arr rb
277 -- XXX We should write a read unfold for ring.
278 snoc' b a = liftIO $ MA.snocUnsafe b a
281 | i < n = RB.unsafeFoldRingM
282 | otherwise = RB.unsafeFoldRingFullM
284-------------------------------------------------------------------------------
286-------------------------------------------------------------------------------
288-------------------------------------------------------------------------------
290-------------------------------------------------------------------------------
292-- | Given a sorted array, perform a binary search to find the given element.
293-- Returns the index of the element if found.
296{-# INLINE binarySearch #-}
297binarySearch :: a -> Array a -> Maybe Int
298binarySearch = undefined
300-- find/findIndex etc can potentially be implemented more efficiently on arrays
301-- compared to streams by using SIMD instructions.
302-- We can also return a bit array instead.
304-- | Perform a linear search to find all the indices where a given element is
305-- present in an array.
308findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
309findIndicesOf = undefined
312findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
313findIndexOf p = Unfold.fold Fold.one . Stream.unfold (findIndicesOf p)
315find :: (a -> Bool) -> Array a -> Bool
316find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
319-------------------------------------------------------------------------------
321-------------------------------------------------------------------------------
323-- XXX We can potentially use SIMD instructions on arrays to fold faster.
325-------------------------------------------------------------------------------
327-------------------------------------------------------------------------------
329-- | /O(1)/ Slice an array in constant time.
331-- Caution: The bounds of the slice are not checked.
336{-# INLINE getSliceUnsafe #-}
339 => Int -- ^ starting index
340 -> Int -- ^ length of the slice
343getSliceUnsafe index len (Array contents start e) =
344 let size = SIZE_OF(a)
345 start1 = start + (index * size)
346 end1 = start1 + (len * size)
347 in assert (end1 <= e) (Array contents start1 end1)
349-- | Split the array into a stream of slices using a predicate. The element
350-- matching the predicate is dropped.
353{-# INLINE splitOn #-}
354splitOn :: (Monad m, Unbox a) =>
355 (a -> Bool) -> Array a -> Stream m (Array a)
356splitOn predicate arr =
357 fmap (\(i, len) -> getSliceUnsafe i len arr)
358 $ D.sliceOnSuffix predicate (A.toStreamD arr)
360{-# INLINE genSlicesFromLen #-}
361genSlicesFromLen :: forall m a. (Monad m, Unbox a)
362 => Int -- ^ from index
363 -> Int -- ^ length of the slice
364 -> Unfold m (Array a) (Int, Int)
365genSlicesFromLen from len =
366 Unfold.lmap A.unsafeThaw (MA.genSlicesFromLen from len)
368-- | Generate a stream of slices of specified length from an array, starting
369-- from the supplied array index. The last slice may be shorter than the
373{-# INLINE getSlicesFromLen #-}
374getSlicesFromLen :: forall m a. (Monad m, Unbox a)
375 => Int -- ^ from index
376 -> Int -- ^ length of the slice
377 -> Unfold m (Array a) (Array a)
378getSlicesFromLen from len =
380 $ Unfold.lmap A.unsafeThaw (MA.getSlicesFromLen from len)
382-------------------------------------------------------------------------------
383-- Random reads and writes
384-------------------------------------------------------------------------------
386-- XXX Change this to a partial function instead of a Maybe type? And use
387-- MA.getIndex instead.
389-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
391{-# INLINE getIndex #-}
392getIndex :: forall a. Unbox a => Int -> Array a -> Maybe a
396 let elemPtr = INDEX_OF(arrStart arr, i, a)
397 if i >= 0 && INDEX_VALID(elemPtr, arrEnd arr, a)
398 then Just <$> peekByteIndex elemPtr (arrContents arr)
401-- | Given a stream of array indices, read the elements on those indices from
402-- the supplied Array. An exception is thrown if an index is out of bounds.
404-- This is the most general operation. We can implement other operations in
409-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
410-- in Unfold.lmap f (getIndices arr)
413-- let i = length arr - 1
414-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
418{-# INLINE getIndices #-}
419getIndices :: (Monad m, Unbox a) => Stream m Int -> Unfold m (Array a) a
421 let unf = MA.getIndicesD (return . unsafeInlineIO) m
422 in Unfold.lmap A.unsafeThaw unf
424-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
425-- element is the array value from the index @from@ and the successive elements
426-- are from the indices in increments of @then@ up to @to@. Index enumeration
427-- can occur downwards or upwards depending on whether @then@ comes before or
431-- getIndicesFromThenTo =
432-- let f (from, next, to, arr) =
433-- (Stream.enumerateFromThenTo from next to, arr)
434-- in Unfold.lmap f getIndices
438{-# INLINE getIndicesFromThenTo #-}
439getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
440getIndicesFromThenTo = undefined
442-------------------------------------------------------------------------------
443-- Transform via stream operations
444-------------------------------------------------------------------------------
446-- for non-length changing operations we can use the original length for
447-- allocation. If we can predict the length then we can use the prediction for
448-- new allocation. Otherwise we can use a hint and adjust dynamically.
451-- | Transform an array into another array using a pipe transformation
454{-# INLINE runPipe #-}
455runPipe :: (MonadIO m, Unbox a, Unbox b)
456 => Pipe m a b -> Array a -> m (Array b)
457runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
460-- XXX For transformations that cannot change the number of elements e.g. "map"
461-- we can use a predetermined array length.
463-- | Transform an array into another array using a stream transformation
467{-# INLINE streamTransform #-}
468streamTransform :: forall m a b. (MonadIO m, Unbox a, Unbox b)
469 => (Stream m a -> Stream m b) -> Array a -> m (Array b)
470streamTransform f arr =
471 Stream.fold (A.writeWith (length arr)) $ f (A.read arr)
473-------------------------------------------------------------------------------
475-------------------------------------------------------------------------------
477-- | Cast an array having elements of type @a@ into an array having elements of
478-- type @b@. The array size must be a multiple of the size of type @b@
479-- otherwise accessing the last element of the array may result into a crash or
489castUnsafe (Array contents start end) =
490 Array contents start end
492-- | Cast an @Array a@ into an @Array Word8@.
495asBytes :: Array a -> Array Word8
498-- | Cast an array having elements of type @a@ into an array having elements of
499-- type @b@. The length of the array should be a multiple of the size of the
500-- target element otherwise 'Nothing' is returned.
503cast :: forall a b. (Unbox b) => Array a -> Maybe (Array b)
505 let len = A.byteLength arr
506 r = len `mod` SIZE_OF(b)
509 else Just $ castUnsafe arr
511-- | Convert an array of any type into a null terminated CString Ptr. If the
512-- array is unpinned it is first converted to a pinned array which requires a
517-- /O(n) Time: (creates a copy of the array)/
521asCStringUnsafe :: Array a -> (CString -> IO b) -> IO b
522asCStringUnsafe arr act = do
523 let arr1 = asBytes arr <> A.fromList [0]
524 -- asPtrUnsafe makes sure the array is pinned
525 asPtrUnsafe arr1 $ \ptr -> act (castPtr ptr)
527-------------------------------------------------------------------------------
529-------------------------------------------------------------------------------
531-- XXX We can directly use toStreamD and D.fold here.
533-- | Fold an array using a 'Fold'.
537fold :: forall m a b. (Monad m, Unbox a) => Fold m a b -> Array a -> m b
538fold f arr = Stream.fold f (A.read arr)
540-- | Fold an array using a stream fold operation.
543{-# INLINE streamFold #-}
544streamFold :: (Monad m, Unbox a) => (Stream m a -> m b) -> Array a -> m b
545streamFold f arr = f (A.read 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