RFR 8214761 : Bug in parallel Kahan summation implementation
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
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&pr=3442&range=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
RFR: 8214761: Bug in parallel Kahan summation implementation
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&pr=4674&range=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
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
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
Re: RFR: 8214761: Bug in parallel Kahan summation implementation
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
Re: RFR: 8214761: Bug in parallel Kahan summation implementation
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
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
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
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
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
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
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 [v2]
> 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&pr=4674&range=01 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=4674&range=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 [v2]
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]
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 [v3]
> 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&pr=4674&range=02 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=4674&range=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 [v4]
> 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&pr=4674&range=03 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=4674&range=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
