Safe Haskell | Safe-Infered |
---|
Parallel virtual segment descriptors.
See Data.Array.Parallel.Unlifted for how this works.
- data UPVSegd
- valid :: UPVSegd -> Bool
- mkUPVSegd :: Vector Int -> UPSSegd -> UPVSegd
- fromUPSegd :: UPSegd -> UPVSegd
- fromUPSSegd :: UPSSegd -> UPVSegd
- empty :: UPVSegd
- singleton :: Int -> UPVSegd
- replicated :: Int -> Int -> UPVSegd
- isManifest :: UPVSegd -> Bool
- isContiguous :: UPVSegd -> Bool
- length :: UPVSegd -> Int
- takeVSegids :: UPVSegd -> Vector Int
- takeVSegidsRedundant :: UPVSegd -> Vector Int
- takeUPSSegd :: UPVSegd -> UPSSegd
- takeUPSSegdRedundant :: UPVSegd -> UPSSegd
- takeLengths :: UPVSegd -> Vector Int
- getSeg :: UPVSegd -> Int -> (Int, Int, Int)
- unsafeDemoteToUPSSegd :: UPVSegd -> UPSSegd
- unsafeDemoteToUPSegd :: UPVSegd -> UPSegd
- updateVSegs :: (Vector Int -> Vector Int) -> UPVSegd -> UPVSegd
- updateVSegsReachable :: (Vector Int -> Vector Int) -> UPVSegd -> UPVSegd
- appendWith :: UPVSegd -> Int -> UPVSegd -> Int -> UPVSegd
- combine2 :: UPSel2 -> UPVSegd -> Int -> UPVSegd -> Int -> UPVSegd
Types
Parallel Virtual Segment descriptor.
Show UPVSegd | |
PprPhysical UPVSegd | Pretty print the physical representation of a |
Consistency check
valid :: UPVSegd -> BoolSource
O(1). Check the internal consistency of a virutal segmentation descriptor.
Constructors
:: Vector Int | Array saying which physical segment to use for each virtual segment. |
-> UPSSegd | Scattered segment descriptor defining the physical segments. |
-> UPVSegd |
O(1). Construct a new virtual segment descriptor.
fromUPSegd :: UPSegd -> UPVSegdSource
fromUPSSegd :: UPSSegd -> UPVSegdSource
singleton :: Int -> UPVSegdSource
O(1). Construct a singleton segment descriptor. The single segment covers the given number of elements in a flat array with sourceid 0.
O(1). Construct a UPVSegd
that describes an array created by replicating
a single segment several times.
Predicates
isManifest :: UPVSegd -> BoolSource
O(1). Checks whether all the segments are manifest (unshared / non-virtual). If this is the case, then the vsegids field will be [0..len-1].
Consumers can check this field, avoid demanding the vsegids field. This can avoid the need for it to be constructed in the first place, due to lazy evaluation.
isContiguous :: UPVSegd -> BoolSource
O(1). True when the starts are identical to the usegd indices field and the sources are all 0's.
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.
Projections
takeVSegidsRedundant :: UPVSegd -> Vector IntSource
O(1). Take the vsegids of a UPVSegd
, 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.
takeUPSSegdRedundant :: UPVSegd -> UPSSegdSource
O(1). Take the UPSSegd
of a UPVSegd
, but don't require that every physical
segment is referenced by some virtual segment.
See the note in takeVSegidsRedundant
.
takeLengths :: UPVSegd -> Vector IntSource
O(segs). Yield the lengths of the segments described by a UPVSegd
.
getSeg :: UPVSegd -> Int -> (Int, Int, Int)Source
O(1). Get the length, starting index, and source id of a segment.
Demotion
unsafeDemoteToUPSSegd :: UPVSegd -> UPSSegdSource
O(segs). Yield a UPSSegd
that describes each segment of a UPVSegd
individually.
By doing this we lose information about which virtual segments correspond to the same physical segments.
WARNING: Trying to take the UPSegd
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.
unsafeDemoteToUPSegd :: UPVSegd -> UPSegdSource
O(segs). Yield a UPSegd
that describes each segment of a UPVSegd
individually, assuming all segments have been concatenated to
remove scattering.
- See the warning in
unsafeDemoteToUPSSegd
.
Operators
updateVSegs :: (Vector Int -> Vector Int) -> UPVSegd -> UPVSegdSource
Update the vsegids of a UPVSegd
, and then cull the physical
segment descriptor so that all physical segments are reachable from
some virtual segment.
This function lets you perform filtering operations on the virtual segments, while maintaining the invariant that all physical segments are referenced by some virtual segment.
updateVSegsReachable :: (Vector Int -> Vector Int) -> UPVSegd -> UPVSegdSource
Update the vsegids of UPVSegd
, where the result is guaranteed to
cover all physical segments.
Using this version saves 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 segmented fold will have the wrong work complexity.
:: UPVSegd | Descriptor of first array. |
-> Int | Number of flat physical arrays for first descriptor. |
-> UPVSegd | Descriptor of second array. |
-> Int | Number of flat physical arrays for second descriptor. |
-> UPVSegd |
Produce a segment descriptor that describes the result of appending two arrays.