Should memory overlap between arguments be allowed

[djelovina]

Currently there is no consistent assertion mechanism for the overlap.
e.g. this is not allowed

eWiseMul(z,x,x...)

while this is allowed

eWiseApply(z,x,x...)

[anyzelman]

Let's use this issue to discuss pros and cons first. For example, a pro is that allowing overlap results in a more flexible interface. A con is that to provide high-performance implementations, we have to account for all possible combinations of overlap.

One thing that should never be allowed are output containers overlapping with input containers, which does help curtail that con. However, "self-masking" (output masks overlapping with output containers) seems to be fine. So, e.g., eWiseMul( z, m, a, b, semiring ) with z, m, a, b vector containers would have to account for the following overlaps:

• z and m overlap,
• m and a overlap,
• m and b overlap,
• m, a, and b overlap,
• a and b overlap.

The following are illegal overlaps because of the input shall not overlap with output constraints:

• z, m, and a overlap,
• z, m, and b overlap,
• z, m, a, and b overlap,
• z and a overlap,
• z and b overlap,
• z, a, and b overlap.

So eWiseMul would have to provide 5 implementations (or sacrifice performance).

The present implementation seems to be closest to only allowing self-masking; i.e., allowing z and m to overlap, but nothing else; but this is inconsistently applied.

[anyzelman]

In terms of methodology, we could make a pass to disallow all overlaps including* self-masking, and then see if any of the standard algorithms presently provided would fail. This towards a pragmatic approach where we choose the option that best matches realistic use cases.

* edited this ~20 minutes later, easiest is ofc to make a pass to not allow any overlap and then see if anything breaks

[anyzelman]

In ALP/Dense, looks like we made the choice to not overlap anything (consider, e.g., views)

[anyzelman]

dot is a clear use-case where practically speaking, the same input vectors should be allowed.

• check whether it is allowed and whether aliasing is handled correctly

[anyzelman]

dot is a clear use-case where practically speaking, the same input vectors should be allowed.

* [ ]  check whether it is allowed and whether aliasing is handled correctly

I coincidentally did this check in the context of #379 . Dot allows the same input arguments, but does NOT handle overlap correctly. I will hence create a new sub-issue to address that.

[djelovina]

Summary of conclusion from #387

The representative aliasing case in this codebase is dot(scalar, v, v, ring): both input Vector arguments are const, the output is a separate scalar, and nothing is written through either aliased pointer.

This example demonstrates a use case where due to a complex vector-to-scalar reduction operation,
the two-vector-to-scalar is used to rexpress the reduction, and the same vector is passed as both inputs.

The correctness and performance are ensured. For example, the compiler can hoist loads out of the loop and fully vectorise,
because the __restrict__ annotations on the const input pointers allow all optimisations at the definition site. The aliased call at runtime is still correct (no writes occur) and achieves the same throughput as the non-aliased case.

On the other hand, in branch 387 we demonstrate that we can express complex single-vector-to-scalar reduction by defining a wrapper type and monoid, which allows us to avoid the aliasing issue entirely.

In the context of performance modelling, the fake two-vector-to-scalar (and similar) will be represented as a more complex operations than it actually is.

Therefore I would take this example as a case against aliased calls,

1. since the API is powerful enough to express the reduction without aliasing,
2. and it exposed clean performance semantics.