1 /*
2  * Copyright (C) 2011 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.google.common.math;
18 
19 import static com.google.common.math.MathBenchmarking.ARRAY_MASK;
20 import static com.google.common.math.MathBenchmarking.ARRAY_SIZE;
21 import static com.google.common.math.MathBenchmarking.RANDOM_SOURCE;
22 import static com.google.common.math.MathBenchmarking.randomBigInteger;
23 import static com.google.common.math.MathBenchmarking.randomNonNegativeBigInteger;
24 
25 import com.google.caliper.BeforeExperiment;
26 import com.google.caliper.Benchmark;
27 import com.google.caliper.Param;
28 import com.google.common.math.DoubleMath;
29 import com.google.common.math.IntMath;
30 import com.google.common.math.LongMath;
31 
32 /**
33  * Benchmarks against the Apache Commons Math utilities.
34  *
35  * <p>Note: the Apache benchmarks are not open sourced to avoid the extra dependency.
36  *
37  * @author Louis Wasserman
38  */
39 public class ApacheBenchmark {
40   private enum Impl {
41     GUAVA {
42       @Override
factorialDouble(int n)43       public double factorialDouble(int n) {
44         return DoubleMath.factorial(n);
45       }
46 
47       @Override
gcdInt(int a, int b)48       public int gcdInt(int a, int b) {
49         return IntMath.gcd(a, b);
50       }
51 
52       @Override
gcdLong(long a, long b)53       public long gcdLong(long a, long b) {
54         return LongMath.gcd(a, b);
55       }
56 
57       @Override
binomialCoefficient(int n, int k)58       public long binomialCoefficient(int n, int k) {
59         return LongMath.binomial(n, k);
60       }
61 
62       @Override
noAddOverflow(int a, int b)63       public boolean noAddOverflow(int a, int b) {
64         try {
65           IntMath.checkedAdd(a, b);
66           return true;
67         } catch (ArithmeticException e) {
68           return false;
69         }
70       }
71 
72       @Override
noAddOverflow(long a, long b)73       public boolean noAddOverflow(long a, long b) {
74         try {
75           LongMath.checkedAdd(a, b);
76           return true;
77         } catch (ArithmeticException e) {
78           return false;
79         }
80       }
81 
82       @Override
noMulOverflow(int a, int b)83       public boolean noMulOverflow(int a, int b) {
84         try {
85           IntMath.checkedMultiply(a, b);
86           return true;
87         } catch (ArithmeticException e) {
88           return false;
89         }
90       }
91 
92       @Override
noMulOverflow(long a, long b)93       public boolean noMulOverflow(long a, long b) {
94         try {
95           LongMath.checkedMultiply(a, b);
96           return true;
97         } catch (ArithmeticException e) {
98           return false;
99         }
100       }
101     };
102 
factorialDouble(int n)103     public abstract double factorialDouble(int n);
104 
binomialCoefficient(int n, int k)105     public abstract long binomialCoefficient(int n, int k);
106 
gcdInt(int a, int b)107     public abstract int gcdInt(int a, int b);
108 
gcdLong(long a, long b)109     public abstract long gcdLong(long a, long b);
110 
noAddOverflow(int a, int b)111     public abstract boolean noAddOverflow(int a, int b);
112 
noAddOverflow(long a, long b)113     public abstract boolean noAddOverflow(long a, long b);
114 
noMulOverflow(int a, int b)115     public abstract boolean noMulOverflow(int a, int b);
116 
noMulOverflow(long a, long b)117     public abstract boolean noMulOverflow(long a, long b);
118   }
119 
120   private final int[] factorials = new int[ARRAY_SIZE];
121   private final int[][] binomials = new int[ARRAY_SIZE][2];
122   private final int[][] nonnegInt = new int[ARRAY_SIZE][2];
123   private final long[][] nonnegLong = new long[ARRAY_SIZE][2];
124   private final int[][] intsToAdd = new int[ARRAY_SIZE][2];
125   private final int[][] intsToMul = new int[ARRAY_SIZE][2];
126   private final long[][] longsToAdd = new long[ARRAY_SIZE][2];
127   private final long[][] longsToMul = new long[ARRAY_SIZE][2];
128 
129   @Param({"APACHE", "GUAVA"})
130   Impl impl;
131 
132   @BeforeExperiment
setUp()133   void setUp() {
134     for (int i = 0; i < ARRAY_SIZE; i++) {
135       factorials[i] = RANDOM_SOURCE.nextInt(200);
136       for (int j = 0; j < 2; j++) {
137         nonnegInt[i][j] = randomNonNegativeBigInteger(Integer.SIZE - 2).intValue();
138         nonnegLong[i][j] = randomNonNegativeBigInteger(Long.SIZE - 2).longValue();
139       }
140       do {
141         for (int j = 0; j < 2; j++) {
142           intsToAdd[i][j] = randomBigInteger(Integer.SIZE - 2).intValue();
143         }
144       } while (!Impl.GUAVA.noAddOverflow(intsToAdd[i][0], intsToAdd[i][1]));
145       do {
146         for (int j = 0; j < 2; j++) {
147           longsToAdd[i][j] = randomBigInteger(Long.SIZE - 2).longValue();
148         }
149       } while (!Impl.GUAVA.noAddOverflow(longsToAdd[i][0], longsToAdd[i][1]));
150       do {
151         for (int j = 0; j < 2; j++) {
152           intsToMul[i][j] = randomBigInteger(Integer.SIZE - 2).intValue();
153         }
154       } while (!Impl.GUAVA.noMulOverflow(intsToMul[i][0], intsToMul[i][1]));
155       do {
156         for (int j = 0; j < 2; j++) {
157           longsToMul[i][j] = randomBigInteger(Long.SIZE - 2).longValue();
158         }
159       } while (!Impl.GUAVA.noMulOverflow(longsToMul[i][0], longsToMul[i][1]));
160 
161       int k = binomials[i][1] = RANDOM_SOURCE.nextInt(MathBenchmarking.biggestBinomials.length);
162       binomials[i][0] = RANDOM_SOURCE.nextInt(MathBenchmarking.biggestBinomials[k] - k) + k;
163     }
164   }
165 
factorialDouble(int reps)166   @Benchmark long factorialDouble(int reps) {
167     long tmp = 0;
168     for (int i = 0; i < reps; i++) {
169       int j = i & ARRAY_MASK;
170       tmp += Double.doubleToRawLongBits(impl.factorialDouble(factorials[j]));
171     }
172     return tmp;
173   }
174 
intGCD(int reps)175   @Benchmark int intGCD(int reps) {
176     int tmp = 0;
177     for (int i = 0; i < reps; i++) {
178       int j = i & ARRAY_MASK;
179       tmp += impl.gcdInt(nonnegInt[j][0], nonnegInt[j][1]);
180     }
181     return tmp;
182   }
183 
longGCD(int reps)184   @Benchmark long longGCD(int reps) {
185     long tmp = 0;
186     for (int i = 0; i < reps; i++) {
187       int j = i & ARRAY_MASK;
188       tmp += impl.gcdLong(nonnegLong[j][0], nonnegLong[j][1]);
189     }
190     return tmp;
191   }
192 
binomialCoefficient(int reps)193   @Benchmark long binomialCoefficient(int reps) {
194     long tmp = 0;
195     for (int i = 0; i < reps; i++) {
196       int j = i & ARRAY_MASK;
197       tmp += impl.binomialCoefficient(binomials[j][0], binomials[j][1]);
198     }
199     return tmp;
200   }
201 
intAddOverflow(int reps)202   @Benchmark int intAddOverflow(int reps) {
203     int tmp = 0;
204     for (int i = 0; i < reps; i++) {
205       int j = i & ARRAY_MASK;
206       if (impl.noAddOverflow(intsToAdd[j][0], intsToAdd[j][1])) {
207         tmp++;
208       }
209     }
210     return tmp;
211   }
212 
longAddOverflow(int reps)213   @Benchmark int longAddOverflow(int reps) {
214     int tmp = 0;
215     for (int i = 0; i < reps; i++) {
216       int j = i & ARRAY_MASK;
217       if (impl.noAddOverflow(longsToAdd[j][0], longsToAdd[j][1])) {
218         tmp++;
219       }
220     }
221     return tmp;
222   }
223 
intMulOverflow(int reps)224   @Benchmark int intMulOverflow(int reps) {
225     int tmp = 0;
226     for (int i = 0; i < reps; i++) {
227       int j = i & ARRAY_MASK;
228       if (impl.noMulOverflow(intsToMul[j][0], intsToMul[j][1])) {
229         tmp++;
230       }
231     }
232     return tmp;
233   }
234 
longMulOverflow(int reps)235   @Benchmark int longMulOverflow(int reps) {
236     int tmp = 0;
237     for (int i = 0; i < reps; i++) {
238       int j = i & ARRAY_MASK;
239       if (impl.noMulOverflow(longsToMul[j][0], longsToMul[j][1])) {
240         tmp++;
241       }
242     }
243     return tmp;
244   }
245 }
246