RFR 8214761 : Bug in parallel Kahan summation implementation

[Joe Darcy]

Hello,

Thanks for the nudge; I'll get to this sometime after the Skara 
transition for jdk/jdk.

Cheers,

-Joe

On 9/3/2020 9:29 AM, Chris Dennis wrote:
> In case there is a need for extra motivation here:
>
> import java.util.stream.DoubleStream;
>
> public class Test8214761 {
>    public static void main(String[] args) {
>      double a = Double.valueOf(args[0]);
>      if (Math.ulp(a) <= Math.ulp(Math.nextAfter(a, 0))) {
>        System.out.println("Stable addition");
>      } else {
>        double b = Math.signum(a) * Math.ulp(a) / 2;
>
>        double sum = a + b;
>        double streamSum = DoubleStream.of(a, b).sum();
>
>        System.out.println(a + " + " + b + "\n => " + sum);
>        System.out.println("DoubleStream.of(" + a + ", " + b + ").sum()\n => " + streamSum);
>      }
>    }
> }
>
> $ java -showversion Test8214761 1
> openjdk version "16-internal" 2021-03-16
> OpenJDK Runtime Environment (build 16-internal+0-cdennis.0178d0f136e9)
> OpenJDK 64-Bit Server VM (build 16-internal+0-cdennis.0178d0f136e9, mixed mode, sharing)
> 1.0 + 1.1102230246251565E-16
>   => 1.0
> DoubleStream.of(1.0, 1.1102230246251565E-16).sum()
>   => 0.9999999999999999
>
> That's the sum of two positive doubles returning a result smaller than one of the two.
>
> Apologies for the zeal,
>
> Chris
>
> On 8/27/20, 10:52 AM, "Chris Dennis" <chris.w.dennis at gmail.com> wrote:
>
>      Bump...
>
>      I've run in to this while running tests that check computation results against the expected bounds of a Kahan summation. Any chance that this gets picked up in the near future?
>
>      Thanks,
>
>      Chris
>
>      On 12/13/18, 6:16 PM, "core-libs-dev on behalf of Ivan Gerasimov" <core-libs-dev-bounces at openjdk.java.net on behalf of ivan.gerasimov at oracle.com> wrote:
>
>          Gentle ping.
>
>
>          On 12/9/18 7:37 PM, Ivan Gerasimov wrote:
>          > Hello!
>          >
>          > DoubleSummaryStatistics takes advantage of Kahan summation algorithm
>          > to reduce the error of the total sum.
>          >
>          > Internally it maintains a field double sumCompensation, which keeps
>          > lower bits (which were rounded off) of the last addition.
>          >
>          > Note, that the compensation has to be subtracted from the result to
>          > add those bits back:
>          >
>          >  166     private void sumWithCompensation(double value) {
>          >  167         double tmp = value - sumCompensation;
>          >  168         double velvel = sum + tmp; // Little wolf of rounding error
>          >  169         sumCompensation = (velvel - sum) - tmp;
>          >  170         sum = velvel;
>          >  171     }
>          >
>          > At the line 169, tmp normally has more lower bits than (velvel - sum).
>          >
>          > However, when two DoubleSummaryStatistics objects are combined, this
>          > compensation part is *added* to the total, which may result in a less
>          > accurate result.
>          >
>          > The same bug is replicated in DoubleStreams.
>          >
>          > Would you please help review the fix?
>          >
>          > BUGURL: https://bugs.openjdk.java.net/browse/JDK-8214761
>          > WEBREV: http://cr.openjdk.java.net/~igerasim/8214761/00/webrev/
>          >
>
>          --
>          With kind regards,
>          Ivan Gerasimov
>