1{-# LANGUAGE BangPatterns #-}
3{-# LANGUAGE MagicHash #-}
4{-# LANGUAGE RecordWildCards #-}
5{-# LANGUAGE UnboxedTuples #-}
6{-# LANGUAGE ScopedTypeVariables #-}
11-- Module : Streamly.Mem.Array
12-- Copyright : (c) 2019 Harendra Kumar
15-- Maintainer : harendra.kumar@gmail.com
16-- Stability : experimental
19-- Arrays are the computing duals of streams. Streams are good at sequential
20-- access, immutable transformations of in-transit data whereas arrays are good
21-- at random access, in-place transformations of buffered data. Unlike streams
22-- which are potentially infinite, arrays are necessarily /finite/. Arrays can
23-- be used as an efficient interface between streams and external storage
24-- systems like memory, files and network. Streams and arrays complete each
25-- other to provide a general purpose computing system. The design of streamly
26-- as a general purpose computing framework is centered around these two
27-- fundamental aspects of computing and storage.
29-- Even though the implementation allows for in-place mutation, the current
30-- implementation of arrays is immutable. Arrays are of fixed size. The size of
31-- an array is fixed at creation and cannot be changed later without copying.
32-- Arrays are chunks of memory that hold a sequence of 'Storable' values of a
33-- given type. They are designed to store serializable data, they cannot store
34-- non-serializable data like functions, this is reflected by the 'Storable'
35-- constraint. For efficient buffering of data, arrays use pinned memory and
36-- therefore can hold arbitrary number of elements with a single movable
37-- pointer visible to GC, therefore, adding no pressure to GC. Moreover,
38-- pinned memory allows communication with foreign consumers and producers
39-- (e.g. file or network IO) without copying the data.
41-- By design, there are no transformation operations provided in this module,
42-- only stream conversion and IO routines are provided. An array is purely a
43-- data store, therefore, it is not a 'Functor'. Arrays can be operated upon
44-- /efficiently/ by converting them into a stream, applying the desired
45-- transformations on the stream and then converting it back to an array.
46-- 'Foldable' instance is not provided because the implementation would be much
47-- less efficient compared to folding via streams. 'Semigroup' and 'Monoid'
48-- instances are deliberately not provided to avoid misuse; concatenating
49-- arrays using binary operations can be highly inefficient. Instead, use
50-- 'spliceArrays' to concatenate N arrays at once.
54-- * Arrays are finite and fixed in size
55-- * provide /O(1)/ access to elements
56-- * store only data and not functions
57-- * provide efficient IO interfacing
59-- 'ByteString' data type from the 'bytestring' package and the 'Text' data
60-- type from the 'text' package are just special cases of arrays. 'ByteString'
61-- is equivalent to @Array Word8@ and 'Text' is equivalent to a @utf16@ encoded
62-- @Array Word8@. All the 'bytestring' and 'text' operations can be performed
63-- on arrays with equivalent or better performance by converting them to and
66-- This module is designed to be imported qualified:
68-- > import qualified Streamly.Array as A
70-- Each array is one pointer visible to the GC. Too many small arrays (e.g.
71-- single byte) are only as good as holding those elements in a Haskell list.
72-- However, small arrays can be compacted into large ones to reduce the
73-- overhead. To hold 32GB memory in 32k sized buffers we need 1 million arrays
74-- if we use one array for each chunk. This is still significant to add
75-- pressure to GC. However, we can create arrays of arrays (trees) to scale to
76-- arbitrarily large amounts of memory but still using small chunks of
79module Streamly.Mem.Array
86 -- | When performance matters, the fastest way to generate an array is
87 -- 'writeN'. For regular use, 'IsList' and 'IsString' instances can be
88 -- used to conveniently construct arrays from literal values.
89 -- 'OverloadedLists' extension or 'fromList' can be used to construct an
90 -- array from a list literal. Similarly, 'OverloadedStrings' extension or
91 -- 'fromList' can be used to construct an array from a string literal.
108 -- 'GHC.Exts.toList' from "GHC.Exts" can be used to convert an array to a
115 -- , flattenArraysRev
134import Control.Monad.IO.Class (MonadIO(..))
135import Foreign.ForeignPtr (withForeignPtr)
136import Foreign.Ptr (minusPtr, plusPtr, castPtr)
137import Foreign.Storable (Storable(..))
138import Prelude hiding (length, null, last, map, (!!), read)
140import Streamly.Mem.Array.Types hiding (flattenArrays, newArray)
141import Streamly.Streams.Serial (SerialT)
142import Streamly.Streams.StreamK.Type (IsStream)
144import qualified Streamly.Mem.Array.Types as A
145import qualified Streamly.Prelude as S
146import qualified Streamly.Streams.StreamD as D
148-------------------------------------------------------------------------------
150-------------------------------------------------------------------------------
153-- | Create a new uninitialized array of given length.
156newArray :: (MonadIO m, Storable a) => Int -> m (Array a)
157newArray len = undefined
160-- | Create an 'Array' from the first N elements of a stream. The array is
161-- allocated to size N, if the stream terminates before N elements then the
162-- array may hold less than N elements.
166writeN :: (MonadIO m, Storable a) => Int -> SerialT m a -> m (Array a)
167writeN n m = fromStreamDN n $ D.toStreamD m
169-------------------------------------------------------------------------------
171-------------------------------------------------------------------------------
173-- | Convert an 'Array' into a stream.
176{-# INLINE_EARLY read #-}
177read :: (Monad m, IsStream t, Storable a) => Array a -> t m a
178read = D.fromStreamD . toStreamD
179-- XXX add fallback to StreamK rule
180-- {-# RULES "Streamly.Array.read fallback to StreamK" [1]
181-- forall a. S.readK (read a) = K.fromArray a #-}
183-- | Convert an 'Array' into a stream in reverse order.
186{-# INLINE_EARLY readRev #-}
187readRev :: (Monad m, IsStream t, Storable a) => Array a -> t m a
188readRev = D.fromStreamD . toStreamDRev
189-- XXX add fallback to StreamK rule
190-- {-# RULES "Streamly.Array.readRev fallback to StreamK" [1]
191-- forall a. S.toStreamK (readRev a) = K.revFromArray a #-}
194_null :: Storable a => Array a -> Bool
195_null arr = length arr == 0
198_last :: forall a. Storable a => Array a -> Maybe a
199_last arr = readIndex arr (length arr - 1)
201-------------------------------------------------------------------------------
203-------------------------------------------------------------------------------
205-- | /O(1)/ Lookup the element at the given index.
208{-# INLINE readIndex #-}
209readIndex :: Storable a => Array a -> Int -> Maybe a
211 if i < 0 || i > length arr - 1
213 else Just $ unsafeIndex arr i
216-- | @readSlice arr i count@ streams a slice of the array @arr@ starting
217-- at index @i@ and reading up to @count@ elements in the forward direction
218-- ending at the index @i + count - 1@.
221{-# INLINE readSlice #-}
222readSlice :: (IsStream t, Monad m, Storable a)
223 => Array a -> Int -> Int -> t m a
224readSlice arr i len = undefined
226-- | @readSliceRev arr i count@ streams a slice of the array @arr@ starting at
227-- index @i@ and reading up to @count@ elements in the reverse direction ending
228-- at the index @i - count + 1@.
231{-# INLINE readSliceRev #-}
232readSliceRev :: (IsStream t, Monad m, Storable a)
233 => Array a -> Int -> Int -> t m a
234readSliceRev arr i len = undefined
236-- | /O(1)/ Write the given element at the given index in the array.
239{-# INLINE writeIndex #-}
240writeIndex :: (MonadIO m, Storable a) => Array a -> Int -> a -> m ()
241writeIndex arr i a = undefined
243-- | @writeSlice arr i count stream@ writes a stream to the array @arr@
244-- starting at index @i@ and writing up to @count@ elements in the forward
245-- direction ending at the index @i + count - 1@.
248{-# INLINE writeSlice #-}
249writeSlice :: (IsStream t, Monad m, Storable a)
250 => Array a -> Int -> Int -> t m a -> m ()
251writeSlice arr i len s = undefined
253-- | @writeSliceRev arr i count stream@ writes a stream to the array @arr@
254-- starting at index @i@ and writing up to @count@ elements in the reverse
255-- direction ending at the index @i - count + 1@.
258{-# INLINE writeSliceRev #-}
259writeSliceRev :: (IsStream t, Monad m, Storable a)
260 => Array a -> Int -> Int -> t m a -> m ()
261writeSliceRev arr i len s = undefined
264-------------------------------------------------------------------------------
266-------------------------------------------------------------------------------
268-- | Convert a stream of arrays into a stream of their elements.
271{-# INLINE flattenArrays #-}
272flattenArrays :: (IsStream t, MonadIO m, Storable a) => t m (Array a) -> t m a
273flattenArrays m = D.fromStreamD $ A.flattenArrays (D.toStreamD m)
275-- XXX should we have a reverseArrays API to reverse the stream of arrays
278-- | Convert a stream of arrays into a stream of their elements reversing the
279-- contents of each array before flattening.
282{-# INLINE _flattenArraysRev #-}
283_flattenArraysRev :: (IsStream t, MonadIO m, Storable a) => t m (Array a) -> t m a
284_flattenArraysRev m = D.fromStreamD $ A.flattenArraysRev (D.toStreamD m)
287-- > arraysOf n = FL.groupsOf n (FL.toArrayN n)
289-- Groups the elements in an input stream into arrays of given size.
292{-# INLINE arraysOf #-}
293arraysOf :: (IsStream t, MonadIO m, Storable a)
294 => Int -> t m a -> t m (Array a)
296 D.fromStreamD $ fromStreamDArraysOf n (D.toStreamD str)
298-- | Given a stream of arrays, splice them all together to generate a single
299-- array. The stream must be /finite/.
302{-# INLINABLE spliceArrays #-}
303spliceArrays :: (MonadIO m, Storable a) => SerialT m (Array a) -> m (Array a)
305 buffered <- S.foldr S.cons S.nil s
306 len <- S.sum (S.map length buffered)
308 arr <- liftIO $ A.newArray len
309 end <- S.foldlM' writeArr (aEnd arr) buffered
310 return $ arr {aEnd = end}
314 writeArr dst Array{..} =
315 liftIO $ withForeignPtr aStart $ \src -> do
316 let len = aEnd `minusPtr` src
317 memcpy (castPtr dst) (castPtr src) len
318 return $ dst `plusPtr` len
320-- | Create an 'Array' from a stream. This is useful when we want to create a
321-- single array from a stream of unknown size. 'writeN' is at least twice
322-- as efficient when the size is already known.
324-- Note that if the input stream is too large memory allocation for the array
325-- may fail. When the stream size is not known, `arraysOf` followed by
326-- processing of indvidual arrays in the resulting stream should be preferred.
329write :: (MonadIO m, Storable a) => SerialT m a -> m (Array a)
330write m = A.fromStreamD $ D.toStreamD m
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