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
33 , A.writeN -- drop new
35 , A.write -- full buffer
50 , producer -- experimental
55 , A.unsafeIndex -- XXX Rename to getIndexUnsafe??
57 , last -- XXX getIndexLast?
59 , getIndicesFromThenTo
60 -- , getIndicesFrom -- read from a given position to the end of file
61 -- , getIndicesUpto -- read from beginning up to the given position
63 -- , getIndicesFromRev -- read from a given position to the beginning of file
64 -- , getIndicesUptoRev -- read from end to the given position in file
82 , A.unsafeFreeze -- asImmutableUnsafe?
83 , A.unsafeThaw -- asMutableUnsafe?
92 -- * Streaming Operations
106#include "ArrayMacros.h"
108import Control.Exception (assert)
109import Control.Monad (when)
110import Control.Monad.IO.Class (MonadIO(..))
111import Data.Functor.Identity (Identity)
112import Data.Proxy (Proxy(..))
113import Data.Word (Word8)
114import Foreign.C.String (CString)
115import Foreign.Ptr (castPtr)
116import Foreign.Storable (Storable)
117import Streamly.Internal.Data.Unboxed
122import Prelude hiding (length, null, last, map, (!!), read, concat)
124import Streamly.Internal.Data.Array.Mut.Type (ArrayUnsafe(..))
125import Streamly.Internal.Data.Array.Type
126 (Array(..), length, asPtrUnsafe)
127import Streamly.Internal.Data.Fold.Type (Fold(..))
128import Streamly.Internal.Data.Producer.Type (Producer(..))
129import Streamly.Internal.Data.Stream.StreamD (Stream)
130import Streamly.Internal.Data.Tuple.Strict (Tuple3Fused'(..))
131import Streamly.Internal.Data.Unfold.Type (Unfold(..))
132import Streamly.Internal.System.IO (unsafeInlineIO)
134import qualified Streamly.Internal.Data.Array.Mut.Type as MA
135import qualified Streamly.Internal.Data.Array.Mut as MA
136import qualified Streamly.Internal.Data.Array.Type as A
137import qualified Streamly.Internal.Data.Fold as FL
138import qualified Streamly.Internal.Data.Producer.Type as Producer
139import qualified Streamly.Internal.Data.Producer as Producer
140import qualified Streamly.Internal.Data.Ring.Unboxed as RB
141import qualified Streamly.Internal.Data.Stream.StreamD as D
142import qualified Streamly.Internal.Data.Stream.StreamD as Stream
143import qualified Streamly.Internal.Data.Unfold as Unfold
145#include "DocTestDataArray.hs"
151-- * Arrays are finite and fixed in size
152-- * provide /O(1)/ access to elements
153-- * store only data and not functions
154-- * provide efficient IO interfacing
156-- 'Foldable' instance is not provided because the implementation would be much
157-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
158-- instances should be used with care; concatenating arrays using binary
159-- operations can be highly inefficient. Instead, use
160-- 'Streamly.Internal.Data.Stream.Chunked.toArray' to concatenate N
163-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
164-- single byte) are only as good as holding those elements in a Haskell list.
165-- However, small arrays can be compacted into large ones to reduce the
166-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
167-- if we use one array for each chunk. This is still significant to add
170-------------------------------------------------------------------------------
172-------------------------------------------------------------------------------
174-- | Create an 'Array' from the first N elements of a stream. The array is
175-- allocated to size N, if the stream terminates before N elements then the
176-- array may hold less than N elements.
179{-# INLINE fromStreamN #-}
180fromStreamN :: (MonadIO m, Unbox a) => Int -> Stream m a -> m (Array a)
182 when (n < 0) $ error "writeN: negative write count specified"
185-- | Create an 'Array' from a stream. This is useful when we want to create a
186-- single array from a stream of unknown size. 'writeN' is at least twice
187-- as efficient when the size is already known.
189-- Note that if the input stream is too large memory allocation for the array
190-- may fail. When the stream size is not known, `chunksOf` followed by
191-- processing of indvidual arrays in the resulting stream should be preferred.
194{-# INLINE fromStream #-}
195fromStream :: (MonadIO m, Unbox a) => Stream m a -> m (Array a)
196fromStream = Stream.fold A.write
197-- write m = A.fromStreamD $ D.fromStreamK m
199-------------------------------------------------------------------------------
201-------------------------------------------------------------------------------
203{-# INLINE_NORMAL producer #-}
204producer :: forall m a. (Monad m, Unbox a) => Producer m (Array a) a
206 Producer.translate A.unsafeThaw A.unsafeFreeze
207 $ MA.producerWith (return . unsafeInlineIO)
209-- | Unfold an array into a stream.
211{-# INLINE_NORMAL reader #-}
212reader :: forall m a. (Monad m, Unbox a) => Unfold m (Array a) a
213reader = Producer.simplify producer
215-- | Unfold an array into a stream, does not check the end of the array, the
216-- user is responsible for terminating the stream within the array bounds. For
217-- high performance application where the end condition can be determined by
218-- a terminating fold.
220-- Written in the hope that it may be faster than "read", however, in the case
221-- for which this was written, "read" proves to be faster even though the core
222-- generated with unsafeRead looks simpler.
226{-# INLINE_NORMAL readerUnsafe #-}
227readerUnsafe :: forall m a. (Monad m, Unbox a) => Unfold m (Array a) a
228readerUnsafe = Unfold step inject
231 inject (Array contents start end) =
232 return (ArrayUnsafe contents end start)
234 {-# INLINE_LATE step #-}
235 step (ArrayUnsafe contents end p) = do
236 -- unsafeInlineIO allows us to run this in Identity monad for pure
237 -- toList/foldr case which makes them much faster due to not
238 -- accumulating the list and fusing better with the pure consumers.
240 -- This should be safe as the array contents are guaranteed to be
241 -- evaluated/written to before we peek at them.
242 let !x = unsafeInlineIO $ peekWith contents p
243 let !p1 = INDEX_NEXT(p,a)
244 return $ D.Yield x (ArrayUnsafe contents end p1)
248-- >>> import qualified Streamly.Internal.Data.Array.Type as Array
249-- >>> null arr = Array.byteLength arr == 0
253null :: Array a -> Bool
254null arr = A.byteLength arr == 0
256-- | Like 'getIndex' but indexes the array in reverse from the end.
259{-# INLINE getIndexRev #-}
260getIndexRev :: forall a. Unbox a => Int -> Array a -> Maybe a
264 let elemPtr = RINDEX_OF(arrEnd arr, i, a)
265 if i >= 0 && elemPtr >= arrStart arr
266 then Just <$> peekWith (arrContents arr) elemPtr
271-- >>> import qualified Streamly.Internal.Data.Array as Array
272-- >>> last arr = Array.getIndexRev arr 0
276last :: Unbox a => Array a -> Maybe a
279-------------------------------------------------------------------------------
280-- Folds with Array as the container
281-------------------------------------------------------------------------------
283-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
284-- stream to an 'Array'.
286{-# INLINE writeLastN #-}
288 (Storable a, Unbox a, MonadIO m) => Int -> Fold m a (Array a)
290 | n <= 0 = fmap (const mempty) FL.drain
291 | otherwise = A.unsafeFreeze <$> Fold step initial done
295 step (Tuple3Fused' rb rh i) a = do
296 rh1 <- liftIO $ RB.unsafeInsert rb rh a
297 return $ FL.Partial $ Tuple3Fused' rb rh1 (i + 1)
300 let f (a, b) = FL.Partial $ Tuple3Fused' a b (0 :: Int)
301 in fmap f $ liftIO $ RB.new n
303 done (Tuple3Fused' rb rh i) = do
304 arr <- liftIO $ MA.newPinned n
305 foldFunc i rh snoc' arr rb
307 -- XXX We should write a read unfold for ring.
308 snoc' b a = liftIO $ MA.snocUnsafe b a
311 | i < n = RB.unsafeFoldRingM
312 | otherwise = RB.unsafeFoldRingFullM
314-------------------------------------------------------------------------------
316-------------------------------------------------------------------------------
318-------------------------------------------------------------------------------
320-------------------------------------------------------------------------------
322-- | Given a sorted array, perform a binary search to find the given element.
323-- Returns the index of the element if found.
326{-# INLINE binarySearch #-}
327binarySearch :: a -> Array a -> Maybe Int
328binarySearch = undefined
330-- find/findIndex etc can potentially be implemented more efficiently on arrays
331-- compared to streams by using SIMD instructions.
332-- We can also return a bit array instead.
334-- | Perform a linear search to find all the indices where a given element is
335-- present in an array.
338findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
339findIndicesOf = undefined
342findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
343findIndexOf p = Unfold.fold Fold.one . Stream.unfold (findIndicesOf p)
345find :: (a -> Bool) -> Array a -> Bool
346find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
349-------------------------------------------------------------------------------
351-------------------------------------------------------------------------------
353-- XXX We can potentially use SIMD instructions on arrays to fold faster.
355-------------------------------------------------------------------------------
357-------------------------------------------------------------------------------
359-- | /O(1)/ Slice an array in constant time.
361-- Caution: The bounds of the slice are not checked.
366{-# INLINE getSliceUnsafe #-}
369 => Int -- ^ starting index
370 -> Int -- ^ length of the slice
373getSliceUnsafe index len (Array contents start e) =
374 let size = SIZE_OF(a)
375 start1 = start + (index * size)
376 end1 = start1 + (len * size)
377 in assert (end1 <= e) (Array contents start1 end1)
379-- | Split the array into a stream of slices using a predicate. The element
380-- matching the predicate is dropped.
383{-# INLINE splitOn #-}
384splitOn :: (Monad m, Unbox a) =>
385 (a -> Bool) -> Array a -> Stream m (Array a)
386splitOn predicate arr =
387 fmap (\(i, len) -> getSliceUnsafe i len arr)
388 $ D.sliceOnSuffix predicate (A.toStreamD arr)
390{-# INLINE genSlicesFromLen #-}
391genSlicesFromLen :: forall m a. (Monad m, Unbox a)
392 => Int -- ^ from index
393 -> Int -- ^ length of the slice
394 -> Unfold m (Array a) (Int, Int)
395genSlicesFromLen from len =
396 Unfold.lmap A.unsafeThaw (MA.genSlicesFromLen from len)
398-- | Generate a stream of slices of specified length from an array, starting
399-- from the supplied array index. The last slice may be shorter than the
403{-# INLINE getSlicesFromLen #-}
404getSlicesFromLen :: forall m a. (Monad m, Unbox a)
405 => Int -- ^ from index
406 -> Int -- ^ length of the slice
407 -> Unfold m (Array a) (Array a)
408getSlicesFromLen from len =
410 $ Unfold.lmap A.unsafeThaw (MA.getSlicesFromLen from len)
412-------------------------------------------------------------------------------
413-- Random reads and writes
414-------------------------------------------------------------------------------
416-- XXX Change this to a partial function instead of a Maybe type? And use
417-- MA.getIndex instead.
419-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
421{-# INLINE getIndex #-}
422getIndex :: forall a. Unbox a => Int -> Array a -> Maybe a
426 let elemPtr = INDEX_OF(arrStart arr, i, a)
427 if i >= 0 && INDEX_VALID(elemPtr, arrEnd arr, a)
428 then Just <$> peekWith (arrContents arr) elemPtr
431-- | Given a stream of array indices, read the elements on those indices from
432-- the supplied Array. An exception is thrown if an index is out of bounds.
434-- This is the most general operation. We can implement other operations in
439-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
440-- in Unfold.lmap f (getIndices arr)
443-- let i = length arr - 1
444-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
448{-# INLINE getIndices #-}
449getIndices :: (Monad m, Unbox a) => Stream m Int -> Unfold m (Array a) a
451 let unf = MA.getIndicesD (return . unsafeInlineIO) m
452 in Unfold.lmap A.unsafeThaw unf
454-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
455-- element is the array value from the index @from@ and the successive elements
456-- are from the indices in increments of @then@ up to @to@. Index enumeration
457-- can occur downwards or upwards depending on whether @then@ comes before or
461-- getIndicesFromThenTo =
462-- let f (from, next, to, arr) =
463-- (Stream.enumerateFromThenTo from next to, arr)
464-- in Unfold.lmap f getIndices
468{-# INLINE getIndicesFromThenTo #-}
469getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
470getIndicesFromThenTo = undefined
472-------------------------------------------------------------------------------
473-- Transform via stream operations
474-------------------------------------------------------------------------------
476-- for non-length changing operations we can use the original length for
477-- allocation. If we can predict the length then we can use the prediction for
478-- new allocation. Otherwise we can use a hint and adjust dynamically.
481-- | Transform an array into another array using a pipe transformation
484{-# INLINE runPipe #-}
485runPipe :: (MonadIO m, Unbox a, Unbox b)
486 => Pipe m a b -> Array a -> m (Array b)
487runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
490-- XXX For transformations that cannot change the number of elements e.g. "map"
491-- we can use a predetermined array length.
493-- | Transform an array into another array using a stream transformation
497{-# INLINE streamTransform #-}
498streamTransform :: forall m a b. (MonadIO m, Unbox a, Unbox b)
499 => (Stream m a -> Stream m b) -> Array a -> m (Array b)
500streamTransform f arr =
501 Stream.fold (A.writeWith (length arr)) $ f (A.read arr)
503-------------------------------------------------------------------------------
505-------------------------------------------------------------------------------
507-- | Cast an array having elements of type @a@ into an array having elements of
508-- type @b@. The array size must be a multiple of the size of type @b@
509-- otherwise accessing the last element of the array may result into a crash or
519castUnsafe (Array contents start end) =
520 Array contents start end
522-- | Cast an @Array a@ into an @Array Word8@.
525asBytes :: Array a -> Array Word8
528-- | Cast an array having elements of type @a@ into an array having elements of
529-- type @b@. The length of the array should be a multiple of the size of the
530-- target element otherwise 'Nothing' is returned.
533cast :: forall a b. (Unbox b) => Array a -> Maybe (Array b)
535 let len = A.byteLength arr
536 r = len `mod` SIZE_OF(b)
539 else Just $ castUnsafe arr
541-- | Convert an array of any type into a null terminated CString Ptr.
545-- /O(n) Time: (creates a copy of the array)/
549asCStringUnsafe :: Array a -> (CString -> IO b) -> IO b
550asCStringUnsafe arr act = do
551 -- XXX Ensure a pinned allocation here.
552 let arr1 = asBytes arr <> A.fromList [0]
553 asPtrUnsafe arr1 $ \ptr -> act (castPtr ptr)
555-------------------------------------------------------------------------------
557-------------------------------------------------------------------------------
559-- XXX We can directly use toStreamD and D.fold here.
561-- | Fold an array using a 'Fold'.
565fold :: forall m a b. (Monad m, Unbox a) => Fold m a b -> Array a -> m b
566fold f arr = Stream.fold f (A.read arr)
568-- | Fold an array using a stream fold operation.
571{-# INLINE streamFold #-}
572streamFold :: (Monad m, Unbox a) => (Stream m a -> m b) -> Array a -> m b
573streamFold 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