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 public synchronized void report() {
117 RVMThread.dumpLock.lockNoHandshake();
118 VM.sysWrite("Method counts: A total of " + totalCountsTaken + " samples\n");
119 for (int i = 1; i < nextIndex; i++) {
120 double percent = 100 * countsToHotness(counts[i]);
121 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmids[i]);
122 VM.sysWrite(counts[i] + " (" + percent + "%) ");
123 if (cm == null) {
124 VM.sysWriteln("OBSOLETE"); // Compiled Method Obsolete
125 } else {
126 if (cm.getCompilerType() == CompiledMethod.TRAP) {
127 VM.sysWriteln("<Hardware Trap Frame>");
128 } else {
129 RVMMethod m = cm.getMethod();
130 VM.sysWrite(m);
131 if (m.getDeclaringClass().isInBootImage()) {
132 VM.sysWrite("\tBOOT");
133 }
134 }
135 VM.sysWriteln();
136 }
137 }
138 RVMThread.dumpLock.unlock();
139 }
140
141 /**
142 * @return the total number of samples taken
143 */
144 public double getTotalNumberOfSamples() {
145 return totalCountsTaken;
146 }
147
148 /**
149 * Reset (clear) the method counts
150 */
151 public synchronized void reset() {
152 initialize();
153 }
154
155 /**
156 * Get the current count for a given compiled method id.
157 *
158 * @param cmid compiled method id
159 */
160 public synchronized double getData(int cmid) {
161 int index = findHeapIdx(cmid);
162 if (index > 0) {
163 return counts[index];
164 } else {
165 return 0.0;
166 }
167 }
168
169 /**
170 * Reset (set to 0.0) the count for a given compiled method id.
171 *
172 * @param cmid compiled method id
173 */
174 public synchronized void reset(int cmid) {
175 int index = findHeapIdx(cmid);
176 if (index > 0) {
177 // Cmid does have a value in the heap.
178 // (1) clear map[cmid].
179 // (2) shrink the heap by one slot.
180 // (a) If index is the last element in the heap we have nothing
181 // to do after we decrement nextIndex.
182 // (b) If index is not the last element in the heap, then move the
183 // last heap element to index and heapify.
184 map[cmid] = 0;
185 nextIndex--;
186 if (index < nextIndex) {
187 double oldValue = counts[index];
188 counts[index] = counts[nextIndex];
189 cmids[index] = cmids[nextIndex];
190 map[cmids[index]] = index;
191 if (counts[index] > oldValue) {
192 heapifyUp(index);
193 } else {
194 heapifyDown(index);
195 }
196 }
197 }
198 if (DEBUG) validityCheck();
199 }
200
201 /**
202 * Augment the data associated with a given cmid by the specified number of samples
203 *
204 * @param cmid compiled method id
205 * @param addVal samples to add
206 */
207 public synchronized void augmentData(int cmid, double addVal) {
208 if (addVal == 0) return; // nothing to do
209 int index = findOrCreateHeapIdx(cmid);
210 counts[index] += addVal;
211 if (addVal > 0) {
212 heapifyUp(index);
213 } else {
214 heapifyDown(index);
215 }
216 if (DEBUG) validityCheck();
217 }
218
219 /**
220 * Enqueue events describing the "hot" methods on the organizer's event queue.
221 *
222 * @param filterOptLevel filter out all methods already compiled at
223 * this opt level (or higher)
224 * @param threshold hotness value above which the method is considered
225 * to be hot. (0.0 to 1.0)
226 */
227 public synchronized void insertHotMethods(int filterOptLevel, double threshold) {
228 if (DEBUG) validityCheck();
229 insertHotMethodsInternal(1, filterOptLevel, hotnessToCounts(threshold));
230 }
231
232 /**
233 * Collect the hot methods that have been compiled at the given opt level.
234 *
235 * @param optLevel target opt level
236 * @param threshold hotness value above which the method is considered to
237 * be hot. (0.0 to 1.0)
238 * @return a MethodCountSet containing an
239 * array of compiled methods and an array of their counts.
240 */
241 public synchronized MethodCountSet collectHotMethods(int optLevel, double threshold) {
242 if (DEBUG) validityCheck();
243 ArrayList<HotMethodRecompilationEvent> collect = new ArrayList<HotMethodRecompilationEvent>();
244 collectHotOptMethodsInternal(1, collect, hotnessToCounts(threshold), optLevel);
245
246 // now package the data into the form the caller expects.
247 int numHotMethods = collect.size();
248 double[] numCounts = new double[numHotMethods];
249 CompiledMethod[] hotMethods = new CompiledMethod[numHotMethods];
250 for (int i = 0; i < numHotMethods; i++) {
251 HotMethodEvent event = collect.get(i);
252 hotMethods[i] = event.getCompiledMethod();
253 numCounts[i] = event.getNumSamples();
254 }
255 return new MethodCountSet(hotMethods, numCounts);
256 }
257
258 /**
259 * Convert from a [0.0...1.0] hotness value to the number of counts
260 * that represents that fraction of hotness
261 *
262 * @param hotness a value [0.0...1.0]
263 * @return a number of counts
264 */
265 private double hotnessToCounts(double hotness) {
266 return totalCountsTaken * hotness;
267 }
268
269 /**
270 * Convert a value to a [0.0...1.0] fractional hotness value
271 *
272 * @param numCounts number of counts
273 * @return a value [0.0...1.0]
274 */
275 private double countsToHotness(double numCounts) {
276 if (VM.VerifyAssertions) VM._assert(numCounts <= totalCountsTaken);
277 return numCounts / totalCountsTaken;
278 }
279
280 /**
281 * Recursive implementation of insertHotMethods. Exploit heap property.
282 * Note threshold has been converted into a count value by my caller!
283 *
284 * @param index count array index
285 * @param filterOptLevel filter out all methods already compiled at
286 * this opt level (or higher)
287 * @param threshold hotness value above which the method is considered
288 * to be hot. (0.0 to 1.0)
289 */
290 private void insertHotMethodsInternal(int index, int filterOptLevel, double threshold) {
291 if (index < nextIndex) {
292 if (counts[index] > threshold) {
293 int cmid = cmids[index];
294 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmid);
295 if (cm == null) { // obsolete and deleted
296 reset(cmid); // free up this slot
297 // Visit new one in the slot
298 insertHotMethodsInternal(index, filterOptLevel, threshold);
299 } else {
300 int compilerType = cm.getCompilerType();
301 // Enqueue it unless it's either a trap method or already
302 // opt compiled at filterOptLevel or higher.
303 if (!(compilerType == CompiledMethod.TRAP ||
304 (compilerType == CompiledMethod.OPT &&
305 (((OptCompiledMethod) cm).getOptLevel() >= filterOptLevel)))) {
306 double ns = counts[index];
307 HotMethodRecompilationEvent event = new HotMethodRecompilationEvent(cm, ns);
308 Controller.controllerInputQueue.insert(ns, event);
309 AOSLogging.logger.controllerNotifiedForHotness(cm, ns);
310 }
311
312 // Since I was hot enough, also consider my children.
313 insertHotMethodsInternal(index * 2, filterOptLevel, threshold);
314 insertHotMethodsInternal(index * 2 + 1, filterOptLevel, threshold);
315 }
316 }
317 }
318 }
319
320 /**
321 * Recursive implementation of collectHotOptNMethods.
322 * Exploit heap property.
323 * Constraint: threshold has been converted into a count value by my caller!
324 *
325 * @param index count array index
326 * @param collect vector used to collect output.
327 * @param threshold hotness value above which the method is considered
328 * to be hot. (0.0 to 1.0)
329 * @param optLevel target opt level to look for.
330 */
331 private void collectHotOptMethodsInternal(int index, List<HotMethodRecompilationEvent> collect, double threshold,
332 int optLevel) {
333 if (index < nextIndex) {
334 if (counts[index] > threshold) {
335 int cmid = cmids[index];
336 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmid);
337 if (cm == null) { // obsolete and deleted
338 reset(cmid); // free up this slot
339 // Visit new one in the slot
340 collectHotOptMethodsInternal(index, collect, threshold, optLevel);
341 } else {
342 int compilerType = cm.getCompilerType();
343 if (compilerType == CompiledMethod.OPT && ((OptCompiledMethod) cm).getOptLevel() == optLevel) {
344 double ns = counts[index];
345 collect.add(new HotMethodRecompilationEvent(cm, ns));
346 }
347
348 // Since I was hot enough, also consider my children.
349 collectHotOptMethodsInternal(index * 2, collect, threshold, optLevel);
350 collectHotOptMethodsInternal(index * 2 + 1, collect, threshold, optLevel);
351 }
352 }
353 }
354 }
355
356 /**
357 * Either find the index that is already being used to hold the counts
358 * for cmid or allocate a new entry in the heap for cmid.
359 *
360 * @param cmid compiled method id
361 * @return count array index
362 */
363 private int findOrCreateHeapIdx(int cmid) {
364 if (cmid >= map.length) {
365 growHeapMap(cmid);
366 }
367 int index = map[cmid];
368 if (index == 0) {
369 // A new cmid. Allocate a heap entry for it.
370 index = nextIndex++;
371 if (index >= counts.length) {
372 growHeap();
373 }
374 counts[index] = 0.0;
375 cmids[index] = cmid;
376 map[cmid] = index;
377 }
378 return index;
379 }
380
381 /**
382 * Find the index that is already being used to hold the counts for cmid.
383 * If no such index exists, return 0.
384 *
385 * @param cmid compiled method id
386 */
387 private int findHeapIdx(int cmid) {
388 if (cmid < map.length) {
389 int index = map[cmid];
390 return index;
391 } else {
392 return 0;
393 }
394 }
395
396 /**
397 * Grow the map to be at least as large as would be required to map cmid
398 *
399 * @param cmid compiled method id
400 */
401 private void growHeapMap(int cmid) {
402 int[] newMap = new int[Math.max((int) (map.length * 1.25), cmid + 1)];
403 for (int j = 0; j < map.length; j++) {
404 newMap[j] = map[j];
405 }
406 map = newMap;
407 }
408
409 /**
410 * Increase the size of the count's backing arrays
411 */
412 private void growHeap() {
413 double[] tmp1 = new double[counts.length * 2];
414 for (int i = 1; i < counts.length; i++) {
415 tmp1[i] = counts[i];
416 }
417 counts = tmp1;
418 int[] tmp2 = new int[cmids.length * 2];
419 for (int i = 1; i < cmids.length; i++) {
420 tmp2[i] = cmids[i];
421 }
422 cmids = tmp2;
423 }
424
425 /**
426 * Restore the heap property after increasing a count array entry's value
427 *
428 * @param index of count array entry
429 */
430 private void heapifyUp(int index) {
431 int current = index;
432 int parent = index / 2;
433 while (parent > 0 && counts[parent] < counts[current]) {
434 swap(parent, current);
435 current = parent;
436 parent = parent / 2;
437 }
438 }
439
440 /**
441 * Restore the heap property after decreasing a count array entry's value
442 *
443 * @param index of count array entry
444 */
445 private void heapifyDown(int index) {
446 int current = index;
447 int child1 = current * 2;
448 while (child1 < nextIndex) {
449 int child2 = current * 2 + 1;
450 int larger = (child2 < nextIndex && counts[child2] > counts[child1]) ? child2 : child1;
451 if (counts[current] >= counts[larger]) break; // done
452 swap(current, larger);
453 current = larger;
454 child1 = current * 2;
455 }
456 }
457
458 /**
459 * Swap the heap entries at i and j.
460 *
461 * @param i count array index
462 * @param j count array index
463 */
464 private void swap(int i, int j) {
465 double tmpS = counts[i];
466 counts[i] = counts[j];
467 counts[j] = tmpS;
468 int tmpC = cmids[i];
469 cmids[i] = cmids[j];
470 cmids[j] = tmpC;
471 map[cmids[i]] = i;
472 map[cmids[j]] = j;
473 }
474
475 /**
476 * Validate that internal fields are consistent.
477 * This is very expensive. Only use for debugging purposes.
478 */
479 private void validityCheck() {
480 if (DEBUG && VM.VerifyAssertions) {
481 // (1) Verify map and cmids are in synch
482 for (int i = 0; i < map.length; i++) {
483 VM._assert(map[i] == 0 || cmids[map[i]] == i);
484 }
485 for (int i = 1; i < nextIndex; i++) {
486 VM._assert(map[cmids[i]] == i);
487 }
488
489 // Verify that heap property holds on data.
490 for (int i = 2; i < nextIndex; i++) {
491 VM._assert(counts[i] <= counts[i / 2]);
492 }
493 }
494 }
495 }
496