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
94 , unsafeCast -- castUnsafe?
95 , unsafeAsPtr -- asPtrUnsafe?
96 , unsafeAsCString -- asCStringUnsafe?
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 GHC.Ptr (Ptr(..))
134import Streamly.Internal.Data.Array.Foreign.Mut.Type (ReadUState(..), touch)
135import Streamly.Internal.Data.Array.Foreign.Type
136 (Array(..), length, unsafeWithArray)
137import Streamly.Internal.Data.Fold.Type (Fold(..))
138import Streamly.Internal.Data.Producer.Type (Producer(..))
139import Streamly.Internal.Data.Stream.Serial (SerialT(..))
140import Streamly.Internal.Data.Tuple.Strict (Tuple3Fused'(..))
141import Streamly.Internal.Data.Unfold.Type (Unfold(..))
142import Streamly.Internal.System.IO (unsafeInlineIO)
144import qualified Streamly.Internal.Data.Array.Foreign.Mut.Type as MA
145import qualified Streamly.Internal.Data.Array.Foreign.Mut as MA
146import qualified Streamly.Internal.Data.Array.Foreign.Type as A
147import qualified Streamly.Internal.Data.Fold as FL
148import qualified Streamly.Internal.Data.Producer as Producer
149import qualified Streamly.Internal.Data.Stream.IsStream.Type as IsStream
150import qualified Streamly.Internal.Data.Stream.Prelude as P
151import qualified Streamly.Internal.Data.Stream.StreamD as D
152import qualified Streamly.Internal.Data.Unfold as Unfold
153import qualified Streamly.Internal.Data.Ring.Foreign as RB
155-------------------------------------------------------------------------------
157-------------------------------------------------------------------------------
159-- | Create an 'Array' from the first N elements of a stream. The array is
160-- allocated to size N, if the stream terminates before N elements then the
161-- array may hold less than N elements.
164{-# INLINE fromStreamN #-}
165fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
166fromStreamN n (SerialT m) = do
167 when (n < 0) $ error "writeN: negative write count specified"
168 A.fromStreamDN n $ D.fromStreamK m
170-- | Create an 'Array' from a stream. This is useful when we want to create a
171-- single array from a stream of unknown size. 'writeN' is at least twice
172-- as efficient when the size is already known.
174-- Note that if the input stream is too large memory allocation for the array
175-- may fail. When the stream size is not known, `arraysOf` followed by
176-- processing of indvidual arrays in the resulting stream should be preferred.
179{-# INLINE fromStream #-}
180fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
181fromStream (SerialT m) = P.fold A.write m
182-- write m = A.fromStreamD $ D.fromStreamK m
184-------------------------------------------------------------------------------
186-------------------------------------------------------------------------------
188{-# INLINE_NORMAL producer #-}
189producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
190producer = Producer step inject extract
193 {-# INLINE inject #-}
194 inject (Array contents start end) = return $ ReadUState contents end start
196 {-# INLINE_LATE step #-}
197 step (ReadUState contents end cur)
198 | assert (cur <= end) (cur == end) =
199 let x = unsafeInlineIO $ touch contents
200 in x `seq` return D.Stop
201 step (ReadUState contents end cur) = do
202 -- unsafeInlineIO allows us to run this in Identity monad for pure
203 -- toList/foldr case which makes them much faster due to not
204 -- accumulating the list and fusing better with the pure consumers.
206 -- This should be safe as the array contents are guaranteed to be
207 -- evaluated/written to before we peek at them.
208 let !x = unsafeInlineIO $ peek cur
209 return $ D.Yield x (ReadUState contents end (PTR_NEXT(cur,a)))
211 extract (ReadUState contents end cur) = return $ Array contents cur end
213-- | Unfold an array into a stream.
215-- /Since 0.7.0 (Streamly.Memory.Array)/
218{-# INLINE_NORMAL read #-}
219read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
220read = Producer.simplify producer
222-- | Unfold an array into a stream, does not check the end of the array, the
223-- user is responsible for terminating the stream within the array bounds. For
224-- high performance application where the end condition can be determined by
225-- a terminating fold.
227-- Written in the hope that it may be faster than "read", however, in the case
228-- for which this was written, "read" proves to be faster even though the core
229-- generated with unsafeRead looks simpler.
233{-# INLINE_NORMAL unsafeRead #-}
234unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
235unsafeRead = Unfold step inject
238 inject (Array contents start end) =
239 return (ReadUState contents end start)
241 {-# INLINE_LATE step #-}
242 step (ReadUState contents end p) = do
243 -- unsafeInlineIO allows us to run this in Identity monad for pure
244 -- toList/foldr case which makes them much faster due to not
245 -- accumulating the list and fusing better with the pure consumers.
247 -- This should be safe as the array contents are guaranteed to be
248 -- evaluated/written to before we peek at them.
249 let !x = unsafeInlineIO $ do
253 let !p1 = PTR_NEXT(p,a)
254 return $ D.Yield x (ReadUState contents end p1)
258-- >>> import qualified Streamly.Internal.Data.Array.Foreign.Type as Array
259-- >>> null arr = Array.byteLength arr == 0
263null :: Array a -> Bool
264null arr = A.byteLength arr == 0
266-- | Like 'getIndex' but indexes the array in reverse from the end.
269{-# INLINE getIndexRev #-}
270getIndexRev :: forall a. Storable a => Int -> Array a -> Maybe a
273 $ unsafeWithArray arr
275 let elemPtr = PTR_RINDEX(aEnd arr,i,a)
276 if i >= 0 && elemPtr >= ptr
277 then Just <$> peek elemPtr
282-- >>> import qualified Streamly.Internal.Data.Array.Foreign as Array
283-- >>> last arr = Array.getIndexRev arr 0
287last :: Storable a => Array a -> Maybe a
290-------------------------------------------------------------------------------
291-- Folds with Array as the container
292-------------------------------------------------------------------------------
294-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
295-- stream to an 'Array'.
298{-# INLINE writeLastN #-}
299writeLastN :: (Storable a, MonadIO m) => Int -> Fold m a (Array a)
301 | n <= 0 = fmap (const mempty) FL.drain
302 | otherwise = A.unsafeFreeze <$> Fold step initial done
306 step (Tuple3Fused' rb rh i) a = do
307 rh1 <- liftIO $ RB.unsafeInsert rb rh a
308 return $ FL.Partial $ Tuple3Fused' rb rh1 (i + 1)
311 let f (a, b) = FL.Partial $ Tuple3Fused' a b (0 :: Int)
312 in fmap f $ liftIO $ RB.new n
314 done (Tuple3Fused' rb rh i) = do
315 arr <- liftIO $ MA.newArray n
316 foldFunc i rh snoc' arr rb
318 -- XXX We should write a read unfold for ring.
319 snoc' b a = liftIO $ MA.snocUnsafe b a
322 | i < n = RB.unsafeFoldRingM
323 | otherwise = RB.unsafeFoldRingFullM
325-------------------------------------------------------------------------------
327-------------------------------------------------------------------------------
329-------------------------------------------------------------------------------
331-------------------------------------------------------------------------------
333-- | Given a sorted array, perform a binary search to find the given element.
334-- Returns the index of the element if found.
337{-# INLINE binarySearch #-}
338binarySearch :: a -> Array a -> Maybe Int
339binarySearch = undefined
341-- find/findIndex etc can potentially be implemented more efficiently on arrays
342-- compared to streams by using SIMD instructions.
343-- We can also return a bit array instead.
345-- | Perform a linear search to find all the indices where a given element is
346-- present in an array.
349findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
350findIndicesOf = undefined
353findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
354findIndexOf p = Unfold.fold Fold.head . Stream.unfold (findIndicesOf p)
356find :: (a -> Bool) -> Array a -> Bool
357find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
360-------------------------------------------------------------------------------
362-------------------------------------------------------------------------------
364-- XXX We can potentially use SIMD instructions on arrays to fold faster.
366-------------------------------------------------------------------------------
368-------------------------------------------------------------------------------
370-- | /O(1)/ Slice an array in constant time.
372-- Caution: The bounds of the slice are not checked.
377{-# INLINE getSliceUnsafe #-}
380 => Int -- ^ starting index
381 -> Int -- ^ length of the slice
384getSliceUnsafe index len (Array contents start e) =
385 let size = SIZE_OF(a)
386 fp1 = start `plusPtr` (index * size)
387 end = fp1 `plusPtr` (len * size)
388 in assert (end <= e) (Array contents fp1 end)
390-- | Split the array into a stream of slices using a predicate. The element
391-- matching the predicate is dropped.
394{-# INLINE splitOn #-}
395splitOn :: (Monad m, Storable a) =>
396 (a -> Bool) -> Array a -> SerialT m (Array a)
397splitOn predicate arr =
399 $ fmap (\(i, len) -> getSliceUnsafe i len arr)
400 $ D.sliceOnSuffix predicate (A.toStreamD arr)
402{-# INLINE genSlicesFromLen #-}
403genSlicesFromLen :: forall m a. (Monad m, Storable a)
404 => Int -- ^ from index
405 -> Int -- ^ length of the slice
406 -> Unfold m (Array a) (Int, Int)
407genSlicesFromLen from len =
408 Unfold.lmap A.unsafeThaw (MA.genSlicesFromLen from len)
410-- | Generate a stream of slices of specified length from an array, starting
411-- from the supplied array index. The last slice may be shorter than the
415{-# INLINE getSlicesFromLen #-}
416getSlicesFromLen :: forall m a. (Monad m, Storable a)
417 => Int -- ^ from index
418 -> Int -- ^ length of the slice
419 -> Unfold m (Array a) (Array a)
420getSlicesFromLen from len =
422 $ Unfold.lmap A.unsafeThaw (MA.getSlicesFromLen from len)
424-------------------------------------------------------------------------------
425-- Random reads and writes
426-------------------------------------------------------------------------------
428-- XXX Change this to a partial function instead of a Maybe type? And use
429-- MA.getIndex instead.
431-- XXX The signature should be "Int -> Array a -> Maybe a"
432-- XXX This is a released API so make this change in the next major release.
433-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
436{-# INLINE getIndex #-}
437getIndex :: forall a. Storable a => Array a -> Int -> Maybe a
440 $ unsafeWithArray arr
442 let elemPtr = PTR_INDEX(ptr,i,a)
443 if i >= 0 && PTR_VALID(elemPtr,aEnd arr,a)
444 then Just <$> peek elemPtr
447-- | Given a stream of array indices, read the elements on those indices from
448-- the supplied Array. An exception is thrown if an index is out of bounds.
450-- This is the most general operation. We can implement other operations in
455-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
456-- in Unfold.lmap f (getIndices arr)
459-- let i = length arr - 1
460-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
464{-# INLINE getIndices #-}
465getIndices :: Unfold m (Array a) Int -> Unfold m (Array a) a
466getIndices = undefined
468-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
469-- element is the array value from the index @from@ and the successive elements
470-- are from the indices in increments of @then@ up to @to@. Index enumeration
471-- can occur downwards or upwards depending on whether @then@ comes before or
475-- getIndicesFromThenTo =
476-- let f (from, next, to, arr) =
477-- (Stream.enumerateFromThenTo from next to, arr)
478-- in Unfold.lmap f getIndices
482{-# INLINE getIndicesFromThenTo #-}
483getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
484getIndicesFromThenTo = undefined
486-------------------------------------------------------------------------------
487-- Transform via stream operations
488-------------------------------------------------------------------------------
490-- for non-length changing operations we can use the original length for
491-- allocation. If we can predict the length then we can use the prediction for
492-- new allocation. Otherwise we can use a hint and adjust dynamically.
495-- | Transform an array into another array using a pipe transformation
499{-# INLINE runPipe #-}
500runPipe :: (MonadIO m, Storable a, Storable b)
501 => Pipe m a b -> Array a -> m (Array b)
502runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
505-- XXX For transformations that cannot change the number of elements e.g. "map"
506-- we can use a predetermined array length.
508-- | Transform an array into another array using a stream transformation
512{-# INLINE streamTransform #-}
513streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
514 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
515streamTransform f arr =
516 P.fold (A.writeWith (length arr)) $ getSerialT $ f (A.toStream arr)
518-------------------------------------------------------------------------------
520-------------------------------------------------------------------------------
522-- | Cast an array having elements of type @a@ into an array having elements of
523-- type @b@. The array size must be a multiple of the size of type @b@
524-- otherwise accessing the last element of the array may result into a crash or
534unsafeCast (Array contents start end) =
535 Array contents (castPtr start) (castPtr end)
537-- | Cast an @Array a@ into an @Array Word8@.
541asBytes :: Array a -> Array Word8
544-- | Cast an array having elements of type @a@ into an array having elements of
545-- type @b@. The length of the array should be a multiple of the size of the
546-- target element otherwise 'Nothing' is returned.
550cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
552 let len = A.byteLength arr
553 r = len `mod` SIZE_OF(b)
556 else Just $ unsafeCast arr
558-- | Use an @Array a@ as @Ptr b@.
564unsafeAsPtr :: Array a -> (Ptr b -> IO c) -> IO c
565unsafeAsPtr arr act = do
566 unsafeWithArray arr $ \ptr -> act (castPtr ptr)
568-- | Convert an array of any type into a null terminated CString Ptr.
572-- /O(n) Time: (creates a copy of the array)/
576unsafeAsCString :: Array a -> (CString -> IO b) -> IO b
577unsafeAsCString arr act = do
578 let arr1 = asBytes arr <> A.fromList [0]
579 unsafeWithArray arr1 $ \ptr -> act (castPtr ptr)
581-------------------------------------------------------------------------------
583-------------------------------------------------------------------------------
585-- | Fold an array using a 'Fold'.
589fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
590fold f arr = P.fold f (getSerialT (A.toStream arr))
592-- | Fold an array using a stream fold operation.
595{-# INLINE streamFold #-}
596streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
597streamFold 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