Improved arithmetic operations for arrays

Start with the ArrayBase documentation on Arithmetic Operations and review related issues #697, #83, and #478. Compare the proposed ownership, broadcasting, copying, allocation, and compile-time concerns, then narrow the collaborative issue to a specific implementation goal with measurable completion criteria.

(This is a collaborative issue, please edit and add points, if applicable, or join the discussion in the issue below)

For context, please read the ArrayBase documentation on Arithmetic Operations first.

Goals

• Ease of use: Arithmetic operations should be available when the user expects it
• Transparency: It should be possible to understand how much copying and allocation is involved in an operation
• Performance
  A. Allocate only what's needed and reuse when possible
  B. Copy only what's needed, compute and insert in place otherwise
  C. Autovectorization and vectorization — single threaded performance of the computation

Non-Goals

Parallelization and multithreading is not in scope for this issue

Prioritization

• I think we should continue to focus on primitive numeric types as operands, these are always the most important, while improving the situation for generic array elements. This focus means that we can accept solutions that are perfect for primitives but not yet perfect for other elements.

Known Problems in Current Implementation

• Excessive copying of the whole array.
  • Example: In &A @ &A we use self.to_owned().add(rhs) to implement it, while it could be implemented without copying the first operand's data
• Excessive copying of elements: We use elt1.clone() + elt2.clone() in some places.
  • The alternative would be: Use by-reference operators or other general interface
  • Copying primitive numeric types (integers, floats) like this is not a problem, and for this reason, the current implementation only has a problem when concerning non-primitive array elements.
• Right hand side and left hand side scalar operands are implemented in completely different ways, due to Rust limitations in how this is expressed.
  • We should continue to strive for symmetry in which operands are supported on the lhs and rhs. But as a compromise, in generic code, we can document that users sometimes must prefer array-scalar operations where the scalar is the right hand side operand(?)

Expanding the Number of Implementations

• Proposed solution: Where a &A is expected, also permit consuming an array A
  • Before: "a += &x.dot(y);"
  • After: "a += x.dot(y);"
  • Drawback is that it compiles despite wasting an allocated array - in some cases, it could have been done in-place instead, maybe avoiding the allocated array altogether
  • But note, an in place operation could be more efficent - Zip allows the user many ways to write in place operations themselves, and in this case, there's general_mat_mut which can perform the operation A += X × Y in place.
• Proposed improvement: Where &A is expected, also permit &mut A
  • But this is a combinatoric explosion. &A @ &A turns into four possibilities if we permit both &A and &mut A - How to avoid this?

Which solution is better for compile time?

A. Make impl blocks more generic (admitting more array kinds per impl, for example admitting both &A and &mut A)
B. Expand the number of impls to cover all cases (for example, one for each combination of &A/&mut A)

Consider both plain ndarray "cargo build" compile time, and compile time when ndarray is used in a project and compiles to non-generic code.

Co-broadcasting for Dynamic dimensionality

For static dimensionality array operations we use right hand side broadcasting: in A @ B, we can attempt to broadcast B to the shape of A.

For dynamic dimensionality operations, we can improve this to co-broadcasting so that A @ B can result in an array with a shape that's neither that of A or B.

Note: Co-broadcasting only ever expands the number of arrays that are compatible in operations, it does not change the result of operations that are already permitted by the right hand side broadcasting rule.

Related issues:

• Additional arithmetic operations/variants #697
• Previously decided: Don't mutate ArrayViewMut in place: Non-assignment binary operations shouldn't mutate input #83
• (Tangentially related): and_broadcast_mut for Zip #478