Version 15 (modified by chak, 5 years ago) (diff)


Preventing space blow-up due to replicate

The problem





treeLookup table xx
  | lengthP xx == 1
  | otherwise
  = let len     = lengthP xx
        half    = len `div` 2
        s1      = sliceP 0    half xx
        s2      = sliceP half half  xx           


What's happening here?


A plan to fix the problem


Repeated segments





Collapse repeated segments

In practice, segments descriptors store more information than just the segment length. They at least additionally store the start position of each segment in the data array. In the conventional representation, an invariant is that the start positions are such that the segments don't overlap. To represent arrays with repeated segments more efficiently, we propose to relax that invariant. Specifically, all start positions of a contiguous sequence of repeated segments are the same; i.e., the segment data is stored only once per sequence of repeated segments.

Then, we have for [:[:1, 2, 3:], [:1, 2, 3:], [:1, 2, 3:]:],

start: [:0, 0, 0:]
len:   [:3, 3, 3:]
data:  [:1, 2, 3:])


data:  [:1, 2, 3:])


Operations on arrays with repeated segments

As multiple segments overlap in arrays with repeated segments, array consumers need to be adapted to work correctly in this situation.

Lifted indexing

In the smvm example, a replicated array is consumed by lifted indexing to extract matching elements of the vector for all non-zero elements of the matrix. Using just an length array as a segment descriptor without overlapping segments, lifted indexing might be implemented as follows:


With overlapping segments, we have


In the case of smvm, where the first argument is produced by replicatePA (lengthPA row) v, we have as_start = replicatePA (lengthPA row) 0 and as-data = v. In other words, lifted indexing draws from a single copy of v, which is what we wanted.


TODO rl's exmaple

Multiple levels of nesting

TODO What if we have segment descriptors on top of one with repeated segments?

Related work

  • Blelloch's work on the space-behaviour of data-parallel programs.


A plan to fix the problem



The trouble with indices


In the treeLookup example, the table is replicated and grows exponentially. But it is a segmented structure (one segment per copy of the original array) and it is accessed in the base case by a lifted index operation. When you look at the input to that application of lifted indexing, its first argument is huge (the replicated table), but the second argument contains the same data as the original value of xx, albeit segmented into an array with one segment per element. So we have effectively got


Note how the xx_i are unchanged. It is only in the implementation of (!^) that the xx_i are blown up to index into the data vector of [:table, table, ...., table:] (which is concatP [:table, table, ...., table:]). It is that multiplication of the xx_i with the prescaned segment descriptor of [:table, table, ...., table:] that will overflow. Notice how that is internal to the implementation of (!^). If the first argument of (!^) is a replicated structure, there is no need whatsoever to perform that multiplication (and subsequent division) and the indices never overflow!

Never take the length of a replicated array

Unfortunately, not only indices blow out, the length of replicated arrays may also overflow 64bit integers. Hence, the consuming code must carefully avoid to take the length of such arrays. This is only the case for replicatePs introduced by the vectoriser. It is the responsibility of the DPH user to ensure that replicatePs that are explicit in the user code do not blow out. (We may want to switch to 64bit indices —at least on 64bit builds— anyway.)

Concrete implementation of replicated arrays


Replicating and slicing

