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
63 -- , writeLastN -- drop old (ring 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
97 -- , writeFrom -- start writing at the given position
99 -- , writeTo -- write from beginning up to the given position
104 -- , writeChunksOfFrom
118 -- -- * In-pace mutation (for Mutable Array type)
126 -- * Immutable Transformations
140 -- * Folds with Array as the container
145import Control.Monad (when)
146import Control.Monad.IO.Class (MonadIO(..))
147#if !(MIN_VERSION_base(4,11,0))
148import Data.Semigroup ((<>))
150import Data.Word (Word8)
151-- import Data.Functor.Identity (Identity)
152import Foreign.C.String (CString)
153import Foreign.ForeignPtr (withForeignPtr, castForeignPtr)
154import Foreign.ForeignPtr.Unsafe (unsafeForeignPtrToPtr)
155import Foreign.Ptr (plusPtr, castPtr)
156import Foreign.Storable (Storable(..))
157import Prelude hiding (length, null, last, map, (!!), read, concat)
159import GHC.ForeignPtr (ForeignPtr(..))
160import GHC.Ptr (Ptr(..))
161import GHC.Prim (touch#)
162import GHC.IO (IO(..))
164import Streamly.Internal.Data.Array.Foreign.Type (Array(..), length)
165import Streamly.Internal.Data.Fold.Type (Fold(..))
166import Streamly.Internal.Data.Producer.Type (Producer)
167import Streamly.Internal.Data.Stream.Serial (SerialT)
168import Streamly.Internal.Data.Tuple.Strict (Tuple3'(..))
169import Streamly.Internal.Data.Unfold.Type (Unfold(..))
171import qualified Streamly.Internal.Data.Array.Foreign.Mut.Type as MA
172import qualified Streamly.Internal.Data.Array.Foreign.Type as A
173import qualified Streamly.Internal.Data.Fold as FL
174import qualified Streamly.Internal.Data.Stream.Prelude as P
175import qualified Streamly.Internal.Data.Stream.Serial as Serial
176import qualified Streamly.Internal.Data.Stream.StreamD as D
177import qualified Streamly.Internal.Data.Unfold as Unfold
178import qualified Streamly.Internal.Data.Producer.Type as Producer
179import qualified Streamly.Internal.Ring.Foreign as RB
181#if MIN_VERSION_base(4,10,0)
182import Foreign.ForeignPtr (plusForeignPtr)
184import GHC.Base (Int(..), plusAddr#)
185import GHC.ForeignPtr (ForeignPtr(..))
186plusForeignPtr :: ForeignPtr a -> Int -> ForeignPtr b
187plusForeignPtr (ForeignPtr addr c) (I# d) = ForeignPtr (plusAddr# addr d) c
190-------------------------------------------------------------------------------
192-------------------------------------------------------------------------------
194-- | Create an 'Array' from the first N elements of a stream. The array is
195-- allocated to size N, if the stream terminates before N elements then the
196-- array may hold less than N elements.
199{-# INLINE fromStreamN #-}
200fromStreamN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
202 when (n < 0) $ error "writeN: negative write count specified"
203 A.fromStreamDN n $ D.toStreamD m
205-- | Create an 'Array' from a stream. This is useful when we want to create a
206-- single array from a stream of unknown size. 'writeN' is at least twice
207-- as efficient when the size is already known.
209-- Note that if the input stream is too large memory allocation for the array
210-- may fail. When the stream size is not known, `arraysOf` followed by
211-- processing of indvidual arrays in the resulting stream should be preferred.
214{-# INLINE fromStream #-}
215fromStream :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
216fromStream = P.fold A.write
217-- write m = A.fromStreamD $ D.toStreamD m
219-------------------------------------------------------------------------------
221-------------------------------------------------------------------------------
223-- | Unfold an array into a stream.
226{-# INLINE_NORMAL read #-}
227read :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
228read = Unfold.lmap A.unsafeThaw MA.read
230{-# INLINE_NORMAL producer #-}
231producer :: forall m a. (Monad m, Storable a) => Producer m (Array a) a
232producer = Producer.translate A.unsafeThaw A.unsafeFreeze MA.producer
234-- | Unfold an array into a stream, does not check the end of the array, the
235-- user is responsible for terminating the stream within the array bounds. For
236-- high performance application where the end condition can be determined by
237-- a terminating fold.
239-- Written in the hope that it may be faster than "read", however, in the case
240-- for which this was written, "read" proves to be faster even though the core
241-- generated with unsafeRead looks simpler.
245{-# INLINE_NORMAL unsafeRead #-}
246unsafeRead :: forall m a. (Monad m, Storable a) => Unfold m (Array a) a
247unsafeRead = Unfold step inject
250 inject (Array fp _) = return fp
252 {-# INLINE_LATE step #-}
253 step (ForeignPtr p contents) = do
254 -- unsafeInlineIO allows us to run this in Identity monad for pure
255 -- toList/foldr case which makes them much faster due to not
256 -- accumulating the list and fusing better with the pure consumers.
258 -- This should be safe as the array contents are guaranteed to be
259 -- evaluated/written to before we peek at them.
260 let !x = A.unsafeInlineIO $ do
264 let !(Ptr p1) = Ptr p `plusPtr` sizeOf (undefined :: a)
265 return $ D.Yield x (ForeignPtr p1 contents)
267 touch r = IO $ \s -> case touch# r s of s' -> (# s', () #)
269-- | > null arr = length arr == 0
273null :: Storable a => Array a -> Bool
274null arr = length arr == 0
276-- | > last arr = readIndex arr (length arr - 1)
280last :: Storable a => Array a -> Maybe a
281last arr = readIndex arr (length arr - 1)
283-------------------------------------------------------------------------------
284-- Folds with Array as the container
285-------------------------------------------------------------------------------
287-- | Take last 'n' elements from the stream and discard the rest.
289lastN :: (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
294 step (Tuple3' rb rh i) a = do
295 rh1 <- liftIO $ RB.unsafeInsert rb rh a
296 return $ FL.Partial $ Tuple3' rb rh1 (i + 1)
298 let f (a, b) = FL.Partial $ Tuple3' a b (0 :: Int)
299 in fmap f $ liftIO $ RB.new n
300 done (Tuple3' rb rh i) = do
301 arr <- liftIO $ MA.newArray n
302 foldFunc i rh snoc' arr rb
303 snoc' b a = liftIO $ MA.unsafeSnoc b a
305 | i < n = RB.unsafeFoldRingM
306 | otherwise = RB.unsafeFoldRingFullM
308-------------------------------------------------------------------------------
310-------------------------------------------------------------------------------
312-------------------------------------------------------------------------------
314-------------------------------------------------------------------------------
317-- | Perform a binary search in the array to find an element.
318bsearch :: a -> Array a -> Maybe Bool
321-- | Perform a binary search in the array to find an element index.
322{-# INLINE elemIndex #-}
323bsearchIndex :: a -> Array a -> Maybe Int
324bsearchIndex elem arr = undefined
326-- find/findIndex etc can potentially be implemented more efficiently on arrays
327-- compared to streams by using SIMD instructions.
329find :: (a -> Bool) -> Array a -> Bool
332findIndex :: (a -> Bool) -> Array a -> Maybe Int
335findIndices :: (a -> Bool) -> Array a -> Array Int
336findIndices = undefined
339-------------------------------------------------------------------------------
341-------------------------------------------------------------------------------
343-- XXX We can potentially use SIMD instructions on arrays to fold faster.
345-------------------------------------------------------------------------------
347-------------------------------------------------------------------------------
349-- | /O(1)/ Slice an array in constant time.
351-- Caution: The bounds of the slice are not checked.
356{-# INLINE unsafeSlice #-}
359 => Int -- ^ starting index
360 -> Int -- ^ length of the slice
363unsafeSlice start len (Array fp _) =
364 let size = sizeOf (undefined :: a)
365 fp1 = fp `plusForeignPtr` (start * size)
366 end = unsafeForeignPtrToPtr fp1 `plusPtr` (len * size)
371splitAt :: Int -> Array a -> (Array a, Array a)
372splitAt i arr = undefined
374-- XXX This operation can be performed efficiently via streams.
375-- | Append two arrays together to create a single array.
376splice :: Array a -> Array a -> Array a
377splice arr1 arr2 = undefined
379-------------------------------------------------------------------------------
380-- In-place mutation APIs
381-------------------------------------------------------------------------------
383-- | Partition an array into two halves using a partitioning predicate. The
384-- first half retains values where the predicate is 'False' and the second half
385-- retains values where the predicate is 'True'.
386{-# INLINE partitionBy #-}
387partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
388partitionBy f arr = undefined
390-- | Shuffle corresponding elements from two arrays using a shuffle function.
391-- If the shuffle function returns 'False' then do nothing otherwise swap the
392-- elements. This can be used in a bottom up fold to shuffle or reorder the
394shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
395shuffleBy f arr1 arr2 = undefined
397-- XXX we can also make the folds partial by stopping at a certain level.
399-- | Perform a top down hierarchical recursive partitioning fold of items in
400-- the container using the given function as the partition function.
402-- This will perform a quick sort if the partition function is
403-- 'partitionBy (< pivot)'.
406{-# INLINABLE foldtWith #-}
407foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
408foldtWith level f = undefined
410-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
411-- indicates the level in the tree where the fold would stop.
413-- This will perform a random shuffle if the shuffle function is random.
414-- If we stop at level 0 and repeatedly apply the function then we can do a
416foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
417foldbWith level f = undefined
420-- XXX consider the bulk update/accumulation/permutation APIs from vector.
422-------------------------------------------------------------------------------
423-- Random reads and writes
424-------------------------------------------------------------------------------
426-- | /O(1)/ Lookup the element at the given index, starting from 0.
429{-# INLINE readIndex #-}
430readIndex :: Storable a => Array a -> Int -> Maybe a
432 if i < 0 || i > length arr - 1
434 else A.unsafeInlineIO $
435 withForeignPtr (aStart arr) $ \p -> Just <$> peekElemOff p i
438-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
439-- at index @i@ and reading up to @count@ elements in the forward direction
440-- ending at the index @i + count - 1@.
443{-# INLINE readSlice #-}
444readSlice :: (IsStream t, Monad m, Storable a)
445 => Array a -> Int -> Int -> t m a
446readSlice arr i len = undefined
448-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
449-- index @i@ and reading up to @count@ elements in the reverse direction ending
450-- at the index @i - count + 1@.
453{-# INLINE readSliceRev #-}
454readSliceRev :: (IsStream t, Monad m, Storable a)
455 => Array a -> Int -> Int -> t m a
456readSliceRev arr i len = undefined
459-- | /O(1)/ Write the given element at the given index in the array.
460-- Performs in-place mutation of the array.
463{-# INLINE writeIndex #-}
464writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
465writeIndex arr i a = do
466 let maxIndex = length arr - 1
468 then error "writeIndex: negative array index"
470 then error $ "writeIndex: specified array index " ++ show i
471 ++ " is beyond the maximum index " ++ show maxIndex
473 liftIO $ withForeignPtr (aStart arr) $ \p ->
477-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
478-- starting at index @i@ and writing up to @count@ elements in the forward
479-- direction ending at the index @i + count - 1@.
482{-# INLINE writeSlice #-}
483writeSlice :: (IsStream t, Monad m, Storable a)
484 => Array a -> Int -> Int -> t m a -> m (Array a)
485writeSlice arr i len s = undefined
487-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
488-- starting at index @i@ and writing up to @count@ elements in the reverse
489-- direction ending at the index @i - count + 1@.
492{-# INLINE writeSliceRev #-}
493writeSliceRev :: (IsStream t, Monad m, Storable a)
494 => Array a -> Int -> Int -> t m a -> m (Array a)
495writeSliceRev arr i len s = undefined
498-------------------------------------------------------------------------------
499-- Transform via stream operations
500-------------------------------------------------------------------------------
502-- for non-length changing operations we can use the original length for
503-- allocation. If we can predict the length then we can use the prediction for
504-- new allocation. Otherwise we can use a hint and adjust dynamically.
507-- | Transform an array into another array using a pipe transformation
511{-# INLINE runPipe #-}
512runPipe :: (MonadIO m, Storable a, Storable b)
513 => Pipe m a b -> Array a -> m (Array b)
514runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
517-- | Transform an array into another array using a stream transformation
521{-# INLINE streamTransform #-}
522streamTransform :: forall m a b. (MonadIO m, Storable a, Storable b)
523 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
524streamTransform f arr =
525 P.fold (A.toArrayMinChunk (alignment (undefined :: a)) (length arr))
528-------------------------------------------------------------------------------
530-------------------------------------------------------------------------------
532-- | Cast an array having elements of type @a@ into an array having elements of
533-- type @b@. The array size must be a multiple of the size of type @b@
534-- otherwise accessing the last element of the array may result into a crash or
544unsafeCast (Array start end) = Array (castForeignPtr start) (castPtr end)
546-- | Cast an array into a Word8 array
550asByteArray :: Array a -> Array Word8
551asByteArray = unsafeCast
553-- | Cast an array having elements of type @a@ into an array having elements of
554-- type @b@. The length of the array should be a multiple of the size of the
555-- target element otherwise 'Nothing' is returned.
559cast :: forall a b. (Storable b) => Array a -> Maybe (Array b)
561 let len = A.byteLength arr
562 r = len `mod` sizeOf (undefined :: b)
565 else Just $ unsafeCast arr
567-- | Use an @Array a@ as @Ptr b@.
573asPtr :: Array a -> (Ptr b -> IO c) -> IO c
574asPtr Array{..} act = do
575 withForeignPtr aStart $ \ptr -> act (castPtr ptr)
577-- | Convert an array of any type into a null terminated CString Ptr.
581-- /O(n) Time: (creates a copy of the array)/
585asCString :: Array a -> (CString -> IO b) -> IO b
586asCString arr act = do
587 let Array{..} = asByteArray arr <> A.fromList [0]
588 withForeignPtr aStart $ \ptr -> act (castPtr ptr)
590-------------------------------------------------------------------------------
592-------------------------------------------------------------------------------
594-- | Fold an array using a 'Fold'.
598fold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
599fold f arr = P.fold f (A.toStream arr :: Serial.SerialT m a)
601-- | Fold an array using a stream fold operation.
604{-# INLINE streamFold #-}
605streamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
606streamFold 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