2-- Module : Streamly.Internal.Data.Array.Unboxed
3-- Copyright : (c) 2019 Composewell Technologies
6-- Maintainer : streamly@composewell.com
7-- Stability : experimental
12-- * Arrays are finite and fixed in size
13-- * provide /O(1)/ access to elements
14-- * store only data and not functions
15-- * provide efficient IO interfacing
17-- 'Foldable' instance is not provided because the implementation would be much
18-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
19-- instances should be used with care; concatenating arrays using binary
20-- operations can be highly inefficient. Instead, use
21-- 'Streamly.Internal.Data.Array.Unboxed.Stream.toArray' to concatenate N
24-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
25-- single byte) are only as good as holding those elements in a Haskell list.
26-- However, small arrays can be compacted into large ones to reduce the
27-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
28-- if we use one array for each chunk. This is still significant to add
31module Streamly.Internal.Data.Array.Unboxed
46 , A.writeN -- drop new
48 , A.write -- full buffer
56 , unsafeRead -- XXX readUnsafe?
58 , producer -- experimental
63 , A.unsafeIndex -- XXX Rename to getIndexUnsafe??
65 , last -- XXX getIndexLast?
67 , getIndicesFromThenTo
68 -- , getIndicesFrom -- read from a given position to the end of file
69 -- , getIndicesUpto -- read from beginning up to the given position
71 -- , getIndicesFromRev -- read from a given position to the beginning of file
72 -- , getIndicesUptoRev -- read from end to the given position in file
90 , A.unsafeFreeze -- asImmutableUnsafe?
91 , A.unsafeThaw -- asMutableUnsafe?
100 -- * Streaming Operations
110#include "ArrayMacros.h"
112import Control.Exception (assert)
113import Control.Monad (when)
114import Control.Monad.IO.Class (MonadIO(..))
115import Data.Functor.Identity (Identity)
116import Data.Word (Word8)
117import Foreign.C.String (CString)
118import Foreign.Ptr (castPtr)
119import Streamly.Internal.Data.Unboxed
125import Prelude hiding (length, null, last, map, (!!), read, concat)
127import Streamly.Internal.Data.Array.Unboxed.Mut.Type (ArrayUnsafe(..))
128import Streamly.Internal.Data.Array.Unboxed.Type
129 (Array(..), length, asPtrUnsafe)
130import Streamly.Internal.Data.Fold.Type (Fold(..))
131import Streamly.Internal.Data.Producer.Type (Producer(..))
132import Streamly.Internal.Data.Stream (Stream)
133import Streamly.Internal.Data.Tuple.Strict (Tuple3Fused'(..))
134import Streamly.Internal.Data.Unfold.Type (Unfold(..))
135import Streamly.Internal.System.IO (unsafeInlineIO)
137import qualified Streamly.Internal.Data.Array.Unboxed.Mut.Type as MA
138import qualified Streamly.Internal.Data.Array.Unboxed.Mut as MA
139import qualified Streamly.Internal.Data.Array.Unboxed.Type as A
140import qualified Streamly.Internal.Data.Fold as FL
141import qualified Streamly.Internal.Data.Producer.Type as Producer
142import qualified Streamly.Internal.Data.Producer as Producer
143import qualified Streamly.Internal.Data.Ring.Unboxed as RB
144import qualified Streamly.Internal.Data.Stream.Common as P
145import qualified Streamly.Internal.Data.Stream.StreamD as D
146import qualified Streamly.Internal.Data.Stream.Type as Stream
147import qualified Streamly.Internal.Data.Unfold as Unfold
149-------------------------------------------------------------------------------
151-------------------------------------------------------------------------------
153-- | Create an 'Array' from the first N elements of a stream. The array is
154-- allocated to size N, if the stream terminates before N elements then the
155-- array may hold less than N elements.
158{-# INLINE fromStreamN #-}
159fromStreamN :: (MonadIO m, Unboxed a) => Int -> Stream m a -> m (Array a)
161 when (n < 0) $ error "writeN: negative write count specified"
162 A.fromStreamDN n $ Stream.toStreamD m
164-- | Create an 'Array' from a stream. This is useful when we want to create a
165-- single array from a stream of unknown size. 'writeN' is at least twice
166-- as efficient when the size is already known.
168-- Note that if the input stream is too large memory allocation for the array
169-- may fail. When the stream size is not known, `arraysOf` followed by
170-- processing of indvidual arrays in the resulting stream should be preferred.
173{-# INLINE fromStream #-}
174fromStream :: (MonadIO m, Unboxed a) => Stream m a -> m (Array a)
175fromStream m = P.fold A.write $ Stream.toStreamK m
176-- write m = A.fromStreamD $ D.fromStreamK m
178-------------------------------------------------------------------------------
180-------------------------------------------------------------------------------
182{-# INLINE_NORMAL producer #-}
183producer :: forall m a. (Monad m, Unboxed a) => Producer m (Array a) a
185 Producer.translate A.unsafeThaw A.unsafeFreeze
186 $ MA.producerWith (return . unsafeInlineIO)
188-- | Unfold an array into a stream.
190-- /Since 0.7.0 (Streamly.Memory.Array)/
193{-# INLINE_NORMAL read #-}
194read :: forall m a. (Monad m, Unboxed a) => Unfold m (Array a) a
195read = Producer.simplify producer
197-- | Unfold an array into a stream, does not check the end of the array, the
198-- user is responsible for terminating the stream within the array bounds. For
199-- high performance application where the end condition can be determined by
200-- a terminating fold.
202-- Written in the hope that it may be faster than "read", however, in the case
203-- for which this was written, "read" proves to be faster even though the core
204-- generated with unsafeRead looks simpler.
208{-# INLINE_NORMAL unsafeRead #-}
209unsafeRead :: forall m a. (Monad m, Unboxed a) => Unfold m (Array a) a
210unsafeRead = Unfold step inject
213 inject (Array contents start end) =
214 return (ArrayUnsafe contents end start)
216 {-# INLINE_LATE step #-}
217 step (ArrayUnsafe contents end p) = do
218 -- unsafeInlineIO allows us to run this in Identity monad for pure
219 -- toList/foldr case which makes them much faster due to not
220 -- accumulating the list and fusing better with the pure consumers.
222 -- This should be safe as the array contents are guaranteed to be
223 -- evaluated/written to before we peek at them.
224 let !x = unsafeInlineIO $ peekWith contents p
225 let !p1 = INDEX_NEXT(p,a)
226 return $ D.Yield x (ArrayUnsafe contents end p1)
230-- >>> import qualified Streamly.Internal.Data.Array.Unboxed.Type as Array
231-- >>> null arr = Array.byteLength arr == 0
235null :: Array a -> Bool
236null arr = A.byteLength arr == 0
238-- | Like 'getIndex' but indexes the array in reverse from the end.
241{-# INLINE getIndexRev #-}
242getIndexRev :: forall a. Unboxed a => Int -> Array a -> Maybe a
246 let elemPtr = RINDEX_OF(arrEnd arr, i, a)
247 if i >= 0 && elemPtr >= arrStart arr
248 then Just <$> peekWith (arrContents arr) elemPtr
253-- >>> import qualified Streamly.Internal.Data.Array.Unboxed as Array
254-- >>> last arr = Array.getIndexRev arr 0
258last :: Unboxed a => Array a -> Maybe a
261-------------------------------------------------------------------------------
262-- Folds with Array as the container
263-------------------------------------------------------------------------------
265-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
266-- stream to an 'Array'.
269{-# INLINE writeLastN #-}
271 (Unboxed a, MonadIO m) => Int -> Fold m a (Array a)
273 | n <= 0 = fmap (const mempty) FL.drain
274 | otherwise = A.unsafeFreeze <$> Fold step initial done
278 step (Tuple3Fused' rb rh i) a = do
279 rh1 <- liftIO $ RB.unsafeInsert rb rh a
280 return $ FL.Partial $ Tuple3Fused' rb rh1 (i + 1)
283 let f (a, b) = FL.Partial $ Tuple3Fused' a b (0 :: Int)
284 in fmap f $ liftIO $ RB.new n
286 done (Tuple3Fused' rb rh i) = do
287 arr <- liftIO $ MA.newPinned n
288 foldFunc i rh snoc' arr rb
290 -- XXX We should write a read unfold for ring.
291 snoc' b a = liftIO $ MA.snocUnsafe b a
294 | i < n = RB.unsafeFoldRingM
295 | otherwise = RB.unsafeFoldRingFullM
297-------------------------------------------------------------------------------
299-------------------------------------------------------------------------------
301-------------------------------------------------------------------------------
303-------------------------------------------------------------------------------
305-- | Given a sorted array, perform a binary search to find the given element.
306-- Returns the index of the element if found.
309{-# INLINE binarySearch #-}
310binarySearch :: a -> Array a -> Maybe Int
311binarySearch = undefined
313-- find/findIndex etc can potentially be implemented more efficiently on arrays
314-- compared to streams by using SIMD instructions.
315-- We can also return a bit array instead.
317-- | Perform a linear search to find all the indices where a given element is
318-- present in an array.
321findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
322findIndicesOf = undefined
325findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
326findIndexOf p = Unfold.fold Fold.one . Stream.unfold (findIndicesOf p)
328find :: (a -> Bool) -> Array a -> Bool
329find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
332-------------------------------------------------------------------------------
334-------------------------------------------------------------------------------
336-- XXX We can potentially use SIMD instructions on arrays to fold faster.
338-------------------------------------------------------------------------------
340-------------------------------------------------------------------------------
342-- | /O(1)/ Slice an array in constant time.
344-- Caution: The bounds of the slice are not checked.
349{-# INLINE getSliceUnsafe #-}
352 => Int -- ^ starting index
353 -> Int -- ^ length of the slice
356getSliceUnsafe index len (Array contents start e) =
357 let size = SIZE_OF(a)
358 start1 = start + (index * size)
359 end1 = start1 + (len * size)
360 in assert (end1 <= e) (Array contents start1 end1)
362-- | Split the array into a stream of slices using a predicate. The element
363-- matching the predicate is dropped.
366{-# INLINE splitOn #-}
367splitOn :: (Monad m, Unboxed a) =>
368 (a -> Bool) -> Array a -> Stream m (Array a)
369splitOn predicate arr =
371 $ fmap (\(i, len) -> getSliceUnsafe i len arr)
372 $ D.sliceOnSuffix predicate (A.toStreamD arr)
374{-# INLINE genSlicesFromLen #-}
375genSlicesFromLen :: forall m a. (Monad m, Unboxed a)
376 => Int -- ^ from index
377 -> Int -- ^ length of the slice
378 -> Unfold m (Array a) (Int, Int)
379genSlicesFromLen from len =
380 Unfold.lmap A.unsafeThaw (MA.genSlicesFromLen from len)
382-- | Generate a stream of slices of specified length from an array, starting
383-- from the supplied array index. The last slice may be shorter than the
387{-# INLINE getSlicesFromLen #-}
388getSlicesFromLen :: forall m a. (Monad m, Unboxed a)
389 => Int -- ^ from index
390 -> Int -- ^ length of the slice
391 -> Unfold m (Array a) (Array a)
392getSlicesFromLen from len =
394 $ Unfold.lmap A.unsafeThaw (MA.getSlicesFromLen from len)
396-------------------------------------------------------------------------------
397-- Random reads and writes
398-------------------------------------------------------------------------------
400-- XXX Change this to a partial function instead of a Maybe type? And use
401-- MA.getIndex instead.
403-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
406{-# INLINE getIndex #-}
407getIndex :: forall a. Unboxed a => Int -> Array a -> Maybe a
411 let elemPtr = INDEX_OF(arrStart arr, i, a)
412 if i >= 0 && INDEX_VALID(elemPtr, arrEnd arr, a)
413 then Just <$> peekWith (arrContents arr) elemPtr
416-- | Given a stream of array indices, read the elements on those indices from
417-- the supplied Array. An exception is thrown if an index is out of bounds.
419-- This is the most general operation. We can implement other operations in
424-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
425-- in Unfold.lmap f (getIndices arr)
428-- let i = length arr - 1
429-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
433{-# INLINE getIndices #-}
434getIndices :: (Monad m, Unboxed a) => Stream m Int -> Unfold m (Array a) a
436 let unf = MA.getIndicesD (return . unsafeInlineIO) $ D.fromStreamK $ Stream.toStreamK m
437 in Unfold.lmap A.unsafeThaw unf
439-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
440-- element is the array value from the index @from@ and the successive elements
441-- are from the indices in increments of @then@ up to @to@. Index enumeration
442-- can occur downwards or upwards depending on whether @then@ comes before or
446-- getIndicesFromThenTo =
447-- let f (from, next, to, arr) =
448-- (Stream.enumerateFromThenTo from next to, arr)
449-- in Unfold.lmap f getIndices
453{-# INLINE getIndicesFromThenTo #-}
454getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
455getIndicesFromThenTo = undefined
457-------------------------------------------------------------------------------
458-- Transform via stream operations
459-------------------------------------------------------------------------------
461-- for non-length changing operations we can use the original length for
462-- allocation. If we can predict the length then we can use the prediction for
463-- new allocation. Otherwise we can use a hint and adjust dynamically.
466-- | Transform an array into another array using a pipe transformation
470{-# INLINE runPipe #-}
471runPipe :: (MonadIO m, Unboxed a, Unboxed b)
472 => Pipe m a b -> Array a -> m (Array b)
473runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
476-- XXX For transformations that cannot change the number of elements e.g. "map"
477-- we can use a predetermined array length.
479-- | Transform an array into another array using a stream transformation
483{-# INLINE streamTransform #-}
484streamTransform :: forall m a b. (MonadIO m, Unboxed a, Unboxed b)
485 => (Stream m a -> Stream m b) -> Array a -> m (Array b)
486streamTransform f arr =
487 P.fold (A.writeWith (length arr)) $ Stream.toStreamK $ f (A.toStream arr)
489-------------------------------------------------------------------------------
491-------------------------------------------------------------------------------
493-- | Cast an array having elements of type @a@ into an array having elements of
494-- type @b@. The array size must be a multiple of the size of type @b@
495-- otherwise accessing the last element of the array may result into a crash or
505castUnsafe (Array contents start end) =
506 Array (castContents contents) start end
508-- | Cast an @Array a@ into an @Array Word8@.
512asBytes :: Array a -> Array Word8
515-- | Cast an array having elements of type @a@ into an array having elements of
516-- type @b@. The length of the array should be a multiple of the size of the
517-- target element otherwise 'Nothing' is returned.
521cast :: forall a b. (Unboxed b) => Array a -> Maybe (Array b)
523 let len = A.byteLength arr
524 r = len `mod` SIZE_OF(b)
527 else Just $ castUnsafe arr
529-- | Convert an array of any type into a null terminated CString Ptr.
533-- /O(n) Time: (creates a copy of the array)/
537asCStringUnsafe :: Array a -> (CString -> IO b) -> IO b
538asCStringUnsafe arr act = do
539 -- XXX Ensure a pinned allocation here.
540 let arr1 = asBytes arr <> A.fromList [0]
541 asPtrUnsafe arr1 $ \ptr -> act (castPtr ptr)
543-------------------------------------------------------------------------------
545-------------------------------------------------------------------------------
547-- | Fold an array using a 'Fold'.
551fold :: forall m a b. (Monad m, Unboxed a) => Fold m a b -> Array a -> m b
552fold f arr = P.fold f (Stream.toStreamK (A.toStream arr))
554-- | Fold an array using a stream fold operation.
557{-# INLINE streamFold #-}
558streamFold :: (Monad m, Unboxed a) => (Stream m a -> m b) -> Array a -> m b
559streamFold f arr = f (A.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