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.Stream.Foreign.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 Foreign.Storable as Storable
138import qualified Streamly.Internal.Data.Array.Unboxed.Mut.Type as MA
139import qualified Streamly.Internal.Data.Array.Unboxed.Mut as MA
140import qualified Streamly.Internal.Data.Array.Unboxed.Type as A
141import qualified Streamly.Internal.Data.Fold as FL
142import qualified Streamly.Internal.Data.Producer.Type as Producer
143import qualified Streamly.Internal.Data.Producer as Producer
144import qualified Streamly.Internal.Data.Ring.Foreign as RB
145import qualified Streamly.Internal.Data.Stream.Common as P
146import qualified Streamly.Internal.Data.Stream.StreamD as D
147import qualified Streamly.Internal.Data.Stream.Type as Stream
148import qualified Streamly.Internal.Data.Unfold as Unfold
150-------------------------------------------------------------------------------
152-------------------------------------------------------------------------------
154-- | Create an 'Array' from the first N elements of a stream. The array is
155-- allocated to size N, if the stream terminates before N elements then the
156-- array may hold less than N elements.
159{-# INLINE fromStreamN #-}
160fromStreamN :: (MonadIO m, Unboxed a) => Int -> Stream m a -> m (Array a)
162 when (n < 0) $ error "writeN: negative write count specified"
163 A.fromStreamDN n $ Stream.toStreamD m
165-- | Create an 'Array' from a stream. This is useful when we want to create a
166-- single array from a stream of unknown size. 'writeN' is at least twice
167-- as efficient when the size is already known.
169-- Note that if the input stream is too large memory allocation for the array
170-- may fail. When the stream size is not known, `arraysOf` followed by
171-- processing of indvidual arrays in the resulting stream should be preferred.
174{-# INLINE fromStream #-}
175fromStream :: (MonadIO m, Unboxed a) => Stream m a -> m (Array a)
176fromStream m = P.fold A.write $ Stream.toStreamK m
177-- write m = A.fromStreamD $ D.fromStreamK m
179-------------------------------------------------------------------------------
181-------------------------------------------------------------------------------
183{-# INLINE_NORMAL producer #-}
184producer :: forall m a. (Monad m, Unboxed a) => Producer m (Array a) a
186 Producer.translate A.unsafeThaw A.unsafeFreeze
187 $ MA.producerWith (return . unsafeInlineIO)
189-- | Unfold an array into a stream.
191-- /Since 0.7.0 (Streamly.Memory.Array)/
194{-# INLINE_NORMAL read #-}
195read :: forall m a. (Monad m, Unboxed a) => Unfold m (Array a) a
196read = Producer.simplify producer
198-- | Unfold an array into a stream, does not check the end of the array, the
199-- user is responsible for terminating the stream within the array bounds. For
200-- high performance application where the end condition can be determined by
201-- a terminating fold.
203-- Written in the hope that it may be faster than "read", however, in the case
204-- for which this was written, "read" proves to be faster even though the core
205-- generated with unsafeRead looks simpler.
209{-# INLINE_NORMAL unsafeRead #-}
210unsafeRead :: forall m a. (Monad m, Unboxed a) => Unfold m (Array a) a
211unsafeRead = Unfold step inject
214 inject (Array contents start end) =
215 return (ArrayUnsafe contents end start)
217 {-# INLINE_LATE step #-}
218 step (ArrayUnsafe contents end p) = do
219 -- unsafeInlineIO allows us to run this in Identity monad for pure
220 -- toList/foldr case which makes them much faster due to not
221 -- accumulating the list and fusing better with the pure consumers.
223 -- This should be safe as the array contents are guaranteed to be
224 -- evaluated/written to before we peek at them.
225 let !x = unsafeInlineIO $ peekWith contents p
226 let !p1 = INDEX_NEXT(p,a)
227 return $ D.Yield x (ArrayUnsafe contents end p1)
231-- >>> import qualified Streamly.Internal.Data.Array.Unboxed.Type as Array
232-- >>> null arr = Array.byteLength arr == 0
236null :: Array a -> Bool
237null arr = A.byteLength arr == 0
239-- | Like 'getIndex' but indexes the array in reverse from the end.
242{-# INLINE getIndexRev #-}
243getIndexRev :: forall a. Unboxed a => Int -> Array a -> Maybe a
247 let elemPtr = RINDEX_OF(arrEnd arr, i, a)
248 if i >= 0 && elemPtr >= arrStart arr
249 then Just <$> peekWith (arrContents arr) elemPtr
254-- >>> import qualified Streamly.Internal.Data.Array.Unboxed as Array
255-- >>> last arr = Array.getIndexRev arr 0
259last :: Unboxed a => Array a -> Maybe a
262-------------------------------------------------------------------------------
263-- Folds with Array as the container
264-------------------------------------------------------------------------------
266-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
267-- stream to an 'Array'.
270{-# INLINE writeLastN #-}
272 (Unboxed a, Storable.Storable a, MonadIO m) => Int -> Fold m a (Array a)
274 | n <= 0 = fmap (const mempty) FL.drain
275 | otherwise = A.unsafeFreeze <$> Fold step initial done
279 step (Tuple3Fused' rb rh i) a = do
280 rh1 <- liftIO $ RB.unsafeInsert rb rh a
281 return $ FL.Partial $ Tuple3Fused' rb rh1 (i + 1)
284 let f (a, b) = FL.Partial $ Tuple3Fused' a b (0 :: Int)
285 in fmap f $ liftIO $ RB.new n
287 done (Tuple3Fused' rb rh i) = do
288 arr <- liftIO $ MA.newArray n
289 foldFunc i rh snoc' arr rb
291 -- XXX We should write a read unfold for ring.
292 snoc' b a = liftIO $ MA.snocUnsafe b a
295 | i < n = RB.unsafeFoldRingM
296 | otherwise = RB.unsafeFoldRingFullM
298-------------------------------------------------------------------------------
300-------------------------------------------------------------------------------
302-------------------------------------------------------------------------------
304-------------------------------------------------------------------------------
306-- | Given a sorted array, perform a binary search to find the given element.
307-- Returns the index of the element if found.
310{-# INLINE binarySearch #-}
311binarySearch :: a -> Array a -> Maybe Int
312binarySearch = undefined
314-- find/findIndex etc can potentially be implemented more efficiently on arrays
315-- compared to streams by using SIMD instructions.
316-- We can also return a bit array instead.
318-- | Perform a linear search to find all the indices where a given element is
319-- present in an array.
322findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
323findIndicesOf = undefined
326findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
327findIndexOf p = Unfold.fold Fold.head . Stream.unfold (findIndicesOf p)
329find :: (a -> Bool) -> Array a -> Bool
330find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
333-------------------------------------------------------------------------------
335-------------------------------------------------------------------------------
337-- XXX We can potentially use SIMD instructions on arrays to fold faster.
339-------------------------------------------------------------------------------
341-------------------------------------------------------------------------------
343-- | /O(1)/ Slice an array in constant time.
345-- Caution: The bounds of the slice are not checked.
350{-# INLINE getSliceUnsafe #-}
353 => Int -- ^ starting index
354 -> Int -- ^ length of the slice
357getSliceUnsafe index len (Array contents start e) =
358 let size = SIZE_OF(a)
359 start1 = start + (index * size)
360 end1 = start1 + (len * size)
361 in assert (end1 <= e) (Array contents start1 end1)
363-- | Split the array into a stream of slices using a predicate. The element
364-- matching the predicate is dropped.
367{-# INLINE splitOn #-}
368splitOn :: (Monad m, Unboxed a) =>
369 (a -> Bool) -> Array a -> Stream m (Array a)
370splitOn predicate arr =
372 $ fmap (\(i, len) -> getSliceUnsafe i len arr)
373 $ D.sliceOnSuffix predicate (A.toStreamD arr)
375{-# INLINE genSlicesFromLen #-}
376genSlicesFromLen :: forall m a. (Monad m, Unboxed a)
377 => Int -- ^ from index
378 -> Int -- ^ length of the slice
379 -> Unfold m (Array a) (Int, Int)
380genSlicesFromLen from len =
381 Unfold.lmap A.unsafeThaw (MA.genSlicesFromLen from len)
383-- | Generate a stream of slices of specified length from an array, starting
384-- from the supplied array index. The last slice may be shorter than the
388{-# INLINE getSlicesFromLen #-}
389getSlicesFromLen :: forall m a. (Monad m, Unboxed a)
390 => Int -- ^ from index
391 -> Int -- ^ length of the slice
392 -> Unfold m (Array a) (Array a)
393getSlicesFromLen from len =
395 $ Unfold.lmap A.unsafeThaw (MA.getSlicesFromLen from len)
397-------------------------------------------------------------------------------
398-- Random reads and writes
399-------------------------------------------------------------------------------
401-- XXX Change this to a partial function instead of a Maybe type? And use
402-- MA.getIndex instead.
404-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
407{-# INLINE getIndex #-}
408getIndex :: forall a. Unboxed a => Int -> Array a -> Maybe a
412 let elemPtr = INDEX_OF(arrStart arr, i, a)
413 if i >= 0 && INDEX_VALID(elemPtr, arrEnd arr, a)
414 then Just <$> peekWith (arrContents arr) elemPtr
417-- | Given a stream of array indices, read the elements on those indices from
418-- the supplied Array. An exception is thrown if an index is out of bounds.
420-- This is the most general operation. We can implement other operations in
425-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
426-- in Unfold.lmap f (getIndices arr)
429-- let i = length arr - 1
430-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
434{-# INLINE getIndices #-}
435getIndices :: (Monad m, Unboxed a) => Stream m Int -> Unfold m (Array a) a
437 let unf = MA.getIndicesD (return . unsafeInlineIO) $ D.fromStreamK $ Stream.toStreamK m
438 in Unfold.lmap A.unsafeThaw unf
440-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
441-- element is the array value from the index @from@ and the successive elements
442-- are from the indices in increments of @then@ up to @to@. Index enumeration
443-- can occur downwards or upwards depending on whether @then@ comes before or
447-- getIndicesFromThenTo =
448-- let f (from, next, to, arr) =
449-- (Stream.enumerateFromThenTo from next to, arr)
450-- in Unfold.lmap f getIndices
454{-# INLINE getIndicesFromThenTo #-}
455getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
456getIndicesFromThenTo = undefined
458-------------------------------------------------------------------------------
459-- Transform via stream operations
460-------------------------------------------------------------------------------
462-- for non-length changing operations we can use the original length for
463-- allocation. If we can predict the length then we can use the prediction for
464-- new allocation. Otherwise we can use a hint and adjust dynamically.
467-- | Transform an array into another array using a pipe transformation
471{-# INLINE runPipe #-}
472runPipe :: (MonadIO m, Unboxed a, Unboxed b)
473 => Pipe m a b -> Array a -> m (Array b)
474runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
477-- XXX For transformations that cannot change the number of elements e.g. "map"
478-- we can use a predetermined array length.
480-- | Transform an array into another array using a stream transformation
484{-# INLINE streamTransform #-}
485streamTransform :: forall m a b. (MonadIO m, Unboxed a, Unboxed b)
486 => (Stream m a -> Stream m b) -> Array a -> m (Array b)
487streamTransform f arr =
488 P.fold (A.writeWith (length arr)) $ Stream.toStreamK $ f (A.toStream arr)
490-------------------------------------------------------------------------------
492-------------------------------------------------------------------------------
494-- | Cast an array having elements of type @a@ into an array having elements of
495-- type @b@. The array size must be a multiple of the size of type @b@
496-- otherwise accessing the last element of the array may result into a crash or
506castUnsafe (Array contents start end) =
507 Array (castContents contents) start end
509-- | Cast an @Array a@ into an @Array Word8@.
513asBytes :: Array a -> Array Word8
516-- | Cast an array having elements of type @a@ into an array having elements of
517-- type @b@. The length of the array should be a multiple of the size of the
518-- target element otherwise 'Nothing' is returned.
522cast :: forall a b. (Unboxed b) => Array a -> Maybe (Array b)
524 let len = A.byteLength arr
525 r = len `mod` SIZE_OF(b)
528 else Just $ castUnsafe arr
530-- | Convert an array of any type into a null terminated CString Ptr.
534-- /O(n) Time: (creates a copy of the array)/
538asCStringUnsafe :: Array a -> (CString -> IO b) -> IO b
539asCStringUnsafe arr act = do
540 -- XXX Ensure a pinned allocation here.
541 let arr1 = asBytes arr <> A.fromList [0]
542 asPtrUnsafe arr1 $ \ptr -> act (castPtr ptr)
544-------------------------------------------------------------------------------
546-------------------------------------------------------------------------------
548-- | Fold an array using a 'Fold'.
552fold :: forall m a b. (Monad m, Unboxed a) => Fold m a b -> Array a -> m b
553fold f arr = P.fold f (Stream.toStreamK (A.toStream arr))
555-- | Fold an array using a stream fold operation.
558{-# INLINE streamFold #-}
559streamFold :: (Monad m, Unboxed a) => (Stream m a -> m b) -> Array a -> m b
560streamFold 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