1 /*
2
3 dsh-timer Timer with nanosecond resolution and summary statistics
4 on recorded elapsed times.
5 Copyright (c) 2004-2013 held jointly by the individual authors.
6
7 This library is free software; you can redistribute it and/or modify it
8 under the terms of the GNU Lesser General Public License as published
9 by the Free Software Foundation; either version 3 of the License, or (at
10 your option) any later version.
11
12 This library is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; with out even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
15 License for more details.
16
17 You should have received a copy of the GNU Lesser General Public License
18 along with this library; if not, write to the Free Software Foundation,
19 Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
20
21 > http://www.fsf.org/licensing/licenses/lgpl.html
22 > http://www.opensource.org/licenses/lgpl-license.php
23
24 */
25 package org.dishevelled.timer;
26
27 import java.util.Map;
28 import java.util.List;
29 import java.util.ArrayList;
30 import java.util.Random;
31 import java.util.HashMap;
32 import java.util.Collections;
33
34 import org.apache.commons.math.stat.descriptive.SummaryStatistics;
35
36 /**
37 * Timer class with nanosecond resolution and summary
38 * statistics on recorded elapsed times. This class provides
39 * nanosecond precision but not necessarily nanosecond accuracy
40 * (see the javadoc for <code>System.nanoTime()</code> for more
41 * details). The recorded times themselves are not preserved,
42 * however, only the statistics. As a consequence <code>start()</code>
43 * and <code>stop()</code> can be called many number of times
44 * without requiring large amounts of memory.
45 *
46 * <h4>Special cases</h4>
47 * <p>When <code>size() == 0</code>,
48 * <pre>
49 * min() == Double.NaN
50 * max() == Double.NaN
51 * mean() == Double.NaN
52 * standardDeviation() == Double.NaN
53 * </pre>
54 * </p>
55 * <p>When <code>size() == 1</code>,
56 * <pre>
57 * standardDeviation() == 0.0d
58 * </pre>
59 * </p>
60 *
61 * <h4>Static methods</h4>
62 * <p>Execution time can be sensitive to various factors, such
63 * as order of execution, runtime optimization from the just-in-time compiler
64 * (JIT), and garbage collection. This class provides static methods
65 * to help deal with these factors.</p>
66 *
67 * <p>Given a few benchmarks to run, wrap them in Runnable objects
68 * <pre>
69 * Runnable r0 = new Runnable() { public void run() { ... } };
70 * Runnable r1 = new Runnable() { public void run() { ... } };
71 * Runnable r2 = new Runnable() { public void run() { ... } };
72 * List<Runnable> benchmarks = Arrays.asList(new Runnable[] { r0, r1, r2 });
73 * </pre>
74 * Prime the JIT by running the benchmarks several times
75 * <pre>
76 * Timer.prime(benchmarks, 1000);
77 * </pre>
78 * Then measure the execution times of the benchmarks by running
79 * them several times in random execution order
80 * <pre>
81 * Map<Runnable, Timer> result = Timer.shuffle(benchmarks, 100, 100);
82 * </pre>
83 * Summary statistics on recorded execution times are captured by the
84 * timer returned for each Runnable benchmark
85 * <pre>
86 * for (Map.Entry<Runnable, Timer> e : result.entrySet()) {
87 * Runnable r = e.getKey();
88 * Timer t = e.getValue();
89 * System.out.println("runnable=" + r + " mean execution time=" + t.mean() + "ns");
90 * }
91 * </pre></p>
92 *
93 * @see java.lang.System#nanoTime
94 * @author Michael Heuer
95 */
96 public final class Timer
97 {
98 /** Summary statistics. */
99 private final SummaryStatistics summaryStatistics;
100
101 /** Last start time, in nanoseconds. */
102 private double startTime;
103
104 /** Flag indicating this timer has been started at least once. */
105 private boolean started;
106
107
108 /**
109 * Create a new timer.
110 */
111 public Timer()
112 {
113 summaryStatistics = new SummaryStatistics();
114 started = false;
115 }
116
117
118 /**
119 * Reset the record of elapsed times from this timer. After
120 * the timer has been reset, it must be started at least once
121 * before <code>stop()</code> is called.
122 */
123 public void reset()
124 {
125 summaryStatistics.clear();
126 started = false;
127 }
128
129 /**
130 * Start the timer. The timer must be started at least once
131 * before <code>stop()</code> is called.
132 */
133 public void start()
134 {
135 started = true;
136 startTime = System.nanoTime();
137 }
138
139 /**
140 * Stop the timer and record the time elapsed in nanoseconds
141 * since <code>start()</code> was last called.
142 *
143 * @throws TimerException if <code>start()</code> has not been called
144 * at least once before this method was called
145 */
146 public void stop()
147 {
148 if (started)
149 {
150 double currentTime = System.nanoTime();
151 double elapsedTime = currentTime - startTime;
152 summaryStatistics.addValue(elapsedTime);
153 }
154 else
155 {
156 throw new TimerException("timer was never started");
157 }
158 }
159
160 /**
161 * Return the minimum elapsed time recorded by this timer
162 * in nanoseconds.
163 *
164 * @return the minimum elapsed time recorded by this timer
165 * in nanoseconds
166 */
167 public double min()
168 {
169 return summaryStatistics.getMin();
170 }
171
172 /**
173 * Return the maximum elapsed time recorded by this timer
174 * in nanoseconds.
175 *
176 * @return the maximum elapsed time recorded by this timer
177 * in nanoseconds
178 */
179 public double max()
180 {
181 return summaryStatistics.getMax();
182 }
183
184 /**
185 * Return the number of elapsed times recorded by this timer.
186 *
187 * @return the number of elapsed times recorded by this timer
188 */
189 public long size()
190 {
191 return summaryStatistics.getN();
192 }
193
194 /**
195 * Return the sum of the elapsed times recorded by this timer
196 * in nanoseconds.
197 *
198 * @return the sum of the elapsed times recorded by this timer
199 */
200 public double sum()
201 {
202 return summaryStatistics.getSum();
203 }
204
205 /**
206 * Return the arithmetic mean of the elapsed times recorded by this
207 * timer in nanoseconds.
208 *
209 * @return the arithmetic mean of the elapsed times recorded by this
210 * timer in nanoseconds
211 */
212 public double mean()
213 {
214 return summaryStatistics.getMean();
215 }
216
217 /**
218 * Return the standard deviation of the elapsed times recorded by this
219 * timer in nanoseconds.
220 *
221 * @return the standard deviation of the elapsed times recorded by this
222 * timer in nanoseconds
223 */
224 public double standardDeviation()
225 {
226 return summaryStatistics.getStandardDeviation();
227 }
228
229
230 /**
231 * Time the specified code block.
232 *
233 * @param codeBlock code block to execute
234 * @return timer used to measure execution time
235 */
236 public static Timer time(final Runnable codeBlock)
237 {
238 return time(codeBlock, new Timer());
239 }
240
241 /**
242 * Time the specified code block with the specified timer.
243 *
244 * @param codeBlock code block to execute
245 * @param t timer to use to measure execution time
246 * @return timer used to measure execution time
247 */
248 public static Timer time(final Runnable codeBlock, final Timer t)
249 {
250 t.start();
251 codeBlock.run();
252 t.stop();
253 return t;
254 }
255
256 /**
257 * Prime the just-in-time compiler (JIT) by executing the
258 * specified code block <code>n</code> times.
259 *
260 * @param codeBlock code block to execute
261 * @param n number of times to execute code block
262 */
263 public static void prime(final Runnable codeBlock, final int n)
264 {
265 for (int i = 0; i < n; i++)
266 {
267 codeBlock.run();
268 }
269 }
270
271 /**
272 * Prime the just-in-time compiler (JIT) by executing each
273 * code block in the specified list of code blocks <code>n</code> times.
274 *
275 * @param codeBlocks list of code blocks to execute
276 * @param n number of times to execute each code block
277 */
278 public static void prime(final List<? extends Runnable> codeBlocks, final int n)
279 {
280 for (Runnable codeBlock : codeBlocks)
281 {
282 prime(codeBlock, n);
283 }
284 }
285
286 /**
287 * Loop over the specified code block <code>n</code> times.
288 *
289 * @param codeBlock code block to execute
290 * @param n number of times to execute code block
291 * @return timer used to measure execution time
292 */
293 public static Timer loop(final Runnable codeBlock, final int n)
294 {
295 return loop(codeBlock, n, new Timer());
296 }
297
298 /**
299 * Loop over the specified code block <code>n</code> times
300 * with the specified timer.
301 *
302 * @param codeBlock code block to execute
303 * @param n number of times to execute code block
304 * @param t timer to use to measure execution time
305 * @return timer used to measure execution time
306 */
307 public static Timer loop(final Runnable codeBlock, final int n, final Timer t)
308 {
309 for (int i = 0; i < n; i++)
310 {
311 time(codeBlock, t);
312 }
313 return t;
314 }
315
316 /**
317 * For each of the code blocks in the specified list of code blocks,
318 * loop over the code block <code>n</code> times.
319 *
320 * @param codeBlocks list of code blocks to execute
321 * @param n number of times to execute each code block
322 * @return map of code blocks to timers used to measure execution time
323 */
324 public static Map<Runnable, Timer> loop(final List<? extends Runnable> codeBlocks, final int n)
325 {
326 Map<Runnable, Timer> map = new HashMap<Runnable, Timer>(codeBlocks.size());
327 for (Runnable codeBlock : codeBlocks)
328 {
329 map.put(codeBlock, loop(codeBlock, n));
330 }
331 return Collections.unmodifiableMap(map);
332 }
333
334 /**
335 * Loop over the code blocks in the specified list of code blocks
336 * <code>n</code> times, executing each code block <code>m</code> times.
337 *
338 * @param codeBlocks list of code blocks to execute
339 * @param n number of times to loop over the list of code blocks
340 * @param m number of times to execute each code block
341 * @return map of code blocks to timers used to measure execution time
342 */
343 public static Map<Runnable, Timer> loop(final List<? extends Runnable> codeBlocks, final int n, final int m)
344 {
345 Map<Runnable, Timer> map = new HashMap<Runnable, Timer>(codeBlocks.size());
346 for (int i = 0; i < n; i++)
347 {
348 for (Runnable codeBlock : codeBlocks)
349 {
350 if (map.containsKey(codeBlock))
351 {
352 Timer t = map.get(codeBlock);
353 loop(codeBlock, m, t);
354 map.put(codeBlock, t);
355 }
356 else
357 {
358 map.put(codeBlock, loop(codeBlock, m));
359 }
360 }
361 }
362 return Collections.unmodifiableMap(map);
363 }
364
365 /**
366 * For each of the code blocks in the specified list of code blocks,
367 * executed in random order, loop over the code block <code>n</code> times.
368 *
369 * @param codeBlocks list of code blocks to execute
370 * @param n number of times to execute each code block
371 * @return map of code blocks to timers used to measure execution time
372 */
373 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks, final int n)
374 {
375 return shuffle(codeBlocks, n, new Random());
376 }
377
378 /**
379 * For each of the code blocks in the specified list of code blocks,
380 * executed in random order using the specified source of randomness,
381 * loop over the code block <code>n</code> times.
382 *
383 * @param codeBlocks list of code blocks to execute
384 * @param n number of times to execute each code block
385 * @param random source of randomness
386 * @return map of code blocks to timers used to measure execution time
387 */
388 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks, final int n, final Random random)
389 {
390 List<Runnable> codeBlocksCopy = new ArrayList<Runnable>(codeBlocks);
391 Collections.shuffle(codeBlocksCopy, random);
392 return loop(codeBlocksCopy, n);
393 }
394
395 /**
396 * Loop over the code blocks in the specified list of code blocks
397 * <code>n</code> times, in random order, executing each code block
398 * <code>m</code> times.
399 *
400 * @param codeBlocks list of code blocks to execute
401 * @param n number of times to loop over the list of code blocks
402 * @param m number of times to execute each code block
403 * @return map of code blocks to timers used to measure execution time
404 */
405 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks, final int n, final int m)
406 {
407 return shuffle(codeBlocks, n, m, new Random());
408 }
409
410 /**
411 * Loop over the code blocks in the specified list of code blocks
412 * <code>n</code> times, in random order using the specified source of
413 * randomness, executing each code block <code>m</code> times.
414 *
415 * @param codeBlocks list of code blocks to execute
416 * @param n number of times to loop over the list of code blocks
417 * @param m number of times to execute each code block
418 * @param random source of randomness
419 * @return map of code blocks to timers used to measure execution time
420 */
421 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks,
422 final int n,
423 final int m,
424 final Random random)
425 {
426 List<Runnable> codeBlocksCopy = new ArrayList<Runnable>(codeBlocks);
427 Map<Runnable, Timer> map = new HashMap<Runnable, Timer>(codeBlocksCopy.size());
428 for (int i = 0; i < n; i++)
429 {
430 Collections.shuffle(codeBlocksCopy, random);
431 for (Runnable codeBlock : codeBlocksCopy)
432 {
433 if (map.containsKey(codeBlock))
434 {
435 Timer t = map.get(codeBlock);
436 loop(codeBlock, m, t);
437 map.put(codeBlock, t);
438 }
439 else
440 {
441 map.put(codeBlock, loop(codeBlock, m));
442 }
443 }
444 }
445 return Collections.unmodifiableMap(map);
446 }
447 }