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
105 -- * Immutable Transformations
121import Control.Monad (when)
122import Control.Monad.IO.Class (MonadIO(..))
123#if !(MIN_VERSION_base(4,11,0))
124import Data.Semigroup ((<>))
126import Data.Word (Word8)
127-- import Data.Functor.Identity (Identity)
128import Foreign.C.String (CString)
129import Foreign.ForeignPtr (castForeignPtr)
130import Foreign.ForeignPtr.Unsafe (unsafeForeignPtrToPtr)
131import Foreign.Ptr (plusPtr, castPtr)
132import Foreign.Storable (Storable(..))
133import Prelude hiding (length, null, last, map, (!!), read, concat)
135import GHC.ForeignPtr (ForeignPtr(..))
136import GHC.Ptr (Ptr(..))
137import GHC.Prim (touch#)
138import GHC.IO (IO(..))
140import Streamly.Internal.BaseCompat
141import Streamly.Internal.Data.Array.Foreign.Type (Array(..), length)
142import Streamly.Internal.Data.Fold.Type (Fold(..))
143import Streamly.Internal.Data.Producer.Type (Producer)
144import Streamly.Internal.Data.Stream.Serial (SerialT(..))
145import Streamly.Internal.Data.Tuple.Strict (Tuple3'(..))
146import Streamly.Internal.Data.Unfold.Type (Unfold(..))
147import Streamly.Internal.System.IO (unsafeInlineIO)
149import qualified Streamly.Internal.Data.Array.Foreign.Mut.Type as MA
150import qualified Streamly.Internal.Data.Array.Foreign.Type as A
151import qualified Streamly.Internal.Data.Fold as FL
152import qualified Streamly.Internal.Data.Stream.Prelude as P
153import qualified Streamly.Internal.Data.Stream.StreamD as D
154import qualified Streamly.Internal.Data.Unfold as Unfold
155import qualified Streamly.Internal.Data.Producer.Type as Producer
156import qualified Streamly.Internal.Ring.Foreign as RB
158#if MIN_VERSION_base(4,10,0)
159import Foreign.ForeignPtr (plusForeignPtr)
161import GHC.Base (Int(..), plusAddr#)
162import GHC.ForeignPtr (ForeignPtr(..))
163plusForeignPtr :: ForeignPtr a -> Int -> ForeignPtr b
164plusForeignPtr (ForeignPtr addr c) (I# d) = ForeignPtr (plusAddr# addr d) c
167-------------------------------------------------------------------------------
169-------------------------------------------------------------------------------
171-- | Create an 'Array' from the first N elements of a stream. The array is
172-- allocated to size N, if the stream terminates before N elements then the
173-- array may hold less than N elements.
176{-# INLINE fromStreamN #-}
177fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
178fromStreamN n (SerialT m) = do
179 when (n < 0) $ error "writeN: negative write count specified"
180 A.fromStreamDN n $ D.fromStreamK m
182-- | Create an 'Array' from a stream. This is useful when we want to create a
183-- single array from a stream of unknown size. 'writeN' is at least twice
184-- as efficient when the size is already known.
186-- Note that if the input stream is too large memory allocation for the array
187-- may fail. When the stream size is not known, `arraysOf` followed by
188-- processing of indvidual arrays in the resulting stream should be preferred.
191{-# INLINE fromStream #-}
192fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
193fromStream (SerialT m) = P.fold A.write m
194-- write m = A.fromStreamD $ D.fromStreamK m
196-------------------------------------------------------------------------------
198-------------------------------------------------------------------------------
200-- | Unfold an array into a stream.
202-- /Since 0.7.0 (Streamly.Memory.Array)/
205{-# INLINE_NORMAL read #-}
206read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
207read = Unfold.lmap A.unsafeThaw MA.read
209{-# INLINE_NORMAL producer #-}
210producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
211producer = Producer.translate A.unsafeThaw A.unsafeFreeze MA.producer
213-- | Unfold an array into a stream, does not check the end of the array, the
214-- user is responsible for terminating the stream within the array bounds. For
215-- high performance application where the end condition can be determined by
216-- a terminating fold.
218-- Written in the hope that it may be faster than "read", however, in the case
219-- for which this was written, "read" proves to be faster even though the core
220-- generated with unsafeRead looks simpler.
224{-# INLINE_NORMAL unsafeRead #-}
225unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
226unsafeRead = Unfold step inject
229 inject (Array fp _) = return fp
231 {-# INLINE_LATE step #-}
232 step (ForeignPtr p contents) = do
233 -- unsafeInlineIO allows us to run this in Identity monad for pure
234 -- toList/foldr case which makes them much faster due to not
235 -- accumulating the list and fusing better with the pure consumers.
237 -- This should be safe as the array contents are guaranteed to be
238 -- evaluated/written to before we peek at them.
239 let !x = unsafeInlineIO $ do
243 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
244 return $ D.Yield x (ForeignPtr p1 contents)
246 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
248-- | > null arr = length arr == 0
252null :: Storable a => Array a -> Bool
253null arr = length arr == 0
255-- | > last arr = getIndex arr (length arr - 1)
259last :: Storable a => Array a -> Maybe a
260last arr = getIndex arr (length arr - 1)
262-------------------------------------------------------------------------------
263-- Folds with Array as the container
264-------------------------------------------------------------------------------
266-- | @writeLastN n@ folds a maximum of @n@ elements from the end of the input
267-- stream to an 'Array'.
270{-# INLINE writeLastN #-}
271writeLastN :: (Storable a, MonadIO m) => Int -> Fold m a (Array a)
273 | n <= 0 = fmap (const mempty) FL.drain
274 | otherwise = A.unsafeFreeze <$> Fold step initial done
278 step (Tuple3' rb rh i) a = do
279 rh1 <- liftIO $ RB.unsafeInsert rb rh a
280 return $ FL.Partial $ Tuple3' rb rh1 (i + 1)
283 let f (a, b) = FL.Partial $ Tuple3' a b (0 :: Int)
284 in fmap f $ liftIO $ RB.new n
286 done (Tuple3' rb rh i) = do
287 arr <- liftIO $ MA.newArray n
288 foldFunc i rh snoc' arr rb
290 snoc' b a = liftIO $ MA.unsafeSnoc b a
293 | i < n = RB.unsafeFoldRingM
294 | otherwise = RB.unsafeFoldRingFullM
296-------------------------------------------------------------------------------
298-------------------------------------------------------------------------------
300-------------------------------------------------------------------------------
302-------------------------------------------------------------------------------
305-- | Perform a binary search in the array to find an element.
306bsearch :: a -> Array a -> Maybe Bool
309-- | Perform a binary search in the array to find an element index.
310{-# INLINE elemIndex #-}
311bsearchIndex :: a -> Array a -> Maybe Int
312bsearchIndex elem arr = undefined
314-- find/findIndex etc can potentially be implemented more efficiently on arrays
315-- compared to streams by using SIMD instructions.
317find :: (a -> Bool) -> Array a -> Bool
320findIndex :: (a -> Bool) -> Array a -> Maybe Int
323findIndices :: (a -> Bool) -> Array a -> Array Int
324findIndices = undefined
327-------------------------------------------------------------------------------
329-------------------------------------------------------------------------------
331-- XXX We can potentially use SIMD instructions on arrays to fold faster.
333-------------------------------------------------------------------------------
335-------------------------------------------------------------------------------
337-- | /O(1)/ Slice an array in constant time.
339-- Caution: The bounds of the slice are not checked.
344{-# INLINE unsafeSlice #-}
347 => Int -- ^ starting index
348 -> Int -- ^ length of the slice
351unsafeSlice start len (Array fp _) =
352 let size = sizeOf (undefined :: a)
353 fp1 = fp `plusForeignPtr` (start * size)
354 end = unsafeForeignPtrToPtr fp1 `plusPtr` (len * size)
359splitAt :: Int -> Array a -> (Array a, Array a)
360splitAt i arr = undefined
362-- XXX This operation can be performed efficiently via streams.
363-- | Append two arrays together to create a single array.
364splice :: Array a -> Array a -> Array a
365splice arr1 arr2 = undefined
369-------------------------------------------------------------------------------
370-- Random reads and writes
371-------------------------------------------------------------------------------
373-- | /O(1)/ Lookup the element at the given index, starting from 0.
376{-# INLINE getIndex #-}
377getIndex :: Storable a => Array a -> Int -> Maybe a
379 if i < 0 || i > length arr - 1
381 else unsafeInlineIO $
382 unsafeWithForeignPtr (aStart arr) $ \p -> Just <$> peekElemOff p i
385-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
386-- at index @i@ and reading up to @count@ elements in the forward direction
387-- ending at the index @i + count - 1@.
390{-# INLINE readSlice #-}
391readSlice :: (IsStream t, Monad m, Storable a)
392 => Array a -> Int -> Int -> t m a
393readSlice arr i len = undefined
395-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
396-- index @i@ and reading up to @count@ elements in the reverse direction ending
397-- at the index @i - count + 1@.
400{-# INLINE readSliceRev #-}
401readSliceRev :: (IsStream t, Monad m, Storable a)
402 => Array a -> Int -> Int -> t m a
403readSliceRev arr i len = undefined
407-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
408-- starting at index @i@ and writing up to @count@ elements in the forward
409-- direction ending at the index @i + count - 1@.
412{-# INLINE writeSlice #-}
413writeSlice :: (IsStream t, Monad m, Storable a)
414 => Array a -> Int -> Int -> t m a -> m (Array a)
415writeSlice arr i len s = undefined
417-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
418-- starting at index @i@ and writing up to @count@ elements in the reverse
419-- direction ending at the index @i - count + 1@.
422{-# INLINE writeSliceRev #-}
423writeSliceRev :: (IsStream t, Monad m, Storable a)
424 => Array a -> Int -> Int -> t m a -> m (Array a)
425writeSliceRev arr i len s = undefined
428-------------------------------------------------------------------------------
429-- Transform via stream operations
430-------------------------------------------------------------------------------
432-- for non-length changing operations we can use the original length for
433-- allocation. If we can predict the length then we can use the prediction for
434-- new allocation. Otherwise we can use a hint and adjust dynamically.
437-- | Transform an array into another array using a pipe transformation
441{-# INLINE runPipe #-}
442runPipe :: (MonadIO m, Storable a, Storable b)
443 => Pipe m a b -> Array a -> m (Array b)
444runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
447-- | Transform an array into another array using a stream transformation
451{-# INLINE streamTransform #-}
452streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
453 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
454streamTransform f arr =
455 P.fold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
456 $ getSerialT $ f (A.toStream arr)
458-------------------------------------------------------------------------------
460-------------------------------------------------------------------------------
462-- | Cast an array having elements of type @a@ into an array having elements of
463-- type @b@. The array size must be a multiple of the size of type @b@
464-- otherwise accessing the last element of the array may result into a crash or
474unsafeCast (Array start end) = Array (castForeignPtr start) (castPtr end)
476-- | Cast an @Array a@ into an @Array Word8@.
480asBytes :: Array a -> Array Word8
483-- | Cast an array having elements of type @a@ into an array having elements of
484-- type @b@. The length of the array should be a multiple of the size of the
485-- target element otherwise 'Nothing' is returned.
489cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
491 let len = A.byteLength arr
492 r = len `mod` sizeOf (undefined :: b)
495 else Just $ unsafeCast arr
497-- | Use an @Array a@ as @Ptr b@.
503unsafeAsPtr :: Array a -> (Ptr b -> IO c) -> IO c
504unsafeAsPtr Array{..} act = do
505 unsafeWithForeignPtr aStart $ \ptr -> act (castPtr ptr)
507-- | Convert an array of any type into a null terminated CString Ptr.
511-- /O(n) Time: (creates a copy of the array)/
515unsafeAsCString :: Array a -> (CString -> IO b) -> IO b
516unsafeAsCString arr act = do
517 let Array{..} = asBytes arr <> A.fromList [0]
518 unsafeWithForeignPtr aStart $ \ptr -> act (castPtr ptr)
520-------------------------------------------------------------------------------
522-------------------------------------------------------------------------------
524-- | Fold an array using a 'Fold'.
528fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
529fold f arr = P.fold f (getSerialT (A.toStream arr))
531-- | Fold an array using a stream fold operation.
534{-# INLINE streamFold #-}
535streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
536streamFold 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