Integrated: 8214761: Bug in parallel Kahan summation implementation

2021-09-02 Thread Ian Graves 
On Fri, 2 Jul 2021 20:12:39 GMT, Ian Graves  wrote:

> 8214761: Bug in parallel Kahan summation implementation

This pull request has now been integrated.

Changeset: dd871819
Author:Ian Graves 
URL:   
https://git.openjdk.java.net/jdk/commit/dd871819a05886ee09fc00c7c778268440ebedb7
Stats: 235 lines in 5 files changed: 225 ins; 0 del; 10 mod

8214761: Bug in parallel Kahan summation implementation

Reviewed-by: darcy

-

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation [v4]

2021-09-01 Thread Ian Graves 
> 8214761: Bug in parallel Kahan summation implementation

Ian Graves has updated the pull request incrementally with one additional 
commit since the last revision:

  Fixing compensation test

-

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/4674/files
  - new: https://git.openjdk.java.net/jdk/pull/4674/files/905450d8..722826fc

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk=4674=03
 - incr: https://webrevs.openjdk.java.net/?repo=jdk=4674=02-03

  Stats: 13 lines in 1 file changed: 5 ins; 4 del; 4 mod
  Patch: https://git.openjdk.java.net/jdk/pull/4674.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/4674/head:pull/4674

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation [v3]

2021-08-31 Thread Ian Graves 
> 8214761: Bug in parallel Kahan summation implementation

Ian Graves has updated the pull request with a new target base due to a merge 
or a rebase. The incremental webrev excludes the unrelated changes brought in 
by the merge/rebase. The pull request contains six additional commits since the 
last revision:

 - Changing some comments.
 - Merge branch 'master' into kahan-summation-bug
 - Updates with more test coverage
 - stashing
 - Stashing
 - 8214761: Bug in parallel Kahan summation implementation

-

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/4674/files
  - new: https://git.openjdk.java.net/jdk/pull/4674/files/10b8dcda..905450d8

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk=4674=02
 - incr: https://webrevs.openjdk.java.net/?repo=jdk=4674=01-02

  Stats: 107423 lines in 2079 files changed: 73519 ins; 22961 del; 10943 mod
  Patch: https://git.openjdk.java.net/jdk/pull/4674.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/4674/head:pull/4674

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation [v2]

2021-08-30 Thread Joe Darcy 
On Wed, 21 Jul 2021 20:19:31 GMT, Ian Graves  wrote:

>> 8214761: Bug in parallel Kahan summation implementation
>
> Ian Graves has updated the pull request incrementally with three additional 
> commits since the last revision:
> 
>  - Updates with more test coverage
>  - stashing
>  - Stashing

The code changes look fine, but IMO the comments should be re-worded a bit.

Rather text like

// Negating this value because low-order bits are in negated form

I suggest something like

// Subtract compensation bits

The main compensation loop also subtracts the compensation bits. A comment like 
"subtract compensation bits" makes the corrected handling of them seem less 
anomalous.

-

Marked as reviewed by darcy (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation [v2]

2021-07-22 Thread Ian Graves 
On Wed, 21 Jul 2021 20:19:31 GMT, Ian Graves  wrote:

>> 8214761: Bug in parallel Kahan summation implementation
>
> Ian Graves has updated the pull request incrementally with three additional 
> commits since the last revision:
> 
>  - Updates with more test coverage
>  - stashing
>  - Stashing

Circling back on this. I've worked in the test from Ivan Gerasimov's email back 
when. It includes some additional comparisons to prior approaches to assert 
improvements in error.

-

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation [v2]

2021-07-21 Thread Ian Graves 
> 8214761: Bug in parallel Kahan summation implementation

Ian Graves has updated the pull request incrementally with three additional 
commits since the last revision:

 - Updates with more test coverage
 - stashing
 - Stashing

-

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/4674/files
  - new: https://git.openjdk.java.net/jdk/pull/4674/files/d7fc3948..10b8dcda

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk=4674=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk=4674=00-01

  Stats: 216 lines in 4 files changed: 213 ins; 0 del; 3 mod
  Patch: https://git.openjdk.java.net/jdk/pull/4674.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/4674/head:pull/4674

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation

2021-07-06 Thread Ian Graves 
On Fri, 2 Jul 2021 21:30:56 GMT, stefan-zobel 
 wrote:

>> 8214761: Bug in parallel Kahan summation implementation
>
> src/java.base/share/classes/java/util/DoubleSummaryStatistics.java line 161:
> 
>> 159: 
>> 160: //Negating this value because low-order bits are in negated form
>> 161: sumWithCompensation(-other.sumCompensation);
> 
> Wouldn't that be `double tmp =  sum - sumCompensation;` in getSum() in line 
> 246 too?

Good catch will review and make the change.

-

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation

2021-07-02 Thread stefan-zobel 
On Fri, 2 Jul 2021 20:30:24 GMT, Andrew Haley  wrote:

> Crikey, how did we get that wrong?
> It'd be nice if we had a regression test for this. Can you provide one, 
> please?

I found this: 
https://mail.openjdk.java.net/pipermail/core-libs-dev/2018-December/057239.html
Ivan Gerasimov already tackled this back then. His webrev still exists and it 
contains a simple regression test.

-

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation

2021-07-02 Thread stefan-zobel 
On Fri, 2 Jul 2021 20:12:39 GMT, Ian Graves  wrote:

> 8214761: Bug in parallel Kahan summation implementation

What about `Collectors.computeFinalSum()` - should this be `double tmp = 
summands[0] + summands[1];` or `double tmp = summands[0] - summands[1];` ?

-

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation

2021-07-02 Thread stefan-zobel 
On Fri, 2 Jul 2021 20:12:39 GMT, Ian Graves  wrote:

> 8214761: Bug in parallel Kahan summation implementation

src/java.base/share/classes/java/util/DoubleSummaryStatistics.java line 161:

> 159: 
> 160: //Negating this value because low-order bits are in negated form
> 161: sumWithCompensation(-other.sumCompensation);

Wouldn't that be `double tmp =  sum - sumCompensation;` in getSum() in line 246 
too?

-

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation

2021-07-02 Thread Andrew Haley 
On Fri, 2 Jul 2021 20:12:39 GMT, Ian Graves  wrote:

> 8214761: Bug in parallel Kahan summation implementation

Crikey, how did we get that wrong?
It'd be nice if we had a regression test for this. Can you provide one, please?

-

PR: https://git.openjdk.java.net/jdk/pull/4674

RFR: 8214761: Bug in parallel Kahan summation implementation

2021-07-02 Thread Ian Graves 
8214761: Bug in parallel Kahan summation implementation

-

Commit messages:
 - 8214761: Bug in parallel Kahan summation implementation

Changes: https://git.openjdk.java.net/jdk/pull/4674/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk=4674=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8214761
  Stats: 18 lines in 3 files changed: 11 ins; 0 del; 7 mod
  Patch: https://git.openjdk.java.net/jdk/pull/4674.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/4674/head:pull/4674

PR: https://git.openjdk.java.net/jdk/pull/4674

Re: RFR: 8214761: Bug in parallel Kahan summation implementation

2021-04-12 Thread Ian Graves 
On Mon, 12 Apr 2021 19:45:24 GMT, Ian Graves  wrote:

> Fixes a bug where the compensated sum should be negated when added together 
> in the merge step of a given collector. This impacts accuracy of parallel 
> summations with Double streams and creates larger deviations from a standard 
> sequential (ie non-parallel) compensated summation.

Duplicate of https://github.com/openjdk/jdk/pull/2988

-

PR: https://git.openjdk.java.net/jdk/pull/3442

Withdrawn: 8214761: Bug in parallel Kahan summation implementation

2021-04-12 Thread Ian Graves 
On Mon, 12 Apr 2021 19:45:24 GMT, Ian Graves  wrote:

> Fixes a bug where the compensated sum should be negated when added together 
> in the merge step of a given collector. This impacts accuracy of parallel 
> summations with Double streams and creates larger deviations from a standard 
> sequential (ie non-parallel) compensated summation.

This pull request has been closed without being integrated.

-

PR: https://git.openjdk.java.net/jdk/pull/3442

RFR: 8214761: Bug in parallel Kahan summation implementation

2021-04-12 Thread Ian Graves 
Fixes a bug where the compensated sum should be negated when added together in 
the merge step of a given collector. This impacts accuracy of parallel 
summations with Double streams and creates larger deviations from a standard 
sequential (ie non-parallel) compensated summation.

-

Commit messages:
 - Fixing a compensated/Kahan summation bug that increase error

Changes: https://git.openjdk.java.net/jdk/pull/3442/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk=3442=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8214761
  Stats: 16 lines in 3 files changed: 10 ins; 0 del; 6 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3442.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3442/head:pull/3442

PR: https://git.openjdk.java.net/jdk/pull/3442

Re: 8214761: Bug in parallel Kahan summation implementation

2021-04-09 Thread Dalibor Topic 

Hi Anirvan,

You can contact contact Oracle’s open-source administrators at 
opensource_ww_...@oracle.com, who run the OCA app.


We don't use the github usernames from the OCA app for OpenJDK pull 
requests, so you should not be running into issues with that for 
contributions to OpenJDK. If you do, please let me know off-list which 
pull request is involved.


cheers,
dalibor topic

On 03.04.2021 22:11, Anirvan Sarkar wrote:

Hi Pavel,

I think I have the same issue as Chris.

The new OCA contributors list [1] is incorrectly linking the user names to
GitHub as compared to the old contributors list [2].
It seems the new OCA contributors list is assuming that the GitHub username
of past contributors is the same as the username of the project, when they
had signed the OCA in the past.

When I had signed OCA a few years back for the OpenJFX project, I had
provided my username as *anirvan.sarkar*.
This was my username on java.net / javafx-jira.kenai.com (the old JIRA for
JavaFX project).
But my GitHub username is *AnirvanSarkar*, not *anirvan.sarkar* which user
does not exist on GitHub.

[1] : https://oca.opensource.oracle.com/?ojr=contrib-list
[2] : https://oca.opensource.oracle.com/?ojr=old-contrib-list


On Sun, 4 Apr 2021 at 03:35, Pavel Rappo  wrote:


Hey Chris,

I don't know exactly what triggers removal of the "oca" and "oca-verify"
labels. The only OCA entry for Chris Dennis I could find [1] had a
different GitHub username. Did you mistype it or it belongs to another
person? Mind you, that person's GitHub page is 404.

-Pavel

[1] https://oca.opensource.oracle.com/?ojr=contrib-list


On 3 Apr 2021, at 16:12, Chris Dennis  wrote:

A gentle prod. Am I misunderstanding procedure here?

From: Chris Dennis 
Date: Monday, March 22, 2021 at 2:28 PM
To: core-libs-dev 
Subject: 8214761: Bug in parallel Kahan summation implementation
I created a PR for 8214761: https://github.com/openjdk/jdk/pull/2988 -

but have been stuck waiting on OCA signatory status to be confirmed. Did
something get lost in the shuffle or do I just need to be more patient.


Thanks,

Chris







--
<http://www.oracle.com> Dalibor Topic
Consulting Product Manager
Phone: +494089091214 , Mobile: +491737185961
, Video: dalibor.to...@oracle.com


Oracle Global Services Germany GmbH
Hauptverwaltung: Riesstr. 25, D-80992 München
Registergericht: Amtsgericht München, HRB 246209
Geschäftsführer: Ralf Herrmann

Re: 8214761: Bug in parallel Kahan summation implementation

2021-04-03 Thread Anirvan Sarkar 
Hi Pavel,

I think I have the same issue as Chris.

The new OCA contributors list [1] is incorrectly linking the user names to
GitHub as compared to the old contributors list [2].
It seems the new OCA contributors list is assuming that the GitHub username
of past contributors is the same as the username of the project, when they
had signed the OCA in the past.

When I had signed OCA a few years back for the OpenJFX project, I had
provided my username as *anirvan.sarkar*.
This was my username on java.net / javafx-jira.kenai.com (the old JIRA for
JavaFX project).
But my GitHub username is *AnirvanSarkar*, not *anirvan.sarkar* which user
does not exist on GitHub.

[1] : https://oca.opensource.oracle.com/?ojr=contrib-list
[2] : https://oca.opensource.oracle.com/?ojr=old-contrib-list


On Sun, 4 Apr 2021 at 03:35, Pavel Rappo  wrote:

> Hey Chris,
>
> I don't know exactly what triggers removal of the "oca" and "oca-verify"
> labels. The only OCA entry for Chris Dennis I could find [1] had a
> different GitHub username. Did you mistype it or it belongs to another
> person? Mind you, that person's GitHub page is 404.
>
> -Pavel
>
> [1] https://oca.opensource.oracle.com/?ojr=contrib-list
>
> > On 3 Apr 2021, at 16:12, Chris Dennis  wrote:
> >
> > A gentle prod. Am I misunderstanding procedure here?
> >
> > From: Chris Dennis 
> > Date: Monday, March 22, 2021 at 2:28 PM
> > To: core-libs-dev 
> > Subject: 8214761: Bug in parallel Kahan summation implementation
> > I created a PR for 8214761: https://github.com/openjdk/jdk/pull/2988 -
> but have been stuck waiting on OCA signatory status to be confirmed. Did
> something get lost in the shuffle or do I just need to be more patient.
> >
> > Thanks,
> >
> > Chris
>
>

-- 
Anirvan

Re: 8214761: Bug in parallel Kahan summation implementation

2021-04-03 Thread Chris Dennis 
I’m pretty certain that is meant to be me but ‘chris_dennis’ is a now defunct 
java.net username and not a Github one. The username appears in this list 
https://oca.opensource.oracle.com/?ojr=old-contrib-list#t too as: “Terracotta 
Inc. (Christopher Dennis), OpenJDK, chris_dennis”. My Github username is tied 
to the previous commits I’ve authored though: 
https://github.com/openjdk/jdk/commits?author=chrisdennis. I also believe there 
should be a signed OCA for my current employer “Software AG” too since I’ve 
contributed under it to both OpenJDK and JSR-107.

Chris


From: Pavel Rappo 
Date: Saturday, April 3, 2021 at 2:35 PM
To: Chris Dennis 
Cc: core-libs-dev 
Subject: Re: 8214761: Bug in parallel Kahan summation implementation
Hey Chris,

I don't know exactly what triggers removal of the "oca" and "oca-verify" 
labels. The only OCA entry for Chris Dennis I could find [1] had a different 
GitHub username. Did you mistype it or it belongs to another person? Mind you, 
that person's GitHub page is 404.

-Pavel

[1] https://oca.opensource.oracle.com/?ojr=contrib-list

> On 3 Apr 2021, at 16:12, Chris Dennis  wrote:
>
> A gentle prod. Am I misunderstanding procedure here?
>
> From: Chris Dennis 
> Date: Monday, March 22, 2021 at 2:28 PM
> To: core-libs-dev 
> Subject: 8214761: Bug in parallel Kahan summation implementation
> I created a PR for 8214761: https://github.com/openjdk/jdk/pull/2988 - but 
> have been stuck waiting on OCA signatory status to be confirmed. Did 
> something get lost in the shuffle or do I just need to be more patient.
>
> Thanks,
>
> Chris

Re: 8214761: Bug in parallel Kahan summation implementation

2021-04-03 Thread Pavel Rappo 
Hey Chris,

I don't know exactly what triggers removal of the "oca" and "oca-verify" 
labels. The only OCA entry for Chris Dennis I could find [1] had a different 
GitHub username. Did you mistype it or it belongs to another person? Mind you, 
that person's GitHub page is 404.

-Pavel

[1] https://oca.opensource.oracle.com/?ojr=contrib-list

> On 3 Apr 2021, at 16:12, Chris Dennis  wrote:
> 
> A gentle prod. Am I misunderstanding procedure here?
> 
> From: Chris Dennis 
> Date: Monday, March 22, 2021 at 2:28 PM
> To: core-libs-dev 
> Subject: 8214761: Bug in parallel Kahan summation implementation
> I created a PR for 8214761: https://github.com/openjdk/jdk/pull/2988 - but 
> have been stuck waiting on OCA signatory status to be confirmed. Did 
> something get lost in the shuffle or do I just need to be more patient.
> 
> Thanks,
> 
> Chris

Re: 8214761: Bug in parallel Kahan summation implementation

2021-04-03 Thread Chris Dennis 
A gentle prod. Am I misunderstanding procedure here?

From: Chris Dennis 
Date: Monday, March 22, 2021 at 2:28 PM
To: core-libs-dev 
Subject: 8214761: Bug in parallel Kahan summation implementation
I created a PR for 8214761: https://github.com/openjdk/jdk/pull/2988 - but have 
been stuck waiting on OCA signatory status to be confirmed. Did something get 
lost in the shuffle or do I just need to be more patient.

Thanks,

Chris

8214761: Bug in parallel Kahan summation implementation

2021-03-22 Thread Chris Dennis 
I created a PR for 8214761: https://github.com/openjdk/jdk/pull/2988 - but have 
been stuck waiting on OCA signatory status to be confirmed. Did something get 
lost in the shuffle or do I just need to be more patient.

Thanks,

Chris

Re: RFR 8214761 : Bug in parallel Kahan summation implementation

2020-09-03 Thread 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.

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"  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" 
 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

Re: RFR 8214761 : Bug in parallel Kahan summation implementation

2020-09-03 Thread Chris Dennis 
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.

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"  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" 
 
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

Re: RFR 8214761 : Bug in parallel Kahan summation implementation

2020-08-27 Thread Chris Dennis 
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" 
 
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

Re: RFR 8214761 : Bug in parallel Kahan summation implementation

2018-12-13 Thread Ivan Gerasimov 

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

RFR 8214761 : Bug in parallel Kahan summation implementation

2018-12-09 Thread Ivan Gerasimov 

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