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
63 , producer -- experimental
68 , A.unsafeIndex -- XXX Rename to getIndexUnsafe??
70 , last -- XXX getIndexLast?
72 , getIndicesFromThenTo
73 -- , getIndicesFrom -- read from a given position to the end of file
74 -- , getIndicesUpto -- read from beginning up to the given position
76 -- , getIndicesFromRev -- read from a given position to the beginning of file
77 -- , getIndicesUptoRev -- read from end to the given position in file
95 , A.unsafeFreeze -- asImmutableUnsafe?
96 , A.unsafeThaw -- asMutableUnsafe?
105 -- * Streaming Operations
119#include "ArrayMacros.h"
121import Control.Exception (assert)
122import Control.Monad (when)
123import Control.Monad.IO.Class (MonadIO(..))
124import Data.Functor.Identity (Identity)
125import Data.Word (Word8)
126import Foreign.C.String (CString)
127import Foreign.Ptr (castPtr)
128import Streamly.Internal.Data.Unboxed
134import Prelude hiding (length, null, last, map, (!!), read, concat)
136import Streamly.Internal.Data.Array.Unboxed.Mut.Type (ArrayUnsafe(..))
137import Streamly.Internal.Data.Array.Unboxed.Type
138 (Array(..), length, asPtrUnsafe)
139import Streamly.Internal.Data.Fold.Type (Fold(..))
140import Streamly.Internal.Data.Producer.Type (Producer(..))
141import Streamly.Internal.Data.Stream (Stream)
142import Streamly.Internal.Data.Tuple.Strict (Tuple3Fused'(..))
143import Streamly.Internal.Data.Unfold.Type (Unfold(..))
144import Streamly.Internal.System.IO (unsafeInlineIO)
146import qualified Streamly.Internal.Data.Array.Unboxed.Mut.Type as MA
147import qualified Streamly.Internal.Data.Array.Unboxed.Mut as MA
148import qualified Streamly.Internal.Data.Array.Unboxed.Type as A
149import qualified Streamly.Internal.Data.Fold as FL
150import qualified Streamly.Internal.Data.Producer.Type as Producer
151import qualified Streamly.Internal.Data.Producer as Producer
152import qualified Streamly.Internal.Data.Ring.Unboxed as RB
153import qualified Streamly.Internal.Data.Stream.Common as P
154import qualified Streamly.Internal.Data.Stream.StreamD as D
155import qualified Streamly.Internal.Data.Stream.Type as Stream
156import qualified Streamly.Internal.Data.Unfold as Unfold
158-------------------------------------------------------------------------------
160-------------------------------------------------------------------------------
162-- | Create an 'Array' from the first N elements of a stream. The array is
163-- allocated to size N, if the stream terminates before N elements then the
164-- array may hold less than N elements.
167{-# INLINE fromStreamN #-}
168fromStreamN :: (MonadIO m, Unboxed a) => Int -> Stream m a -> m (Array a)
170 when (n < 0) $ error "writeN: negative write count specified"
171 A.fromStreamDN n $ Stream.toStreamD m
173-- | Create an 'Array' from a stream. This is useful when we want to create a
174-- single array from a stream of unknown size. 'writeN' is at least twice
175-- as efficient when the size is already known.
177-- Note that if the input stream is too large memory allocation for the array
178-- may fail. When the stream size is not known, `arraysOf` followed by
179-- processing of indvidual arrays in the resulting stream should be preferred.
182{-# INLINE fromStream #-}
183fromStream :: (MonadIO m, Unboxed a) => Stream m a -> m (Array a)
184fromStream m = P.fold A.write $ Stream.toStreamK m
185-- write m = A.fromStreamD $ D.fromStreamK m
187-------------------------------------------------------------------------------
189-------------------------------------------------------------------------------
191{-# INLINE_NORMAL producer #-}
192producer :: forall m a. (Monad m, Unboxed a) => Producer m (Array a) a
194 Producer.translate A.unsafeThaw A.unsafeFreeze
195 $ MA.producerWith (return . unsafeInlineIO)
197-- | Unfold an array into a stream.
200{-# INLINE_NORMAL reader #-}
201reader :: forall m a. (Monad m, Unboxed a) => Unfold m (Array a) a
202reader = Producer.simplify producer
204-- | Unfold an array into a stream, does not check the end of the array, the
205-- user is responsible for terminating the stream within the array bounds. For
206-- high performance application where the end condition can be determined by
207-- a terminating fold.
209-- Written in the hope that it may be faster than "read", however, in the case
210-- for which this was written, "read" proves to be faster even though the core
211-- generated with unsafeRead looks simpler.
215{-# INLINE_NORMAL readerUnsafe #-}
216readerUnsafe :: forall m a. (Monad m, Unboxed a) => Unfold m (Array a) a
217readerUnsafe = Unfold step inject
220 inject (Array contents start end) =
221 return (ArrayUnsafe contents end start)
223 {-# INLINE_LATE step #-}
224 step (ArrayUnsafe contents end p) = do
225 -- unsafeInlineIO allows us to run this in Identity monad for pure
226 -- toList/foldr case which makes them much faster due to not
227 -- accumulating the list and fusing better with the pure consumers.
229 -- This should be safe as the array contents are guaranteed to be
230 -- evaluated/written to before we peek at them.
231 let !x = unsafeInlineIO $ peekWith contents p
232 let !p1 = INDEX_NEXT(p,a)
233 return $ D.Yield x (ArrayUnsafe contents end p1)
237-- >>> import qualified Streamly.Internal.Data.Array.Unboxed.Type as Array
238-- >>> null arr = Array.byteLength arr == 0
242null :: Array a -> Bool
243null arr = A.byteLength arr == 0
245-- | Like 'getIndex' but indexes the array in reverse from the end.
248{-# INLINE getIndexRev #-}
249getIndexRev :: forall a. Unboxed a => Int -> Array a -> Maybe a
253 let elemPtr = RINDEX_OF(arrEnd arr, i, a)
254 if i >= 0 && elemPtr >= arrStart arr
255 then Just <$> peekWith (arrContents arr) elemPtr
260-- >>> import qualified Streamly.Internal.Data.Array.Unboxed as Array
261-- >>> last arr = Array.getIndexRev arr 0
265last :: Unboxed a => Array a -> Maybe a
268-------------------------------------------------------------------------------
269-- Folds with Array as the container
270-------------------------------------------------------------------------------
272-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
273-- stream to an 'Array'.
276{-# INLINE writeLastN #-}
278 (Unboxed a, MonadIO m) => Int -> Fold m a (Array a)
280 | n <= 0 = fmap (const mempty) FL.drain
281 | otherwise = A.unsafeFreeze <$> Fold step initial done
285 step (Tuple3Fused' rb rh i) a = do
286 rh1 <- liftIO $ RB.unsafeInsert rb rh a
287 return $ FL.Partial $ Tuple3Fused' rb rh1 (i + 1)
290 let f (a, b) = FL.Partial $ Tuple3Fused' a b (0 :: Int)
291 in fmap f $ liftIO $ RB.new n
293 done (Tuple3Fused' rb rh i) = do
294 arr <- liftIO $ MA.newPinned n
295 foldFunc i rh snoc' arr rb
297 -- XXX We should write a read unfold for ring.
298 snoc' b a = liftIO $ MA.snocUnsafe b a
301 | i < n = RB.unsafeFoldRingM
302 | otherwise = RB.unsafeFoldRingFullM
304-------------------------------------------------------------------------------
306-------------------------------------------------------------------------------
308-------------------------------------------------------------------------------
310-------------------------------------------------------------------------------
312-- | Given a sorted array, perform a binary search to find the given element.
313-- Returns the index of the element if found.
316{-# INLINE binarySearch #-}
317binarySearch :: a -> Array a -> Maybe Int
318binarySearch = undefined
320-- find/findIndex etc can potentially be implemented more efficiently on arrays
321-- compared to streams by using SIMD instructions.
322-- We can also return a bit array instead.
324-- | Perform a linear search to find all the indices where a given element is
325-- present in an array.
328findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
329findIndicesOf = undefined
332findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
333findIndexOf p = Unfold.fold Fold.one . Stream.unfold (findIndicesOf p)
335find :: (a -> Bool) -> Array a -> Bool
336find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
339-------------------------------------------------------------------------------
341-------------------------------------------------------------------------------
343-- XXX We can potentially use SIMD instructions on arrays to fold faster.
345-------------------------------------------------------------------------------
347-------------------------------------------------------------------------------
349-- | /O(1)/ Slice an array in constant time.
351-- Caution: The bounds of the slice are not checked.
356{-# INLINE getSliceUnsafe #-}
359 => Int -- ^ starting index
360 -> Int -- ^ length of the slice
363getSliceUnsafe index len (Array contents start e) =
364 let size = SIZE_OF(a)
365 start1 = start + (index * size)
366 end1 = start1 + (len * size)
367 in assert (end1 <= e) (Array contents start1 end1)
369-- | Split the array into a stream of slices using a predicate. The element
370-- matching the predicate is dropped.
373{-# INLINE splitOn #-}
374splitOn :: (Monad m, Unboxed a) =>
375 (a -> Bool) -> Array a -> Stream m (Array a)
376splitOn predicate arr =
378 $ fmap (\(i, len) -> getSliceUnsafe i len arr)
379 $ D.sliceOnSuffix predicate (A.toStreamD arr)
381{-# INLINE genSlicesFromLen #-}
382genSlicesFromLen :: forall m a. (Monad m, Unboxed a)
383 => Int -- ^ from index
384 -> Int -- ^ length of the slice
385 -> Unfold m (Array a) (Int, Int)
386genSlicesFromLen from len =
387 Unfold.lmap A.unsafeThaw (MA.genSlicesFromLen from len)
389-- | Generate a stream of slices of specified length from an array, starting
390-- from the supplied array index. The last slice may be shorter than the
394{-# INLINE getSlicesFromLen #-}
395getSlicesFromLen :: forall m a. (Monad m, Unboxed a)
396 => Int -- ^ from index
397 -> Int -- ^ length of the slice
398 -> Unfold m (Array a) (Array a)
399getSlicesFromLen from len =
401 $ Unfold.lmap A.unsafeThaw (MA.getSlicesFromLen from len)
403-------------------------------------------------------------------------------
404-- Random reads and writes
405-------------------------------------------------------------------------------
407-- XXX Change this to a partial function instead of a Maybe type? And use
408-- MA.getIndex instead.
410-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
413{-# INLINE getIndex #-}
414getIndex :: forall a. Unboxed a => Int -> Array a -> Maybe a
418 let elemPtr = INDEX_OF(arrStart arr, i, a)
419 if i >= 0 && INDEX_VALID(elemPtr, arrEnd arr, a)
420 then Just <$> peekWith (arrContents arr) elemPtr
423-- | Given a stream of array indices, read the elements on those indices from
424-- the supplied Array. An exception is thrown if an index is out of bounds.
426-- This is the most general operation. We can implement other operations in
431-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
432-- in Unfold.lmap f (getIndices arr)
435-- let i = length arr - 1
436-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
440{-# INLINE getIndices #-}
441getIndices :: (Monad m, Unboxed a) => Stream m Int -> Unfold m (Array a) a
443 let unf = MA.getIndicesD (return . unsafeInlineIO) $ D.fromStreamK $ Stream.toStreamK m
444 in Unfold.lmap A.unsafeThaw unf
446-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
447-- element is the array value from the index @from@ and the successive elements
448-- are from the indices in increments of @then@ up to @to@. Index enumeration
449-- can occur downwards or upwards depending on whether @then@ comes before or
453-- getIndicesFromThenTo =
454-- let f (from, next, to, arr) =
455-- (Stream.enumerateFromThenTo from next to, arr)
456-- in Unfold.lmap f getIndices
460{-# INLINE getIndicesFromThenTo #-}
461getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
462getIndicesFromThenTo = undefined
464-------------------------------------------------------------------------------
465-- Transform via stream operations
466-------------------------------------------------------------------------------
468-- for non-length changing operations we can use the original length for
469-- allocation. If we can predict the length then we can use the prediction for
470-- new allocation. Otherwise we can use a hint and adjust dynamically.
473-- | Transform an array into another array using a pipe transformation
477{-# INLINE runPipe #-}
478runPipe :: (MonadIO m, Unboxed a, Unboxed b)
479 => Pipe m a b -> Array a -> m (Array b)
480runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
483-- XXX For transformations that cannot change the number of elements e.g. "map"
484-- we can use a predetermined array length.
486-- | Transform an array into another array using a stream transformation
490{-# INLINE streamTransform #-}
491streamTransform :: forall m a b. (MonadIO m, Unboxed a, Unboxed b)
492 => (Stream m a -> Stream m b) -> Array a -> m (Array b)
493streamTransform f arr =
494 P.fold (A.writeWith (length arr)) $ Stream.toStreamK $ f (A.read arr)
496-------------------------------------------------------------------------------
498-------------------------------------------------------------------------------
500-- | Cast an array having elements of type @a@ into an array having elements of
501-- type @b@. The array size must be a multiple of the size of type @b@
502-- otherwise accessing the last element of the array may result into a crash or
512castUnsafe (Array contents start end) =
513 Array (castContents contents) start end
515-- | Cast an @Array a@ into an @Array Word8@.
519asBytes :: Array a -> Array Word8
522-- | Cast an array having elements of type @a@ into an array having elements of
523-- type @b@. The length of the array should be a multiple of the size of the
524-- target element otherwise 'Nothing' is returned.
528cast :: forall a b. (Unboxed b) => Array a -> Maybe (Array b)
530 let len = A.byteLength arr
531 r = len `mod` SIZE_OF(b)
534 else Just $ castUnsafe arr
536-- | Convert an array of any type into a null terminated CString Ptr.
540-- /O(n) Time: (creates a copy of the array)/
544asCStringUnsafe :: Array a -> (CString -> IO b) -> IO b
545asCStringUnsafe arr act = do
546 -- XXX Ensure a pinned allocation here.
547 let arr1 = asBytes arr <> A.fromList [0]
548 asPtrUnsafe arr1 $ \ptr -> act (castPtr ptr)
550-------------------------------------------------------------------------------
552-------------------------------------------------------------------------------
554-- XXX We can directly use toStreamD and D.fold here.
556-- | Fold an array using a 'Fold'.
560fold :: forall m a b. (Monad m, Unboxed a) => Fold m a b -> Array a -> m b
561fold f arr = P.fold f (Stream.toStreamK (A.read arr))
563-- | Fold an array using a stream fold operation.
566{-# INLINE streamFold #-}
567streamFold :: (Monad m, Unboxed a) => (Stream m a -> m b) -> Array a -> m b
568streamFold 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