dph-prim-par-0.7.0.1: Data Parallel Haskell segmented arrays. (production version)

Safe HaskellNone

Data.Array.Parallel.Unlifted

Contents

Description

Parallel implementation of the segmented array API defined in dph-prim-interface.

Some of them don't yet have parallel implementations, so we fall back to the sequential ones from dph-prim-seq.

WARNING: Although this library is intended to be used as a target for the DPH vectoriser, it is also fine to use it directly from non DPH programs. However, this library does not support nested parallelism by itself. If you try to run further parallel computations in the workers passed to map, zipWith, fold etc, then they will just run sequentially.

Synopsis

Types

class (Unbox a, DT a) => Elt a Source

Instances

Elt Bool 
Elt Double 
Elt Float 
Elt Int 
Elt Word8 
(Unbox (a, b), DT (a, b), Elt a, Elt b) => Elt (a, b) 

type Array = VectorSource

Arrays are stored as unboxed vectors. They have bulk-strict semantics, so demanding one element demands them all.

Constructors

empty :: Elt a => Array aSource

O(1). Construct an array with no elements.

generate :: Elt a => Int -> (Int -> a) -> Array aSource

Generate a new array given its length and a function to compute each element.

replicate :: Elt a => Int -> a -> Array aSource

O(length result). Construct a new array by replicating a single element the given number of times.

replicate_s :: Elt a => Segd -> Array a -> Array aSource

O(length result). Segmented replicate.

Elements of the array are replicated according to the lengths of the segments defined by the Segd.

replicate_rs :: Elt a => Int -> Array a -> Array aSource

O(length result). Regular segmented replicate.

Like replicate_s, but all segments are assumed to have the given length.

repeatSource

Arguments

:: Elt a 
=> Int

Number of times to repeat the source.

-> Int

Length of source (can be less than the provided array).

-> Array a

Array elements to repeat.

-> Array a 

O(length result). Construct an array by copying a portion of another array.

indexed :: Elt a => Array a -> Array (Int, a)Source

O(length result). Tag each element of an array with its index.

indexed [42, 93, 13] = [(0, 42), (1, 93), (2, 13)]

(+:+) :: Elt a => Array a -> Array a -> Array aSource

O(length result). Append two arrays.

append_sSource

Arguments

:: Elt a 
=> Segd

Segment descriptor of result aarray.

-> Segd

Segment descriptor of first array.

-> Array a

Data of first array.

-> Segd

Segment descriptor of second array.

-> Array a

Data of second array.

-> Array a 

O(length result). Segmented append.

append_vsSource

Arguments

:: (Elt a, Elts a) 
=> Segd

Segment descriptor of result aarray.

-> VSegd

Segment descriptor of first array.

-> Arrays a

Data of first array.

-> VSegd

Segment descriptor of second array.

-> Arrays a

Data of second array.

-> Array a 

indices_s :: Segd -> Array IntSource

O(length result). Segmented indices.

Construct an array containing containing the segments defined by the given Segd.

Each segment will contain the elements [0..len-1] where len is the length of that segment.

Projections

length :: Elt a => Array a -> IntSource

O(1). Yield the number of elements in an array.

index :: Elt a => String -> Array a -> Int -> aSource

O(1). Retrieve a numbered element from an array.

The first argument gives a source-code location for out-of-bounds errors.

indexs :: Elt a => Array a -> Array Int -> Array aSource

O(length result). Scattered indexing from a single Array.

This is an alias for bpermute.

indexs_avsSource

Arguments

:: (Elt a, Elts a) 
=> Arrays a

Irregular 2D array of elements.

-> VSegd

Maps (segment id, segment index) pairs to 2D indices in the Arrays

-> Array (Int, Int)

Pairs of (segment id, segment index).

-> Array a 

O(length result). Scattered indexing through a VSegd.

The index array contains pairs of segment id and the index within that segment.

We use the VSegd to map the pairs to 2D indices within the Arrays, and return an array of the resulting elements.

extractSource

Arguments

:: Elt a 
=> Array a

Source array.

-> Int

Starting index in source array.

-> Int

Length of result array.

-> Array a 

O(length result). Extract a subrange of elements from an array.

extract [23, 42, 93, 50, 27] 1 3  = [42, 93, 50]

extracts_nss :: Elt a => SSegd -> Vector (Array a) -> Array aSource

O(length result). Extract segments defined by a SSegd from a vector of arrays.

NOTE: This is a transitory interface, and will be removed in future versions. Use extracts_ass instead.

extracts_assSource

Arguments

:: (Elt a, Elts a) 
=> SSegd

SSegd defining the slices to extract.

-> Arrays a

Source arrays.

-> Array a 

O(length result). Extract segments defined by a SSegd.

Extract all the segments defined by the SSegd from the Arrays, returning them concatenated in a fresh Array.

extracts_avsSource

Arguments

:: (Elt a, Elts a) 
=> VSegd

VSegd defining the slices to extract.

-> Arrays a

Source arrays.

-> Array a 

O(length result). Extract segments defined by a VSegd.

Extract all the segments defined by the VSegd from the Arrays, returning them concatenated in a fresh Array.

drop :: Elt a => Int -> Array a -> Array aSource

O(length result). Drop elements from the front of an array, returning the latter portion.

Update

updateSource

Arguments

:: Elt a 
=> Array a

Source array.

-> Array (Int, a)

Index and value of new elements.

-> Array a 

O(length result). Copy the source array while replacing some elements by new ones in the result.

Permutation

permuteSource

Arguments

:: Elt a 
=> Array a

Source array.

-> Array Int

Indices in the destination to copy elements to.

-> Array a 

O(length result). Forwards permutation of array elements.

bpermuteSource

Arguments

:: Elt a 
=> Array a

Source array.

-> Array Int

Indices in the source to copy elements from.

-> Array a 

O(length result). Backwards permutation of array elements.

bpermute [50, 60, 20, 30] [0, 3, 2] = [50, 30, 20]

mbpermute :: (Elt a, Elt b) => (a -> b) -> Array a -> Array Int -> Array bSource

Combination of map and bpermute.

The advantage of using this combined version is that we don't need to apply the parameter function to source elements that don't appear in the result.

bpermuteDft :: Elt e => Int -> (Int -> e) -> Array (Int, e) -> Array eSource

Default backwards permutation.

The values of the index-value pairs are written into the position in the result array that is indicated by the corresponding index.

All positions not covered by the index-value pairs will have the value determined by the initialiser function for that index position.

Zipping and Unzipping

zip :: (Elt a, Elt b) => Array a -> Array b -> Array (a, b)Source

O(1). Zip two arrays into an array of pairs. If one array is short, excess elements of the longer array are discarded.

zip3 :: (Elt a, Elt b, Elt c) => Array a -> Array b -> Array c -> Array (a, b, c)Source

O(1). Zip three arrays into an array of triples. If one array is short, excess elements of the longer arrays are discarded.

unzip :: (Elt a, Elt b) => Array (a, b) -> (Array a, Array b)Source

O(1). Unzip an array of pairs into a pair of arrays.

unzip3 :: (Elt a, Elt b, Elt c) => Array (a, b, c) -> (Array a, Array b, Array c)Source

O(1). Unzip an array of triples into a triple of arrays.

fsts :: (Elt a, Elt b) => Array (a, b) -> Array aSource

O(1). Take the first elements of an array of pairs.

snds :: (Elt a, Elt b) => Array (a, b) -> Array bSource

O(1). Take the second elements of an array of pairs.

Map and ZipWith

map :: (Elt a, Elt b) => (a -> b) -> Array a -> Array bSource

Apply a worker function to each element of an array, yielding a new array.

zipWith :: (Elt a, Elt b, Elt c) => (a -> b -> c) -> Array a -> Array b -> Array cSource

Apply a worker function to correponding elements of two arrays.

zipWith3 :: (Elt a, Elt b, Elt c, Elt d) => (a -> b -> c -> d) -> Array a -> Array b -> Array c -> Array dSource

Apply a worker function to corresponding elements of three arrays.

zipWith4 :: (Elt a, Elt b, Elt c, Elt d, Elt e) => (a -> b -> c -> d -> e) -> Array a -> Array b -> Array c -> Array d -> Array eSource

Apply a worker function to corresponding elements of four arrays.

zipWith5 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (a -> b -> c -> d -> e -> f) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array fSource

Apply a worker function to corresponding elements of five arrays.

zipWith6 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (a -> b -> c -> d -> e -> f -> g) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array f -> Array gSource

Apply a worker function to corresponding elements of six arrays.

zipWith7 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (a -> b -> c -> d -> e -> f -> g -> h) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array f -> Array g -> Array hSource

Apply a worker function to corresponding elements of seven arrays.

zipWith8 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (a -> b -> c -> d -> e -> f -> g -> h -> i) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array f -> Array g -> Array h -> Array iSource

Apply a worker function to corresponding elements of six arrays.

Scans and Folds

scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array aSource

Similar to foldl but return an array of the intermediate states, including the final state that is computed by foldl.

fold :: Elt a => (a -> a -> a) -> a -> Array a -> aSource

Undirected fold over an array.

  • The worker function must be associative.
  • The provided starting element must be neutral with respect to the worker. For example 0 is neutral wrt (+) and 1 is neutral wrt (*).

fold_s :: Elt a => (a -> a -> a) -> a -> Segd -> Array a -> Array aSource

Undirected segmented fold.

All segments are folded individually, and the result contains one element for each segment.

Same preconditions as fold.

fold_ss :: (Elts a, Elt a) => (a -> a -> a) -> a -> SSegd -> Arrays a -> Array aSource

Undirected scattered segmented fold.

Like fold_s, but the segments can be scattered through an Arrays.

Same preconditions as fold.

fold_vs :: (Elts a, Elt a) => (a -> a -> a) -> a -> VSegd -> Arrays a -> Array aSource

Undirected fold over virtual segments.

The physical segments defined by the VSegd are folded individually, and these results are replicated according to the virtual segment id table of the VSegd. The result contains as many elements as there virtual segments.

Same preconditions as fold.

fold_r :: Elt a => (a -> a -> a) -> a -> Int -> Array a -> Array aSource

Regular segmented fold.

All segements have the given length.

Same preconditions as fold.

fold1 :: Elt a => (a -> a -> a) -> Array a -> aSource

Undirected fold, using the first element to initialise the state.

  • The worker function must be associative.
  • The provided starting element must be neutral with respect to the worker. For example 0 is neutral wrt (+) and 1 is neutral wrt (*).
  • If the array contains no elements then you'll get a bounds check error.

fold1_s :: Elt a => (a -> a -> a) -> Segd -> Array a -> Array aSource

Like fold_s, but using the first element of each segment to initialise the state of that segment.

Same preconditions as fold1.

fold1_ss :: (Elts a, Elt a) => (a -> a -> a) -> SSegd -> Arrays a -> Array aSource

Like fold_ss, but using the first element of each segment to intialise the state of that segment.

Same preconditions as fold1.

fold1_vs :: (Elts a, Elt a) => (a -> a -> a) -> VSegd -> Arrays a -> Array aSource

Like fold_vs, but using the first element of each segment to initialise the state of that segment.

Same preconditions as fold1.

sum :: (Num a, Elt a) => Array a -> aSource

Same as fold (+) 0

sum_s :: (Num a, Elt a) => Segd -> Array a -> Array aSource

Same as fold_s (+) 0

sum_ss :: (Num a, Elts a, Elt a) => SSegd -> Arrays a -> Array aSource

Same as fold_ss (+) 0

sum_r :: (Num a, Elt a) => Int -> Array a -> Array aSource

Same as fold_r (+) 0

count :: (Elt a, Eq a) => Array a -> a -> IntSource

Count the number of elements in array that are equal to the given value.

count_s :: (Elt a, Eq a) => Segd -> Array a -> a -> Array IntSource

Segmented count.

count_ss :: (Elt a, Eq a) => SSegd -> Vector (Array a) -> a -> Array IntSource

Scattered segmented count.

NOTE: This is a transitory interface, and will be removed in future versions.

and :: Array Bool -> BoolSource

O(length source). Compute the conjunction of all elements in a boolean array.

Pack and Filter

pack :: Elt a => Array a -> Array Bool -> Array aSource

O(length result). Extract elements of an array where the associated flag is true.

packByTagSource

Arguments

:: Elt a 
=> Array a

data values

-> Array Tag

tag values

-> Tag

the tag of values to select

-> Array a

data values that had that tag

O(length result). Select the elements of an array that have a corresponding tag.

packByTag [12, 24, 42, 93] [1, 0, 0, 1] 0 = [24, 42]

filter :: Elt a => (a -> Bool) -> Array a -> Array aSource

Extract the elements from an array that match the given predicate.

pick :: (Elt a, Eq a) => Array a -> a -> Array BoolSource

Compute an array of flags indicating which elements match a given value.

pick [4, 5, 3, 6, 5, 2, 5] 5 = [F, T, F, F, T, F, T]

Combine and Interleave

combine :: Elt a => Array Bool -> Array a -> Array a -> Array aSource

Combine two arrays, using a flags array to tell us where to get each element from.

combine [T, F, F, T, T, F] [1, 2, 3] [4, 5, 6] = [1, 4, 5, 2, 3, 6]

combine2 :: Elt a => Array Tag -> SelRep2 -> Array a -> Array a -> Array aSource

Like combine, but use a precomputed selector to speed up the process.

See the description of mkSel2 for how this works.

interleave :: Elt a => Array a -> Array a -> Array aSource

Interleave the elements of two arrays.

interleave [1, 2, 3] [4, 5, 6] = [1, 4, 2, 5, 3, 6]

Selectors

mkSel2Source

Arguments

:: Array Tag

Tags array.

-> Array Int

Indices array.

-> Int

Number of elements taken from first source array.

-> Int

Number of elements taken from second source array.

-> SelRep2

Parallel selector representation.

-> Sel2 

O(1). Construct a selector.

A selector is a description of how to perform a combine operation.

Suppose we are evaluating the following expression:

combine [F,F,T,F,T,T] [1,2,3] [4,5,6] = [4,5,1,6,2,3]

This is difficult to parallelise. For each element in the result, the source array we get this element from depends on the tag values associated with all previous elements.

However, if we going to apply combine several times with the same flags array, we can precompute a selector that tells us where to get each element. The selector contains the original flags, as well as the source index telling us where to get each element for the result array.

For example:

tagsToIndices2 [F,F,T,F,T,T]   -- tags
             = [0,1,0,2,1,2]   -- indices

This says get the first element from index 0 in the second array, then from index 1 in the second array, then index 0 in the first array ...

The selector then consists of both the tag and indices arrays.

tagsSel2 :: Sel2 -> Array TagSource

O(1). Yield the tags array of a selector.

indicesSel2 :: Sel2 -> Array IntSource

O(1). Yield the indices array of a selector.

elementsSel2_0 :: Sel2 -> IntSource

O(1). Yield the number of elements that will be taken from the first array.

elementsSel2_1 :: Sel2 -> IntSource

O(1). Yield the number of elements that will be taken from the second array.

repSel2 :: Sel2 -> SelRep2Source

O(1). Yield the parallel representation of a selector.

tagsToSel2 :: Array Tag -> Sel2Source

O(n). Compute a selector from a tags array.

Selector Representations

mkSelRep2 :: Array Tag -> SelRep2Source

O(n). Construct a parallel selector representation.

A SelRep2 describes how to distribute the two data vectors corresponding to a Sel2 across several PEs.

Suppose we want to perform the following combine operation:

 combine [F,F,T,T,F,T,F,F,T] [A0,A1,A2,A3,A4] [B0,B1,B2,B3] 
   = [A0,A1,B0,B1,A2,B2,A3,A4,B3]

The first array is the flags array, that says which of the data arrays to get each successive element from. As combine is difficult to compute in parallel, if we are going to perform several combines with the same flags array, we can precompute a selector that tells us where to get each element. The selector contains the original flags, as well as the source index telling us where to get each element for the result array.

 flags:   [F,F,T,T,F,T,F,F,T]
 indices: [0,1,0,1,2,2,3,4,3]

Suppose we want to distribute the combine operation across 3 PEs. It's easy to split the selector like so:

            PE0                PE1               PE2
 flags:   [F,F,T]            [T,F,T]           [F,F,T] 
 indices: [0,1,0]            [1,2,2]           [3,4,3]

We now need to split the two data arrays. Each PE needs slices of the data arrays that correspond to the parts of the selector that were given to it. For the current example we get:

            PE0                PE1               PE2
 data_A:   [A0,A1]            [A2]              [A3,A4]
 data_B:   [B0]               [B1,B2]           [B3]

The SelRep2 contains the starting index and length of each of of these slices:

            PE0                PE1               PE2
      ((0, 0), (2, 1))   ((2, 1), (1, 2))  ((3, 3), (2, 1))
       indices   lens      indices  lens    indices  lens

indicesSelRep2 :: Array Tag -> SelRep2 -> Array IntSource

O(1). Take the indices field from a SelRep2.

elementsSelRep2_0 :: Array Tag -> SelRep2 -> IntSource

O(1). Yield the number of elements to take from the first array.

elementsSelRep2_1 :: Array Tag -> SelRep2 -> IntSource

O(1). Yield the number of elements to take from the second array.

Segment Descriptors

mkSegdSource

Arguments

:: Array Int

(lengths) Segment lengths.

-> Array Int

(indices) Segment indices.

-> Int

Total number of elements.

-> Segd 

O(max(segs, threads) . log segs). Construct a segment descriptor.

A segment desciptor defines an irregular 2D array based on a flat, 1D array of elements. The defined array is a nested array of segments, where every segment covers some of the elements from the flat array.

  • The starting indices must be equal to init (scanl (+) 0 lengths)
  • If you don't want to cover all the elements from the flat arrary then use a SSegd instead.

Example:

   flat array data: [1 2 3 4 5 6 7 8]
     (segmentation)  --- ----- - ---
     segd  lengths: [2, 3, 1, 2]
           indices: [0, 2, 5, 6]
          elements: 8 

validSegd :: Segd -> BoolSource

Check whether a Segd is well formed.

emptySegd :: SegdSource

O(1). Construct an empty Segd.

singletonSegd :: Int -> SegdSource

O(1). Construct a Segd containing a single segment of the given length.

lengthsToSegd :: Array Int -> SegdSource

O(max(segs, threads) . log segs). Construct a Segd from an array of segment lengths.

lengthSegd :: Segd -> IntSource

O(1). Yield the length of a Segd.

lengthsSegd :: Segd -> Array IntSource

O(1). Yield the segment lengths of a Segd.

indicesSegd :: Segd -> Array IntSource

O(1). Yield the segment starting indices of a Segd.

elementsSegd :: Segd -> IntSource

O(1). Yield the total number of elements defined by a Segd.

plusSegd :: Segd -> Segd -> SegdSource

O(max(segs, threads) . log segs). Add the lengths of corresponding segments in two descriptors.

plusSegd [lens: 2 3 1] [lens: 3 1 1] = [lens: 5 4 2]

Scattered Segment Descriptors

mkSSegdSource

Arguments

:: Array Int

(starts) Starting index of each segment within its flat array.

-> Array Int

(sources) Source id of flat array to get each segment from.

-> Segd

Plain segment descriptor giving the lengths of the segments.

-> SSegd 

Construct a Scattered Segment Descriptor.

A SSegd is an extension of a Segd that that allows the segments to be scattered through multiple flat arrays.

Each segment is associated with a source id that indicates what flat array it is in, along with the starting index in that flat array.

  • The segments need not cover the entire flat array.
  • Different segments may point to the same elements.

validSSegd :: SSegd -> BoolSource

Check whether a Segd is well formed.

emptySSegd :: SSegdSource

O(1). Construct an empty SSegd.

singletonSSegd :: Int -> SSegdSource

O(1). Construct a Segd containing a single segment of the given length.

promoteSegdToSSegd :: Segd -> SSegdSource

O(segs). Promote a Segd to a SSegd, assuming all segments are contiguous and come from a single array.

isContiguousSSegd :: SSegd -> BoolSource

O(1). True when a SSegd has been constructed by promoting a SSegd.

In this case all the data elements are in one contiguous flat array, and consumers can avoid looking at the real starts and sources fields.

lengthOfSSegd :: SSegd -> IntSource

O(1). Yield the length of a SSegd.

lengthsOfSSegd :: SSegd -> Array IntSource

O(1). Yield the segment lengths of a SSegd.

indicesOfSSegd :: SSegd -> Array IntSource

O(1). Yield the indices field of a SSegd.

startsOfSSegd :: SSegd -> Array IntSource

O(1). Yield the starts field of a SSegd.

sourcesOfSSegd :: SSegd -> Array IntSource

O(1). Yield the sources field of a SSegd.

getSegOfSSegd :: SSegd -> Int -> (Int, Int, Int, Int)Source

O(1). Get the length, segment index, starting index, and source id of a segment.

appendSSegd :: SSegd -> Int -> SSegd -> Int -> SSegdSource

Produce a segment descriptor that describes the result of appending two segmented arrays.

Virtual Segment Descriptors

mkVSegdSource

Arguments

:: Array Int

(vsegids) Mapping from virtual to physical segments.

-> SSegd

Scattered Segment descriptor defining the physical segments.

-> VSegd 

Construct a Virtual Segment Descriptor.

A VSegd is an extension of a SSegd that allows data from the underlying flat array to be shared between segments. For example, you can define an array of 10 virtual segments that all have the same length and elements as a single physical segment.

  • Internally we maintain the invariant that all physical segments must be reachable by some virtual segment. This is needed to ensure that operations such as fold_ss segmented fold have the right complexity.
  • If you don't need the invariant then you can sidestep the code that maintains it by using the redundant versions of the following operators, and sometimes get faster code.

validVSegd :: VSegd -> BoolSource

Check whether a Segd is well formed.

emptyVSegd :: VSegdSource

O(1). Construct an empty SSegd.

singletonVSegd :: Int -> VSegdSource

O(1). Construct a VSegd containing a single segment of the given length.

replicatedVSegdSource

Arguments

:: Int

Length of segment.

-> Int

Number of times replicated.

-> VSegd 

O(len). Construct a VSegd that describes an array where all virtual segments point to the same physical segment.

promoteSegdToVSegd :: Segd -> VSegdSource

O(segs). Promote a plain Segd to a VSegd.

The result contains one virtual segment for every physical segment the provided Segd.

promoteSSegdToVSegd :: SSegd -> VSegdSource

O(segs). Promote a plain SSegd to a VSegd.

The result contains one virtual segment for every physical segment the provided SSegd.

isManifestVSegd :: VSegd -> BoolSource

O(1). If true then the segments are all unshared, and the vsegids field be just [0..len-1].

Consumers can check this field to avoid demanding the vsegids field. This can avoid the need for it to be constructed in the first place, due to lazy evaluation.

isContiguousVSegd :: VSegd -> BoolSource

O(1). If true then the starts field is identical to the indices field and the sourceids are all 0s.

In this case all the data elements are in one contiguous flat array, and consumers can avoid looking at the real starts and sources fields.

lengthOfVSegd :: VSegd -> IntSource

O(1). Yield the length of a VSegd.

takeVSegidsOfVSegd :: VSegd -> Array IntSource

O(1). Yield the vsegids of a VSegd.

takeVSegidsRedundantOfVSegd :: VSegd -> Array IntSource

O(1). Yield the vsegids of a VSegd, but don't require that every physical segment is referenced by some virtual segment.

If you're just performing indexing and don't need the invariant that all physical segments are reachable from some virtual segment, then use this version as it's faster. This sidesteps the code that maintains the invariant.

The stated O(1) complexity assumes that the array has already been fully evalauted. If this is not the case then we can avoid demanding the result of a prior computation on the vsegids, thus reducing the cost attributed to that prior computation.

takeSSegdOfVSegd :: VSegd -> SSegdSource

O(1). Yield the SSegd of a VSegd.

takeSSegdRedundantOfVSegd :: VSegd -> SSegdSource

O(1). Yield the SSegd of a VSegd, but don't require that every physical segment is referenced by some virtual segment.

See the note in takeVSegidsRedundantOfVSegd.

takeLengthsOfVSegd :: VSegd -> Array IntSource

O(1). Yield the segment lengths of a VSegd.

getSegOfVSegd :: VSegd -> Int -> (Int, Int, Int)Source

O(1). Get the length, starting index, and source id of a segment.

unsafeDemoteToSSegdOfVSegd :: VSegd -> SSegdSource

O(segs). Yield a SSegd that describes each segment of a VSegd individually.

By doing this we lose information about which virtual segments correspond to the same physical segments.

WARNING: Trying to take the SSegd of a nested array that has been constructed with replication can cause index space overflow. This is because the virtual size of the corresponding flat data can be larger than physical memory. If this happens then indices fields and element count in the result will be invalid.

unsafeDemoteToSegdOfVSegd :: VSegd -> SegdSource

O(segs). Yield a Segd that describes each segment of a VSegd individually.

By doing this we lose information about which virtual segments correspond to the same physical segments.

See the warning in unsafeDemoteToSSegdOfVSegd.

updateVSegsOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegdSource

Update the vsegids of a VSegd, and then cull the physical segment descriptor so that all physical segments are reachable from some virtual segment.

updateVSegsReachableOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegdSource

Update the vsegids of VSegd, where the result is guaranteed to cover all physical segments.

Using this version avoids performing the cull operation which discards unreachable physical segments.

  • The resulting vsegids must cover all physical segments. If they do not then there will be physical segments that are not reachable from some virtual segment, and subsequent operations like fold_ss will have the wrong work complexity.

appendVSegdSource

Arguments

:: VSegd

Descriptor of first array.

-> Int

Number of flat physical arrays for first descriptor.

-> VSegd

Descriptor of second array.

-> Int

Number of flat physical arrays for second descriptor.

-> VSegd 

Produce a virtual segment descriptor that describes the result of appending two segmented arrays.

combine2VSegdSource

Arguments

:: Sel2

Selector for the combine operation.

-> VSegd

Descriptor of first array.

-> Int

Number of flat physical arrays for first descriptor.

-> VSegd

Descriptor of second array.

-> Int

Number of flat physical arrays for second descriptor.

-> VSegd 

Combine two virtual segment descriptors.

Irregular two dimensional arrays

class (Unboxes a, DT a) => Elts a Source

emptys :: Arrays aSource

O(1). Construct an empty Arrays with no elements.

singletons :: (Elt a, Elts a) => Array a -> Arrays aSource

O(1). Construct an Arrays consisting of a single Array.

lengths :: Elts a => Arrays a -> IntSource

O(1). Yield the number of Array in an Arrays.

unsafeIndexs :: (Elt a, Elts a) => Arrays a -> Int -> Array aSource

O(1). Take one of the outer Array from an Arrays.

unsafeIndex2s :: (Elt a, Elts a) => Arrays a -> Int -> Int -> aSource

O(1). Retrieve a single element from an Arrays, given the outer and inner indices.

appends :: (Elt a, Elts a) => Arrays a -> Arrays a -> Arrays aSource

O(n). Append two Arrays, using work proportional to the length of the outer array.

fromVectors :: (Elt a, Elts a) => Vector (Array a) -> Arrays aSource

O(number of inner arrays). Convert a boxed vector of Array to an Arrays.

toVectors :: (Elt a, Elts a) => Arrays a -> Vector (Array a)Source

O(number of inner arrays). Convert an Arrays to a boxed vector of Array.

Random arrays

randoms :: (Elt a, Random a, RandomGen g) => Int -> g -> Array aSource

Generate an array of the given length full of random data. Good for testing.

randomRs :: (Elt a, Random a, RandomGen g) => Int -> (a, a) -> g -> Array aSource

Generate an array of the given length full of random data. Good for testing.

Array IO

class UIO a => IOElt a Source

Instances

IOElt Double 
IOElt Int 
(UIO (a, b), IOElt a, IOElt b) => IOElt (a, b) 

hGet :: IOElt a => Handle -> IO (Array a)Source

Read an array from a file.

hPut :: IOElt a => Handle -> Array a -> IO ()Source

Write an array to a file.

toList :: Elt a => Array a -> [a]Source

Convert an array to a list of elements.

fromList :: Elt a => [a] -> Array aSource

Convert a list of elements to an array.