Investigate panic behavior of sum

[steveklabnik]

Originally reported on HN: https://news.ycombinator.com/item?id=12316209

Basically, the docs for Iterator::sum say

Panics

When calling sum and a primitive integer type is being returned, this method will panic if the computation overflows.

Is this a special behavior of sum, or is this just the regular behavior of arithmetic? If it's the latter, then these docs are probably wrong / unnecessary.

I am not sure, but am willing to bet that this might just be out of date. To resolve this ticket, either the behavior should be confirmed, or the docs should be updated.

[mike-bourgeous]

pbsd posted this: https://news.ycombinator.com/item?id=12316401

[Stebalien]

There's a key difference between iter.sum() and a + b: I can detect overflow in a + b with a.checked_add(b).unwrap() but there's no way to do so with sum. Really, we should have a checked_sum for this.

As for performance, this appears to be preventing auto-vectorization which is rather unfortunate for a method for adding up a bunch of numbers. It's theoretically possible to vectorize and detect overflows but LLVM isn't that smart.

Benchmark:

#![feature(test)]
extern crate test;

use test::Bencher;

#[bench]
fn sum(b: &mut Bencher) {
    let numbers: Vec<i32> = (1..1000).collect();
    b.iter(|| {
        let out: i32 = test::black_box(&numbers).iter().sum();
        test::black_box(out);
    });
}

#[bench]
fn forloop(b: &mut Bencher) {
    let numbers: Vec<i32> = (1..1000).collect();
    b.iter(|| {
        let mut out = 0i32;
        for i in test::black_box(&numbers) {
            out += *i;
        }
        test::black_box(out);
    })
}

Results:

running 2 tests
test forloop ... bench:          67 ns/iter (+/- 1)
test sum     ... bench:         638 ns/iter (+/- 18)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured

[sfackler]

sum and prod currently use checked_add/checked_mul explicitly: https://github.com/rust-lang/rust/blob/master/src/libcore/iter/traits.rs#L593.

This is obviously not ideal, but we do it that way because unlike with your own crate or third party crates, libstd is compiled ahead of time so you can't choose if you want overflow to panic or not. I can't find the issue, but I believe MIR in particular makes this the case even for things that are inlined. @alexcrichton, do you remember the details here?

[alexcrichton]

Yes this documentation is both explicit and correct. MIR forces us to make a decision about overflow in the standard library, we can't rely on changing it when it's monomorphized.

[dten]

https://twitter.com/CryZe107/status/769498246930661376

short discussion about this here. personally I think it's a shame that the swapping fold(0, Add:add) for sum() results it such a performance hit

Docs perhaps could mention that it's checked_add

[sfackler]

I believe we just need to add a #[rustc_inherit_overflow_checks] to all of the Sum/Product implementations:

rust/src/libcore/iter/mod.rs

Line 1106 in 7a187c3

#[rustc_inherit_overflow_checks]