4-- Module : Streamly.Internal.Data.Array.Foreign
5-- Copyright : (c) 2019 Composewell Technologies
8-- Maintainer : streamly@composewell.com
9-- Stability : experimental
14-- * Arrays are finite and fixed in size
15-- * provide /O(1)/ access to elements
16-- * store only data and not functions
17-- * provide efficient IO interfacing
19-- 'Foldable' instance is not provided because the implementation would be much
20-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
21-- instances should be used with care; concatenating arrays using binary
22-- operations can be highly inefficient. Instead, use
23-- 'Streamly.Internal.Data.Array.Stream.Foreign.toArray' to concatenate N
26-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
27-- single byte) are only as good as holding those elements in a Haskell list.
28-- However, small arrays can be compacted into large ones to reduce the
29-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
30-- if we use one array for each chunk. This is still significant to add
33module Streamly.Internal.Data.Array.Foreign
39 -- Pure, From Static Memory (Unsafe)
40 -- We can use fromPtrM#, fromCStringM# and fromAddrM# to create arrays from
41 -- a dynamic memory address which requires a finalizer.
55 , A.writeN -- drop new
57 , A.write -- full buffer
65 , unsafeRead -- XXX readUnsafe?
67 , producer -- experimental
72 , A.unsafeIndex -- XXX Rename to getIndexUnsafe??
74 , last -- XXX getIndexLast?
76 , getIndicesFromThenTo
77 -- , getIndicesFrom -- read from a given position to the end of file
78 -- , getIndicesUpto -- read from beginning up to the given position
80 -- , getIndicesFromRev -- read from a given position to the beginning of file
81 -- , getIndicesUptoRev -- read from end to the given position in file
96 , unsafeCast -- castUnsafe?
97 , unsafeAsPtr -- asPtrUnsafe?
98 , unsafeAsCString -- asCStringUnsafe?
99 , A.unsafeFreeze -- asImmutableUnsafe?
100 , A.unsafeThaw -- asMutableUnsafe?
109 -- * Streaming Operations
118import Control.Exception (assert)
119import Control.Monad (when)
120import Control.Monad.IO.Class (MonadIO(..))
121import Data.Functor.Identity (Identity)
122#if !(MIN_VERSION_base(4,11,0))
123import Data.Semigroup ((<>))
125import Data.Word (Word8)
126import Foreign.C.String (CString)
127import Foreign.Ptr (plusPtr, castPtr)
128import Foreign.Storable (Storable(..))
129import Prelude hiding (length, null, last, map, (!!), read, concat)
131import GHC.Ptr (Ptr(..))
133import Streamly.Internal.Data.Array.Foreign.Mut.Type (ReadUState(..), touch)
134import Streamly.Internal.Data.Array.Foreign.Type (Array(..), length)
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 (Tuple3'(..))
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.IsStream.Type as IsStream
148import qualified Streamly.Internal.Data.Stream.Prelude as P
149import qualified Streamly.Internal.Data.Stream.StreamD as D
150import qualified Streamly.Internal.Data.Unfold as Unfold
151import qualified Streamly.Internal.Data.Ring.Foreign as RB
153-------------------------------------------------------------------------------
155-------------------------------------------------------------------------------
157-- | Create an 'Array' from the first N elements of a stream. The array is
158-- allocated to size N, if the stream terminates before N elements then the
159-- array may hold less than N elements.
162{-# INLINE fromStreamN #-}
163fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
164fromStreamN n (SerialT m) = do
165 when (n < 0) $ error "writeN: negative write count specified"
166 A.fromStreamDN n $ D.fromStreamK m
168-- | Create an 'Array' from a stream. This is useful when we want to create a
169-- single array from a stream of unknown size. 'writeN' is at least twice
170-- as efficient when the size is already known.
172-- Note that if the input stream is too large memory allocation for the array
173-- may fail. When the stream size is not known, `arraysOf` followed by
174-- processing of indvidual arrays in the resulting stream should be preferred.
177{-# INLINE fromStream #-}
178fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
179fromStream (SerialT m) = P.fold A.write m
180-- write m = A.fromStreamD $ D.fromStreamK m
182-------------------------------------------------------------------------------
184-------------------------------------------------------------------------------
186{-# INLINE_NORMAL producer #-}
187producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
188producer = Producer step inject extract
191 {-# INLINE inject #-}
192 inject (Array contents start end) = return $ ReadUState contents end start
194 {-# INLINE_LATE step #-}
195 step (ReadUState contents end cur)
196 | assert (cur <= end) (cur == end) =
197 let x = unsafeInlineIO $ touch contents
198 in x `seq` return D.Stop
199 step (ReadUState contents end cur) = do
200 -- unsafeInlineIO allows us to run this in Identity monad for pure
201 -- toList/foldr case which makes them much faster due to not
202 -- accumulating the list and fusing better with the pure consumers.
204 -- This should be safe as the array contents are guaranteed to be
205 -- evaluated/written to before we peek at them.
206 let !x = unsafeInlineIO $ peek cur
207 cur1 = cur `plusPtr` sizeOf (undefined :: a)
208 return $ D.Yield x (ReadUState contents end cur1)
210 extract (ReadUState contents end cur) = return $ Array contents cur end
212-- | Unfold an array into a stream.
214-- /Since 0.7.0 (Streamly.Memory.Array)/
217{-# INLINE_NORMAL read #-}
218read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
219read = Producer.simplify producer
221-- | Unfold an array into a stream, does not check the end of the array, the
222-- user is responsible for terminating the stream within the array bounds. For
223-- high performance application where the end condition can be determined by
224-- a terminating fold.
226-- Written in the hope that it may be faster than "read", however, in the case
227-- for which this was written, "read" proves to be faster even though the core
228-- generated with unsafeRead looks simpler.
232{-# INLINE_NORMAL unsafeRead #-}
233unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
234unsafeRead = Unfold step inject
237 inject (Array contents start end) =
238 return (ReadUState contents end start)
240 {-# INLINE_LATE step #-}
241 step (ReadUState contents end p) = do
242 -- unsafeInlineIO allows us to run this in Identity monad for pure
243 -- toList/foldr case which makes them much faster due to not
244 -- accumulating the list and fusing better with the pure consumers.
246 -- This should be safe as the array contents are guaranteed to be
247 -- evaluated/written to before we peek at them.
248 let !x = unsafeInlineIO $ do
252 let !p1 = p `plusPtr` sizeOf (undefined :: a)
253 return $ D.Yield x (ReadUState contents end p1)
257-- >>> import qualified Streamly.Internal.Data.Array.Foreign.Type as Array
258-- >>> null arr = Array.byteLength arr == 0
262null :: Array a -> Bool
263null arr = A.byteLength arr == 0
265-- | Like 'getIndex' but indexes the array in reverse from the end.
268{-# INLINE getIndexRev #-}
269getIndexRev :: forall a. Storable a => Array a -> Int -> Maybe a
272 $ MA.unsafeWithArrayContents (arrContents arr) (arrStart arr)
274 let elemSize = sizeOf (undefined :: a)
275 elemPtr = aEnd arr `plusPtr` negate (elemSize * (i + 1))
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
288last arr = getIndexRev arr 0
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 (Tuple3' rb rh i) a = do
307 rh1 <- liftIO $ RB.unsafeInsert rb rh a
308 return $ FL.Partial $ Tuple3' rb rh1 (i + 1)
311 let f (a, b) = FL.Partial $ Tuple3' a b (0 :: Int)
312 in fmap f $ liftIO $ RB.new n
314 done (Tuple3' 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 = sizeOf (undefined :: 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-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
434{-# INLINE getIndex #-}
435getIndex :: forall a. Storable a => Array a -> Int -> Maybe a
438 $ MA.unsafeWithArrayContents (arrContents arr) (arrStart arr)
440 let elemSize = sizeOf (undefined :: a)
441 elemPtr = ptr `plusPtr` (elemSize * i)
442 if i >= 0 && elemPtr `plusPtr` elemSize <= aEnd arr
443 then Just <$> peek elemPtr
446-- | Given a stream of array indices, read the elements on those indices from
447-- the supplied Array. An exception is thrown if an index is out of bounds.
449-- This is the most general operation. We can implement other operations in
454-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
455-- in Unfold.lmap f (getIndices arr)
458-- let i = length arr - 1
459-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
463{-# INLINE getIndices #-}
464getIndices :: Unfold m (Array a) Int -> Unfold m (Array a) a
465getIndices = undefined
467-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
468-- element is the array value from the index @from@ and the successive elements
469-- are from the indices in increments of @then@ up to @to@. Index enumeration
470-- can occur downwards or upwards depending on whether @then@ comes before or
474-- getIndicesFromThenTo =
475-- let f (from, next, to, arr) =
476-- (Stream.enumerateFromThenTo from next to, arr)
477-- in Unfold.lmap f getIndices
481{-# INLINE getIndicesFromThenTo #-}
482getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
483getIndicesFromThenTo = undefined
485-------------------------------------------------------------------------------
486-- Transform via stream operations
487-------------------------------------------------------------------------------
489-- for non-length changing operations we can use the original length for
490-- allocation. If we can predict the length then we can use the prediction for
491-- new allocation. Otherwise we can use a hint and adjust dynamically.
494-- | Transform an array into another array using a pipe transformation
498{-# INLINE runPipe #-}
499runPipe :: (MonadIO m, Storable a, Storable b)
500 => Pipe m a b -> Array a -> m (Array b)
501runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
504-- XXX For transformations that cannot change the number of elements e.g. "map"
505-- we can use a predetermined array length.
507-- | Transform an array into another array using a stream transformation
511{-# INLINE streamTransform #-}
512streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
513 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
514streamTransform f arr =
515 P.fold (A.writeWith (length arr)) $ getSerialT $ f (A.toStream arr)
517-------------------------------------------------------------------------------
519-------------------------------------------------------------------------------
521-- | Cast an array having elements of type @a@ into an array having elements of
522-- type @b@. The array size must be a multiple of the size of type @b@
523-- otherwise accessing the last element of the array may result into a crash or
533unsafeCast (Array contents start end) =
534 Array contents (castPtr start) (castPtr end)
536-- | Cast an @Array a@ into an @Array Word8@.
540asBytes :: Array a -> Array Word8
543-- | Cast an array having elements of type @a@ into an array having elements of
544-- type @b@. The length of the array should be a multiple of the size of the
545-- target element otherwise 'Nothing' is returned.
549cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
551 let len = A.byteLength arr
552 r = len `mod` sizeOf (undefined :: b)
555 else Just $ unsafeCast arr
557-- | Use an @Array a@ as @Ptr b@.
563unsafeAsPtr :: Array a -> (Ptr b -> IO c) -> IO c
564unsafeAsPtr Array{..} act = do
565 MA.unsafeWithArrayContents arrContents arrStart $ \ptr -> act (castPtr ptr)
567-- | Convert an array of any type into a null terminated CString Ptr.
571-- /O(n) Time: (creates a copy of the array)/
575unsafeAsCString :: Array a -> (CString -> IO b) -> IO b
576unsafeAsCString arr act = do
577 let Array{..} = asBytes arr <> A.fromList [0]
578 MA.unsafeWithArrayContents arrContents arrStart $ \ptr -> act (castPtr ptr)
580-------------------------------------------------------------------------------
582-------------------------------------------------------------------------------
584-- | Fold an array using a 'Fold'.
588fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
589fold f arr = P.fold f (getSerialT (A.toStream arr))
591-- | Fold an array using a stream fold operation.
594{-# INLINE streamFold #-}
595streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
596streamFold 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