# HG changeset patch # User igerasim # Date 1544550946 28800 # Tue Dec 11 09:55:46 2018 -0800 # Node ID ef61ea08ac5ec8d8f186596fc8e76565e11390f9 # Parent 3addaaf7eaea7b58c3496c56c5e345aa9bc44ced [mq]: 8214761-Bug-in-parallel-Kahan-summation-implementation-for-Doublestream-sum diff --git a/src/java.base/share/classes/java/util/DoubleSummaryStatistics.java b/src/java.base/share/classes/java/util/DoubleSummaryStatistics.java --- a/src/java.base/share/classes/java/util/DoubleSummaryStatistics.java +++ b/src/java.base/share/classes/java/util/DoubleSummaryStatistics.java @@ -1,5 +1,5 @@ /* - * Copyright (c) 2012, 2017, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2012, 2018, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -64,7 +64,7 @@ public class DoubleSummaryStatistics implements DoubleConsumer { private long count; private double sum; - private double sumCompensation; // Low order bits of sum + private double sumCompensation; // Negative low order bits of sum private double simpleSum; // Used to compute right sum for non-finite inputs private double min = Double.POSITIVE_INFINITY; private double max = Double.NEGATIVE_INFINITY; @@ -154,7 +154,7 @@ count += other.count; simpleSum += other.simpleSum; sumWithCompensation(other.sum); - sumWithCompensation(other.sumCompensation); + sumWithCompensation(-other.sumCompensation); min = Math.min(min, other.min); max = Math.max(max, other.max); } @@ -239,7 +239,7 @@ */ public final double getSum() { // Better error bounds to add both terms as the final sum - double tmp = sum + sumCompensation; + double tmp = sum - sumCompensation; if (Double.isNaN(tmp) && Double.isInfinite(simpleSum)) // If the compensated sum is spuriously NaN from // accumulating one or more same-signed infinite values, diff --git a/src/java.base/share/classes/java/util/stream/Collectors.java b/src/java.base/share/classes/java/util/stream/Collectors.java --- a/src/java.base/share/classes/java/util/stream/Collectors.java +++ b/src/java.base/share/classes/java/util/stream/Collectors.java @@ -714,7 +714,7 @@ /* * In the arrays allocated for the collect operation, index 0 * holds the high-order bits of the running sum, index 1 holds - * the low-order bits of the sum computed via compensated + * the (negative) low-order bits of the sum computed via compensated * summation, and index 2 holds the simple sum used to compute * the proper result if the stream contains infinite values of * the same sign. @@ -726,7 +726,7 @@ a[2] += val;}, (a, b) -> { sumWithCompensation(a, b[0]); a[2] += b[2]; - return sumWithCompensation(a, b[1]); }, + return sumWithCompensation(a, -b[1]); }, a -> computeFinalSum(a), CH_NOID); } @@ -735,9 +735,9 @@ * Incorporate a new double value using Kahan summation / * compensation summation. * - * High-order bits of the sum are in intermediateSum[0], low-order - * bits of the sum are in intermediateSum[1], any additional - * elements are application-specific. + * High-order bits of the sum are in intermediateSum[0], + * negative low-order bits of the sum are in intermediateSum[1], + * any additional elements are application-specific. * * @param intermediateSum the high-order and low-order words of the intermediate sum * @param value the name value to be included in the running sum @@ -758,7 +758,7 @@ */ static double computeFinalSum(double[] summands) { // Better error bounds to add both terms as the final sum - double tmp = summands[0] + summands[1]; + double tmp = summands[0] - summands[1]; double simpleSum = summands[summands.length - 1]; if (Double.isNaN(tmp) && Double.isInfinite(simpleSum)) return simpleSum; @@ -832,13 +832,13 @@ /* * In the arrays allocated for the collect operation, index 0 * holds the high-order bits of the running sum, index 1 holds - * the low-order bits of the sum computed via compensated + * the (negative) low-order bits of the sum computed via compensated * summation, and index 2 holds the number of values seen. */ return new CollectorImpl<>( () -> new double[4], - (a, t) -> { double val = mapper.applyAsDouble(t); sumWithCompensation(a, val); a[2]++; a[3]+= val;}, - (a, b) -> { sumWithCompensation(a, b[0]); sumWithCompensation(a, b[1]); a[2] += b[2]; a[3] += b[3]; return a; }, + (a, t) -> { double val = mapper.applyAsDouble(t); sumWithCompensation(a, val); a[2]++; a[3] += val; }, + (a, b) -> { sumWithCompensation(a, b[0]); sumWithCompensation(a, -b[1]); a[2] += b[2]; a[3] += b[3]; return a; }, a -> (a[2] == 0) ? 0.0d : (computeFinalSum(a) / a[2]), CH_NOID); } diff --git a/src/java.base/share/classes/java/util/stream/DoublePipeline.java b/src/java.base/share/classes/java/util/stream/DoublePipeline.java --- a/src/java.base/share/classes/java/util/stream/DoublePipeline.java +++ b/src/java.base/share/classes/java/util/stream/DoublePipeline.java @@ -1,5 +1,5 @@ /* - * Copyright (c) 2013, 2017, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2013, 2018, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -417,10 +417,10 @@ /* * In the arrays allocated for the collect operation, index 0 * holds the high-order bits of the running sum, index 1 holds - * the low-order bits of the sum computed via compensated - * summation, and index 2 holds the simple sum used to compute - * the proper result if the stream contains infinite values of - * the same sign. + * the (negative) low-order bits of the sum computed via + * compensated summation, and index 2 holds the simple sum used + * to compute the proper result if the stream contains infinite + * values of the same sign. */ double[] summation = collect(() -> new double[3], (ll, d) -> { @@ -429,7 +429,7 @@ }, (ll, rr) -> { Collectors.sumWithCompensation(ll, rr[0]); - Collectors.sumWithCompensation(ll, rr[1]); + Collectors.sumWithCompensation(ll, -rr[1]); ll[2] += rr[2]; }); @@ -460,9 +460,9 @@ /* * In the arrays allocated for the collect operation, index 0 * holds the high-order bits of the running sum, index 1 holds - * the low-order bits of the sum computed via compensated - * summation, index 2 holds the number of values seen, index 3 - * holds the simple sum. + * the (negative) low-order bits of the sum computed via + * compensated summation, index 2 holds the number of values + * seen, index 3 holds the simple sum. */ double[] avg = collect(() -> new double[4], (ll, d) -> { @@ -472,7 +472,7 @@ }, (ll, rr) -> { Collectors.sumWithCompensation(ll, rr[0]); - Collectors.sumWithCompensation(ll, rr[1]); + Collectors.sumWithCompensation(ll, -rr[1]); ll[2] += rr[2]; ll[3] += rr[3]; }); diff --git a/test/jdk/java/util/DoubleSummaryStatistics/NegativeCompensation.java b/test/jdk/java/util/DoubleSummaryStatistics/NegativeCompensation.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/util/DoubleSummaryStatistics/NegativeCompensation.java @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/* + * @test + * @bug 8214761 + * @summary When combining two DoubleSummaryStatistics, the compensation + * has to be subtracted. + */ + +import java.util.DoubleSummaryStatistics; + +public class NegativeCompensation { + static final double VAL = 1.000000001; + static final int LOG_ITER = 21; + + public static void main(String[] args) { + DoubleSummaryStatistics stat0 = new DoubleSummaryStatistics(); + DoubleSummaryStatistics stat1 = new DoubleSummaryStatistics(); + DoubleSummaryStatistics stat2 = new DoubleSummaryStatistics(); + + stat1.accept(VAL); + stat1.accept(VAL); + stat2.accept(VAL); + stat2.accept(VAL); + stat2.accept(VAL); + + for (int i = 0; i < LOG_ITER; ++i) { + stat1.combine(stat2); + stat2.combine(stat1); + } + + System.out.println("count: " + stat2.getCount()); + for (long i = 0, iend = stat2.getCount(); i < iend; ++i) { + stat0.accept(VAL); + } + + double absErr = Math.abs(stat0.getSum() - stat2.getSum()); + System.out.println("serial sum: " + stat0.getSum()); + System.out.println("combined sum: " + stat2.getSum()); + System.out.println("abs error: " + absErr); + if (absErr > 0.00000001) { + throw new RuntimeException("Absolute error is too big: " + absErr); + } + } +}