1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.math4.legacy;
18
19 import java.util.regex.Pattern;
20 import java.util.regex.Matcher;
21 import java.util.regex.MatchResult;
22 import java.util.concurrent.Callable;
23
24 import org.apache.commons.rng.UniformRandomProvider;
25 import org.apache.commons.rng.simple.RandomSource;
26 import org.apache.commons.rng.sampling.PermutationSampler;
27 import org.apache.commons.math4.legacy.exception.MathIllegalStateException;
28 import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException;
29 import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
30 import org.apache.commons.math4.legacy.stat.descriptive.StatisticalSummary;
31 import org.apache.commons.math4.legacy.stat.descriptive.SummaryStatistics;
32
33 /**
34 * Simple benchmarking utilities.
35 */
36 public final class PerfTestUtils {
37 /** Formatting. */
38 private static final int DEFAULT_MAX_NAME_WIDTH = 45;
39 /** Formatting. */
40 private static final String ELLIPSIS = "...";
41 /** Formatting. */
42 private static final String TO_STRING_MEMORY_ADDRESS_REGEX = "@\\p{XDigit}{1,8}";
43 /** Formatting. */
44 private static final String JAVA_IDENTIFIER_REGEX =
45 "(\\p{javaJavaIdentifierStart}\\p{javaJavaIdentifierPart}*\\.)*\\p{javaJavaIdentifierStart}\\p{javaJavaIdentifierPart}*";
46 /** Formatting. */
47 private static final Pattern JAVA_IDENTIFIER_PATTERN =
48 Pattern.compile(JAVA_IDENTIFIER_REGEX);
49 /** Nanoseconds to milliseconds conversion factor ({@value}). */
50 public static final double NANO_TO_MILLI = 1e-6;
51 /** Default number of code repeat per timed block. */
52 private static final int DEFAULT_REPEAT_CHUNK = 1000;
53 /** Default number of code repeats for computing the average run time. */
54 private static final int DEFAULT_REPEAT_STAT = 10000;
55 /** RNG. */
56 private static UniformRandomProvider rng = RandomSource.WELL_19937_C.create();
57
58 /** No instances. */
59 private PerfTestUtils() {}
60
61 /**
62 * Timing.
63 *
64 * @param repeatChunk Each timing measurement will done done for that
65 * number of repeats of the code.
66 * @param repeatStat Timing will be averaged over that number of runs.
67 * @param runGC Call {@code System.gc()} between each timed block. When
68 * set to {@code true}, the test will run much slower.
69 * @param methods Codes being timed.
70 * @return for each of the given {@code methods}, a
71 * {@link StatisticalSummary} of the average times (in milliseconds)
72 * taken by a single call to the {@code call} method (i.e. the time
73 * taken by each timed block divided by {@code repeatChunk}).
74 */
75 @SafeVarargs
76 public static StatisticalSummary[] time(int repeatChunk,
77 int repeatStat,
78 boolean runGC,
79 Callable<Double> ... methods) {
80 final double[][][] times = timesAndResults(repeatChunk,
81 repeatStat,
82 runGC,
83 methods);
84
85 final int len = methods.length;
86 final StatisticalSummary[] stats = new StatisticalSummary[len];
87 for (int j = 0; j < len; j++) {
88 final SummaryStatistics s = new SummaryStatistics();
89 for (int k = 0; k < repeatStat; k++) {
90 s.addValue(times[j][k][0]);
91 }
92 stats[j] = s.getSummary();
93 }
94
95 return stats;
96 }
97
98 /**
99 * Timing.
100 *
101 * @param repeatChunk Each timing measurement will done done for that
102 * number of repeats of the code.
103 * @param repeatStat Timing will be averaged over that number of runs.
104 * @param runGC Call {@code System.gc()} between each timed block. When
105 * set to {@code true}, the test will run much slower.
106 * @param methods Codes being timed.
107 * @return for each of the given {@code methods} (first dimension), and
108 * each of the {@code repeatStat} runs (second dimension):
109 * <ul>
110 * <li>
111 * the average time (in milliseconds) taken by a single call to the
112 * {@code call} method (i.e. the time taken by each timed block divided
113 * by {@code repeatChunk})
114 * </li>
115 * <li>
116 * the result returned by the {@code call} method.
117 * </li>
118 * </ul>
119 */
120 @SafeVarargs
121 public static double[][][] timesAndResults(int repeatChunk,
122 int repeatStat,
123 boolean runGC,
124 Callable<Double> ... methods) {
125 final int numMethods = methods.length;
126 final double[][][] timesAndResults = new double[numMethods][repeatStat][2];
127
128 // Indices into the array containing the methods to benchmark.
129 // The purpose is that at each repeat, the "methods" are called in a different order.
130 final int[] methodSequence = PermutationSampler.natural(numMethods);
131
132 try {
133 for (int k = 0; k < repeatStat; k++) {
134 PermutationSampler.shuffle(rng, methodSequence);
135 for (int n = 0; n < numMethods; n++) {
136 final int j = methodSequence[n]; // Index of the timed method.
137
138 if (runGC) {
139 // Try to perform GC outside the timed block.
140 System.gc();
141 }
142
143 final Callable<Double> r = methods[j];
144 final double[] result = new double[repeatChunk];
145
146 // Timed block.
147 final long start = System.nanoTime();
148 for (int i = 0; i < repeatChunk; i++) {
149 result[i] = r.call().doubleValue();
150 }
151 final long stop = System.nanoTime();
152
153 // Collect run time.
154 timesAndResults[j][k][0] = (stop - start) * NANO_TO_MILLI;
155 // Keep track of a randomly selected result.
156 timesAndResults[j][k][1] = result[rng.nextInt(repeatChunk)];
157 }
158 }
159 } catch (Exception e) {
160 // Abort benchmarking if codes throw exceptions.
161 throw new MathIllegalStateException(LocalizedFormats.SIMPLE_MESSAGE, e.getMessage());
162 }
163
164 final double normFactor = 1d / repeatChunk;
165 for (int j = 0; j < numMethods; j++) {
166 for (int k = 0; k < repeatStat; k++) {
167 timesAndResults[j][k][0] *= normFactor;
168 }
169 }
170
171 return timesAndResults;
172 }
173
174 /**
175 * Timing and report (to standard output) the average time and standard
176 * deviation of a single call.
177 * The timing is performed by calling the
178 * {@link #time(int,int,boolean,Callable[]) time} method.
179 *
180 * @param title Title of the test (for the report).
181 * @param maxNameWidth Maximum width of the first column of the report.
182 * @param repeatChunk Each timing measurement will done done for that
183 * number of repeats of the code.
184 * @param repeatStat Timing will be averaged over that number of runs.
185 * @param runGC Call {@code System.gc()} between each timed block. When
186 * set to {@code true}, the test will run much slower.
187 * @param methods Codes being timed.
188 * @return for each of the given {@code methods}, a statistics of the
189 * average times (in milliseconds) taken by a single call to the
190 * {@code call} method (i.e. the time taken by each timed block divided
191 * by {@code repeatChunk}).
192 */
193 @SuppressWarnings("boxing")
194 public static StatisticalSummary[] timeAndReport(String title,
195 int maxNameWidth,
196 int repeatChunk,
197 int repeatStat,
198 boolean runGC,
199 RunTest ... methods) {
200 // Header format.
201 final String hFormat = "%s (calls per timed block: %d, timed blocks: %d, time unit: ms)";
202
203 // TODO: user-defined parameter?
204 final boolean removePackageName = false;
205
206 // Width of the longest name.
207 int nameLength = 0;
208 for (RunTest m : methods) {
209 int len = shorten(m.getName(), removePackageName).length();
210 if (len > nameLength) {
211 nameLength = len;
212 }
213 }
214 final int actualNameLength = nameLength < maxNameWidth ?
215 nameLength :
216 maxNameWidth;
217 final String nameLengthFormat = "%" + actualNameLength + "s";
218
219 // Column format.
220 final String cFormat = nameLengthFormat + " %9s %7s %10s %5s %4s %10s";
221 // Result format.
222 final String format = nameLengthFormat + " %.3e %.1e %.4e %.3f %.2f %.4e";
223
224 System.out.println(String.format(hFormat,
225 title,
226 repeatChunk,
227 repeatStat));
228 System.out.println(String.format(cFormat,
229 "name",
230 "time/call",
231 "std dev",
232 "total time",
233 "ratio",
234 "cv",
235 "difference"));
236 final StatisticalSummary[] time = time(repeatChunk,
237 repeatStat,
238 runGC,
239 methods);
240 final double refSum = time[0].getSum() * repeatChunk;
241 for (int i = 0, max = time.length; i < max; i++) {
242 final StatisticalSummary s = time[i];
243 final double sum = s.getSum() * repeatChunk;
244 final double mean = s.getMean();
245 final double sigma = s.getStandardDeviation();
246 System.out.println(String.format(format,
247 truncate(shorten(methods[i].getName(),
248 removePackageName),
249 actualNameLength,
250 ELLIPSIS),
251 mean,
252 sigma,
253 sum,
254 sum / refSum,
255 sigma / mean,
256 sum - refSum));
257 }
258
259 return time;
260 }
261
262 /**
263 * Timing and report (to standard output).
264 * This method calls {@link #timeAndReport(String,int,int,int,boolean,RunTest[])
265 * timeAndReport(title, 45, 1000, 10000, false, methods)}.
266 *
267 * @param title Title of the test (for the report).
268 * @param methods Codes being timed.
269 * @return for each of the given {@code methods}, a statistics of the
270 * average times (in milliseconds) taken by a single call to the
271 * {@code call} method (i.e. the time taken by each timed block divided
272 * by {@code repeatChunk}).
273 */
274 public static StatisticalSummary[] timeAndReport(String title,
275 RunTest ... methods) {
276 return timeAndReport(title,
277 DEFAULT_MAX_NAME_WIDTH,
278 DEFAULT_REPEAT_CHUNK,
279 DEFAULT_REPEAT_STAT,
280 false,
281 methods);
282 }
283
284 /**
285 * Utility class for storing a test label.
286 */
287 public abstract static class RunTest implements Callable<Double> {
288 private final String name;
289
290 /**
291 * @param name Test name.
292 */
293 public RunTest(String name) {
294 this.name = name;
295 }
296
297 /**
298 * @return the name of this test.
299 */
300 public String getName() {
301 return name;
302 }
303
304 /** {@inheritDoc} */
305 @Override
306 public abstract Double call() throws Exception;
307 }
308
309 /**
310 * Truncates a string so that it will not be longer than the
311 * specified length.
312 *
313 * @param str String to truncate.
314 * @param maxLength Maximum length.
315 * @param ellipsis String to use in place of the part being removed
316 * from the original string.
317 * @return the truncated string.
318 * @throws NumberIsTooLargeException if the length of {@code ellipsis}
319 * is larger than {@code maxLength - 2}.
320 */
321 private static String truncate(String str,
322 int maxLength,
323 String ellipsis) {
324 final int ellSize = ellipsis.length();
325 if (ellSize > maxLength - 2) {
326 throw new NumberIsTooLargeException(ellSize, maxLength - 2, false);
327 }
328
329 final int strSize = str.length();
330 if (strSize <= maxLength) {
331 // Size is OK.
332 return str;
333 }
334
335 return str.substring(0, maxLength - ellSize) + ellipsis;
336 }
337
338 /**
339 * Shortens a string.
340 * It will shorten package names and remove memory addresses
341 * that appear in an instance's name.
342 *
343 * @param str Original string.
344 * @param removePackageName Whether package name part of a
345 * fully-qualified name should be removed entirely.
346 * @return the shortened string.
347 */
348 private static String shorten(String str,
349 boolean removePackageName) {
350 final Matcher m = JAVA_IDENTIFIER_PATTERN.matcher(str);
351 final StringBuffer sb = new StringBuffer();
352 while (m.find()) {
353 final MatchResult r = m.toMatchResult();
354 m.appendReplacement(sb, shortenPackageName(r.group(),
355 removePackageName));
356 }
357 m.appendTail(sb);
358
359 return sb.toString().replaceAll(TO_STRING_MEMORY_ADDRESS_REGEX, "");
360 }
361
362 /**
363 * Shortens package part of the name of a class.
364 *
365 * @param name Class name.
366 * @param remove Whether package name part of a fully-qualified
367 * name should be removed entirely.
368 * @return the shortened name.
369 */
370 private static String shortenPackageName(String name,
371 boolean remove) {
372 final String[] comp = name.split("\\.");
373 final int last = comp.length - 1;
374
375 if (remove) {
376 return comp[last];
377 }
378
379 final StringBuilder s = new StringBuilder();
380 for (int i = 0; i < last; i++) {
381 s.append(comp[i].substring(0, 1)).append(".");
382 }
383 s.append(comp[last]);
384
385 return s.toString();
386 }
387 }