10 | | Here the variable 'v' is constant in the array comprehensions and will be replicated while lifting the expression `v !: i`. In other words, for every single element in a `row`, lifting implies the allocation of a separate copy of of the entire array `v` — and this only to perform a single indexing operation on that copy of `v`. More precisely, in the lifted code, lifted indexing (which we usually denote by `(!^)` is applied to a nested array consisting of multiple copies of `v`; i.e., it is applied to the result of `replicateP (length row) v`. |
| 10 | Here the variable 'v' is constant in the array comprehensions and will be replicated while lifting the expression `v !: i`. In other words, for every single element in a `row`, lifting implies the allocation of a separate copy of of the entire array `v` — and this only to perform a single indexing operation on that copy of `v`. More precisely, in the lifted code, lifted indexing (which we usually denote by `(!:^)` is applied to a nested array consisting of multiple copies of `v`; i.e., it is applied to the result of `replicateP (length row) v`. |
| 55 | Then, we have for `[:[:1, 2, 3:], [:1, 2, 3:], [:1, 2, 3:]:]`, |
| 56 | {{{ |
| 57 | start: [:0, 0, 0:] |
| 58 | len: [:3, 3, 3:] |
| 59 | data: [:1, 2, 3:]) |
| 60 | }}} |
| 61 | and for `[:[:1, 2:], [:1, 2:], [:3:], [:3:], [:3:]:]`, |
| 62 | {{{ |
| 63 | start: [:0, 0, 2, 2, 2:] |
| 64 | len: [:2, 2, 1, 1, 1:] |
| 65 | data: [:1, 2, 3:]) |
| 66 | }}} |
| 67 | |
| 68 | This is merely a change in the array representation that does not affect vectorisation. |
| 69 | |
| 70 | == Operations on arrays with repeated segments == |
| 71 | |
| 72 | As multiple segments overlap in arrays with repeated segments, array consumers need to be adapted to work correctly in this situation. |
| 73 | |
| 74 | === Lifted indexing === |
| 75 | |
| 76 | 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: |
| 77 | {{{ |
| 78 | (as_len, as_data) !:^ is = bpermute ((prescan (+) 0 as_len) +^ is) as_data |
| 79 | }}} |
| 80 | |
| 81 | With overlapping segments, we have |
| 82 | {{{ |
| 83 | (as_start, as_len, as_data) !:^ is = bpermute (as_start +^ is) as_data |
| 84 | }}} |
| 85 | In the case of `smvm`, where the first argument is produced by `replicateP (length row) v`, we have `as_start = replicate (length row) 0` and `as-data = v`. In other words, lifted indexing draws from a single copy of `v`, which is what we wanted. |
| 86 | |