1{-# LANGUAGE UnboxedTuples #-}
6-- Module : Streamly.Internal.Data.Array.Foreign
7-- Copyright : (c) 2019 Composewell Technologies
10-- Maintainer : streamly@composewell.com
11-- Stability : experimental
16-- * Arrays are finite and fixed in size
17-- * provide /O(1)/ access to elements
18-- * store only data and not functions
19-- * provide efficient IO interfacing
21-- 'Foldable' instance is not provided because the implementation would be much
22-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
23-- instances should be used with care; concatenating arrays using binary
24-- operations can be highly inefficient. Instead, use
25-- 'Streamly.Internal.Data.Array.Stream.Foreign.toArray' to concatenate N
28-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
29-- single byte) are only as good as holding those elements in a Haskell list.
30-- However, small arrays can be compacted into large ones to reduce the
31-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
32-- if we use one array for each chunk. This is still significant to add
35module Streamly.Internal.Data.Array.Foreign
41 -- Pure, From Static Memory (Unsafe)
42 -- We can use fromPtrM#, fromCStringM# and fromAddrM# to create arrays from
43 -- a dynamic memory address which requires a finalizer.
57 , A.writeN -- drop new
59 , A.write -- full buffer
67 , unsafeRead -- XXX readUnsafe?
69 , producer -- experimental
74 , A.unsafeIndex -- XXX Rename to getIndexUnsafe??
76 , last -- XXX getIndexLast?
78 , getIndicesFromThenTo
79 -- , getIndicesFrom -- read from a given position to the end of file
80 -- , getIndicesUpto -- read from beginning up to the given position
82 -- , getIndicesFromRev -- read from a given position to the beginning of file
83 -- , getIndicesUptoRev -- read from end to the given position in file
98 , unsafeCast -- castUnsafe?
99 , unsafeAsPtr -- asPtrUnsafe?
100 , unsafeAsCString -- asCStringUnsafe?
101 , A.unsafeFreeze -- asImmutableUnsafe?
102 , A.unsafeThaw -- asMutableUnsafe?
107 -- , getSlicesFromLenN
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.ForeignPtr (castForeignPtr)
128import Foreign.ForeignPtr.Unsafe (unsafeForeignPtrToPtr)
129import Foreign.Ptr (plusPtr, castPtr)
130import Foreign.Storable (Storable(..))
131import Prelude hiding (length, null, last, map, (!!), read, concat)
133import GHC.ForeignPtr (ForeignPtr(..))
134import GHC.Ptr (Ptr(..))
135import GHC.Prim (touch#)
136import GHC.IO (IO(..))
138import Streamly.Internal.BaseCompat
139import Streamly.Internal.Data.Array.Foreign.Type (Array(..), length)
140import Streamly.Internal.Data.Fold.Type (Fold(..))
141import Streamly.Internal.Data.Producer.Type (Producer)
142import Streamly.Internal.Data.Stream.Serial (SerialT(..))
143import Streamly.Internal.Data.Tuple.Strict (Tuple3'(..))
144import Streamly.Internal.Data.Unfold.Type (Unfold(..))
145import Streamly.Internal.System.IO (unsafeInlineIO)
147import qualified Streamly.Internal.Data.Array.Foreign.Mut.Type as MA
148import qualified Streamly.Internal.Data.Array.Foreign.Type as A
149import qualified Streamly.Internal.Data.Fold as FL
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.Producer.Type as Producer
154import qualified Streamly.Internal.Ring.Foreign as RB
156#if MIN_VERSION_base(4,10,0)
157import Foreign.ForeignPtr (plusForeignPtr)
159import GHC.Base (Int(..), plusAddr#)
160import GHC.ForeignPtr (ForeignPtr(..))
161plusForeignPtr :: ForeignPtr a -> Int -> ForeignPtr b
162plusForeignPtr (ForeignPtr addr c) (I# d) = ForeignPtr (plusAddr# addr d) c
165-------------------------------------------------------------------------------
167-------------------------------------------------------------------------------
169-- | Create an 'Array' from the first N elements of a stream. The array is
170-- allocated to size N, if the stream terminates before N elements then the
171-- array may hold less than N elements.
174{-# INLINE fromStreamN #-}
175fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
176fromStreamN n (SerialT m) = do
177 when (n < 0) $ error "writeN: negative write count specified"
178 A.fromStreamDN n $ D.fromStreamK m
180-- | Create an 'Array' from a stream. This is useful when we want to create a
181-- single array from a stream of unknown size. 'writeN' is at least twice
182-- as efficient when the size is already known.
184-- Note that if the input stream is too large memory allocation for the array
185-- may fail. When the stream size is not known, `arraysOf` followed by
186-- processing of indvidual arrays in the resulting stream should be preferred.
189{-# INLINE fromStream #-}
190fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
191fromStream (SerialT m) = P.fold A.write m
192-- write m = A.fromStreamD $ D.fromStreamK m
194-------------------------------------------------------------------------------
196-------------------------------------------------------------------------------
198-- | Unfold an array into a stream.
200-- /Since 0.7.0 (Streamly.Memory.Array)/
203{-# INLINE_NORMAL read #-}
204read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
205read = Unfold.lmap A.unsafeThaw MA.read
207{-# INLINE_NORMAL producer #-}
208producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
209producer = Producer.translate A.unsafeThaw A.unsafeFreeze MA.producer
211-- | Unfold an array into a stream, does not check the end of the array, the
212-- user is responsible for terminating the stream within the array bounds. For
213-- high performance application where the end condition can be determined by
214-- a terminating fold.
216-- Written in the hope that it may be faster than "read", however, in the case
217-- for which this was written, "read" proves to be faster even though the core
218-- generated with unsafeRead looks simpler.
222{-# INLINE_NORMAL unsafeRead #-}
223unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
224unsafeRead = Unfold step inject
227 inject (Array fp _) = return fp
229 {-# INLINE_LATE step #-}
230 step (ForeignPtr p contents) = do
231 -- unsafeInlineIO allows us to run this in Identity monad for pure
232 -- toList/foldr case which makes them much faster due to not
233 -- accumulating the list and fusing better with the pure consumers.
235 -- This should be safe as the array contents are guaranteed to be
236 -- evaluated/written to before we peek at them.
237 let !x = unsafeInlineIO $ do
241 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
242 return $ D.Yield x (ForeignPtr p1 contents)
244 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
248-- >>> import qualified Streamly.Internal.Data.Array.Foreign.Type as Array
249-- >>> null arr = Array.byteLength arr == 0
253null :: Array a -> Bool
254null arr = A.byteLength arr == 0
256-- | Like 'getIndex' but indexes the array in reverse from the end.
259{-# INLINE getIndexRev #-}
260getIndexRev :: forall a. Storable a => Array a -> Int -> Maybe a
263 unsafeWithForeignPtr (aStart arr) $ \ptr -> do
264 let elemSize = sizeOf (undefined :: a)
265 elemPtr = aEnd arr `plusPtr` negate (elemSize * (i + 1))
266 if i >= 0 && elemPtr >= ptr
267 then Just <$> peek elemPtr
272-- >>> import qualified Streamly.Internal.Data.Array.Foreign as Array
273-- >>> last arr = Array.getIndexRev arr 0
277last :: Storable a => Array a -> Maybe a
278last arr = getIndexRev arr 0
280-------------------------------------------------------------------------------
281-- Folds with Array as the container
282-------------------------------------------------------------------------------
284-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
285-- stream to an 'Array'.
288{-# INLINE writeLastN #-}
289writeLastN :: (Storable a, MonadIO m) => Int -> Fold m a (Array a)
291 | n <= 0 = fmap (const mempty) FL.drain
292 | otherwise = A.unsafeFreeze <$> Fold step initial done
296 step (Tuple3' rb rh i) a = do
297 rh1 <- liftIO $ RB.unsafeInsert rb rh a
298 return $ FL.Partial $ Tuple3' rb rh1 (i + 1)
301 let f (a, b) = FL.Partial $ Tuple3' a b (0 :: Int)
302 in fmap f $ liftIO $ RB.new n
304 done (Tuple3' rb rh i) = do
305 arr <- liftIO $ MA.newArray n
306 foldFunc i rh snoc' arr rb
308 -- XXX We should write a read unfold for ring.
309 snoc' b a = liftIO $ MA.snocUnsafe b a
312 | i < n = RB.unsafeFoldRingM
313 | otherwise = RB.unsafeFoldRingFullM
315-------------------------------------------------------------------------------
317-------------------------------------------------------------------------------
319-------------------------------------------------------------------------------
321-------------------------------------------------------------------------------
323-- | Given a sorted array, perform a binary search to find the given element.
324-- Returns the index of the element if found.
327{-# INLINE binarySearch #-}
328binarySearch :: a -> Array a -> Maybe Int
329binarySearch = undefined
331-- find/findIndex etc can potentially be implemented more efficiently on arrays
332-- compared to streams by using SIMD instructions.
333-- We can also return a bit array instead.
335-- | Perform a linear search to find all the indices where a given element is
336-- present in an array.
339findIndicesOf :: (a -> Bool) -> Unfold Identity (Array a) Int
340findIndicesOf = undefined
343findIndexOf :: (a -> Bool) -> Array a -> Maybe Int
344findIndexOf p = Unfold.fold Fold.head . Stream.unfold (findIndicesOf p)
346find :: (a -> Bool) -> Array a -> Bool
347find = Unfold.fold Fold.null . Stream.unfold (findIndicesOf p)
350-------------------------------------------------------------------------------
352-------------------------------------------------------------------------------
354-- XXX We can potentially use SIMD instructions on arrays to fold faster.
356-------------------------------------------------------------------------------
358-------------------------------------------------------------------------------
360-- | /O(1)/ Slice an array in constant time.
362-- Caution: The bounds of the slice are not checked.
367{-# INLINE getSliceUnsafe #-}
370 => Int -- ^ starting index
371 -> Int -- ^ length of the slice
374getSliceUnsafe index len (Array fp e) =
375 let size = sizeOf (undefined :: a)
376 fp1 = fp `plusForeignPtr` (index * size)
377 end = unsafeForeignPtrToPtr fp1 `plusPtr` (len * size)
378 in assert (end <= e) (Array fp1 end)
380-------------------------------------------------------------------------------
381-- Random reads and writes
382-------------------------------------------------------------------------------
384-- XXX Change this to a partial function instead of a Maybe type? And use
385-- MA.getIndex instead.
387-- | /O(1)/ Lookup the element at the given index. Index starts from 0.
390{-# INLINE getIndex #-}
391getIndex :: forall a. Storable a => Array a -> Int -> Maybe a
394 unsafeWithForeignPtr (aStart arr) $ \ptr -> do
395 let elemSize = sizeOf (undefined :: a)
396 elemPtr = ptr `plusPtr` (elemSize * i)
397 if i >= 0 && elemPtr `plusPtr` elemSize <= aEnd arr
398 then Just <$> peek elemPtr
401-- | Given a stream of array indices, read the elements on those indices from
402-- the supplied Array. An exception is thrown if an index is out of bounds.
404-- This is the most general operation. We can implement other operations in
409-- let u = lmap (\arr -> (0, length arr - 1)) Unfold.enumerateFromTo
410-- in Unfold.lmap f (getIndices arr)
413-- let i = length arr - 1
414-- in Unfold.lmap f (getIndicesFromThenTo i (i - 1) 0)
418{-# INLINE getIndices #-}
419getIndices :: Unfold m (Array a) Int -> Unfold m (Array a) a
420getIndices = undefined
422-- | Unfolds @(from, then, to, array)@ generating a finite stream whose first
423-- element is the array value from the index @from@ and the successive elements
424-- are from the indices in increments of @then@ up to @to@. Index enumeration
425-- can occur downwards or upwards depending on whether @then@ comes before or
429-- getIndicesFromThenTo =
430-- let f (from, next, to, arr) =
431-- (Stream.enumerateFromThenTo from next to, arr)
432-- in Unfold.lmap f getIndices
436{-# INLINE getIndicesFromThenTo #-}
437getIndicesFromThenTo :: Unfold m (Int, Int, Int, Array a) a
438getIndicesFromThenTo = undefined
440-------------------------------------------------------------------------------
441-- Transform via stream operations
442-------------------------------------------------------------------------------
444-- for non-length changing operations we can use the original length for
445-- allocation. If we can predict the length then we can use the prediction for
446-- new allocation. Otherwise we can use a hint and adjust dynamically.
449-- | Transform an array into another array using a pipe transformation
453{-# INLINE runPipe #-}
454runPipe :: (MonadIO m, Storable a, Storable b)
455 => Pipe m a b -> Array a -> m (Array b)
456runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
459-- XXX For transformations that cannot change the number of elements e.g. "map"
460-- we can use a predetermined array length.
462-- | Transform an array into another array using a stream transformation
466{-# INLINE streamTransform #-}
467streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
468 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
469streamTransform f arr =
470 P.fold (A.writeWith (alignment (undefined :: a)) (length arr))
471 $ getSerialT $ f (A.toStream arr)
473-------------------------------------------------------------------------------
475-------------------------------------------------------------------------------
477-- | Cast an array having elements of type @a@ into an array having elements of
478-- type @b@. The array size must be a multiple of the size of type @b@
479-- otherwise accessing the last element of the array may result into a crash or
489unsafeCast (Array start end) = Array (castForeignPtr start) (castPtr end)
491-- | Cast an @Array a@ into an @Array Word8@.
495asBytes :: Array a -> Array Word8
498-- | Cast an array having elements of type @a@ into an array having elements of
499-- type @b@. The length of the array should be a multiple of the size of the
500-- target element otherwise 'Nothing' is returned.
504cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
506 let len = A.byteLength arr
507 r = len `mod` sizeOf (undefined :: b)
510 else Just $ unsafeCast arr
512-- | Use an @Array a@ as @Ptr b@.
518unsafeAsPtr :: Array a -> (Ptr b -> IO c) -> IO c
519unsafeAsPtr Array{..} act = do
520 unsafeWithForeignPtr aStart $ \ptr -> act (castPtr ptr)
522-- | Convert an array of any type into a null terminated CString Ptr.
526-- /O(n) Time: (creates a copy of the array)/
530unsafeAsCString :: Array a -> (CString -> IO b) -> IO b
531unsafeAsCString arr act = do
532 let Array{..} = asBytes arr <> A.fromList [0]
533 unsafeWithForeignPtr aStart $ \ptr -> act (castPtr ptr)
535-------------------------------------------------------------------------------
537-------------------------------------------------------------------------------
539-- | Fold an array using a 'Fold'.
543fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
544fold f arr = P.fold f (getSerialT (A.toStream arr))
546-- | Fold an array using a stream fold operation.
549{-# INLINE streamFold #-}
550streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
551streamFold 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