1 /*
2  * Copyright (c) 2021, 2022, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 
24 /*
25  * @test
26  * @bug 8214761
27  * @key randomness
28  * @library /test/lib
29  * @build jdk.test.lib.RandomFactory
30  * @run testng CompensatedSums
31  * @summary
32  */
33 
34 package test.java.util.DoubleStreamSums;
35 
36 import android.platform.test.annotations.LargeTest;
37 
38 import java.util.Random;
39 import java.util.function.BiConsumer;
40 import java.util.function.ObjDoubleConsumer;
41 import java.util.function.Supplier;
42 import java.util.stream.DoubleStream;
43 
44 import jdk.test.lib.RandomFactory;
45 import org.testng.Assert;
46 import org.testng.annotations.Test;
47 
48 public class CompensatedSums {
49 
50     @LargeTest
51     @Test
testCompensatedSums()52     public void testCompensatedSums() {
53         Random r = RandomFactory.getRandom();
54 
55         double naive = 0;
56         double jdkSequentialStreamError = 0;
57         double goodSequentialStreamError = 0;
58         double jdkParallelStreamError = 0;
59         double goodParallelStreamError = 0;
60         double badParallelStreamError = 0;
61 
62         // Android-changed: Reduce number of iterations to limit test runtime.
63         // for (int loop = 0; loop < 100; loop++) {
64         for (int loop = 0; loop < 15; loop++) {
65             // sequence of random numbers of varying magnitudes, both positive and negative
66             double[] rand = r.doubles(1_000_000)
67                     .map(Math::log)
68                     .map(x -> (Double.doubleToLongBits(x) % 2 == 0) ? x : -x)
69                     .toArray();
70 
71             // base case: standard Kahan summation
72             double[] sum = new double[2];
73             for (int i=0; i < rand.length; i++) {
74                 sumWithCompensation(sum, rand[i]);
75             }
76 
77             // All error is the squared difference of the standard Kahan Sum vs JDK Stream sum implementation
78             // Older less accurate implementations included here as the baseline.
79 
80             // squared error of naive sum by reduction - should be large
81             naive += square(DoubleStream.of(rand).reduce((x, y) -> x+y).getAsDouble() - sum[0]);
82 
83             // squared error of sequential sum - should be 0
84             jdkSequentialStreamError += square(DoubleStream.of(rand).sum() - sum[0]);
85 
86             goodSequentialStreamError += square(computeFinalSum(DoubleStream.of(rand).collect(doubleSupplier,objDoubleConsumer,goodCollectorConsumer)) - sum[0]);
87 
88             // squared error of parallel sum from the JDK
89             jdkParallelStreamError += square(DoubleStream.of(rand).parallel().sum() - sum[0]);
90 
91             // squared error of parallel sum
92             goodParallelStreamError += square(computeFinalSum(DoubleStream.of(rand).parallel().collect(doubleSupplier,objDoubleConsumer,goodCollectorConsumer)) - sum[0]);
93 
94             // the bad parallel stream
95             badParallelStreamError += square(computeFinalSum(DoubleStream.of(rand).parallel().collect(doubleSupplier,objDoubleConsumer,badCollectorConsumer)) - sum[0]);
96 
97 
98         }
99 
100         Assert.assertTrue(jdkParallelStreamError <= goodParallelStreamError);
101         // Android-removed: due to limited number of iterations this check might
102         // occasionally fail (b/284693092).
103         // Assert.assertTrue(badParallelStreamError >= jdkParallelStreamError);
104 
105         Assert.assertTrue(goodSequentialStreamError >= jdkSequentialStreamError);
106         Assert.assertTrue(naive > jdkSequentialStreamError);
107         Assert.assertTrue(naive > jdkParallelStreamError);
108 
109     }
110 
square(double arg)111     private static double square(double arg) {
112         return arg * arg;
113     }
114 
115     // from OpenJDK 18 Collectors, unmodified
sumWithCompensation(double[] intermediateSum, double value)116     static double[] sumWithCompensation(double[] intermediateSum, double value) {
117         double tmp = value - intermediateSum[1];
118         double sum = intermediateSum[0];
119         double velvel = sum + tmp; // Little wolf of rounding error
120         intermediateSum[1] = (velvel - sum) - tmp;
121         intermediateSum[0] = velvel;
122         return intermediateSum;
123     }
124 
125     // from OpenJDK 18 Collectors, unmodified
computeFinalSum(double[] summands)126     static double computeFinalSum(double[] summands) {
127         // Final sum with better error bounds subtract second summand as it is negated
128         double tmp = summands[0] - summands[1];
129         double simpleSum = summands[summands.length - 1];
130         if (Double.isNaN(tmp) && Double.isInfinite(simpleSum))
131             return simpleSum;
132         else
133             return tmp;
134     }
135 
136     //Suppliers and consumers for Double Stream summation collection.
137     static Supplier<double[]> doubleSupplier = () -> new double[3];
138     static ObjDoubleConsumer<double[]> objDoubleConsumer = (double[] ll, double d) -> {
139                                                              sumWithCompensation(ll, d);
140                                                              ll[2] += d;
141                                                            };
142     static BiConsumer<double[], double[]> badCollectorConsumer =
143             (ll, rr) -> {
144                 sumWithCompensation(ll, rr[0]);
145                 sumWithCompensation(ll, rr[1]);
146                 ll[2] += rr[2];
147             };
148 
149     static BiConsumer<double[], double[]> goodCollectorConsumer =
150             (ll, rr) -> {
151                 sumWithCompensation(ll, rr[0]);
152                 sumWithCompensation(ll, -rr[1]);
153                 ll[2] += rr[2];
154             };
155 
156 }