1{-# LANGUAGE BangPatterns #-}
3{-# LANGUAGE MagicHash #-}
4{-# LANGUAGE RecordWildCards #-}
5{-# LANGUAGE UnboxedTuples #-}
6{-# LANGUAGE ScopedTypeVariables #-}
11-- Module : Streamly.Memory.Array
12-- Copyright : (c) 2019 Harendra Kumar
15-- Maintainer : harendra.kumar@gmail.com
16-- Stability : experimental
19-- This module provides immutable arrays suitable for storage and random
20-- access. Once created an array cannot be mutated without copying. Arrays in
21-- this module are chunks of memory that hold a sequence of 'Storable' values
22-- of a given type. They are designed to store serializable data, they cannot
23-- store non-serializable data like functions, this is reflected by the
24-- 'Storable' constraint. For efficient buffering of data, arrays use pinned
25-- memory and therefore can hold arbitrary number of elements with a single
26-- movable pointer visible to GC, therefore, adding no pressure to GC.
27-- Moreover, pinned memory allows communication with foreign consumers and
28-- producers (e.g. file or network IO) without copying the data.
30-- By design, there are no array transformation operations provided in this
31-- module, only conversion to and from stream is provided. Arrays can be
32-- operated upon /efficiently/ by converting them into a stream, applying the
33-- desired stream transformations from "Streamly.Prelude" and then converting
34-- it back to an array.
36-- This module is designed to be imported qualified:
38-- > import qualified Streamly.Array as A
42-- Arrays are finite and fixed in size
43-- provide /O(1)/ access to elements
44-- store only data and not functions
45-- provide efficient IO interfacing
47-- 'Foldable' instance is not provided because the implementation would be much
48-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
49-- instances are deliberately not provided to avoid misuse; concatenating
50-- arrays using binary operations can be highly inefficient. Instead, use
51-- 'Streamly.Memory.Array.Stream.toArray' to concatenate N arrays at once.
53-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
54-- single byte) are only as good as holding those elements in a Haskell list.
55-- However, small arrays can be compacted into large ones to reduce the
56-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
57-- if we use one array for each chunk. This is still significant to add
58-- pressure to GC. However, we can create arrays of arrays (trees) to scale to
59-- arbitrarily large amounts of memory but still using small chunks of
62module Streamly.Memory.Array
70 -- | When performance matters, the fastest way to generate an array is
71 -- 'writeN'. For regular use, 'IsList' and 'IsString' instances can be
72 -- used to conveniently construct arrays from literal values.
73 -- 'OverloadedLists' extension or 'fromList' can be used to construct an
74 -- array from a list literal. Similarly, 'OverloadedStrings' extension or
75 -- 'fromList' can be used to construct an array from a string literal.
91 -- 'GHC.Exts.toList' from "GHC.Exts" can be used to convert an array to a
115 -- * Immutable Transformations
123 -- * Streams of Arrays
130 , AS.concatWithSuffix
135 , AS.compact -- compact
139import Control.Monad (when)
140import Control.Monad.IO.Class (MonadIO(..))
141-- import Data.Functor.Identity (Identity)
142import Foreign.ForeignPtr (withForeignPtr)
143import Foreign.ForeignPtr.Unsafe (unsafeForeignPtrToPtr)
144import Foreign.Ptr (minusPtr, plusPtr)
145import Foreign.Storable (Storable(..))
146import Prelude hiding (length, null, last, map, (!!), read, concat)
148import Streamly.Memory.Array.Types (Array(..), length)
149import Streamly.Streams.Serial (SerialT)
150import Streamly.Streams.StreamK.Type (IsStream)
151import Streamly.Fold.Types (Fold(..))
153import qualified Streamly.Memory.Array.Types as A
154import qualified Streamly.Memory.ArrayStream as AS
155import qualified Streamly.Streams.Prelude as P
156import qualified Streamly.Streams.Serial as Serial
157import qualified Streamly.Streams.StreamD as D
159-------------------------------------------------------------------------------
161-------------------------------------------------------------------------------
164-- | Create a new uninitialized array of given length.
167newArray :: (MonadIO m, Storable a) => Int -> m (Array a)
168newArray len = undefined
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 _writeNS #-}
177_writeNS :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
179 if n < 0 then error "writeN: negative write count specified" else return ()
180 A.fromStreamDN n $ D.toStreamD m
182-- XXX The realloc based implementation needs to make one extra copy if we use
183-- shrinkToFit. On the other hand, the stream of arrays implementation may
184-- buffer the array chunk pointers in memory but it does not have to shrink as
185-- we know the exact size in the end. However, memory copying does not seems to
186-- be as expensive as the allocations. Therefore, we need to reduce the number
187-- of allocations instead. Also, the size of allocations matters, right sizing
188-- an allocation even at the cost of copying sems to help. Should be measured
189-- on a big stream with heavy calls to toArray to see the effect.
191-- XXX check if GHC's memory allocator is efficient enough. We can try the C
192-- malloc to compare against.
194{-# INLINE_NORMAL toArrayMinChunk #-}
195toArrayMinChunk :: forall m a. (MonadIO m, Storable a)
196 => Int -> Fold m a (Array a)
197-- toArrayMinChunk n = FL.mapM spliceArrays $ toArraysOf n
198toArrayMinChunk elemCount = Fold step initial extract
202 insertElem (Array start end bound) x = do
204 return $ Array start (end `plusPtr` sizeOf (undefined :: a)) bound
207 when (elemCount < 0) $ error "toArrayMinChunk: elemCount is negative"
208 liftIO $ A.newArray elemCount
209 step arr@(Array start end bound) x | end == bound = do
210 let p = unsafeForeignPtrToPtr start
211 oldSize = end `minusPtr` p
212 newSize = max (oldSize * 2) 1
213 arr1 <- liftIO $ A.realloc newSize arr
215 step arr x = insertElem arr x
216 extract = liftIO . A.shrinkToFit
218-- | Fold the whole input to a single array.
220-- /Caution! Do not use this on infinite streams./
224write :: forall m a. (MonadIO m, Storable a) => Fold m a (Array a)
225write = toArrayMinChunk (A.bytesToElemCount (undefined :: a) (A.mkChunkSize 1024))
227-- | Create an 'Array' from a stream. This is useful when we want to create a
228-- single array from a stream of unknown size. 'writeN' is at least twice
229-- as efficient when the size is already known.
231-- Note that if the input stream is too large memory allocation for the array
232-- may fail. When the stream size is not known, `arraysOf` followed by
233-- processing of indvidual arrays in the resulting stream should be preferred.
235{-# INLINE _writeS #-}
236_writeS :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
237_writeS = P.runFold write
238-- write m = A.fromStreamD $ D.toStreamD m
240-------------------------------------------------------------------------------
242-------------------------------------------------------------------------------
244-- | Convert an 'Array' into a stream in reverse order.
247{-# INLINE_EARLY readRev #-}
248readRev :: (Monad m, IsStream t, Storable a) => Array a -> t m a
249readRev = D.fromStreamD . A.toStreamDRev
250-- XXX add fallback to StreamK rule
251-- {-# RULES "Streamly.Array.readRev fallback to StreamK" [1]
252-- forall a. S.toStreamK (readRev a) = K.revFromArray a #-}
255_null :: Storable a => Array a -> Bool
256_null arr = length arr == 0
259_last :: Storable a => Array a -> Maybe a
260_last arr = readIndex arr (length arr - 1)
262-------------------------------------------------------------------------------
264-------------------------------------------------------------------------------
266-------------------------------------------------------------------------------
268-------------------------------------------------------------------------------
271-- | Perform a binary search in the array to find an element.
272bsearch :: a -> Array a -> Maybe Bool
275-- | Perform a binary search in the array to find an element index.
276{-# INLINE elemIndex #-}
277bsearchIndex :: a -> Array a -> Maybe Int
278bsearchIndex elem arr = undefined
280-- find/findIndex etc can potentially be implemented more efficiently on arrays
281-- compared to streams by using SIMD instructions.
283find :: (a -> Bool) -> Array a -> Bool
286findIndex :: (a -> Bool) -> Array a -> Maybe Int
289findIndices :: (a -> Bool) -> Array a -> Array Int
290findIndices = undefined
293-------------------------------------------------------------------------------
295-------------------------------------------------------------------------------
297-- XXX We can potentially use SIMD instructions on arrays to fold faster.
299-------------------------------------------------------------------------------
301-------------------------------------------------------------------------------
304slice :: Int -> Int -> Array a
305slice begin end arr = undefined
307splitAt :: Int -> Array a -> (Array a, Array a)
308splitAt i arr = undefined
310-- XXX This operation can be performed efficiently via streams.
311-- | Append two arrays together to create a single array.
312splice :: Array a -> Array a -> Array a
313splice arr1 arr2 = undefined
315-------------------------------------------------------------------------------
316-- In-place mutation APIs
317-------------------------------------------------------------------------------
319-- | Partition an array into two halves using a partitioning predicate. The
320-- first half retains values where the predicate is 'False' and the second half
321-- retains values where the predicate is 'True'.
322{-# INLINE partitionBy #-}
323partitionBy :: (a -> Bool) -> Array a -> (Array a, Array a)
324partitionBy f arr = undefined
326-- | Shuffle corresponding elements from two arrays using a shuffle function.
327-- If the shuffle function returns 'False' then do nothing otherwise swap the
328-- elements. This can be used in a bottom up fold to shuffle or reorder the
330shuffleBy :: (a -> a -> m Bool) -> Array a -> Array a -> m (Array a)
331shuffleBy f arr1 arr2 = undefined
333-- XXX we can also make the folds partial by stopping at a certain level.
335-- | Perform a top down hierarchical recursive partitioning fold of items in
336-- the container using the given function as the partition function.
338-- This will perform a quick sort if the partition function is
339-- 'partitionBy (< pivot)'.
342{-# INLINABLE foldtWith #-}
343foldtWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
344foldtWith level f = undefined
346-- | Perform a pairwise bottom up fold recursively merging the pairs. Level
347-- indicates the level in the tree where the fold would stop.
349-- This will perform a random shuffle if the shuffle function is random.
350-- If we stop at level 0 and repeatedly apply the function then we can do a
352foldbWith :: Int -> (Array a -> Array a -> m (Array a)) -> Array a -> m (Array a)
353foldbWith level f = undefined
356-- XXX consider the bulk update/accumulation/permutation APIs from vector.
358-------------------------------------------------------------------------------
359-- Random reads and writes
360-------------------------------------------------------------------------------
362-- | /O(1)/ Lookup the element at the given index, starting from 0.
365{-# INLINE readIndex #-}
366readIndex :: Storable a => Array a -> Int -> Maybe a
368 if i < 0 || i > length arr - 1
370 else A.unsafeInlineIO $
371 withForeignPtr (aStart arr) $ \p -> fmap Just $ peekElemOff p i
374-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
375-- at index @i@ and reading up to @count@ elements in the forward direction
376-- ending at the index @i + count - 1@.
379{-# INLINE readSlice #-}
380readSlice :: (IsStream t, Monad m, Storable a)
381 => Array a -> Int -> Int -> t m a
382readSlice arr i len = undefined
384-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
385-- index @i@ and reading up to @count@ elements in the reverse direction ending
386-- at the index @i - count + 1@.
389{-# INLINE readSliceRev #-}
390readSliceRev :: (IsStream t, Monad m, Storable a)
391 => Array a -> Int -> Int -> t m a
392readSliceRev arr i len = undefined
395-- | /O(1)/ Write the given element at the given index in the array.
396-- Performs in-place mutation of the array.
399{-# INLINE _writeIndex #-}
400_writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
401_writeIndex arr i a = do
402 let maxIndex = length arr - 1
404 then error "writeIndex: negative array index"
406 then error $ "writeIndex: specified array index " ++ show i
407 ++ " is beyond the maximum index " ++ show maxIndex
409 liftIO $ withForeignPtr (aStart arr) $ \p ->
413-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
414-- starting at index @i@ and writing up to @count@ elements in the forward
415-- direction ending at the index @i + count - 1@.
418{-# INLINE writeSlice #-}
419writeSlice :: (IsStream t, Monad m, Storable a)
420 => Array a -> Int -> Int -> t m a -> m ()
421writeSlice arr i len s = undefined
423-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
424-- starting at index @i@ and writing up to @count@ elements in the reverse
425-- direction ending at the index @i - count + 1@.
428{-# INLINE writeSliceRev #-}
429writeSliceRev :: (IsStream t, Monad m, Storable a)
430 => Array a -> Int -> Int -> t m a -> m ()
431writeSliceRev arr i len s = undefined
434-------------------------------------------------------------------------------
435-- Transform via stream operations
436-------------------------------------------------------------------------------
438-- for non-length changing operations we can use the original length for
439-- allocation. If we can predict the length then we can use the prediction for
440-- new allocation. Otherwise we can use a hint and adjust dynamically.
443-- | Transform an array into another array using a pipe transformation
447{-# INLINE runPipe #-}
448runPipe :: (MonadIO m, Storable a, Storable b)
449 => Pipe m a b -> Array a -> m (Array b)
450runPipe f arr = P.runPipe (toArrayMinChunk (length arr)) $ f (A.read arr)
453-- | Transform an array into another array using a stream transformation
457{-# INLINE _runTransform #-}
458_runTransform :: (MonadIO m, Storable a, Storable b)
459 => (SerialT m a -> SerialT m b) -> Array a -> m (Array b)
460_runTransform f arr = P.runFold (toArrayMinChunk (length arr)) $ f (A.read arr)
462-- | Fold an array using a 'Fold'.
465{-# INLINE _runFold #-}
466_runFold :: forall m a b. (MonadIO m, Storable a) => Fold m a b -> Array a -> m b
467_runFold f arr = P.runFold f $ (A.read arr :: Serial.SerialT m a)
469-- | Fold an array using a stream fold operation.
472{-# INLINE _runStreamFold #-}
473_runStreamFold :: (MonadIO m, Storable a) => (SerialT m a -> m b) -> Array a -> m b
474_runStreamFold f arr = f (A.read 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