2-- Module : Streamly.Internal.Data.Array.Foreign
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.Foreign
37 -- Pure, From Static Memory (Unsafe)
38 -- We can use fromPtrM#, fromCStringM# and fromAddrM# to create arrays from
39 -- a dynamic memory address which requires a finalizer.
53 , A.writeN -- drop new
55 , A.write -- full buffer
63 , unsafeRead -- XXX readUnsafe?
65 , producer -- experimental
70 , A.unsafeIndex -- XXX Rename to getIndexUnsafe??
72 , last -- XXX getIndexLast?
74 , getIndicesFromThenTo
75 -- , getIndicesFrom -- read from a given position to the end of file
76 -- , getIndicesUpto -- read from beginning up to the given position
78 -- , getIndicesFromRev -- read from a given position to the beginning of file
79 -- , getIndicesUptoRev -- read from end to the given position in file
97 , A.unsafeFreeze -- asImmutableUnsafe?
98 , A.unsafeThaw -- asMutableUnsafe?
107 -- * Streaming Operations
117#include "ArrayMacros.h"
119import Control.Exception (assert)
120import Control.Monad (when)
121import Control.Monad.IO.Class (MonadIO(..))
122import Data.Functor.Identity (Identity)
123#if !(MIN_VERSION_base(4,11,0))
124import Data.Semigroup ((<>))
126import Data.Word (Word8)
127import Foreign.C.String (CString)
128import Foreign.Ptr (plusPtr, castPtr)
129import Foreign.Storable (Storable(..))
130import Prelude hiding (length, null, last, map, (!!), read, concat)
132import Streamly.Internal.Data.Array.Foreign.Mut.Type (ReadUState(..), touch)
133import Streamly.Internal.Data.Array.Foreign.Type
134 (Array(..), length, asPtrUnsafe)
135import Streamly.Internal.Data.Fold.Type (Fold(..))
136import Streamly.Internal.Data.Producer.Type (Producer(..))
137import Streamly.Internal.Data.Stream.Serial (SerialT(..))
138import Streamly.Internal.Data.Tuple.Strict (Tuple3Fused'(..))
139import Streamly.Internal.Data.Unfold.Type (Unfold(..))
140import Streamly.Internal.System.IO (unsafeInlineIO)
142import qualified Streamly.Internal.Data.Array.Foreign.Mut.Type as MA
143import qualified Streamly.Internal.Data.Array.Foreign.Mut as MA
144import qualified Streamly.Internal.Data.Array.Foreign.Type as A
145import qualified Streamly.Internal.Data.Fold as FL
146import qualified Streamly.Internal.Data.Producer as Producer
147import qualified Streamly.Internal.Data.Stream.Common as P
148import qualified Streamly.Internal.Data.Stream.StreamD as D
149import qualified Streamly.Internal.Data.Unfold as Unfold
150import qualified Streamly.Internal.Data.Ring.Foreign as RB
152-------------------------------------------------------------------------------
154-------------------------------------------------------------------------------
156-- | Create an 'Array' from the first N elements of a stream. The array is
157-- allocated to size N, if the stream terminates before N elements then the
158-- array may hold less than N elements.
161{-# INLINE fromStreamN #-}
162fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
163fromStreamN n (SerialT m) = do
164 when (n < 0) $ error "writeN: negative write count specified"
165 A.fromStreamDN n $ D.fromStreamK m
167-- | Create an 'Array' from a stream. This is useful when we want to create a
168-- single array from a stream of unknown size. 'writeN' is at least twice
169-- as efficient when the size is already known.
171-- Note that if the input stream is too large memory allocation for the array
172-- may fail. When the stream size is not known, `arraysOf` followed by
173-- processing of indvidual arrays in the resulting stream should be preferred.
176{-# INLINE fromStream #-}
177fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
178fromStream (SerialT m) = P.fold A.write m
179-- write m = A.fromStreamD $ D.fromStreamK m
181-------------------------------------------------------------------------------
183-------------------------------------------------------------------------------
185{-# INLINE_NORMAL producer #-}
186producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
187producer = Producer step inject extract
190 {-# INLINE inject #-}
191 inject (Array contents start end) = return $ ReadUState contents end start
193 {-# INLINE_LATE step #-}
194 step (ReadUState contents end cur)
195 | assert (cur <= end) (cur == end) =
196 let x = unsafeInlineIO $ touch contents
197 in x `seq` return D.Stop
198 step (ReadUState contents end cur) = do
199 -- unsafeInlineIO allows us to run this in Identity monad for pure
200 -- toList/foldr case which makes them much faster due to not
201 -- accumulating the list and fusing better with the pure consumers.
203 -- This should be safe as the array contents are guaranteed to be
204 -- evaluated/written to before we peek at them.
205 let !x = unsafeInlineIO $ peek cur
206 return $ D.Yield x (ReadUState contents end (PTR_NEXT(cur,a)))
208 extract (ReadUState contents end cur) = return $ Array contents cur end
210-- | Unfold an array into a stream.
212-- /Since 0.7.0 (Streamly.Memory.Array)/
215{-# INLINE_NORMAL read #-}
216read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
217read = Producer.simplify producer
219-- | Unfold an array into a stream, does not check the end of the array, the
220-- user is responsible for terminating the stream within the array bounds. For
221-- high performance application where the end condition can be determined by
222-- a terminating fold.
224-- Written in the hope that it may be faster than "read", however, in the case
225-- for which this was written, "read" proves to be faster even though the core
226-- generated with unsafeRead looks simpler.
230{-# INLINE_NORMAL unsafeRead #-}
231unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
232unsafeRead = Unfold step inject
235 inject (Array contents start end) =
236 return (ReadUState contents end start)
238 {-# INLINE_LATE step #-}
239 step (ReadUState contents end p) = do
240 -- unsafeInlineIO allows us to run this in Identity monad for pure
241 -- toList/foldr case which makes them much faster due to not
242 -- accumulating the list and fusing better with the pure consumers.
244 -- This should be safe as the array contents are guaranteed to be
245 -- evaluated/written to before we peek at them.
246 let !x = unsafeInlineIO $ do
250 let !p1 = PTR_NEXT(p,a)
251 return $ D.Yield x (ReadUState contents end p1)
255-- >>> import qualified Streamly.Internal.Data.Array.Foreign.Type as Array
256-- >>> null arr = Array.byteLength arr == 0
260null :: Array a -> Bool
261null arr = A.byteLength arr == 0
263-- | Like 'getIndex' but indexes the array in reverse from the end.
266{-# INLINE getIndexRev #-}
267getIndexRev :: forall a. Storable a => Int -> Array a -> Maybe a
272 let elemPtr = PTR_RINDEX(aEnd arr,i,a)
273 if i >= 0 && elemPtr >= ptr
274 then Just <$> peek elemPtr
279-- >>> import qualified Streamly.Internal.Data.Array.Foreign as Array
280-- >>> last arr = Array.getIndexRev arr 0
284last :: Storable a => Array a -> Maybe a
287-------------------------------------------------------------------------------
288-- Folds with Array as the container
289-------------------------------------------------------------------------------
291-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
292-- stream to an 'Array'.
295{-# INLINE writeLastN #-}
296writeLastN :: (Storable a, MonadIO m) => Int -> Fold m a (Array a)
298 | n <= 0 = fmap (const mempty) FL.drain
299 | otherwise = A.unsafeFreeze <$> Fold step initial done
303 step (Tuple3Fused' rb rh i) a = do
304 rh1 <- liftIO $ RB.unsafeInsert rb rh a
305 return $ FL.Partial $ Tuple3Fused' rb rh1 (i + 1)
308 let f (a, b) = FL.Partial $ Tuple3Fused' a b (0 :: Int)
309 in fmap f $ liftIO $ RB.new n
311 done (Tuple3Fused' rb rh i) = do
312 arr <- liftIO $ MA.newArray n
313 foldFunc i rh snoc' arr rb
315 -- XXX We should write a read unfold for ring.
316 snoc' b a = liftIO $ MA.snocUnsafe b a
319 | i < n = RB.unsafeFoldRingM
320 | otherwise = RB.unsafeFoldRingFullM
322-------------------------------------------------------------------------------
324-------------------------------------------------------------------------------
326-------------------------------------------------------------------------------
328-------------------------------------------------------------------------------
330-- | Given a sorted array, perform a binary search to find the given element.
331-- Returns the index of the element if found.
334{-# INLINE binarySearch #-}
335binarySearch :: a -> Array a -> Maybe Int
336binarySearch = undefined
338-- find/findIndex etc can potentially be implemented more efficiently on arrays
339-- compared to streams by using SIMD instructions.
340-- We can also return a bit array instead.
342-- | Perform a linear search to find all the indices where a given element is
343-- present in an array.
346findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
347findIndicesOf = undefined
350findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
351findIndexOf p = Unfold.fold Fold.head . Stream.unfold (findIndicesOf p)
353find :: (a -> Bool) -> Array a -> Bool
354find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
357-------------------------------------------------------------------------------
359-------------------------------------------------------------------------------
361-- XXX We can potentially use SIMD instructions on arrays to fold faster.
363-------------------------------------------------------------------------------
365-------------------------------------------------------------------------------
367-- | /O(1)/ Slice an array in constant time.
369-- Caution: The bounds of the slice are not checked.
374{-# INLINE getSliceUnsafe #-}
377 => Int -- ^ starting index
378 -> Int -- ^ length of the slice
381getSliceUnsafe index len (Array contents start e) =
382 let size = SIZE_OF(a)
383 fp1 = start `plusPtr` (index * size)
384 end = fp1 `plusPtr` (len * size)
385 in assert (end <= e) (Array contents fp1 end)
387-- | Split the array into a stream of slices using a predicate. The element
388-- matching the predicate is dropped.
391{-# INLINE splitOn #-}
392splitOn :: (Monad m, Storable a) =>
393 (a -> Bool) -> Array a -> SerialT m (Array a)
394splitOn predicate arr =
395 SerialT $ D.toStreamK
396 $ fmap (\(i, len) -> getSliceUnsafe i len arr)
397 $ D.sliceOnSuffix predicate (A.toStreamD arr)
399{-# INLINE genSlicesFromLen #-}
400genSlicesFromLen :: forall m a. (Monad m, Storable a)
401 => Int -- ^ from index
402 -> Int -- ^ length of the slice
403 -> Unfold m (Array a) (Int, Int)
404genSlicesFromLen from len =
405 Unfold.lmap A.unsafeThaw (MA.genSlicesFromLen from len)
407-- | Generate a stream of slices of specified length from an array, starting
408-- from the supplied array index. The last slice may be shorter than the
412{-# INLINE getSlicesFromLen #-}
413getSlicesFromLen :: forall m a. (Monad m, Storable a)
414 => Int -- ^ from index
415 -> Int -- ^ length of the slice
416 -> Unfold m (Array a) (Array a)
417getSlicesFromLen from len =
419 $ Unfold.lmap A.unsafeThaw (MA.getSlicesFromLen from len)
421-------------------------------------------------------------------------------
422-- Random reads and writes
423-------------------------------------------------------------------------------
425-- XXX Change this to a partial function instead of a Maybe type? And use
426-- MA.getIndex instead.
428-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
431{-# INLINE getIndex #-}
432getIndex :: forall a. Storable a => Int -> Array a -> Maybe a
437 let elemPtr = PTR_INDEX(ptr,i,a)
438 if i >= 0 && PTR_VALID(elemPtr,aEnd arr,a)
439 then Just <$> peek elemPtr
442-- | Given a stream of array indices, read the elements on those indices from
443-- the supplied Array. An exception is thrown if an index is out of bounds.
445-- This is the most general operation. We can implement other operations in
450-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
451-- in Unfold.lmap f (getIndices arr)
454-- let i = length arr - 1
455-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
459{-# INLINE getIndices #-}
460getIndices :: (Monad m, Storable a) => SerialT m Int -> Unfold m (Array a) a
461getIndices (SerialT stream) =
462 let unf = MA.getIndicesD (return . unsafeInlineIO) $ D.fromStreamK stream
463 in Unfold.lmap A.unsafeThaw unf
465-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
466-- element is the array value from the index @from@ and the successive elements
467-- are from the indices in increments of @then@ up to @to@. Index enumeration
468-- can occur downwards or upwards depending on whether @then@ comes before or
472-- getIndicesFromThenTo =
473-- let f (from, next, to, arr) =
474-- (Stream.enumerateFromThenTo from next to, arr)
475-- in Unfold.lmap f getIndices
479{-# INLINE getIndicesFromThenTo #-}
480getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
481getIndicesFromThenTo = undefined
483-------------------------------------------------------------------------------
484-- Transform via stream operations
485-------------------------------------------------------------------------------
487-- for non-length changing operations we can use the original length for
488-- allocation. If we can predict the length then we can use the prediction for
489-- new allocation. Otherwise we can use a hint and adjust dynamically.
492-- | Transform an array into another array using a pipe transformation
496{-# INLINE runPipe #-}
497runPipe :: (MonadIO m, Storable a, Storable b)
498 => Pipe m a b -> Array a -> m (Array b)
499runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
502-- XXX For transformations that cannot change the number of elements e.g. "map"
503-- we can use a predetermined array length.
505-- | Transform an array into another array using a stream transformation
509{-# INLINE streamTransform #-}
510streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
511 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
512streamTransform f arr =
513 P.fold (A.writeWith (length arr)) $ getSerialT $ f (A.toStream arr)
515-------------------------------------------------------------------------------
517-------------------------------------------------------------------------------
519-- | Cast an array having elements of type @a@ into an array having elements of
520-- type @b@. The array size must be a multiple of the size of type @b@
521-- otherwise accessing the last element of the array may result into a crash or
531castUnsafe (Array contents start end) =
532 Array contents (castPtr start) (castPtr end)
534-- | Cast an @Array a@ into an @Array Word8@.
538asBytes :: Array a -> Array Word8
541-- | Cast an array having elements of type @a@ into an array having elements of
542-- type @b@. The length of the array should be a multiple of the size of the
543-- target element otherwise 'Nothing' is returned.
547cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
549 let len = A.byteLength arr
550 r = len `mod` SIZE_OF(b)
553 else Just $ castUnsafe arr
555-- | Convert an array of any type into a null terminated CString Ptr.
559-- /O(n) Time: (creates a copy of the array)/
563asCStringUnsafe :: Array a -> (CString -> IO b) -> IO b
564asCStringUnsafe arr act = do
565 let arr1 = asBytes arr <> A.fromList [0]
566 asPtrUnsafe arr1 $ \ptr -> act (castPtr ptr)
568-------------------------------------------------------------------------------
570-------------------------------------------------------------------------------
572-- | Fold an array using a 'Fold'.
576fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
577fold f arr = P.fold f (getSerialT (A.toStream arr))
579-- | Fold an array using a stream fold operation.
582{-# INLINE streamFold #-}
583streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
584streamFold 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