001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.adaptive.database.methodsamples;
014
015 import java.util.ArrayList;
016 import java.util.List;
017
018 import org.jikesrvm.VM;
019 import org.jikesrvm.adaptive.controller.Controller;
020 import org.jikesrvm.adaptive.controller.HotMethodEvent;
021 import org.jikesrvm.adaptive.controller.HotMethodRecompilationEvent;
022 import org.jikesrvm.adaptive.measurements.Reportable;
023 import org.jikesrvm.adaptive.util.AOSLogging;
024 import org.jikesrvm.classloader.RVMMethod;
025 import org.jikesrvm.compilers.common.CompiledMethod;
026 import org.jikesrvm.compilers.common.CompiledMethods;
027 import org.jikesrvm.compilers.opt.runtimesupport.OptCompiledMethod;
028 import org.jikesrvm.scheduler.RVMThread;
029
030 /**
031 * A container for recording how often a method is executed.
032 */
033 public final class MethodCountData implements Reportable {
034
035 private static final boolean DEBUG = false;
036
037 /**
038 * Sum of values in count array.
039 */
040 private double totalCountsTaken;
041
042 /**
043 * Count array: counts how many times a method is executed.
044 * Constraint: counts[0] is not used.
045 */
046 private double[] counts;
047 /**
048 * Maps count array index to compiled method id.
049 * Constraint: cmids[0] is not used.
050 */
051 private int[] cmids;
052 /**
053 * Maps compiled method id to count array index.
054 * '0' implies that there is no entry in the count array for this cmid
055 */
056 private int[] map;
057 /**
058 * Next available count array entry.
059 */
060 private int nextIndex;
061
062 /**
063 * Constructor
064 */
065 public MethodCountData() {
066 initialize();
067 }
068
069 /**
070 * Reset fields.
071 */
072 private void initialize() {
073 int numCompiledMethods = CompiledMethods.numCompiledMethods();
074 map = new int[numCompiledMethods + (numCompiledMethods >>> 2)];
075 counts = new double[256];
076 cmids = new int[256];
077 nextIndex = 1;
078 totalCountsTaken = 0;
079 }
080
081 /**
082 * Drain a buffer of compiled method id's and update the count array.
083 *
084 * @param countBuffer a buffer of compiled method id's
085 * @param numCounts the number of valid entries in the buffer
086 */
087 public synchronized void update(int[] countBuffer, int numCounts) {
088 for (int i = 0; i < numCounts; i++) {
089 int cmid = countBuffer[i];
090 int index = findOrCreateHeapIdx(cmid);
091 counts[index]++; // Record count
092 heapifyUp(index); // Fix up the heap
093 }
094 totalCountsTaken += numCounts;
095 if (DEBUG) validityCheck();
096 }
097
098 /**
099 * Increment the count for a compiled method id.
100 *
101 * @param cmid compiled method id
102 * @param numCounts number of counts
103 */
104 public synchronized void update(int cmid, double numCounts) {
105 int index = findOrCreateHeapIdx(cmid);
106 counts[index] += numCounts; // Record counts
107 heapifyUp(index); // Fix up the heap
108 totalCountsTaken += numCounts;
109 if (DEBUG) validityCheck();
110 }
111
112 /**
113 * Print the counted (nonzero) methods.
114 * To get a sorted list, pipe the output through sort -n -r.
115 */
116 @Override
117 public synchronized void report() {
118 RVMThread.dumpLock.lockNoHandshake();
119 VM.sysWrite("Method counts: A total of " + totalCountsTaken + " samples\n");
120 for (int i = 1; i < nextIndex; i++) {
121 double percent = 100 * countsToHotness(counts[i]);
122 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmids[i]);
123 VM.sysWrite(counts[i] + " (" + percent + "%) ");
124 if (cm == null) {
125 VM.sysWriteln("OBSOLETE"); // Compiled Method Obsolete
126 } else {
127 if (cm.getCompilerType() == CompiledMethod.TRAP) {
128 VM.sysWriteln("<Hardware Trap Frame>");
129 } else {
130 RVMMethod m = cm.getMethod();
131 VM.sysWrite(m);
132 if (m.getDeclaringClass().isInBootImage()) {
133 VM.sysWrite("\tBOOT");
134 }
135 }
136 VM.sysWriteln();
137 }
138 }
139 RVMThread.dumpLock.unlock();
140 }
141
142 /**
143 * @return the total number of samples taken
144 */
145 public double getTotalNumberOfSamples() {
146 return totalCountsTaken;
147 }
148
149 /**
150 * Reset (clear) the method counts
151 */
152 @Override
153 public synchronized void reset() {
154 initialize();
155 }
156
157 /**
158 * Get the current count for a given compiled method id.
159 *
160 * @param cmid compiled method id
161 */
162 public synchronized double getData(int cmid) {
163 int index = findHeapIdx(cmid);
164 if (index > 0) {
165 return counts[index];
166 } else {
167 return 0.0;
168 }
169 }
170
171 /**
172 * Reset (set to 0.0) the count for a given compiled method id.
173 *
174 * @param cmid compiled method id
175 */
176 public synchronized void reset(int cmid) {
177 int index = findHeapIdx(cmid);
178 if (index > 0) {
179 // Cmid does have a value in the heap.
180 // (1) clear map[cmid].
181 // (2) shrink the heap by one slot.
182 // (a) If index is the last element in the heap we have nothing
183 // to do after we decrement nextIndex.
184 // (b) If index is not the last element in the heap, then move the
185 // last heap element to index and heapify.
186 map[cmid] = 0;
187 nextIndex--;
188 if (index < nextIndex) {
189 double oldValue = counts[index];
190 counts[index] = counts[nextIndex];
191 cmids[index] = cmids[nextIndex];
192 map[cmids[index]] = index;
193 if (counts[index] > oldValue) {
194 heapifyUp(index);
195 } else {
196 heapifyDown(index);
197 }
198 }
199 }
200 if (DEBUG) validityCheck();
201 }
202
203 /**
204 * Augment the data associated with a given cmid by the specified number of samples
205 *
206 * @param cmid compiled method id
207 * @param addVal samples to add
208 */
209 public synchronized void augmentData(int cmid, double addVal) {
210 if (addVal == 0) return; // nothing to do
211 int index = findOrCreateHeapIdx(cmid);
212 counts[index] += addVal;
213 if (addVal > 0) {
214 heapifyUp(index);
215 } else {
216 heapifyDown(index);
217 }
218 if (DEBUG) validityCheck();
219 }
220
221 /**
222 * Enqueue events describing the "hot" methods on the organizer's event queue.
223 *
224 * @param filterOptLevel filter out all methods already compiled at
225 * this opt level (or higher)
226 * @param threshold hotness value above which the method is considered
227 * to be hot. (0.0 to 1.0)
228 */
229 public synchronized void insertHotMethods(int filterOptLevel, double threshold) {
230 if (DEBUG) validityCheck();
231 insertHotMethodsInternal(1, filterOptLevel, hotnessToCounts(threshold));
232 }
233
234 /**
235 * Collect the hot methods that have been compiled at the given opt level.
236 *
237 * @param optLevel target opt level
238 * @param threshold hotness value above which the method is considered to
239 * be hot. (0.0 to 1.0)
240 * @return a MethodCountSet containing an
241 * array of compiled methods and an array of their counts.
242 */
243 public synchronized MethodCountSet collectHotMethods(int optLevel, double threshold) {
244 if (DEBUG) validityCheck();
245 ArrayList<HotMethodRecompilationEvent> collect = new ArrayList<HotMethodRecompilationEvent>();
246 collectHotOptMethodsInternal(1, collect, hotnessToCounts(threshold), optLevel);
247
248 // now package the data into the form the caller expects.
249 int numHotMethods = collect.size();
250 double[] numCounts = new double[numHotMethods];
251 CompiledMethod[] hotMethods = new CompiledMethod[numHotMethods];
252 for (int i = 0; i < numHotMethods; i++) {
253 HotMethodEvent event = collect.get(i);
254 hotMethods[i] = event.getCompiledMethod();
255 numCounts[i] = event.getNumSamples();
256 }
257 return new MethodCountSet(hotMethods, numCounts);
258 }
259
260 /**
261 * Convert from a [0.0...1.0] hotness value to the number of counts
262 * that represents that fraction of hotness
263 *
264 * @param hotness a value [0.0...1.0]
265 * @return a number of counts
266 */
267 private double hotnessToCounts(double hotness) {
268 return totalCountsTaken * hotness;
269 }
270
271 /**
272 * Convert a value to a [0.0...1.0] fractional hotness value
273 *
274 * @param numCounts number of counts
275 * @return a value [0.0...1.0]
276 */
277 private double countsToHotness(double numCounts) {
278 if (VM.VerifyAssertions) VM._assert(numCounts <= totalCountsTaken);
279 return numCounts / totalCountsTaken;
280 }
281
282 /**
283 * Recursive implementation of insertHotMethods. Exploit heap property.
284 * Note threshold has been converted into a count value by my caller!
285 *
286 * @param index count array index
287 * @param filterOptLevel filter out all methods already compiled at
288 * this opt level (or higher)
289 * @param threshold hotness value above which the method is considered
290 * to be hot. (0.0 to 1.0)
291 */
292 private void insertHotMethodsInternal(int index, int filterOptLevel, double threshold) {
293 if (index < nextIndex) {
294 if (counts[index] > threshold) {
295 int cmid = cmids[index];
296 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmid);
297 if (cm == null) { // obsolete and deleted
298 reset(cmid); // free up this slot
299 // Visit new one in the slot
300 insertHotMethodsInternal(index, filterOptLevel, threshold);
301 } else {
302 int compilerType = cm.getCompilerType();
303 // Enqueue it unless it's either a trap method or already
304 // opt compiled at filterOptLevel or higher.
305 if (!(compilerType == CompiledMethod.TRAP ||
306 (compilerType == CompiledMethod.OPT &&
307 (((OptCompiledMethod) cm).getOptLevel() >= filterOptLevel)))) {
308 double ns = counts[index];
309 HotMethodRecompilationEvent event = new HotMethodRecompilationEvent(cm, ns);
310 Controller.controllerInputQueue.insert(ns, event);
311 AOSLogging.logger.controllerNotifiedForHotness(cm, ns);
312 }
313
314 // Since I was hot enough, also consider my children.
315 insertHotMethodsInternal(index * 2, filterOptLevel, threshold);
316 insertHotMethodsInternal(index * 2 + 1, filterOptLevel, threshold);
317 }
318 }
319 }
320 }
321
322 /**
323 * Recursive implementation of collectHotOptNMethods.
324 * Exploit heap property.
325 * Constraint: threshold has been converted into a count value by my caller!
326 *
327 * @param index count array index
328 * @param collect vector used to collect output.
329 * @param threshold hotness value above which the method is considered
330 * to be hot. (0.0 to 1.0)
331 * @param optLevel target opt level to look for.
332 */
333 private void collectHotOptMethodsInternal(int index, List<HotMethodRecompilationEvent> collect, double threshold,
334 int optLevel) {
335 if (index < nextIndex) {
336 if (counts[index] > threshold) {
337 int cmid = cmids[index];
338 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmid);
339 if (cm == null) { // obsolete and deleted
340 reset(cmid); // free up this slot
341 // Visit new one in the slot
342 collectHotOptMethodsInternal(index, collect, threshold, optLevel);
343 } else {
344 int compilerType = cm.getCompilerType();
345 if (compilerType == CompiledMethod.OPT && ((OptCompiledMethod) cm).getOptLevel() == optLevel) {
346 double ns = counts[index];
347 collect.add(new HotMethodRecompilationEvent(cm, ns));
348 }
349
350 // Since I was hot enough, also consider my children.
351 collectHotOptMethodsInternal(index * 2, collect, threshold, optLevel);
352 collectHotOptMethodsInternal(index * 2 + 1, collect, threshold, optLevel);
353 }
354 }
355 }
356 }
357
358 /**
359 * Either find the index that is already being used to hold the counts
360 * for cmid or allocate a new entry in the heap for cmid.
361 *
362 * @param cmid compiled method id
363 * @return count array index
364 */
365 private int findOrCreateHeapIdx(int cmid) {
366 if (cmid >= map.length) {
367 growHeapMap(cmid);
368 }
369 int index = map[cmid];
370 if (index == 0) {
371 // A new cmid. Allocate a heap entry for it.
372 index = nextIndex++;
373 if (index >= counts.length) {
374 growHeap();
375 }
376 counts[index] = 0.0;
377 cmids[index] = cmid;
378 map[cmid] = index;
379 }
380 return index;
381 }
382
383 /**
384 * Find the index that is already being used to hold the counts for cmid.
385 * If no such index exists, return 0.
386 *
387 * @param cmid compiled method id
388 */
389 private int findHeapIdx(int cmid) {
390 if (cmid < map.length) {
391 int index = map[cmid];
392 return index;
393 } else {
394 return 0;
395 }
396 }
397
398 /**
399 * Grow the map to be at least as large as would be required to map cmid
400 *
401 * @param cmid compiled method id
402 */
403 private void growHeapMap(int cmid) {
404 int[] newMap = new int[Math.max((int) (map.length * 1.25), cmid + 1)];
405 for (int j = 0; j < map.length; j++) {
406 newMap[j] = map[j];
407 }
408 map = newMap;
409 }
410
411 /**
412 * Increase the size of the count's backing arrays
413 */
414 private void growHeap() {
415 double[] tmp1 = new double[counts.length * 2];
416 for (int i = 1; i < counts.length; i++) {
417 tmp1[i] = counts[i];
418 }
419 counts = tmp1;
420 int[] tmp2 = new int[cmids.length * 2];
421 for (int i = 1; i < cmids.length; i++) {
422 tmp2[i] = cmids[i];
423 }
424 cmids = tmp2;
425 }
426
427 /**
428 * Restore the heap property after increasing a count array entry's value
429 *
430 * @param index of count array entry
431 */
432 private void heapifyUp(int index) {
433 int current = index;
434 int parent = index / 2;
435 while (parent > 0 && counts[parent] < counts[current]) {
436 swap(parent, current);
437 current = parent;
438 parent = parent / 2;
439 }
440 }
441
442 /**
443 * Restore the heap property after decreasing a count array entry's value
444 *
445 * @param index of count array entry
446 */
447 private void heapifyDown(int index) {
448 int current = index;
449 int child1 = current * 2;
450 while (child1 < nextIndex) {
451 int child2 = current * 2 + 1;
452 int larger = (child2 < nextIndex && counts[child2] > counts[child1]) ? child2 : child1;
453 if (counts[current] >= counts[larger]) break; // done
454 swap(current, larger);
455 current = larger;
456 child1 = current * 2;
457 }
458 }
459
460 /**
461 * Swap the heap entries at i and j.
462 *
463 * @param i count array index
464 * @param j count array index
465 */
466 private void swap(int i, int j) {
467 double tmpS = counts[i];
468 counts[i] = counts[j];
469 counts[j] = tmpS;
470 int tmpC = cmids[i];
471 cmids[i] = cmids[j];
472 cmids[j] = tmpC;
473 map[cmids[i]] = i;
474 map[cmids[j]] = j;
475 }
476
477 /**
478 * Validate that internal fields are consistent.
479 * This is very expensive. Only use for debugging purposes.
480 */
481 private void validityCheck() {
482 if (DEBUG && VM.VerifyAssertions) {
483 // (1) Verify map and cmids are in synch
484 for (int i = 0; i < map.length; i++) {
485 VM._assert(map[i] == 0 || cmids[map[i]] == i);
486 }
487 for (int i = 1; i < nextIndex; i++) {
488 VM._assert(map[cmids[i]] == i);
489 }
490
491 // Verify that heap property holds on data.
492 for (int i = 2; i < nextIndex; i++) {
493 VM._assert(counts[i] <= counts[i / 2]);
494 }
495 }
496 }
497 }
498