Safe Haskell | None |
---|
Virtual Segment Descriptors.
See Data.Array.Parallel.Unlifted for how this works.
- data UVSegd = UVSegd {}
- valid :: UVSegd -> Bool
- mkUVSegd :: Vector Int -> USSegd -> UVSegd
- fromUSegd :: USegd -> UVSegd
- fromUSSegd :: USSegd -> UVSegd
- empty :: UVSegd
- singleton :: Int -> UVSegd
- replicated :: Int -> Int -> UVSegd
- isManifest :: UVSegd -> Bool
- isContiguous :: UVSegd -> Bool
- length :: UVSegd -> Int
- takeVSegids :: UVSegd -> Vector Int
- takeVSegidsRedundant :: UVSegd -> Vector Int
- takeUSSegd :: UVSegd -> USSegd
- takeUSSegdRedundant :: UVSegd -> USSegd
- takeLengths :: UVSegd -> Vector Int
- getSeg :: UVSegd -> Int -> (Int, Int, Int)
- appendWith :: UVSegd -> Int -> UVSegd -> Int -> UVSegd
- combine2 :: USel2 -> UVSegd -> Int -> UVSegd -> Int -> UVSegd
- updateVSegs :: (Vector Int -> Vector Int) -> UVSegd -> UVSegd
- updateVSegsReachable :: (Vector Int -> Vector Int) -> UVSegd -> UVSegd
- unsafeDemoteToUSSegd :: UVSegd -> USSegd
- unsafeDemoteToUSegd :: UVSegd -> USegd
Types
Virtual segment descriptor.
UVSegd | |
|
Consistency check
O(1). Check the internal consistency of a virutal segmentation descriptor.
Constructors
:: Vector Int | (vsegids) Mapping from virtual to physical segments. |
-> USSegd | Scattered Segment descriptor defining the physical segments. |
-> UVSegd |
O(1). Construct a new virtual segment descriptor. All the provided arrays must have the same lengths.
fromUSegd :: USegd -> UVSegdSource
O(segs). Promote a plain Segd
to a VSegd
.
The result contains one virtual segment for every physical segment
the provided SSegd
.
fromUSSegd :: USSegd -> UVSegdSource
singleton :: Int -> UVSegdSource
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 UVSegd
that describes an array created by replicating
a single segment several times.
Predicates
isManifest :: UVSegd -> 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 generated in the first place, due to lazy evaluation.
isContiguous :: UVSegd -> BoolSource
O(1). Checks whether the starts are identical to the usegd indices field and the sourceids 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 :: UVSegd -> Vector IntSource
O(1). Take the vsegids of a UVSegd
, 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.
takeUSSegdRedundant :: UVSegd -> USSegdSource
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 :: UVSegd -> Vector IntSource
O(segs). Yield the lengths of the segments described by a UVSegd
.
getSeg :: UVSegd -> Int -> (Int, Int, Int)Source
O(1). Get the length, starting index, and source id of a segment.
Operators
:: UVSegd | Descriptor of first array. |
-> Int | Number of flat physical arrays for first descriptor. |
-> UVSegd | Descriptor of second array. |
-> Int | Number of flat physical arrays for second descriptor. |
-> UVSegd |
O(n) Produce a segment descriptor describing the result of appending two arrays.
:: USel2 | Selector for the combine operation. |
-> UVSegd | Descriptor of first array. |
-> Int | Number of flat physical arrays for first descriptor. |
-> UVSegd | Descriptor of second array. |
-> Int | Number of flat physical arrays for second descriptor. |
-> UVSegd |
O(n). Combine two virtual segment descriptors.
updateVSegs :: (Vector Int -> Vector Int) -> UVSegd -> UVSegdSource
Update the vsegids of UPVSegd
, and then cull the physical
segment descriptor so that all phsyical 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) -> UVSegd -> UVSegdSource
Update the vsegids of UPVSegd
, where the result covers
all 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 performing operations like segmented fold will waste work.
- Using this version saves performing the
cull
operation which discards unreachable physical segments. This is O(result segments), but can be expensive in absolute terms.
unsafeDemoteToUSegd :: UVSegd -> USegdSource
O(segs). Yield a USegd
that describes each segment of a UVSegd
individually, assuming all segments have been concatenated to
remove scattering.
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.