Mercurial > hg > graal-compiler

comparison graal/com.oracle.max.base/src/com/sun/max/profile/ValueMetrics.java @ 3733:e233f5660da4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added Java files from Maxine project.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Sat, 17 Dec 2011 19:59:18 +0100
parents
children bc8527f3071c
comparison
equal deleted inserted replaced
3732:3e2e8b8abdaf 3733:e233f5660da4
1 /*
2 * Copyright (c) 2007, 2011, 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 package com.sun.max.profile;
24
25 import java.util.*;
26 import java.util.Arrays;
27
28 import com.sun.max.*;
29 import com.sun.max.profile.Metrics.*;
30 import com.sun.max.program.*;
31
32 /**
33 * This class is a container for a number of inner classes that support recording
34 * metrics about the distribution (i.e. frequency) of values. For example,
35 * these utilities can be used to gather the distribution of compilation times,
36 * object sizes, heap allocations, etc. Several different distribution implementations
37 * are available, with different time and space tradeoffs and different approximations,
38 * ranging from exact distributions to only distributions within a limited range.
39 */
40 public class ValueMetrics {
41
42 public static final Approximation EXACT = new Approximation();
43 public static final Approximation TRACE = new IntegerTraceApproximation(1024);
44
45 public static class Approximation {
46 }
47
48 public static class FixedApproximation extends Approximation {
49 protected final Object[] values;
50 public FixedApproximation(Object... values) {
51 this.values = values.clone();
52 }
53 }
54
55 public static class IntegerRangeApproximation extends Approximation {
56 protected final int lowValue;
57 protected final int highValue;
58 public IntegerRangeApproximation(int low, int high) {
59 lowValue = low;
60 highValue = high;
61 }
62 }
63
64 public static class IntegerTraceApproximation extends Approximation {
65 protected final int bufferSize;
66 public IntegerTraceApproximation(int bufferSize) {
67 this.bufferSize = bufferSize;
68 }
69 }
70
71 /**
72 * This class and its descendants allow recording of a distribution of integer values.
73 * Various implementations implement different approximations with different time and
74 * space tradeoffs. Because this class and its descendants record distributions only
75 * for integers, it can be more efficient than using boxed (e.g. {@code java.lang.Integer}) values.
76 *
77 */
78 public abstract static class IntegerDistribution extends Distribution<Integer> {
79
80 public abstract void record(int value);
81 }
82
83 public static class FixedRangeIntegerDistribution extends IntegerDistribution {
84 protected final int lowValue;
85 protected final int[] counts;
86 protected int missed;
87
88 public FixedRangeIntegerDistribution(int low, int high) {
89 lowValue = low;
90 counts = new int[high - low];
91 }
92
93 @Override
94 public void record(int value) {
95 total++;
96 final int index = value - lowValue;
97 if (index >= 0 && index < counts.length) {
98 counts[index]++;
99 } else {
100 missed++;
101 }
102 }
103
104 @Override
105 public int getCount(Integer value) {
106 final int index = value - lowValue;
107 if (index >= 0 && index < counts.length) {
108 return counts[index];
109 }
110 return missed > 0 ? -1 : 0;
111 }
112
113 @Override
114 public Map<Integer, Integer> asMap() {
115 final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
116 for (int i = 0; i != counts.length; ++i) {
117 map.put(lowValue + i, counts[i]);
118 }
119 return map;
120 }
121
122 @Override
123 public void reset() {
124 super.reset();
125 missed = 0;
126 Arrays.fill(counts, 0);
127 }
128 }
129
130 public static class FixedSetIntegerDistribution extends IntegerDistribution {
131
132 private final int[] set;
133 private final int[] count;
134 protected int missed;
135
136 public FixedSetIntegerDistribution(int[] set) {
137 // TODO: sort() and binarySearch for large sets.
138 this.set = set.clone();
139 count = new int[set.length];
140 }
141
142 @Override
143 public void record(int value) {
144 total++;
145 for (int i = 0; i < set.length; i++) {
146 if (set[i] == value) {
147 count[i]++;
148 return;
149 }
150 }
151 missed++;
152 }
153
154 @Override
155 public int getCount(Integer value) {
156 final int val = value;
157 for (int i = 0; i < set.length; i++) {
158 if (set[i] == val) {
159 return count[i];
160 }
161 }
162 return missed > 0 ? -1 : 0;
163 }
164
165 @Override
166 public Map<Integer, Integer> asMap() {
167 final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
168 for (int i = 0; i != count.length; ++i) {
169 map.put(set[i], count[i]);
170 }
171 return map;
172 }
173
174 @Override
175 public void reset() {
176 super.reset();
177 missed = 0;
178 Arrays.fill(set, 0);
179 Arrays.fill(count, 0);
180 }
181 }
182
183 /**
184 * The trace integer distribution class collects an exact distribution of integer
185 * values by internally recording every integer value in order in a fixed size buffer.
186 * When the buffer fills up, its contents are sorted and then reduced into a
187 * sorted list of value/count pairs. This results in an exact distribution
188 * with a tunable size/performance tradeoff, since a larger buffer means
189 * fewer reduction steps.
190 *
191 * This implementation is <b>not thread safe</b>. It may lose updates and potentially
192 * generate exceptions if used in a multi-threaded scenario. To make updates
193 * to this distribution thread safe, {@linkplain ValueMetrics#threadSafe(IntegerDistribution) wrap}
194 * it with a {@link ThreadsafeIntegerDistribution}.
195 *
196 */
197 public static class TraceIntegerDistribution extends IntegerDistribution {
198 private final int[] buffer;
199 private int cursor;
200
201 private int[] values;
202 private int[] counts;
203
204 public TraceIntegerDistribution(int bufferSize) {
205 assert bufferSize > 0;
206 buffer = new int[bufferSize];
207 }
208
209 @Override
210 public void record(int value) {
211 total++;
212 buffer[cursor++] = value;
213 if (cursor == buffer.length) {
214 reduce();
215 }
216 }
217
218 @Override
219 public int getCount(Integer value) {
220 reduce();
221 final int index = Arrays.binarySearch(values, value);
222 if (index < 0) {
223 return 0;
224 }
225 return counts[index];
226 }
227
228 @Override
229 public Map<Integer, Integer> asMap() {
230 reduce();
231 // TODO: another map implementation might be better.
232 final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
233 if (values != null) {
234 for (int i = 0; i < values.length; i++) {
235 map.put(values[i], counts[i]);
236 }
237 }
238 return map;
239 }
240
241 @Override
242 public void reset() {
243 super.reset();
244 cursor = 0;
245 Arrays.fill(buffer, 0);
246 Arrays.fill(values, 0);
247 Arrays.fill(counts, 0);
248 }
249
250 private void reduce() {
251 if (cursor == 0) {
252 // no recorded values to reduce
253 return;
254 }
255 // compression needed.
256 Arrays.sort(buffer, 0, cursor);
257 if (values != null) {
258 // there are already some entries. need to merge counts
259 removeExistingValues();
260 if (cursor > 0) {
261 final int[] ovalues = values;
262 final int[] ocounts = counts;
263 reduceBuffer(buffer);
264 mergeValues(ovalues, ocounts, values, counts);
265 }
266 } else {
267 // there currently aren't any entry arrays. reduce the buffer to generate the first ones.
268 reduceBuffer(buffer);
269 }
270 cursor = 0;
271 }
272
273 private void removeExistingValues() {
274 // increment counts for values that already occur in the entry arrays
275 // and leave leftover values in the buffer
276 int valuesPos = 0;
277 final int ocursor = cursor;
278 cursor = 0;
279 for (int i = 0; i < ocursor; i++) {
280 final int nvalue = buffer[i];
281 while (valuesPos < values.length && values[valuesPos] < nvalue) {
282 valuesPos++;
283 }
284 if (valuesPos < values.length && values[valuesPos] == nvalue) {
285 counts[valuesPos]++;
286 } else {
287 // retain the new values in the buffer
288 buffer[cursor++] = nvalue;
289 }
290 }
291 }
292
293 private void mergeValues(int[] avalues, int[] acounts, int[] bvalues, int[] bcounts) {
294 final int[] nvalues = new int[avalues.length + values.length];
295 final int[] ncounts = new int[acounts.length + counts.length];
296
297 int a = 0;
298 int b = 0;
299 int n = 0;
300 while (n < nvalues.length) {
301 while (a < avalues.length && (b == bvalues.length || avalues[a] < bvalues[b])) {
302 nvalues[n] = avalues[a];
303 ncounts[n] = acounts[a];
304 n++;
305 a++;
306 }
307 while (b < bvalues.length && (a == avalues.length || bvalues[b] < avalues[a])) {
308 nvalues[n] = bvalues[b];
309 ncounts[n] = bcounts[b];
310 n++;
311 b++;
312 }
313 }
314 assert n == nvalues.length && a == avalues.length && b == bvalues.length;
315 values = nvalues;
316 counts = ncounts;
317 }
318
319 private void reduceBuffer(int[] buf) {
320 // count the unique values
321 int last1 = buf[0];
322 int unique = 1;
323 for (int i1 = 1; i1 < cursor; i1++) {
324 if (buffer[i1] != last1) {
325 unique++;
326 last1 = buffer[i1];
327 }
328 }
329 // create the values arrays and populate them
330 values = new int[unique];
331 counts = new int[unique];
332 int last = buffer[0];
333 int count = 1;
334 int pos = 0;
335 for (int i = 1; i < cursor; i++) {
336 if (buffer[i] != last) {
337 values[pos] = last;
338 counts[pos] = count;
339 pos++;
340 count = 1;
341 last = buffer[i];
342 } else {
343 count++;
344 }
345 }
346 assert pos == values.length - 1;
347 values[pos] = last;
348 counts[pos] = count;
349 }
350 }
351
352 public static class HashedIntegerDistribution extends IntegerDistribution {
353 private Map<Integer, Distribution> map;
354
355 private Map<Integer, Distribution> map() {
356 if (map == null) {
357 map = new HashMap<Integer, Distribution>();
358 }
359 return map;
360 }
361
362 @Override
363 public void record(int value) {
364 total++;
365 final Integer integer = value;
366 Distribution distribution = map().get(integer);
367 if (distribution == null) {
368 distribution = new Distribution();
369 map().put(integer, distribution);
370 }
371 distribution.total++;
372 }
373 @Override
374 public int getCount(Integer value) {
375 final Distribution distribution = map().get(value);
376 if (distribution != null) {
377 return distribution.total;
378 }
379 return 0;
380 }
381
382 @Override
383 public Map<Integer, Integer> asMap() {
384 final Map<Integer, Integer> result = new HashMap<Integer, Integer>();
385 for (Map.Entry<Integer, Distribution> entry : map().entrySet()) {
386 result.put(entry.getKey(), entry.getValue().total);
387 }
388 return result;
389 }
390
391 @Override
392 public void reset() {
393 super.reset();
394 map = null;
395 }
396 }
397
398 /**
399 * This class and its descendants support profiling of individual objects. Reference
400 * equality is used here exclusively. Various implementations with different size and space
401 * tradeoffs offer various levels of accuracy.
402 *
403 */
404 public abstract static class ObjectDistribution<T> extends Distribution<T> {
405 public abstract void record(T value);
406 }
407
408 public static class HashedObjectDistribution<T> extends ObjectDistribution<T> {
409 private Map<T, Distribution> map;
410 private Map<T, Distribution> map() {
411 if (map == null) {
412 map = new IdentityHashMap<T, Distribution>();
413 }
414 return map;
415 }
416
417 public HashedObjectDistribution() {
418 }
419
420 @Override
421 public void record(T value) {
422 total++;
423 Distribution distribution = map().get(value);
424 if (distribution == null) {
425 distribution = new Distribution();
426 map().put(value, distribution);
427 }
428 distribution.total++;
429 }
430 @Override
431 public int getCount(T value) {
432 final Distribution distribution = map().get(value);
433 if (distribution != null) {
434 return distribution.total;
435 }
436 return 0;
437 }
438
439 @Override
440 public Map<T, Integer> asMap() {
441 final Map<T, Integer> result = new IdentityHashMap<T, Integer>();
442 for (Map.Entry<T, Distribution> entry : map().entrySet()) {
443 result.put(entry.getKey(), entry.getValue().total);
444 }
445 return result;
446 }
447
448 @Override
449 public void reset() {
450 super.reset();
451 map = null;
452 }
453 }
454
455 public static class FixedSetObjectDistribution<T> extends ObjectDistribution<T> {
456
457 private final T[] set;
458 private final int[] count;
459 private int missed;
460
461 public FixedSetObjectDistribution(T[] set) {
462 this.set = set.clone();
463 count = new int[set.length];
464 }
465
466 @Override
467 public void record(T value) {
468 total++;
469 for (int i = 0; i < set.length; i++) {
470 if (set[i] == value) {
471 count[i]++;
472 return;
473 }
474 }
475 missed++;
476 }
477 @Override
478 public int getCount(T value) {
479 for (int i = 0; i < set.length; i++) {
480 if (set[i] == value) {
481 return count[i];
482 }
483 }
484 return missed > 0 ? -1 : 0;
485 }
486
487 @Override
488 public Map<T, Integer> asMap() {
489 final Map<T, Integer> map = new IdentityHashMap<T, Integer>();
490 for (int i = 0; i != count.length; ++i) {
491 map.put(set[i], count[i]);
492 }
493 return map;
494 }
495
496 @Override
497 public void reset() {
498 super.reset();
499 missed = 0;
500 Arrays.fill(set, 0);
501 Arrays.fill(count, 0);
502 }
503 }
504
505 /**
506 * This method creates a new distribution for the occurrence of integer values.
507 *
508 * @param name the name of the metric; if non-null, then a global metric of the specified
509 * name will be returned {@see GlobalMetrics}
510 * @param approx the approximation level that is requested. Different approximation levels
511 * have different time and space tradeoffs versus accuracy.
512 * @return a new integer distribution object that can be used to record occurrences of integers
513 */
514 public static IntegerDistribution newIntegerDistribution(String name, Approximation approx) {
515 if (name != null) {
516 final IntegerDistribution prev = GlobalMetrics.getMetric(name, IntegerDistribution.class);
517 if (prev != null) {
518 return prev;
519 }
520 return GlobalMetrics.setMetric(name, IntegerDistribution.class, createIntegerDistribution(approx));
521 }
522 return createIntegerDistribution(approx);
523 }
524
525 private static IntegerDistribution createIntegerDistribution(Approximation approx) throws ProgramError {
526 if (approx instanceof FixedApproximation) {
527 final FixedApproximation fixedApprox = (FixedApproximation) approx;
528 final int[] values = new int[fixedApprox.values.length];
529 for (int i = 0; i < values.length; i++) {
530 values[i] = (Integer) fixedApprox.values[i];
531 }
532 return new FixedSetIntegerDistribution(values);
533 }
534 if (approx instanceof IntegerRangeApproximation) {
535 final IntegerRangeApproximation fixedApprox = (IntegerRangeApproximation) approx;
536 return new FixedRangeIntegerDistribution(fixedApprox.lowValue, fixedApprox.highValue);
537 }
538 if (approx == EXACT) {
539 return new HashedIntegerDistribution();
540 }
541 if (approx instanceof IntegerTraceApproximation) {
542 final IntegerTraceApproximation traceApprox = (IntegerTraceApproximation) approx;
543 return new TraceIntegerDistribution(traceApprox.bufferSize);
544 }
545 return new HashedIntegerDistribution();
546 }
547
548 /**
549 * This is a utility method to create an integer distribution over a range of specified integers.
550 *
551 * @param name the name of the metric
552 * @param low the lowest value to be recorded in the range (inclusive)
553 * @param high the highest value to be recorded (inclusive)
554 * @return a new integer distribution object that will record exact profiles for the integers in the
555 * specified range
556 */
557 public static IntegerDistribution newIntegerDistribution(String name, int low, int high) {
558 return newIntegerDistribution(name, new IntegerRangeApproximation(low, high));
559 }
560
561 /**
562 * This utility method creates a new integer distribution with the {@link #EXACT} approximation.
563 * Note that the implementation of this integer distribution may consume excessive time and/or
564 * space for unstructured distributions.
565 *
566 * @param name the name of the metric; if non-null, then a shared, global metric of the specified name will be returned
567 * @return a new integer distribution that records an exact profile
568 */
569 public static IntegerDistribution newIntegerDistribution(String name) {
570 return newIntegerDistribution(name, EXACT);
571 }
572
573 /**
574 * This utility method creates an integer distribution that records only the specified set of
575 * values, with all other values being not recorded.
576 *
577 * @param name the name of the metric; if non-null, then a shared, global metric of the specified name will be returned
578 * @param values the set of integer values to be recored
579 * @return a new integer distribution recorder
580 */
581 public static IntegerDistribution newIntegerDistribution(String name, int[] values) {
582 final Object[] vals = new Object[values.length];
583 for (int i = 0; i < vals.length; i++) {
584 vals[i] = values[i];
585 }
586 return newIntegerDistribution(name, new FixedApproximation(vals));
587 }
588
589 /**
590 * This method creates a new distribution capable of recording individual objects.
591 *
592 * @param <T> the type of objects being profiled
593 * @param name the name of the metric; if non-null, then a shared, global metric of the specified name will be
594 * returned
595 * @param approx the approximation for the distribution
596 * @return a new distribution capable of profiling the occurrence of objects
597 */
598 public static <T> ObjectDistribution<T> newObjectDistribution(String name, Approximation approx) {
599 if (name != null) {
600 final ObjectDistribution<T> prev = Utils.cast(GlobalMetrics.getMetric(name, ObjectDistribution.class));
601 if (prev != null) {
602 return prev;
603 }
604 return Utils.cast(GlobalMetrics.setMetric(name, ObjectDistribution.class, createObjectDistribution(approx)));
605 }
606 return createObjectDistribution(approx);
607 }
608
609 private static <T> ObjectDistribution<T> createObjectDistribution(Approximation approx) {
610 if (approx instanceof FixedApproximation) {
611 final FixedApproximation fixedApprox = (FixedApproximation) approx;
612 final T[] values = Utils.cast(fixedApprox.values);
613 return new FixedSetObjectDistribution<T>(values);
614 }
615 if (approx == EXACT) {
616 return new HashedObjectDistribution<T>();
617 }
618 // default is to use the hashed object distribution
619 return new HashedObjectDistribution<T>();
620 }
621
622 /**
623 * This is a utility method to create a new object distribution that only records occurrences of
624 * objects in the specified set.
625 *
626 * @param <T> the type of the objects being profiled
627 * @param name the name of the metric
628 * @param set the set of objects for which to record exact profiling information
629 * @return a new distribution capable of producing an exact profile of the occurence of the specified objects
630 */
631 public static <T> ObjectDistribution<T> newObjectDistribution(String name, T... set) {
632 return newObjectDistribution(name, new FixedApproximation(set));
633 }
634
635 /**
636 * This is utility method to create a new object distribution with an exact profile.
637 *
638 * @param <T> the type of the objects being profiled
639 * @param name the name of metric
640 * @return a new distribution capable of producing an exact profile of the occurrences of all of the specified
641 * objects.
642 */
643 public static <T> ObjectDistribution<T> newObjectDistribution(String name) {
644 return newObjectDistribution(name, EXACT);
645 }
646
647 public static class ThreadsafeIntegerDistribution extends IntegerDistribution {
648
649 private final IntegerDistribution distribution;
650
651 public ThreadsafeIntegerDistribution(IntegerDistribution distribution) {
652 this.distribution = distribution;
653 }
654 @Override
655 public void record(int value) {
656 synchronized (distribution) {
657 distribution.record(value);
658 }
659 }
660 @Override
661 public int getCount(Integer value) {
662 synchronized (distribution) {
663 return distribution.getCount(value);
664 }
665 }
666
667 @Override
668 public Map<Integer, Integer> asMap() {
669 synchronized (distribution) {
670 return distribution.asMap();
671 }
672 }
673 @Override
674 public void reset() {
675 super.reset();
676 distribution.reset();
677 }
678
679 }
680
681 private static class ThreadsafeObjectDistribution<T> extends ObjectDistribution<T> {
682
683 private final ObjectDistribution<T> distribution;
684
685 ThreadsafeObjectDistribution(ObjectDistribution<T> distribution) {
686 this.distribution = distribution;
687 }
688 @Override
689 public void record(T value) {
690 synchronized (distribution) {
691 distribution.record(value);
692 }
693 }
694 @Override
695 public int getCount(T value) {
696 synchronized (distribution) {
697 return distribution.getCount(value);
698 }
699 }
700
701 @Override
702 public Map<T, Integer> asMap() {
703 synchronized (distribution) {
704 return distribution.asMap();
705 }
706 }
707 }
708
709 /**
710 * This method creates a wrapper around the specified integer distribution that ensures
711 * access to the distribution is synchronized.
712 *
713 * @param distribution the distribution to wrap in a synchronization
714 * @return a synchronized view of the distribution
715 */
716 public static IntegerDistribution threadSafe(IntegerDistribution distribution) {
717 return new ThreadsafeIntegerDistribution(distribution);
718 }
719
720 /**
721 * This method creates a wrapper around the specified integer distribution that ensures
722 * access to the distribution is synchronized.
723 *
724 * @param distribution the distribution to wrap in a synchronization
725 * @return a synchronized view of the distribution
726 */
727 public static <T> ObjectDistribution<T> threadSafe(ObjectDistribution<T> distribution) {
728 return new ThreadsafeObjectDistribution<T>(distribution);
729 }
730 }