001 /*
002 Galois, a framework to exploit amorphous data-parallelism in irregular
003 programs.
004
005 Copyright (C) 2010, The University of Texas at Austin. All rights reserved.
006 UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS SOFTWARE
007 AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR ANY
008 PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF PERFORMANCE, AND ANY
009 WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF DEALING OR USAGE OF TRADE.
010 NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH RESPECT TO THE USE OF THE
011 SOFTWARE OR DOCUMENTATION. Under no circumstances shall University be liable
012 for incidental, special, indirect, direct or consequential damages or loss of
013 profits, interruption of business, or related expenses which may arise from use
014 of Software or Documentation, including but not limited to those resulting from
015 defects in Software and/or Documentation, or loss or inaccuracy of data of any
016 kind.
017
018 File: StackStatistics.java
019
020 */
021
022
023
024 package util;
025
026 import java.io.PrintStream;
027 import java.util.ArrayList;
028 import java.util.Collections;
029 import java.util.Comparator;
030 import java.util.HashMap;
031 import java.util.HashSet;
032 import java.util.List;
033 import java.util.Map;
034 import java.util.Set;
035
036 /**
037 * Statistics from stack samples. Computes hot methods from stack samples.
038 *
039 *
040 */
041 public class StackStatistics extends Statistics {
042 private final Map<Thread, List<StackTraceElement[]>> threadStacks;
043
044 /**
045 * Creates stack statistics from a list of stack traces.
046 *
047 * @param threadStacks lists of stack traces for each thread
048 */
049 public StackStatistics(Map<Thread, List<StackTraceElement[]>> threadStacks) {
050 this.threadStacks = threadStacks;
051 }
052
053 @Override
054 public void dumpFull(PrintStream out) {
055 printFullHeader(out, "Stacks (top ten)");
056 printTop(out);
057
058 printFullHeader(out, "Stacks");
059
060 for (List<StackTraceElement[]> stacks : threadStacks.values()) {
061 for (StackTraceElement[] stack : stacks) {
062 for (int i = 0; i < stack.length; i++) {
063 out.println(stack[i]);
064 }
065 out.println();
066 }
067 }
068 }
069
070 @Override
071 public void dumpSummary(PrintStream out) {
072 printSummaryHeader(out, "Stacks (top ten)");
073 out.println();
074 printTop(out);
075 }
076
077 private void printTop(PrintStream out) {
078 // TODO(ddn): Collate by threads and with statistics
079 final Map<String, Integer> selfCounts = new HashMap<String, Integer>();
080 // self + children
081 final Map<String, Integer> totalCounts = new HashMap<String, Integer>();
082 int totalSamples = 0;
083 Set<String> seen = new HashSet<String>();
084
085 for (List<StackTraceElement[]> stacks : threadStacks.values()) {
086 totalSamples += stacks.size();
087
088 for (StackTraceElement[] stack : stacks) {
089 int stopIndex = -1;
090 for (int i = stack.length - 1; i >= 0; i--) {
091 String methodName = stack[i].getMethodName();
092
093 if (methodName.startsWith(StackSampler.includeMethodName)) {
094 stopIndex = i;
095 break;
096 }
097 }
098
099 if (stopIndex < 0)
100 continue;
101
102 for (int i = 0; i < stopIndex; i++) {
103 String key = String.format("%s.%s", stack[i].getClassName(), stack[i].getMethodName());
104 // Skip subsequent recursive call frames
105 if (seen.contains(key)) {
106 continue;
107 }
108
109 if (i == 0) {
110 addOne(selfCounts, key);
111 }
112 addOne(totalCounts, key);
113
114 seen.add(key);
115 }
116 seen.clear();
117 }
118 }
119
120 out.println(" Self:");
121 dumpTop(out, selfCounts, totalSamples, " ");
122
123 out.println(" Total:");
124 dumpTop(out, totalCounts, totalSamples, " ");
125 }
126
127 @Override
128 public void merge(Object obj) {
129 StackStatistics other = (StackStatistics) obj;
130 for (Map.Entry<Thread, List<StackTraceElement[]>> entry : other.threadStacks.entrySet()) {
131 List<StackTraceElement[]> value = threadStacks.get(entry.getKey());
132 if (value == null) {
133 value = new ArrayList<StackTraceElement[]>();
134 threadStacks.put(entry.getKey(), value);
135 }
136 value.addAll(entry.getValue());
137 }
138 }
139
140 private void dumpTop(PrintStream out, final Map<String, Integer> counts, int totalSamples, String prefix) {
141 int count = 0;
142 for (String method : descendingOrder(counts)) {
143 float ratio = counts.get(method) / (float) totalSamples;
144 if (count++ > 10)
145 break;
146 else if (ratio > 0.05)
147 out.printf("%s%s %.3f\n", prefix, method, ratio);
148 else
149 break;
150 }
151 }
152
153 private static void addOne(Map<String, Integer> map, String key) {
154 Integer value = map.get(key);
155 if (value == null) {
156 map.put(key, 1);
157 } else {
158 map.put(key, value + 1);
159 }
160 }
161
162 private static List<String> descendingOrder(final Map<String, Integer> map) {
163 List<String> methods = new ArrayList<String>(map.keySet());
164 Collections.sort(methods, new Comparator<String>() {
165 @Override
166 public int compare(String arg0, String arg1) {
167 return map.get(arg1) - map.get(arg0);
168 }
169 });
170 return methods;
171 }
172 }