coeus-ops 0.14.0

Numerical tensor operators for Coeus.
Documentation
// ── scatter_add — accumulate source values into output at given indices ──
//
// `scatter_add(input, dim, index, src)` builds an output tensor equal to
// `input` with `src` values accumulated at positions specified by `index`:
//
//   out[i0, …, index[i0, …, id, …, iN], …, iN] += src[i0, …, id, …, iN]
//
// This is the exact semantic of `torch.scatter_add(input, dim, index, src)`.
//
// Shape contract:
// - `input`, `index`, and `src` must have the same number of dimensions.
// - `index` and `src` must have the same shape.
// - Every dimension of `index` must be ≤ the corresponding dimension of `src`.
//
// `scatter_add` is the **backward operator** of `gather`: if `out = gather(x, dim, idx)`,
// then `dx = scatter_add(zeros_like(x), dim, idx, grad_out)`.

use coeus_core::{ComputeBackend, CpuAddressableStorage, CpuAddressableStorageMut, Scalar};
use coeus_tensor::Tensor;

/// Scatter-accumulate: `out = input` then `out[…, index[…,k,…], …] += src[…,k,…]`.
///
/// Returns a new tensor (does not mutate `input`).
///
/// # Panics
/// - ndim mismatch between `input`, `index`, `src`.
/// - `index` and `src` shapes must match.
/// - `dim` out of range.
/// - Any index value ≥ `input.shape()[dim]`.
#[inline]
pub fn scatter_add<T: Scalar, B: ComputeBackend + Default>(
    input: &Tensor<T, B>,
    dim: usize,
    index: &Tensor<T, B>,
    src: &Tensor<T, B>,
    backend: &B,
) -> Result<Tensor<T, B>, B::Error>
where
    B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
{
    let ndim = input.ndim();
    assert_eq!(ndim, index.ndim(), "scatter_add: input/index ndim mismatch");
    assert_eq!(ndim, src.ndim(), "scatter_add: input/src ndim mismatch");
    assert_eq!(
        index.shape(),
        src.shape(),
        "scatter_add: index and src shapes must match"
    );
    assert!(
        dim < ndim,
        "scatter_add: dim {dim} out of range for {ndim}-D tensor"
    );

    let out_shape = input.shape().to_vec();
    let idx_shape = index.shape().to_vec();

    let in_cont = input.to_contiguous()?;
    let idx_cont = index.to_contiguous()?;
    let src_cont = src.to_contiguous()?;

    let in_s = in_cont.as_slice();
    let idx_s = idx_cont.as_slice();
    let src_s = src_cont.as_slice();

    // Zero-copy fast path: if src contributes no updates, scatter_add is identity.
    if src_s
        .iter()
        .all(|v| <T as coeus_core::NumericElement>::to_f64(*v) == 0.0)
    {
        return input.to_contiguous();
    }

    // Compute strides for output (row-major).
    let mut out_strides = vec![1usize; ndim];
    for d in (0..ndim - 1).rev() {
        out_strides[d] = out_strides[d + 1] * out_shape[d + 1];
    }

    // Compute strides for index/src (row-major).
    let idx_numel: usize = idx_shape.iter().product();
    let mut idx_strides = vec![1usize; ndim];
    for d in (0..ndim - 1).rev() {
        idx_strides[d] = idx_strides[d + 1] * idx_shape[d + 1];
    }

    // Allocate the result once and copy the input into it. Keeping the result
    // in backend storage avoids the temporary host vector and the second
    // tensor allocation that made allocation counts depend on the shape.
    let out_dim = out_shape[dim];
    // SAFETY: The following operation writes every output element before it is read.
    let mut output = unsafe { Tensor::alloc_on(out_shape, backend) }?;
    output.as_mut_slice()?.copy_from_slice(in_s);
    let out_s = output.as_mut_slice()?;

    for flat in 0..idx_numel {
        let scatter_idx = <T as coeus_core::NumericElement>::to_f64(idx_s[flat]) as usize;
        assert!(
            scatter_idx < out_dim,
            "scatter_add: index {scatter_idx} out of bounds for dim {dim} size {out_dim}"
        );

        // Decode `flat` against the index strides and accumulate the output
        // offset in one pass; `dim` takes the scattered coordinate instead.
        // Each coordinate is consumed by the iteration that produces it, so no
        // per-element coordinate buffer exists.
        let mut rem = flat;
        let mut out_flat = 0usize;
        for d in 0..ndim {
            let coord = rem / idx_strides[d];
            rem %= idx_strides[d];
            let c = if d == dim { scatter_idx } else { coord };
            out_flat += c * out_strides[d];
        }

        out_s[out_flat] = out_s[out_flat].add(src_s[flat]);
    }

    Ok(output)
}

#[cfg(test)]
mod tests {
    use super::*;
    use coeus_core::SequentialBackend;
    use coeus_tensor::Tensor;

    #[test]
    fn scatter_add_zero_src_returns_shared_storage() {
        let b = SequentialBackend::new();
        let x = Tensor::from_slice(vec![4], &[1.0f32, 2.0, 3.0, 4.0])
            .expect("invariant: test backend operation succeeds");
        let idx = Tensor::from_slice(vec![2], &[1.0f32, 3.0])
            .expect("invariant: test backend operation succeeds");
        let src = Tensor::from_slice(vec![2], &[0.0f32, 0.0])
            .expect("invariant: test backend operation succeeds");
        let out = scatter_add(&x, 0, &idx, &src, &b).expect("invariant: test operation succeeds");
        assert_eq!(out.shape(), &[4]);
        assert_eq!(out.as_slice(), x.as_slice());
        assert_eq!(out.as_slice().as_ptr(), x.as_slice().as_ptr());
    }
}