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
43 -- Pure, From Static Memory (Unsafe)
44 -- We can use fromPtrM#, fromCStringM# and fromAddrM# to create arrays from
45 -- a dynamic memory address which requires a finalizer.
60 , A.writeN -- drop new
62 , A.write -- full buffer
86 -- , readFrom -- read from a given position to the end of file
87 -- , readFromRev -- read from a given position to the beginning of file
88 -- , readTo -- read from beginning up to the given position
89 -- , readToRev -- read from end to the given position in file
103 -- -- * In-pace mutation (for Mutable Array type)
111 -- * Immutable Transformations
127import Control.Monad (when)
128import Control.Monad.IO.Class (MonadIO(..))
129#if !(MIN_VERSION_base(4,11,0))
130import Data.Semigroup ((<>))
132import Data.Word (Word8)
133-- import Data.Functor.Identity (Identity)
134import Foreign.C.String (CString)
135import Foreign.ForeignPtr (castForeignPtr)
136import Foreign.ForeignPtr.Unsafe (unsafeForeignPtrToPtr)
137import Foreign.Ptr (plusPtr, castPtr)
138import Foreign.Storable (Storable(..))
139import Prelude hiding (length, null, last, map, (!!), read, concat)
141import GHC.ForeignPtr (ForeignPtr(..))
142import GHC.Ptr (Ptr(..))
143import GHC.Prim (touch#)
144import GHC.IO (IO(..))
146import Streamly.Internal.BaseCompat
147import Streamly.Internal.Data.Array.Foreign.Type (Array(..), length)
148import Streamly.Internal.Data.Fold.Type (Fold(..))
149import Streamly.Internal.Data.Producer.Type (Producer)
150import Streamly.Internal.Data.Stream.Serial (SerialT)
151import Streamly.Internal.Data.Tuple.Strict (Tuple3'(..))
152import Streamly.Internal.Data.Unfold.Type (Unfold(..))
154import qualified Streamly.Internal.Data.Array.Foreign.Mut.Type as MA
155import qualified Streamly.Internal.Data.Array.Foreign.Type as A
156import qualified Streamly.Internal.Data.Fold as FL
157import qualified Streamly.Internal.Data.Stream.Prelude as P
158import qualified Streamly.Internal.Data.Stream.Serial as Serial
159import qualified Streamly.Internal.Data.Stream.StreamD as D
160import qualified Streamly.Internal.Data.Unfold as Unfold
161import qualified Streamly.Internal.Data.Producer.Type as Producer
162import qualified Streamly.Internal.Ring.Foreign as RB
164#if MIN_VERSION_base(4,10,0)
165import Foreign.ForeignPtr (plusForeignPtr)
167import GHC.Base (Int(..), plusAddr#)
168import GHC.ForeignPtr (ForeignPtr(..))
169plusForeignPtr :: ForeignPtr a -> Int -> ForeignPtr b
170plusForeignPtr (ForeignPtr addr c) (I# d) = ForeignPtr (plusAddr# addr d) c
173-------------------------------------------------------------------------------
175-------------------------------------------------------------------------------
177-- | Create an 'Array' from the first N elements of a stream. The array is
178-- allocated to size N, if the stream terminates before N elements then the
179-- array may hold less than N elements.
182{-# INLINE fromStreamN #-}
183fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
185 when (n < 0) $ error "writeN: negative write count specified"
186 A.fromStreamDN n $ D.toStreamD m
188-- | Create an 'Array' from a stream. This is useful when we want to create a
189-- single array from a stream of unknown size. 'writeN' is at least twice
190-- as efficient when the size is already known.
192-- Note that if the input stream is too large memory allocation for the array
193-- may fail. When the stream size is not known, `arraysOf` followed by
194-- processing of indvidual arrays in the resulting stream should be preferred.
197{-# INLINE fromStream #-}
198fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
199fromStream = P.fold A.write
200-- write m = A.fromStreamD $ D.toStreamD m
202-------------------------------------------------------------------------------
204-------------------------------------------------------------------------------
206-- | Unfold an array into a stream.
208-- /Since 0.7.0 (Streamly.Memory.Array)/
211{-# INLINE_NORMAL read #-}
212read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
213read = Unfold.lmap A.unsafeThaw MA.read
215{-# INLINE_NORMAL producer #-}
216producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
217producer = Producer.translate A.unsafeThaw A.unsafeFreeze MA.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 fp _) = return fp
237 {-# INLINE_LATE step #-}
238 step (ForeignPtr p contents) = do
239 -- unsafeInlineIO allows us to run this in Identity monad for pure
240 -- toList/foldr case which makes them much faster due to not
241 -- accumulating the list and fusing better with the pure consumers.
243 -- This should be safe as the array contents are guaranteed to be
244 -- evaluated/written to before we peek at them.
245 let !x = A.unsafeInlineIO $ do
249 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
250 return $ D.Yield x (ForeignPtr p1 contents)
252 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
254-- | > null arr = length arr == 0
258null :: Storable a => Array a -> Bool
259null arr = length arr == 0
261-- | > last arr = getIndex arr (length arr - 1)
265last :: Storable a => Array a -> Maybe a
266last arr = getIndex arr (length arr - 1)
268-------------------------------------------------------------------------------
269-- Folds with Array as the container
270-------------------------------------------------------------------------------
272-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
273-- stream to an 'Array'.
276{-# INLINE writeLastN #-}
277writeLastN :: (Storable a, MonadIO m) => Int -> Fold m a (Array a)
279 | n <= 0 = fmap (const mempty) FL.drain
280 | otherwise = A.unsafeFreeze <$> Fold step initial done
284 step (Tuple3' rb rh i) a = do
285 rh1 <- liftIO $ RB.unsafeInsert rb rh a
286 return $ FL.Partial $ Tuple3' rb rh1 (i + 1)
289 let f (a, b) = FL.Partial $ Tuple3' a b (0 :: Int)
290 in fmap f $ liftIO $ RB.new n
292 done (Tuple3' rb rh i) = do
293 arr <- liftIO $ MA.newArray n
294 foldFunc i rh snoc' arr rb
296 snoc' b a = liftIO $ MA.unsafeSnoc b a
299 | i < n = RB.unsafeFoldRingM
300 | otherwise = RB.unsafeFoldRingFullM
302-------------------------------------------------------------------------------
304-------------------------------------------------------------------------------
306-------------------------------------------------------------------------------
308-------------------------------------------------------------------------------
311-- | Perform a binary search in the array to find an element.
312bsearch :: a -> Array a -> Maybe Bool
315-- | Perform a binary search in the array to find an element index.
316{-# INLINE elemIndex #-}
317bsearchIndex :: a -> Array a -> Maybe Int
318bsearchIndex elem arr = undefined
320-- find/findIndex etc can potentially be implemented more efficiently on arrays
321-- compared to streams by using SIMD instructions.
323find :: (a -> Bool) -> Array a -> Bool
326findIndex :: (a -> Bool) -> Array a -> Maybe Int
329findIndices :: (a -> Bool) -> Array a -> Array Int
330findIndices = undefined
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 unsafeSlice #-}
353 => Int -- ^ starting index
354 -> Int -- ^ length of the slice
357unsafeSlice start len (Array fp _) =
358 let size = sizeOf (undefined :: a)
359 fp1 = fp `plusForeignPtr` (start * size)
360 end = unsafeForeignPtrToPtr fp1 `plusPtr` (len * size)
365splitAt :: Int -> Array a -> (Array a, Array a)
366splitAt i arr = undefined
368-- XXX This operation can be performed efficiently via streams.
369-- | Append two arrays together to create a single array.
370splice :: Array a -> Array a -> Array a
371splice arr1 arr2 = undefined
373-------------------------------------------------------------------------------
374-- In-place mutation APIs
375-------------------------------------------------------------------------------
377-- | Partition an array into two halves using a partitioning predicate. The
378-- first half retains values where the predicate is 'False' and the second half
379-- retains values where the predicate is 'True'.
380{-# INLINE partitionBy #-}
381partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
382partitionBy f arr = undefined
384-- | Shuffle corresponding elements from two arrays using a shuffle function.
385-- If the shuffle function returns 'False' then do nothing otherwise swap the
386-- elements. This can be used in a bottom up fold to shuffle or reorder the
388shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
389shuffleBy f arr1 arr2 = undefined
391-- XXX we can also make the folds partial by stopping at a certain level.
393-- | Perform a top down hierarchical recursive partitioning fold of items in
394-- the container using the given function as the partition function.
396-- This will perform a quick sort if the partition function is
397-- 'partitionBy (< pivot)'.
400{-# INLINABLE foldtWith #-}
401foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
402foldtWith level f = undefined
404-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
405-- indicates the level in the tree where the fold would stop.
407-- This will perform a random shuffle if the shuffle function is random.
408-- If we stop at level 0 and repeatedly apply the function then we can do a
410foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
411foldbWith level f = undefined
414-- XXX consider the bulk update/accumulation/permutation APIs from vector.
416-------------------------------------------------------------------------------
417-- Random reads and writes
418-------------------------------------------------------------------------------
420-- | /O(1)/ Lookup the element at the given index, starting from 0.
423{-# INLINE getIndex #-}
424getIndex :: Storable a => Array a -> Int -> Maybe a
426 if i < 0 || i > length arr - 1
428 else A.unsafeInlineIO $
429 unsafeWithForeignPtr (aStart arr) $ \p -> Just <$> peekElemOff p i
432-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
433-- at index @i@ and reading up to @count@ elements in the forward direction
434-- ending at the index @i + count - 1@.
437{-# INLINE readSlice #-}
438readSlice :: (IsStream t, Monad m, Storable a)
439 => Array a -> Int -> Int -> t m a
440readSlice arr i len = undefined
442-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
443-- index @i@ and reading up to @count@ elements in the reverse direction ending
444-- at the index @i - count + 1@.
447{-# INLINE readSliceRev #-}
448readSliceRev :: (IsStream t, Monad m, Storable a)
449 => Array a -> Int -> Int -> t m a
450readSliceRev arr i len = undefined
454-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
455-- starting at index @i@ and writing up to @count@ elements in the forward
456-- direction ending at the index @i + count - 1@.
459{-# INLINE writeSlice #-}
460writeSlice :: (IsStream t, Monad m, Storable a)
461 => Array a -> Int -> Int -> t m a -> m (Array a)
462writeSlice arr i len s = undefined
464-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
465-- starting at index @i@ and writing up to @count@ elements in the reverse
466-- direction ending at the index @i - count + 1@.
469{-# INLINE writeSliceRev #-}
470writeSliceRev :: (IsStream t, Monad m, Storable a)
471 => Array a -> Int -> Int -> t m a -> m (Array a)
472writeSliceRev arr i len s = undefined
475-------------------------------------------------------------------------------
476-- Transform via stream operations
477-------------------------------------------------------------------------------
479-- for non-length changing operations we can use the original length for
480-- allocation. If we can predict the length then we can use the prediction for
481-- new allocation. Otherwise we can use a hint and adjust dynamically.
484-- | Transform an array into another array using a pipe transformation
488{-# INLINE runPipe #-}
489runPipe :: (MonadIO m, Storable a, Storable b)
490 => Pipe m a b -> Array a -> m (Array b)
491runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
494-- | Transform an array into another array using a stream transformation
498{-# INLINE streamTransform #-}
499streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
500 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
501streamTransform f arr =
502 P.fold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
505-------------------------------------------------------------------------------
507-------------------------------------------------------------------------------
509-- | Cast an array having elements of type @a@ into an array having elements of
510-- type @b@. The array size must be a multiple of the size of type @b@
511-- otherwise accessing the last element of the array may result into a crash or
521unsafeCast (Array start end) = Array (castForeignPtr start) (castPtr end)
523-- | Cast an @Array a@ into an @Array Word8@.
527asBytes :: Array a -> Array Word8
530-- | Cast an array having elements of type @a@ into an array having elements of
531-- type @b@. The length of the array should be a multiple of the size of the
532-- target element otherwise 'Nothing' is returned.
536cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
538 let len = A.byteLength arr
539 r = len `mod` sizeOf (undefined :: b)
542 else Just $ unsafeCast arr
544-- | Use an @Array a@ as @Ptr b@.
550unsafeAsPtr :: Array a -> (Ptr b -> IO c) -> IO c
551unsafeAsPtr Array{..} act = do
552 unsafeWithForeignPtr aStart $ \ptr -> act (castPtr ptr)
554-- | Convert an array of any type into a null terminated CString Ptr.
558-- /O(n) Time: (creates a copy of the array)/
562unsafeAsCString :: Array a -> (CString -> IO b) -> IO b
563unsafeAsCString arr act = do
564 let Array{..} = asBytes arr <> A.fromList [0]
565 unsafeWithForeignPtr aStart $ \ptr -> act (castPtr ptr)
567-------------------------------------------------------------------------------
569-------------------------------------------------------------------------------
571-- | Fold an array using a 'Fold'.
575fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
576fold f arr = P.fold f (A.toStream arr :: Serial.SerialT m a)
578-- | Fold an array using a stream fold operation.
581{-# INLINE streamFold #-}
582streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
583streamFold 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