LINQ `Sum` behavior change

[PetSerAl]

Description

84519 introduce vectorization into LINQ Sum for int and long. Vectorization change the order in which number summed. In certain cases this affect whenever OverflowException will be thrown.

Reproduction Steps

IEnumerable<int> Test1() {
    for(int i = 0; i < 32; ++i) {
        yield return 1_000_000_000;
        yield return -1_000_000_000;
    }
}

IEnumerable<int> Test2() {
    for(int i = 0; i < 32; ++i) {
        yield return 100_000_000;
    }
    for(int i = 0; i < 32; ++i) {
        yield return -100_000_000;
    }
}

Test1().Sum();
Test1().ToArray().Sum();
Test2().Sum();
Test2().ToArray().Sum();

Expected behavior

Test1().Sum();           // 0
Test1().ToArray().Sum(); // 0
Test2().Sum();           // OverflowException
Test2().ToArray().Sum(); // OverflowException

Actual behavior

Test1().Sum();           // 0
Test1().ToArray().Sum(); // OverflowException
Test2().Sum();           // OverflowException
Test2().ToArray().Sum(); // 0

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

[ghost]

Tagging subscribers to this area: @dotnet/area-system-linq See info in area-owners.md if you want to be subscribed.

Issue Details

---

### Description #84519 introduce vectorization into LINQ `Sum` for `int` and `long`. Vectorization change the order in which number summed. In certain cases this affect whenever `OverflowException` will be thrown. ### Reproduction Steps ```c# IEnumerable Test1() { for(int i = 0; i < 32; ++i) { yield return 1_000_000_000; yield return -1_000_000_000; } } IEnumerable Test2() { for(int i = 0; i < 32; ++i) { yield return 100_000_000; } for(int i = 0; i < 32; ++i) { yield return -100_000_000; } } Test1().Sum(); Test1().ToArray().Sum(); Test2().Sum(); Test2().ToArray().Sum(); ``` ### Expected behavior ```c# Test1().Sum(); // 0 Test1().ToArray().Sum(); // 0 Test2().Sum(); // OverflowException Test2().ToArray().Sum(); // OverflowException ``` ### Actual behavior ```c# Test1().Sum(); // 0 Test1().ToArray().Sum(); // OverflowException Test2().Sum(); // OverflowException Test2().ToArray().Sum(); // 0 ``` ### Regression? _No response_ ### Known Workarounds _No response_ ### Configuration _No response_ ### Other information _No response_

Author:	PetSerAl
Assignees:	-
Labels:	`area-System.Linq`, `untriaged`
Milestone:	-

[jeffhandley]

Talked with @tannergooding about this. We're leaning toward keeping the new behavior that works well with vectorized implementations. For consistency across configurations though (such as when intrinsics are disabled), the naive implementation would need to be updated. Its new behavior would be to avoid the overflow exceptions through upcasting until the final result is achieved (and checked against the result type). If we stick with the previous behavior, our ability to vectorize this method is substantially hindered.

Assuming the inconsistency is unacceptable, our .NET 8 resolution options are:

1. Update the naive implementation per above (this is risky and late)
2. Revert the vectorization in .NET 8, bring it back in .NET 9 along with the naive implementation change
3. Leave this as a known issue in .NET 8, with documentation stating that we do not guarantee if/when an overflow is thrown while accumulating; make the fix in .NET 9

@stephentoub -- what do you think?

[stephentoub]

@PetSerAl, what is the scenario where this is actually causing problems for you?

[PetSerAl]

I have no scenario, which is currently affected. But I find no discussion of that change in PR. And I decide to raise issue explicitly. So conscious decision about it can be made. And we at least have proper documentation of expected behavior, and any discrepancies between vectorized/non-vectorized versions, if allowed.

[eiriktsarpalis]

I wouldn't say this is an issue specific to vectorization, you can encounter similar behaviour in .NET 7 simply by shuffling the source enumerable:

Test1().Sum(); // 0
Test1().Order().Sum(); // OverflowException

TL;DR adding fixed-size integers isn't an associative operation.

I think we should just document this as a breaking change and consider adding a LINQ-specific feature switch if we do receive reports of users being impacted (I suspect that's going to be unlikely).

[ghost]

Added needs-breaking-change-doc-created label because this issue has the breaking-change label.

1. [ ] Create and link to this issue a matching issue in the dotnet/docs repo using the breaking change documentation template, then remove this needs-breaking-change-doc-created label.

Tagging @dotnet/compat for awareness of the breaking change.

[tannergooding]

@eiriktsarpalis, the consideration here isn't whether there is a difference between [ int.MaxValue, -1, +1 ].Sum() and [ int.MaxValue, +1, -1].Sum() (although that is an interesting case to consider as well)

The consideration is that there is a difference for [ int.MaxValue, +1, -1].Sum() based on the hardware you run on and our behavior is now non-deterministic (which is justifiably very bad and can lead to very hard to track down bugs).

We basically have a few options we could do...

1. We say this break is by design and document the new behavior. -- I personally think this is the worst option because, as I indicated above, it can lead to very hard to track down bugs and bugs that only repro some of the time and only on some hardware.

2. We say this break is not by design and no longer vectorize the code. -- I think this is an "ok" option, but it means we will never be able to provide perf gains here.

3. We say this break is desirable and update the algorithms to only throw if the total sum of integers overflows. This would require a change to both the scalar and vector algorithms to sum themselves in the next largest integer when an overflow is first detected. So something like:

   
   public static int Sum(ReadOnlySpan<int> values)
   {
   int sum = 0;
   int lastSign = 0;
   
   for (int i = 0; i < values.Length; i++)
   {
       int tmp = sum + value;
       int sign = value >>> 31;
   
       // ideally this check is recognized and optimized by the JIT
       if ((lastSign == sign) && (sign != (tmp >>> 31)))
       {
           return SumWithPotentialOverflow(sum, values.Slice(i));
       }
   }
   
   return sum;
   }

private static int SumWithPotentialOverflow(long sum, ReadOnlySpan values) { for (int i = 0; i < values.Length; i++) { sum += values[i]; }

return checked((int)sum); }

Under such a setup we will only throw an `OverflowException` if the total sum of all values results in an overflow and therefore the ordering of them doesn't matter. It also avoids requiring upcasts for every value processed and allows vectorization to be kept.

The one niche consideration that still exists is if someone has defined a custom enumerator that yields more than `int.MaxValue` results for 32-bit sums and more than `long.MaxValue` results for 64-bit sums. That could still overflow, but is likely so rare that it's acceptable to leave as undefined (rather than continuing to fallback to a larger temporary).

[ericstj]

I've marked the PR which made this change as breaking - we will need to document that if the break remains. We should make sure that has a workaround for folks. Moving this to track follow up work (option 3) to 9.0.0. We could always do option 2 in servicing if we get more feedback around this.

[PetSerAl]

My suggestion would be to fallback to sequential summing, when overflow encountered. That will make sure everything, that can be summed sequential, will not overflow with vectorization.

int Fallback(ref int ptr, nuint length, Vector<int> accumulator, nuint index, nuint lastKnownGood) {
    while(index > lastKnownGood) {
        index -= (nuint)Vector<int>.Count;
        accumulator -= Vector.LoadUnsafe(ref ptr, index);
    }
    long wideResult = 0;
    for(int i = 0; i < Vector<int>.Count; ++i) {
        wideResult += accumulator[i];
    }
    int result = checked((int)wideResult);
    for(; index < length; ++index) {
        checked { result += Unsafe.Add(ref ptr, index); }
    }
    return result;
}

[eiriktsarpalis]

I removed the regression-from-last-release label to indicate that this change is already present in .NET 8