Chromium Code Reviews Chromium Code Reviews
Issue 1908513002:
Add mutator utilization metric. (Closed)
Base URL: https://github.com/catapult-project/catapult.git@master| OLD | NEW |
|---|---|
| 1 <!DOCTYPE html> | 1 <!DOCTYPE html> |
| 2 <!-- | 2 <!-- |
| 3 Copyright 2016 The Chromium Authors. All rights reserved. | 3 Copyright 2016 The Chromium Authors. All rights reserved. |
| 4 Use of this source code is governed by a BSD-style license that can be | 4 Use of this source code is governed by a BSD-style license that can be |
| 5 found in the LICENSE file. | 5 found in the LICENSE file. |
| 6 --> | 6 --> |
| 7 <link rel="import" href="/tracing/base/piecewise_linear_function.html"> | |
| 7 <link rel="import" href="/tracing/base/range.html"> | 8 <link rel="import" href="/tracing/base/range.html"> |
| 9 <link rel="import" href="/tracing/base/range_utils.html"> | |
| 8 <link rel="import" href="/tracing/metrics/metric_registry.html"> | 10 <link rel="import" href="/tracing/metrics/metric_registry.html"> |
| 9 <link rel="import" href="/tracing/value/numeric.html"> | 11 <link rel="import" href="/tracing/value/numeric.html"> |
| 10 <link rel="import" href="/tracing/value/unit.html"> | 12 <link rel="import" href="/tracing/value/unit.html"> |
| 11 <link rel="import" href="/tracing/value/value.html"> | 13 <link rel="import" href="/tracing/value/value.html"> |
| 12 | 14 |
| 13 <script> | 15 <script> |
| 14 'use strict'; | 16 'use strict'; |
| 15 | 17 |
| 16 tr.exportTo('tr.metrics.v8.utils', function() { | 18 tr.exportTo('tr.metrics.v8.utils', function() { |
| 17 // The title of the idle task event. | 19 // The title of the idle task event. |
| 18 var IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask'; | 20 var IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask'; |
| 19 | 21 |
| 22 // V8 execution event. | |
| 23 var V8_EXECUTE = 'V8.Execute'; | |
| 24 | |
| 20 // GC events start with this prefix. | 25 // GC events start with this prefix. |
| 21 var GC_EVENT_PREFIX = 'V8.GC'; | 26 var GC_EVENT_PREFIX = 'V8.GC'; |
| 22 | 27 |
| 23 // Special handling is required for full GCs inside low memory notification. | 28 // Special handling is required for full GCs inside low memory notification. |
| 24 var FULL_GC_EVENT = 'V8.GCCompactor'; | 29 var FULL_GC_EVENT = 'V8.GCCompactor'; |
| 25 | 30 |
| 26 var LOW_MEMORY_EVENT = 'V8.GCLowMemoryNotification'; | 31 var LOW_MEMORY_EVENT = 'V8.GCLowMemoryNotification'; |
| 27 | 32 |
| 28 // Maps the top-level GC events in timeline to telemetry friendly names. | 33 // Maps the top-level GC events in timeline to telemetry friendly names. |
| 29 var TOP_GC_EVENTS = { | 34 var TOP_GC_EVENTS = { |
| 30 'V8.GCCompactor': 'v8.gc.full_mark_compactor', | 35 'V8.GCCompactor': 'v8.gc.full_mark_compactor', |
| 31 'V8.GCFinalizeMC': 'v8.gc.latency_mark_compactor', | 36 'V8.GCFinalizeMC': 'v8.gc.latency_mark_compactor', |
| 32 'V8.GCFinalizeMCReduceMemory': 'v8.gc.memory_mark_compactor', | 37 'V8.GCFinalizeMCReduceMemory': 'v8.gc.memory_mark_compactor', |
| 33 'V8.GCIncrementalMarking': 'v8.gc.incremental_step', | 38 'V8.GCIncrementalMarking': 'v8.gc.incremental_step', |
| 34 'V8.GCIncrementalMarkingFinalize': 'v8.gc.incremental_finalize', | 39 'V8.GCIncrementalMarkingFinalize': 'v8.gc.incremental_finalize', |
| 35 'V8.GCIncrementalMarkingStart': 'v8.gc.incremental_start', | 40 'V8.GCIncrementalMarkingStart': 'v8.gc.incremental_start', |
| 36 'V8.GCLowMemoryNotification': 'v8.gc.low_memory_mark_compactor', | 41 'V8.GCLowMemoryNotification': 'v8.gc.low_memory_mark_compactor', |
| 37 'V8.GCScavenger': 'v8.gc.scavenger' | 42 'V8.GCScavenger': 'v8.gc.scavenger' |
| 38 }; | 43 }; |
| 39 | 44 |
| 40 /** | 45 /** |
| 41 * Finds the first parent of the |event| for which the |predicate| holds. | 46 * Finds the first parent of the |event| for which the |predicate| holds. |
| 42 */ | 47 */ |
| 43 function findParent(event, predicate) { | 48 function findParent(event, predicate) { |
| 44 var parent = event.parentSlice; | 49 var parent = event.parentSlice; |
| 45 while (parent) { | 50 while (parent) { |
| 46 if (predicate(parent)) { | 51 if (predicate(parent)) { |
| 47 return parent; | 52 return parent; |
| 48 } | 53 } |
| 49 parent = parent.parentSlice; | 54 parent = parent.parentSlice; |
| 50 } | 55 } |
| 51 return null; | 56 return null; |
| 52 } | 57 } |
| 53 | 58 |
| 54 function isIdleTask(event) { | 59 function isIdleTask(event) { |
| 55 return event.title === IDLE_TASK_EVENT; | 60 return event.title === IDLE_TASK_EVENT; |
| 56 } | 61 } |
| 57 | 62 |
| 58 function isLowMemoryEvent(event) { | 63 function isLowMemoryEvent(event) { |
| 59 return event.title === LOW_MEMORY_EVENT; | 64 return event.title === LOW_MEMORY_EVENT; |
| 60 } | 65 } |
| 61 | 66 |
| 67 function isV8ExecuteEvent(event) { | |
| 68 return event.title === V8_EXECUTE; | |
| 69 } | |
| 70 | |
| 71 function isTopV8ExecuteEvent(event) { | |
| 72 return isV8ExecuteEvent(event) && findParent(isV8ExecuteEvent) === null; | |
| 73 } | |
| 74 | |
| 62 function isGarbageCollectionEvent(event) { | 75 function isGarbageCollectionEvent(event) { |
| 63 // Low memory notification is handled specially because it contains | 76 // Low memory notification is handled specially because it contains |
| 64 // several full mark compact events. | 77 // several full mark compact events. |
| 65 return event.title && event.title.startsWith(GC_EVENT_PREFIX) && | 78 return event.title && event.title.startsWith(GC_EVENT_PREFIX) && |
| 66 event.title != LOW_MEMORY_EVENT; | 79 event.title != LOW_MEMORY_EVENT; |
| 67 } | 80 } |
| 68 | 81 |
| 69 function isTopGarbageCollectionEvent(event) { | 82 function isTopGarbageCollectionEvent(event) { |
| 70 return event.title in TOP_GC_EVENTS; | 83 return event.title in TOP_GC_EVENTS; |
| 71 } | 84 } |
| (...skipping 17 matching lines...) Expand all Loading... | |
| 89 function subGarbageCollectionEventName(event) { | 102 function subGarbageCollectionEventName(event) { |
| 90 var topEvent = findParent(event, isTopGarbageCollectionEvent); | 103 var topEvent = findParent(event, isTopGarbageCollectionEvent); |
| 91 var prefix = topEvent ? topGarbageCollectionEventName(topEvent) : 'unknown'; | 104 var prefix = topEvent ? topGarbageCollectionEventName(topEvent) : 'unknown'; |
| 92 // Remove redundant prefixes and convert to lower case. | 105 // Remove redundant prefixes and convert to lower case. |
| 93 var name = event.title.replace('V8.GC_MC_', '') | 106 var name = event.title.replace('V8.GC_MC_', '') |
| 94 .replace('V8.GC_SCAVENGER_', '') | 107 .replace('V8.GC_SCAVENGER_', '') |
| 95 .replace('V8.GC_', '').toLowerCase(); | 108 .replace('V8.GC_', '').toLowerCase(); |
| 96 return prefix + '.' + name; | 109 return prefix + '.' + name; |
| 97 } | 110 } |
| 98 | 111 |
| 112 /** | |
| 113 * Given a list of intervals, returns a new list with all overalapping | |
| 114 * intervals merged into a single interval. | |
| 115 */ | |
| 116 function unionOfIntervals(intervals) { | |
| 117 if (intervals.length === 0) | |
| 118 return []; | |
| 119 return tr.b.mergeRanges( | |
| 120 intervals.map(x => ({min: x.start, max: x.end})), 1e-6, | |
| 121 function(ranges) { | |
| 122 return { | |
| 123 start: ranges.reduce((acc, x) => Math.min(acc, x.min), ranges[0].min), | |
| 124 end: ranges.reduce((acc, x) => Math.max(acc, x.max), ranges[0].max) | |
| 125 }; | |
| 126 } | |
| 127 ); | |
| 128 } | |
| 129 | |
| 130 /** | |
| 131 * An end-point of a window that is sliding from left to right | |
| 132 * over |points| starting from time |start|. | |
| 133 * It is intended to be used only by the |mutatorUtilization| function. | |
| 134 * @constructor | |
| 135 */ | |
| 136 function WindowEndpoint(start, points) { | |
| 137 this.points = points; | |
| 138 // The index of the last passed point. | |
| 139 this.lastIndex = -1; | |
| 140 // The position of the end-point in the time line. | |
| 141 this.position = start; | |
| 142 // The distance until the next point. | |
| 143 this.distanceUntilNextPoint = points[0].position - start; | |
| 144 // The cumulative duration of GC pauses until this position. | |
| 145 this.cummulativePause = 0; | |
| 146 // The number of entered GC intervals. | |
| 147 this.stackDepth = 0; | |
| 148 }; | |
|
petrcermak
2016/04/25 12:31:17
nit: no need for semicolon here.
ulan
2016/04/25 12:46:26
Done.
| |
| 149 | |
| 150 WindowEndpoint.prototype = { | |
| 151 // Advance the end-point by the given |delta|. | |
| 152 advance: function(delta) { | |
| 153 var points = this.points; | |
| 154 if (delta < this.distanceUntilNextPoint) { | |
| 155 this.position += delta; | |
| 156 this.cummulativePause += this.stackDepth > 0 ? delta : 0; | |
| 157 this.distanceUntilNextPoint = | |
| 158 points[this.lastIndex + 1].position - this.position; | |
| 159 } else { | |
| 160 this.position += this.distanceUntilNextPoint; | |
| 161 this.cummulativePause += | |
| 162 this.stackDepth > 0 ? this.distanceUntilNextPoint : 0; | |
| 163 this.distanceUntilNextPoint = 0; | |
| 164 this.lastIndex++; | |
| 165 if (this.lastIndex < points.length) { | |
| 166 this.stackDepth += points[this.lastIndex].delta; | |
| 167 if (this.lastIndex + 1 < points.length) | |
| 168 this.distanceUntilNextPoint = | |
| 169 points[this.lastIndex + 1].position - this.position; | |
| 170 } | |
| 171 } | |
| 172 } | |
| 173 }; | |
| 174 | |
| 175 /** | |
| 176 * Returns mutator utilization as a piecewise linear function. | |
| 177 * Mutator utilization for a window size w is a function of time mu_w(t) | |
| 178 * that shows how much time in [t, t+w] is left for the mutator relative | |
| 179 * to the time window size. | |
| 180 * More formally: | |
| 181 * mu_w(t) = (w - total_time_spent_in_gc_in(t, t + w)) / w. | |
| 182 * The range of mu_w(t) is [0..1]. | |
| 183 * See "A Parallel, Real-Time Garbage Collector" by Cheng et. al. for | |
| 184 * more info [https://www.cs.cmu.edu/~guyb/papers/gc2001.pdf]. | |
| 185 * | |
| 186 * All parameters must use the same time unit. | |
| 187 * @param {number} start The start time of execution. | |
| 188 * @param {number} end The end time of execution. | |
| 189 * @param {number} timeWindow The size of the time window. | |
| 190 * @param {!Array<!{start: number, end: number}>} intervals The list of | |
| 191 * GC pauses. | |
| 192 */ | |
| 193 function mutatorUtilization(start, end, timeWindow, intervals) { | |
| 194 var mu = new tr.b.PiecewiseLinearFunction(); | |
| 195 // If the interval is smaller than the time window, then the function is | |
| 196 // empty. | |
| 197 if (end - start <= timeWindow) | |
| 198 return mu; | |
| 199 // If there are GC pauses then the mutator utilization is 1.0. | |
| 200 if (intervals.length === 0) { | |
| 201 mu.push(start, 1.0, end - timeWindow, 1.0); | |
| 202 return mu; | |
| 203 } | |
| 204 intervals = unionOfIntervals(intervals); | |
| 205 // Create a point for the start and the end of each interval. | |
| 206 var points = []; | |
| 207 intervals.forEach(function(interval) { | |
| 208 points.push({position: interval.start, delta: 1}); | |
| 209 points.push({position: interval.end, delta: -1}); | |
| 210 }); | |
| 211 points.sort((a, b) => a.position - b.position); | |
| 212 points.push({position: end, delta: 0}); | |
| 213 // The left and the right limit of the sliding window. | |
| 214 var left = new WindowEndpoint(start, points); | |
| 215 var right = new WindowEndpoint(start, points); | |
| 216 // Advance the right end-point until we get the correct window size. | |
| 217 while (right.position - left.position < timeWindow) | |
| 218 right.advance(timeWindow - (right.position - left.position)); | |
| 219 while (right.lastIndex < points.length) { | |
| 220 // Advance the window end-points by the largest possible amount | |
| 221 // without jumping over a point. | |
| 222 var distanceUntilNextPoint = | |
| 223 Math.min(left.distanceUntilNextPoint, right.distanceUntilNextPoint); | |
| 224 var position1 = left.position; | |
| 225 var value1 = right.cummulativePause - left.cummulativePause; | |
| 226 left.advance(distanceUntilNextPoint); | |
| 227 right.advance(distanceUntilNextPoint); | |
| 228 // Add a new mutator utilization segment only if it is non-trivial. | |
| 229 if (distanceUntilNextPoint > 0) { | |
| 230 var position2 = left.position; | |
| 231 var value2 = right.cummulativePause - left.cummulativePause; | |
| 232 mu.push(position1, 1.0 - value1 / timeWindow, | |
| 233 position2, 1.0 - value2 / timeWindow); | |
| 234 } | |
| 235 } | |
| 236 return mu; | |
| 237 } | |
| 238 | |
| 99 return { | 239 return { |
| 100 findParent: findParent, | 240 findParent: findParent, |
| 101 isIdleTask: isIdleTask, | 241 isIdleTask: isIdleTask, |
| 102 isLowMemoryEvent: isLowMemoryEvent, | 242 isLowMemoryEvent: isLowMemoryEvent, |
| 243 isV8ExecuteEvent: isV8ExecuteEvent, | |
| 244 isTopV8ExecuteEvent: isTopV8ExecuteEvent, | |
| 103 isGarbageCollectionEvent: isGarbageCollectionEvent, | 245 isGarbageCollectionEvent: isGarbageCollectionEvent, |
| 104 isTopGarbageCollectionEvent: isTopGarbageCollectionEvent, | 246 isTopGarbageCollectionEvent: isTopGarbageCollectionEvent, |
| 105 isSubGarbageCollectionEvent: isSubGarbageCollectionEvent, | 247 isSubGarbageCollectionEvent: isSubGarbageCollectionEvent, |
| 106 topGarbageCollectionEventName: topGarbageCollectionEventName, | 248 topGarbageCollectionEventName: topGarbageCollectionEventName, |
| 107 subGarbageCollectionEventName: subGarbageCollectionEventName | 249 subGarbageCollectionEventName: subGarbageCollectionEventName, |
| 250 unionOfIntervals: unionOfIntervals, | |
| 251 mutatorUtilization: mutatorUtilization | |
| 108 }; | 252 }; |
| 109 }); | 253 }); |
| 110 </script> | 254 </script> |
| OLD | NEW |
