[ACP] Impl `iter::Sum` (and `iter::Product`) for `num::Saturating<u*>`

[jmillikin]

Proposal

Problem statement

core::iter::Sum is implemented for types that can be created by summing a sequence of values. It's implemented for various integer types, and also the core::num::Wrapping wrapper type (which forces wrapped arithmetic). I propose that it should also be implemented for core::num::Saturating, which would force saturating arithmetic.

Per discussion (below), I'm only proposing to cover unsigned integer types. Summing over signed integers doesn't have an obviously correct behavior, and I don't want to get tangled up in that in my quest for saturating unsigned summation.

Motivating examples or use cases

I sometimes want to sum a set of integers that might cumulatively exceed some bound, without the risk of overflow (wrapping and crashing would both be bad).

For example, when assembling a record with max size isize::MAX from a set of smaller fields, I want to sum all the usize field sizes and then if summed_size > (isize::MAX as usize) { return Err(...); }. On 32-bit targets (e.g. WASM) this summation can easily overflow, so code that does field_sizes().iter().sum() is riskier than it looks.

Solution sketch

Adjust the integer_sum_product!() macro to add Saturating<T>, following the existing example of Wrapping<T> . This macro implements both iter::Sum and iter::Product for the relevant types.

For example, the macro-expanded impl of iter::Sum ends up looking like this:

impl core::iter::Sum for Saturating<$t> {
    fn sum<I: Iterator<Item = $t>>(iter: I) -> Self {
        iter.fold(Saturating(0), |a, b| a + b)  // a + b == a.saturating_add(b)
    }
}

Alternatives

The only alternative is "do nothing" -- both of the types are in the standard library, so users can't implement the glue trait themselves.

Links and related work

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[shepmaster]

the macro-expanded impl of iter::Sum ends up looking like this

Should it short-circuit?

[pitaj]

Should it short-circuit?

Good idea. Given saturation should usually be rare, it may not be worth the extra check. Unless there is no extra check because the saturation is implemented by a branch anyways.

[scottmcm]

Hmm, for signed it can't short-circuit, right? Dunno if that means it shouldn't for unsigned either.

[shepmaster]

Hmm, for signed it can't short-circuit

what should u8::MAX + 2 - 1 yield?

[pitaj]

Hmm yeah how should signed saturating sum be implemented? Saturating in from an unbounded integer type feels more intuitive to me.

[jmillikin]

I wouldn't mind implementing it only for unsigned types.

My intuition is that [i8::MAX, 2, -1].iter().sum() == Saturating(i8::MAX - 1), but if that isn't universal then I'd rather implement only unsigned saturation.

[the8472]

Promising exact short-circuiting may inhibit optimizations because we have to stop taking items the moment it saturates. Without or with sloppy short-circuiting we can take items in batches.

[jmillikin]

Regarding short-circuiting, I think having iter.sum() consume different amounts of items depending on the output type would be surprising to most users. There's no other iter::Sum implementations that behave like that, right?

The existing short-circuiting impls (Option and Result) require the inputs to also be of those types, which raises the idea of having two impls:

• Iterator::<Item = u32>::sum::<Saturating<u32>>() will consume the entire iterator, without short-circuiting.
• Iterator::<Item = Saturating<u32>>::sum::<Saturating<u32>>() will consume up to the entire iterator, returning immediately after reaching saturation ("exact short-circuiting").

[the8472]

That leaves the fastest option on the table.

[jmillikin]

That leaves the fastest option on the table.

Yep, that's true. An method on Iterator that might consume more or fewer items depending on internal compiler optimizations has too many sharp edges for me to be comfortable with, given the wide variety of impl Iterator types.

fn sum_and_next<I: Iterator<Item = u32>>(iter: &mut I) {
    let sum: Saturating<u32> = iter.sum();
    println!("sum: {sum:?}");

    // What does this print? Can the output change depending on compiler
    // optimization level? Use of gccrs / rustc_codegen_gcc ?
    println!("next: {:?}", iter.next());
}

There's probably room somewhere for a function shaped like (for example) &[u32] -> Saturating<u32> if people need to sum up some numbers really really fast and don't need to worry about iterator item counting.

[the8472]

It wouldn't be a compiler optimization, it would be in the library. E.g. we could call next_chunk to get a bunch of items and have that autovectorized.