Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(323)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: tracing/tracing/metrics/v8/utils.html

Issue 1908513002: Add mutator utilization metric. (Closed) Base URL: https://github.com/catapult-project/catapult.git@master
Patch Set: Created 4 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« tracing/tracing/metrics/v8/gc_metric.html ('K') | « tracing/tracing/metrics/v8/gc_metric_test.html ('k') | tracing/tracing/metrics/v8/utils_test.html » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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/range.html"> 7 <link rel="import" href="/tracing/base/range.html">
8 <link rel="import" href="/tracing/metrics/metric_registry.html"> 8 <link rel="import" href="/tracing/metrics/metric_registry.html">
9 <link rel="import" href="/tracing/value/numeric.html"> 9 <link rel="import" href="/tracing/value/numeric.html">
10 <link rel="import" href="/tracing/value/unit.html"> 10 <link rel="import" href="/tracing/value/unit.html">
11 <link rel="import" href="/tracing/value/value.html"> 11 <link rel="import" href="/tracing/value/value.html">
12 12
13 <script> 13 <script>
14 'use strict'; 14 'use strict';
15 15
16 tr.exportTo('tr.metrics.v8.utils', function() { 16 tr.exportTo('tr.metrics.v8.utils', function() {
17 // The title of the idle task event. 17 // The title of the idle task event.
18 var IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask'; 18 var IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask';
19 19
20 // V8 execution event.
21 var V8_EXECUTE = 'V8.Execute';
22
20 // GC events start with this prefix. 23 // GC events start with this prefix.
21 var GC_EVENT_PREFIX = 'V8.GC'; 24 var GC_EVENT_PREFIX = 'V8.GC';
22 25
23 // Special handling is required for full GCs inside low memory notification. 26 // Special handling is required for full GCs inside low memory notification.
24 var FULL_GC_EVENT = 'V8.GCCompactor'; 27 var FULL_GC_EVENT = 'V8.GCCompactor';
25 28
26 var LOW_MEMORY_EVENT = 'V8.GCLowMemoryNotification'; 29 var LOW_MEMORY_EVENT = 'V8.GCLowMemoryNotification';
27 30
28 // Maps the top-level GC events in timeline to telemetry friendly names. 31 // Maps the top-level GC events in timeline to telemetry friendly names.
29 var TOP_GC_EVENTS = { 32 var TOP_GC_EVENTS = {
(...skipping 22 matching lines...) Expand all
52 } 55 }
53 56
54 function isIdleTask(event) { 57 function isIdleTask(event) {
55 return event.title === IDLE_TASK_EVENT; 58 return event.title === IDLE_TASK_EVENT;
56 } 59 }
57 60
58 function isLowMemoryEvent(event) { 61 function isLowMemoryEvent(event) {
59 return event.title === LOW_MEMORY_EVENT; 62 return event.title === LOW_MEMORY_EVENT;
60 } 63 }
61 64
65 function isV8ExecuteEvent(event) {
66 return event.title === V8_EXECUTE;
67 }
68
69 function isTopV8ExecuteEvent(event) {
70 return isV8ExecuteEvent(event) && findParent(isV8ExecuteEvent) === null;
71 }
72
62 function isGarbageCollectionEvent(event) { 73 function isGarbageCollectionEvent(event) {
63 // Low memory notification is handled specially because it contains 74 // Low memory notification is handled specially because it contains
64 // several full mark compact events. 75 // several full mark compact events.
65 return event.title && event.title.startsWith(GC_EVENT_PREFIX) && 76 return event.title && event.title.startsWith(GC_EVENT_PREFIX) &&
66 event.title != LOW_MEMORY_EVENT; 77 event.title != LOW_MEMORY_EVENT;
67 } 78 }
68 79
69 function isTopGarbageCollectionEvent(event) { 80 function isTopGarbageCollectionEvent(event) {
70 return event.title in TOP_GC_EVENTS; 81 return event.title in TOP_GC_EVENTS;
71 } 82 }
(...skipping 17 matching lines...) Expand all
89 function subGarbageCollectionEventName(event) { 100 function subGarbageCollectionEventName(event) {
90 var topEvent = findParent(event, isTopGarbageCollectionEvent); 101 var topEvent = findParent(event, isTopGarbageCollectionEvent);
91 var prefix = topEvent ? topGarbageCollectionEventName(topEvent) : 'unknown'; 102 var prefix = topEvent ? topGarbageCollectionEventName(topEvent) : 'unknown';
92 // Remove redundant prefixes and convert to lower case. 103 // Remove redundant prefixes and convert to lower case.
93 var name = event.title.replace('V8.GC_MC_', '') 104 var name = event.title.replace('V8.GC_MC_', '')
94 .replace('V8.GC_SCAVENGER_', '') 105 .replace('V8.GC_SCAVENGER_', '')
95 .replace('V8.GC_', '').toLowerCase(); 106 .replace('V8.GC_', '').toLowerCase();
96 return prefix + '.' + name; 107 return prefix + '.' + name;
97 } 108 }
98 109
110
eakuefner 2016/04/20 17:25:54 You should look into base/ to see if there's math
ulan 2016/04/20 18:47:04 Done. Moved PiecewiseLinearFunction to base and re
111 /**
112 * A linear segment from (x1, y1) to (x2, y2).
113 * @constructor
114 */
115 function Segment(x1, y1, x2, y2) {
116 this.x1 = x1;
117 this.y1 = y1;
118 this.x2 = x2;
119 this.y2 = y2;
120 }
121
122 Segment.prototype = {
123 /**
124 * The total length of all x points such that f(x) < y.
125 * More formally:
126 * max(x2 - x1) such that for all x in [x1 .. x2]: f(x) < y.
127 */
128 partBelow: function(y) {
129 var width = this.width();
130 if (width == 0) return 0;
131 var minY = this.min();
132 var maxY = this.max();
133 if (y >= maxY)
134 return width;
135 if (y < minY)
136 return 0;
137 return (y - minY) / (maxY - minY) * width;
138 },
139
140 min: function() {
141 return Math.min(this.y1, this.y2);
142 },
143
144 max: function() {
145 return Math.max(this.y1, this.y2);
146 },
147
148 average: function() {
149 return (this.y1 + this.y2) / 2;
150 },
151
152 width: function() {
153 return this.x2 - this.x1;
154 }
155 };
156
157 /**
158 * A function that consists of linear pieces.
159 * See https://en.wikipedia.org/wiki/Piecewise_linear_function.
160 * @constructor
161 */
162 function PiecewiseLinearFunction() {
163 this.pieces = [];
164 }
165
166 PiecewiseLinearFunction.prototype = {
167 /**
168 * Push a linear piece defined by linear interpolation of
169 * (x1, y1) and (x2, y2).
170 */
171 push: function(x1, y1, x2, y2) {
172 if (x1 > x2)
173 throw 'Invalid segment';
174 if (x1 < x2)
175 this.pieces.push(new Segment(x1, y1, x2, y2));
176 },
177
178 /**
179 * The total length of all x points for which f(x) < y.
180 */
181 partBelow: function(y) {
182 return this.pieces.reduce((acc, x) => (acc + x.partBelow(y)), 0);
183 },
184
185 min: function() {
186 return this.pieces.reduce((acc, x) => Math.min(acc, x.min()), Infinity);
187 },
188
189 max: function() {
190 return this.pieces.reduce((acc, x) => Math.max(acc, x.max()), -Infinity);
191 },
192
193 average: function() {
194 var weightedSum = 0;
195 var totalWeight = 0;
196 this.pieces.forEach(function(piece) {
197 weightedSum += piece.width() * piece.average();
198 totalWeight += piece.width();
199 });
200 if (totalWeight == 0)
201 return 0;
202 return weightedSum / totalWeight;
203 },
204
205 /**
206 * Returns the minimum possible value y such that the percentage of x points
207 * that have f(x) <= y is equal to the given |percent|.
208 */
209 percentile: function(percent) {
210 if (!(percent >= 0 && percent <= 1))
211 throw new Error('percent must be [0,1]');
212 var lower = this.min();
213 var upper = this.max();
214 var total = this.partBelow(upper);
215 var PRECISION = 1e-7;
216 if (total == 0) return 0;
217 while (upper - lower > PRECISION) {
218 var middle = (lower + upper) / 2;
219 var below = this.partBelow(middle);
220 if (below / total < percent) {
221 lower = middle;
222 } else {
223 upper = middle;
224 }
225 }
226 return (lower + upper) / 2;
227 }
228 };
229
230 /**
231 * Given a list of intervals, returns a new list with all overalapping
232 * intervals merged into a single interval.
233 */
234 function unionOfIntervals(intervals) {
235 if (intervals.length == 0)
236 return intervals;
237 intervals.sort((a, b) => (a.start - b.start));
238 var result = [];
239 function copy(interval) {
240 return {start: interval.start, end: interval.end };
241 }
242 var last = copy(intervals[0]);
243 intervals.forEach(function(interval) {
244 if (last.end < interval.start) {
245 result.push(last);
246 last = copy(interval);
247 } else {
248 last.end = Math.max(last.end, interval.end);
249 }
250 });
251 result.push(last);
252 return result;
253 }
254
255 /**
256 * Returns mutator utilization as a piecewise linear function.
257 * See "A Parallel, Real-Time Garbage Collector" by Cheng et. al. for
258 * the definition of mutator utilization.
259 * @param {Number} start The start time of execution.
260 * @param {Number} end The end time of execution.
261 * @param {Number} timeWindow The size of the time window.
262 * @param {Array} intervals The list of GC pauses, where each interval
263 * has start and end field.
264 */
265 function mutatorUtilization(start, end, timeWindow, intervals) {
266 var mu = new PiecewiseLinearFunction();
267 if (end - start <= timeWindow)
268 return mu;
269 if (intervals.length == 0) {
270 mu.push(start, 1.0, end - timeWindow, 1.0);
271 return mu;
272 }
273 intervals = unionOfIntervals(intervals);
274 var points = [];
275 intervals.forEach(function(interval) {
276 points.push({position: interval.start, delta: 1});
277 points.push({position: interval.end, delta: -1});
278 });
279 points.sort((a, b) => a.position - b.position);
280 points.push({position: end, delta: 0});
281 var left = {
282 index: -1,
283 position: start,
284 remainder: points[0].position - start,
285 pause: 0,
286 stack: 0
287 };
288 var right = {
289 index: -1,
290 position: start,
291 remainder: points[0].position - start,
292 pause: 0,
293 stack: 0
294 };
295 while (right.position - left.position < timeWindow) {
296 advance(right, timeWindow - (right.position - left.position));
297 }
298 while (right.index < points.length) {
299 var remainder = Math.min(left.remainder, right.remainder);
300 var position1 = left.position;
301 var value1 = right.pause - left.pause;
302 advance(left, remainder);
303 advance(right, remainder);
304 var position2 = left.position;
305 var value2 = right.pause - left.pause;
306 mu.push(position1, 1.0 - value1 / timeWindow,
307 position2, 1.0 - value2 / timeWindow);
308 }
309 function advance(point, delta) {
310 if (delta < point.remainder) {
311 point.position += delta;
312 point.pause += point.stack > 0 ? delta : 0;
313 point.remainder = points[point.index + 1].position - point.position;
314 } else {
315 point.position += point.remainder;
316 point.pause += point.stack > 0 ? point.remainder : 0;
317 point.remainder = 0;
318 point.index += 1;
319 if (point.index < points.length) {
320 point.stack += points[point.index].delta;
321 if (point.index + 1 < points.length)
322 point.remainder = points[point.index + 1].position - point.position;
323 }
324 }
325 }
326 return mu;
327 }
328
99 return { 329 return {
100 findParent: findParent, 330 findParent: findParent,
101 isIdleTask: isIdleTask, 331 isIdleTask: isIdleTask,
102 isLowMemoryEvent: isLowMemoryEvent, 332 isLowMemoryEvent: isLowMemoryEvent,
333 isV8ExecuteEvent: isV8ExecuteEvent,
334 isTopV8ExecuteEvent: isTopV8ExecuteEvent,
103 isGarbageCollectionEvent: isGarbageCollectionEvent, 335 isGarbageCollectionEvent: isGarbageCollectionEvent,
104 isTopGarbageCollectionEvent: isTopGarbageCollectionEvent, 336 isTopGarbageCollectionEvent: isTopGarbageCollectionEvent,
105 isSubGarbageCollectionEvent: isSubGarbageCollectionEvent, 337 isSubGarbageCollectionEvent: isSubGarbageCollectionEvent,
106 topGarbageCollectionEventName: topGarbageCollectionEventName, 338 topGarbageCollectionEventName: topGarbageCollectionEventName,
107 subGarbageCollectionEventName: subGarbageCollectionEventName 339 subGarbageCollectionEventName: subGarbageCollectionEventName,
340 PiecewiseLinearFunction: PiecewiseLinearFunction,
341 unionOfIntervals: unionOfIntervals,
342 mutatorUtilization: mutatorUtilization
108 }; 343 };
109 }); 344 });
110 </script> 345 </script>
OLDNEW
« tracing/tracing/metrics/v8/gc_metric.html ('K') | « tracing/tracing/metrics/v8/gc_metric_test.html ('k') | tracing/tracing/metrics/v8/utils_test.html » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698