1 /*
2
3 dsh-timer Timer with nanosecond resolution and summary statistics
4 on recorded elapsed times.
5 Copyright (c) 2004-2011 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 * @version $Revision: 976 $ $Date: 2011-01-04 21:46:30 -0600 (Tue, 04 Jan 2011) $
96 */
97 public final class Timer
98 {
99 /** Summary statistics. */
100 private final SummaryStatistics summaryStatistics;
101
102 /** Last start time, in nanoseconds. */
103 private double startTime;
104
105 /** Flag indicating this timer has been started at least once. */
106 private boolean started;
107
108
109 /**
110 * Create a new timer.
111 */
112 public Timer()
113 {
114 summaryStatistics = new SummaryStatistics();
115 started = false;
116 }
117
118
119 /**
120 * Reset the record of elapsed times from this timer. After
121 * the timer has been reset, it must be started at least once
122 * before <code>stop()</code> is called.
123 */
124 public void reset()
125 {
126 summaryStatistics.clear();
127 started = false;
128 }
129
130 /**
131 * Start the timer. The timer must be started at least once
132 * before <code>stop()</code> is called.
133 */
134 public void start()
135 {
136 started = true;
137 startTime = System.nanoTime();
138 }
139
140 /**
141 * Stop the timer and record the time elapsed in nanoseconds
142 * since <code>start()</code> was last called.
143 *
144 * @throws TimerException if <code>start()</code> has not been called
145 * at least once before this method was called
146 */
147 public void stop()
148 {
149 if (started)
150 {
151 double currentTime = System.nanoTime();
152 double elapsedTime = currentTime - startTime;
153 summaryStatistics.addValue(elapsedTime);
154 }
155 else
156 {
157 throw new TimerException("timer was never started");
158 }
159 }
160
161 /**
162 * Return the minimum elapsed time recorded by this timer
163 * in nanoseconds.
164 *
165 * @return the minimum elapsed time recorded by this timer
166 * in nanoseconds
167 */
168 public double min()
169 {
170 return summaryStatistics.getMin();
171 }
172
173 /**
174 * Return the maximum elapsed time recorded by this timer
175 * in nanoseconds.
176 *
177 * @return the maximum elapsed time recorded by this timer
178 * in nanoseconds
179 */
180 public double max()
181 {
182 return summaryStatistics.getMax();
183 }
184
185 /**
186 * Return the number of elapsed times recorded by this timer.
187 *
188 * @return the number of elapsed times recorded by this timer
189 */
190 public long size()
191 {
192 return summaryStatistics.getN();
193 }
194
195 /**
196 * Return the sum of the elapsed times recorded by this timer
197 * in nanoseconds.
198 *
199 * @return the sum of the elapsed times recorded by this timer
200 */
201 public double sum()
202 {
203 return summaryStatistics.getSum();
204 }
205
206 /**
207 * Return the arithmetic mean of the elapsed times recorded by this
208 * timer in nanoseconds.
209 *
210 * @return the arithmetic mean of the elapsed times recorded by this
211 * timer in nanoseconds
212 */
213 public double mean()
214 {
215 return summaryStatistics.getMean();
216 }
217
218 /**
219 * Return the standard deviation of the elapsed times recorded by this
220 * timer in nanoseconds.
221 *
222 * @return the standard deviation of the elapsed times recorded by this
223 * timer in nanoseconds
224 */
225 public double standardDeviation()
226 {
227 return summaryStatistics.getStandardDeviation();
228 }
229
230
231 /**
232 * Time the specified code block.
233 *
234 * @param codeBlock code block to execute
235 * @return timer used to measure execution time
236 */
237 public static Timer time(final Runnable codeBlock)
238 {
239 return time(codeBlock, new Timer());
240 }
241
242 /**
243 * Time the specified code block with the specified timer.
244 *
245 * @param codeBlock code block to execute
246 * @param t timer to use to measure execution time
247 * @return timer used to measure execution time
248 */
249 public static Timer time(final Runnable codeBlock, final Timer t)
250 {
251 t.start();
252 codeBlock.run();
253 t.stop();
254 return t;
255 }
256
257 /**
258 * Prime the just-in-time compiler (JIT) by executing the
259 * specified code block <code>n</code> times.
260 *
261 * @param codeBlock code block to execute
262 * @param n number of times to execute code block
263 */
264 public static void prime(final Runnable codeBlock, final int n)
265 {
266 for (int i = 0; i < n; i++)
267 {
268 codeBlock.run();
269 }
270 }
271
272 /**
273 * Prime the just-in-time compiler (JIT) by executing each
274 * code block in the specified list of code blocks <code>n</code> times.
275 *
276 * @param codeBlocks list of code blocks to execute
277 * @param n number of times to execute each code block
278 */
279 public static void prime(final List<? extends Runnable> codeBlocks, final int n)
280 {
281 for (Runnable codeBlock : codeBlocks)
282 {
283 prime(codeBlock, n);
284 }
285 }
286
287 /**
288 * Loop over the specified code block <code>n</code> times.
289 *
290 * @param codeBlock code block to execute
291 * @param n number of times to execute code block
292 * @return timer used to measure execution time
293 */
294 public static Timer loop(final Runnable codeBlock, final int n)
295 {
296 return loop(codeBlock, n, new Timer());
297 }
298
299 /**
300 * Loop over the specified code block <code>n</code> times
301 * with the specified timer.
302 *
303 * @param codeBlock code block to execute
304 * @param n number of times to execute code block
305 * @param t timer to use to measure execution time
306 * @return timer used to measure execution time
307 */
308 public static Timer loop(final Runnable codeBlock, final int n, final Timer t)
309 {
310 for (int i = 0; i < n; i++)
311 {
312 time(codeBlock, t);
313 }
314 return t;
315 }
316
317 /**
318 * For each of the code blocks in the specified list of code blocks,
319 * loop over the code block <code>n</code> times.
320 *
321 * @param codeBlocks list of code blocks to execute
322 * @param n number of times to execute each code block
323 * @return map of code blocks to timers used to measure execution time
324 */
325 public static Map<Runnable, Timer> loop(final List<? extends Runnable> codeBlocks, final int n)
326 {
327 Map<Runnable, Timer> map = new HashMap<Runnable, Timer>(codeBlocks.size());
328 for (Runnable codeBlock : codeBlocks)
329 {
330 map.put(codeBlock, loop(codeBlock, n));
331 }
332 return Collections.unmodifiableMap(map);
333 }
334
335 /**
336 * Loop over the code blocks in the specified list of code blocks
337 * <code>n</code> times, executing each code block <code>m</code> times.
338 *
339 * @param codeBlocks list of code blocks to execute
340 * @param n number of times to loop over the list of code blocks
341 * @param m number of times to execute each code block
342 * @return map of code blocks to timers used to measure execution time
343 */
344 public static Map<Runnable, Timer> loop(final List<? extends Runnable> codeBlocks, final int n, final int m)
345 {
346 Map<Runnable, Timer> map = new HashMap<Runnable, Timer>(codeBlocks.size());
347 for (int i = 0; i < n; i++)
348 {
349 for (Runnable codeBlock : codeBlocks)
350 {
351 if (map.containsKey(codeBlock))
352 {
353 Timer t = map.get(codeBlock);
354 loop(codeBlock, m, t);
355 map.put(codeBlock, t);
356 }
357 else
358 {
359 map.put(codeBlock, loop(codeBlock, m));
360 }
361 }
362 }
363 return Collections.unmodifiableMap(map);
364 }
365
366 /**
367 * For each of the code blocks in the specified list of code blocks,
368 * executed in random order, loop over the code block <code>n</code> times.
369 *
370 * @param codeBlocks list of code blocks to execute
371 * @param n number of times to execute each code block
372 * @return map of code blocks to timers used to measure execution time
373 */
374 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks, final int n)
375 {
376 return shuffle(codeBlocks, n, new Random());
377 }
378
379 /**
380 * For each of the code blocks in the specified list of code blocks,
381 * executed in random order using the specified source of randomness,
382 * loop over the code block <code>n</code> times.
383 *
384 * @param codeBlocks list of code blocks to execute
385 * @param n number of times to execute each code block
386 * @param random source of randomness
387 * @return map of code blocks to timers used to measure execution time
388 */
389 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks, final int n, final Random random)
390 {
391 List<Runnable> codeBlocksCopy = new ArrayList<Runnable>(codeBlocks);
392 Collections.shuffle(codeBlocksCopy, random);
393 return loop(codeBlocksCopy, n);
394 }
395
396 /**
397 * Loop over the code blocks in the specified list of code blocks
398 * <code>n</code> times, in random order, executing each code block
399 * <code>m</code> times.
400 *
401 * @param codeBlocks list of code blocks to execute
402 * @param n number of times to loop over the list of code blocks
403 * @param m number of times to execute each code block
404 * @return map of code blocks to timers used to measure execution time
405 */
406 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks, final int n, final int m)
407 {
408 return shuffle(codeBlocks, n, m, new Random());
409 }
410
411 /**
412 * Loop over the code blocks in the specified list of code blocks
413 * <code>n</code> times, in random order using the specified source of
414 * randomness, executing each code block <code>m</code> times.
415 *
416 * @param codeBlocks list of code blocks to execute
417 * @param n number of times to loop over the list of code blocks
418 * @param m number of times to execute each code block
419 * @param random source of randomness
420 * @return map of code blocks to timers used to measure execution time
421 */
422 public static Map<Runnable, Timer> shuffle(final List<? extends Runnable> codeBlocks,
423 final int n,
424 final int m,
425 final Random random)
426 {
427 List<Runnable> codeBlocksCopy = new ArrayList<Runnable>(codeBlocks);
428 Map<Runnable, Timer> map = new HashMap<Runnable, Timer>(codeBlocksCopy.size());
429 for (int i = 0; i < n; i++)
430 {
431 Collections.shuffle(codeBlocksCopy, random);
432 for (Runnable codeBlock : codeBlocksCopy)
433 {
434 if (map.containsKey(codeBlock))
435 {
436 Timer t = map.get(codeBlock);
437 loop(codeBlock, m, t);
438 map.put(codeBlock, t);
439 }
440 else
441 {
442 map.put(codeBlock, loop(codeBlock, m));
443 }
444 }
445 }
446 return Collections.unmodifiableMap(map);
447 }
448 }