| <!DOCTYPE html> |
| <!-- |
| Copyright 2016 The Chromium Authors. All rights reserved. |
| Use of this source code is governed by a BSD-style license that can be |
| found in the LICENSE file. |
| --> |
| |
| <link rel="import" href="/tracing/base/category_util.html"> |
| <link rel="import" href="/tracing/base/math/piecewise_linear_function.html"> |
| <link rel="import" href="/tracing/base/math/range.html"> |
| <link rel="import" href="/tracing/base/math/range_utils.html"> |
| <link rel="import" href="/tracing/base/unit.html"> |
| <link rel="import" href="/tracing/extras/v8/v8_thread_slice.html"> |
| <link rel="import" href="/tracing/metrics/metric_registry.html"> |
| <link rel="import" href="/tracing/value/histogram.html"> |
| |
| <script> |
| 'use strict'; |
| |
| tr.exportTo('tr.metrics.v8.utils', function() { |
| // The title of the idle task event. |
| const IDLE_TASK_EVENT = 'SingleThreadIdleTaskRunner::RunTask'; |
| |
| // V8 execution event. |
| const V8_EXECUTE = 'V8.Execute'; |
| |
| // GC events start with this prefix. |
| const GC_EVENT_PREFIX = 'V8.GC'; |
| |
| // Special handling is required for full GCs inside low memory notification. |
| const FULL_GC_EVENT = 'V8.GCCompactor'; |
| |
| const LOW_MEMORY_EVENT = 'V8.GCLowMemoryNotification'; |
| |
| const MAJOR_GC_EVENT = 'MajorGC'; |
| const MINOR_GC_EVENT = 'MinorGC'; |
| |
| // Maps the top-level GC events in timeline to telemetry friendly names. |
| const TOP_GC_EVENTS = { |
| 'V8.GCCompactor': 'v8-gc-full-mark-compactor', |
| 'V8.GCFinalizeMC': 'v8-gc-latency-mark-compactor', |
| 'V8.GCFinalizeMCReduceMemory': 'v8-gc-memory-mark-compactor', |
| 'V8.GCIncrementalMarking': 'v8-gc-incremental-step', |
| 'V8.GCIncrementalMarkingFinalize': 'v8-gc-incremental-finalize', |
| 'V8.GCIncrementalMarkingStart': 'v8-gc-incremental-start', |
| 'V8.GCPhantomHandleProcessingCallback': 'v8-gc-phantom-handle-callback', |
| 'V8.GCScavenger': 'v8-gc-scavenger' |
| }; |
| |
| const MARK_COMPACTOR_EVENTS = new Set([ |
| 'V8.GCCompactor', |
| 'V8.GCFinalizeMC', |
| 'V8.GCFinalizeMCReduceMemory', |
| 'V8.GCIncrementalMarking', |
| 'V8.GCIncrementalMarkingFinalize', |
| 'V8.GCIncrementalMarkingStart', |
| 'V8.GCPhantomHandleProcessingCallback' |
| ]); |
| |
| const LOW_MEMORY_MARK_COMPACTOR = 'v8-gc-low-memory-mark-compactor'; |
| |
| /** |
| * Finds the first parent of the |event| for which the |predicate| holds. |
| */ |
| function findParent(event, predicate) { |
| let parent = event.parentSlice; |
| while (parent) { |
| if (predicate(parent)) { |
| return parent; |
| } |
| parent = parent.parentSlice; |
| } |
| return null; |
| } |
| |
| function isIdleTask(event) { |
| return event.title === IDLE_TASK_EVENT; |
| } |
| |
| function isLowMemoryEvent(event) { |
| return event.title === LOW_MEMORY_EVENT; |
| } |
| |
| function isV8Event(event) { |
| return event.title.startsWith('V8.'); |
| } |
| |
| function isV8ExecuteEvent(event) { |
| return event.title === V8_EXECUTE; |
| } |
| |
| function isTopV8ExecuteEvent(event) { |
| return isV8ExecuteEvent(event) && findParent(isV8ExecuteEvent) === null; |
| } |
| |
| function isGarbageCollectionEvent(event) { |
| // Low memory notification is handled specially because it contains |
| // several full mark compact events. |
| return event.title && event.title.startsWith(GC_EVENT_PREFIX) && |
| event.title !== LOW_MEMORY_EVENT; |
| } |
| |
| function isTopGarbageCollectionEvent(event) { |
| return event.title in TOP_GC_EVENTS; |
| } |
| |
| function isForcedGarbageCollectionEvent(event) { |
| return findParent(event, isLowMemoryEvent) !== null; |
| } |
| |
| function isSubGarbageCollectionEvent(event) { |
| // To reduce number of results, we return only the first level of GC |
| // subevents. Some subevents are nested in MajorGC or MinorGC events, so |
| // we have to check for it explicitly. |
| return isGarbageCollectionEvent(event) && |
| event.parentSlice && |
| (isTopGarbageCollectionEvent(event.parentSlice) || |
| event.parentSlice.title === MAJOR_GC_EVENT || |
| event.parentSlice.title === MINOR_GC_EVENT); |
| } |
| |
| function isNotForcedTopGarbageCollectionEvent(event) { |
| // We exclude garbage collection events forced by benchmark runner, |
| // because they cannot happen in real world. |
| return tr.metrics.v8.utils.isTopGarbageCollectionEvent(event) && |
| !tr.metrics.v8.utils.isForcedGarbageCollectionEvent(event); |
| } |
| |
| function isNotForcedSubGarbageCollectionEvent(event) { |
| // We exclude garbage collection events forced by benchmark runner, |
| // because they cannot happen in real world. |
| return tr.metrics.v8.utils.isSubGarbageCollectionEvent(event) && |
| !tr.metrics.v8.utils.isForcedGarbageCollectionEvent(event); |
| } |
| |
| function isFullMarkCompactorEvent(event) { |
| return event.title === 'V8.GCCompactor'; |
| } |
| |
| function isMarkCompactorSummaryEvent(event) { |
| return event.title === 'V8.GCMarkCompactorSummary'; |
| } |
| |
| function isIncrementalMarkingEvent(event) { |
| return event.title.startsWith('V8.GCIncrementalMarking'); |
| } |
| |
| function isLatencyMarkCompactorEvent(event) { |
| return event.title === 'V8.GCFinalizeMC'; |
| } |
| |
| function isMemoryMarkCompactorEvent(event) { |
| return event.title === 'V8.GCFinalizeMCReduceMemory'; |
| } |
| |
| function isScavengerEvent(event) { |
| return event.title === 'V8.GCScavenger'; |
| } |
| |
| function isCompileOptimizeRCSCategory(name) { |
| return name === 'Optimize'; |
| } |
| |
| function isCompileUnoptimizeRCSCategory(name) { |
| return name === 'Compile'; |
| } |
| |
| function isCompileParseRCSCategory(name) { |
| return name === 'Parse'; |
| } |
| |
| function isCompileRCSCategory(name) { |
| return name === 'Compile' || name === 'Optimize' || name === 'Parse'; |
| } |
| |
| function isV8RCSEvent(event) { |
| return event instanceof tr.e.v8.V8ThreadSlice; |
| } |
| |
| function isMarkCompactorEvent(event) { |
| return MARK_COMPACTOR_EVENTS.has(event.title); |
| } |
| |
| function isNotForcedMarkCompactorEvent(event) { |
| return !isForcedGarbageCollectionEvent(event) && |
| isMarkCompactorEvent(event); |
| } |
| |
| function forcedGCEventName() { |
| return LOW_MEMORY_EVENT; |
| } |
| |
| function topGarbageCollectionEventName(event) { |
| if (event.title === FULL_GC_EVENT) { |
| // Full mark compact events inside a low memory notification |
| // are counted as low memory mark compacts. |
| if (findParent(event, isLowMemoryEvent)) { |
| return LOW_MEMORY_MARK_COMPACTOR; |
| } |
| } |
| return TOP_GC_EVENTS[event.title]; |
| } |
| |
| function subGarbageCollectionEventName(event) { |
| const topEvent = findParent(event, isTopGarbageCollectionEvent); |
| const prefix = topEvent ? topGarbageCollectionEventName(topEvent) : |
| 'unknown'; |
| // Remove redundant prefixes and convert to lower case. |
| const name = event.title.replace('V8.GC_MC_', '') |
| .replace('V8.GC_SCAVENGER_', '') |
| .replace('V8.GC_', '') |
| .replace(/_/g, '-').toLowerCase(); |
| return prefix + '-' + name; |
| } |
| |
| /** |
| * Filters events using the |filterCallback|, then groups events by the user |
| * the name computed using the |nameCallback|, and then invokes |
| * the |processCallback| with the grouped events. |
| * @param {Function} filterCallback Takes an event and returns a boolean. |
| * @param {Function} nameCallback Takes event and returns a string. |
| * @param {Function} processCallback Takes a name, and an array of events. |
| */ |
| function groupAndProcessEvents(model, filterCallback, |
| nameCallback, processCallback) { |
| // Map: name -> [events]. |
| const nameToEvents = {}; |
| for (const event of model.getDescendantEvents()) { |
| if (!filterCallback(event)) continue; |
| const name = nameCallback(event); |
| nameToEvents[name] = nameToEvents[name] || []; |
| nameToEvents[name].push(event); |
| } |
| for (const [name, events] of Object.entries(nameToEvents)) { |
| processCallback(name, events); |
| } |
| } |
| |
| /** |
| * Given a list of intervals, returns a new list with all overalapping |
| * intervals merged into a single interval. |
| */ |
| function unionOfIntervals(intervals) { |
| if (intervals.length === 0) return []; |
| return tr.b.math.mergeRanges( |
| intervals.map(x => { return { min: x.start, max: x.end }; }), 1e-6, |
| function(ranges) { |
| return { |
| start: ranges.reduce( |
| (acc, x) => Math.min(acc, x.min), ranges[0].min), |
| end: ranges.reduce((acc, x) => Math.max(acc, x.max), ranges[0].max) |
| }; |
| } |
| ); |
| } |
| |
| function hasV8Stats(globalMemoryDump) { |
| let v8stats = undefined; |
| globalMemoryDump.iterateContainerDumps(function(dump) { |
| v8stats = v8stats || dump.getMemoryAllocatorDumpByFullName('v8'); |
| }); |
| return !!v8stats; |
| } |
| |
| function rangeForMemoryDumps(model) { |
| const startOfFirstDumpWithV8 = |
| model.globalMemoryDumps.filter(hasV8Stats).reduce( |
| (start, dump) => Math.min(start, dump.start), Infinity); |
| // Empty range. |
| if (startOfFirstDumpWithV8 === Infinity) return new tr.b.math.Range(); |
| return tr.b.math.Range.fromExplicitRange(startOfFirstDumpWithV8, Infinity); |
| } |
| |
| /** |
| * An end-point of a window that is sliding from left to right |
| * over |points| starting from time |start|. |
| * It is intended to be used only by the |mutatorUtilization| function. |
| * @constructor |
| */ |
| class WindowEndpoint { |
| constructor(start, points) { |
| this.points = points; |
| // The index of the last passed point. |
| this.lastIndex = -1; |
| // The position of the end-point in the time line. |
| this.position = start; |
| this.distanceUntilNextPoint = points[0].position - start; |
| // The cumulative duration of GC pauses until this position. |
| this.cummulativePause = 0; |
| // The number of entered GC intervals. |
| this.stackDepth = 0; |
| } |
| |
| // Advance the end-point by the given |delta|. |
| advance(delta) { |
| if (delta < this.distanceUntilNextPoint) { |
| this.position += delta; |
| this.cummulativePause += this.stackDepth > 0 ? delta : 0; |
| this.distanceUntilNextPoint = |
| this.points[this.lastIndex + 1].position - this.position; |
| } else { |
| this.position += this.distanceUntilNextPoint; |
| this.cummulativePause += |
| this.stackDepth > 0 ? this.distanceUntilNextPoint : 0; |
| this.distanceUntilNextPoint = 0; |
| this.lastIndex++; |
| if (this.lastIndex < this.points.length) { |
| this.stackDepth += this.points[this.lastIndex].delta; |
| if (this.lastIndex + 1 < this.points.length) { |
| this.distanceUntilNextPoint = |
| this.points[this.lastIndex + 1].position - this.position; |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * Returns mutator utilization as a piecewise linear function. |
| * Mutator utilization for a window size w is a function of time mu_w(t) |
| * that shows how much time in [t, t+w] is left for the mutator relative |
| * to the time window size. |
| * More formally: |
| * mu_w(t) = (w - total_time_spent_in_gc_in(t, t + w)) / w. |
| * The range of mu_w(t) is [0..1]. |
| * See "A Parallel, Real-Time Garbage Collector" by Cheng et. al. for |
| * more info [https://www.cs.cmu.edu/~guyb/papers/gc2001.pdf]. |
| * |
| * All parameters must use the same time unit. |
| * @param {number} start The start time of execution. |
| * @param {number} end The end time of execution. |
| * @param {number} timeWindow The size of the time window. |
| * @param {!Array<!{start: number, end: number}>} intervals The list of |
| * GC pauses. |
| */ |
| function mutatorUtilization(start, end, timeWindow, intervals) { |
| const mu = new tr.b.math.PiecewiseLinearFunction(); |
| // If the interval is smaller than the time window, then the function is |
| // empty. |
| if (end - start <= timeWindow) { |
| return mu; |
| } |
| |
| // If there are GC pauses then the mutator utilization is 1.0. |
| if (intervals.length === 0) { |
| mu.push(start, 1.0, end - timeWindow, 1.0); |
| return mu; |
| } |
| |
| intervals = unionOfIntervals(intervals); |
| |
| // Create a point for the start and the end of each interval. |
| const points = []; |
| for (const interval of intervals) { |
| points.push({position: interval.start, delta: 1}); |
| points.push({position: interval.end, delta: -1}); |
| } |
| points.sort((a, b) => a.position - b.position); |
| points.push({position: end, delta: 0}); |
| |
| // The left and the right limit of the sliding window. |
| const left = new WindowEndpoint(start, points); |
| const right = new WindowEndpoint(start, points); |
| |
| // Advance the right end-point until we get the correct window size. |
| while (right.position - left.position < timeWindow) { |
| right.advance(timeWindow - (right.position - left.position)); |
| } |
| |
| while (right.lastIndex < points.length) { |
| // Advance the window end-points by the largest possible amount |
| // without jumping over a point. |
| const distanceUntilNextPoint = |
| Math.min(left.distanceUntilNextPoint, right.distanceUntilNextPoint); |
| const position1 = left.position; |
| const value1 = right.cummulativePause - left.cummulativePause; |
| left.advance(distanceUntilNextPoint); |
| right.advance(distanceUntilNextPoint); |
| // Add a new mutator utilization segment only if it is non-trivial. |
| if (distanceUntilNextPoint > 0) { |
| const position2 = left.position; |
| const value2 = right.cummulativePause - left.cummulativePause; |
| mu.push(position1, 1.0 - value1 / timeWindow, |
| position2, 1.0 - value2 / timeWindow); |
| } |
| } |
| return mu; |
| } |
| |
| /** |
| * Computes the minimum mutator utilization (MMU) metric for the given time |
| * windows and the given renderers. The results are added as histograms to |
| * the given histogram set. |
| * |
| * For example, passing 'v8-gc-mark-compactor-mmu' as the metric name and |
| * [16, 50, 100] as the time windows will produce the following: |
| * - v8-gc-mark-compactor-mmu-16ms_window |
| * - v8-gc-mark-compactor-mmu-50ms_window |
| * - v8-gc-mark-compactor-mmu-100ms_window |
| * |
| * @param {!string} metricName the name of the metric. |
| * @param {!function(tr.b.Event): boolean} eventFilter the predicate for |
| * filtering the events that will be used for computing the MMU. |
| * @param {!Array.<tr.model.helpers.ChromeRendererHelper>} rendererHelpers |
| * @param {!tr.v.HistogramSet} histograms |
| */ |
| function addMutatorUtilization( |
| metricName, eventFilter, timeWindows, rendererHelpers, histograms) { |
| const histogramMap = new Map(); |
| |
| for (const timeWindow of timeWindows) { |
| const histogramOptions = { |
| avg: false, |
| count: false, |
| max: false, |
| min: true, |
| std: false, |
| sum: false |
| }; |
| const histogram = histograms.createHistogram( |
| `${metricName}-${timeWindow}ms_window`, |
| tr.b.Unit.byName.normalizedPercentage_biggerIsBetter, |
| [], histogramOptions); |
| histogramMap.set(timeWindow, histogram); |
| } |
| |
| for (const rendererHelper of rendererHelpers) { |
| if (rendererHelper.isChromeTracingUI) continue; |
| const pauses = []; |
| for (const event of rendererHelper.mainThread.sliceGroup.childEvents()) { |
| if (eventFilter(event) && event.end > event.start) { |
| pauses.push({start: event.start, end: event.end}); |
| } |
| } |
| pauses.sort((a, b) => a.start - b.start); |
| const start = rendererHelper.mainThread.bounds.min; |
| const end = rendererHelper.mainThread.bounds.max; |
| for (const timeWindow of timeWindows) { |
| const mu = mutatorUtilization(start, end, timeWindow, pauses); |
| histogramMap.get(timeWindow).addSample(mu.min); |
| } |
| } |
| } |
| |
| |
| return { |
| addMutatorUtilization, |
| findParent, |
| forcedGCEventName, |
| groupAndProcessEvents, |
| isForcedGarbageCollectionEvent, |
| isFullMarkCompactorEvent, |
| isGarbageCollectionEvent, |
| isIdleTask, |
| isIncrementalMarkingEvent, |
| isLatencyMarkCompactorEvent, |
| isLowMemoryEvent, |
| isMarkCompactorSummaryEvent, |
| isMemoryMarkCompactorEvent, |
| isNotForcedMarkCompactorEvent, |
| isNotForcedTopGarbageCollectionEvent, |
| isNotForcedSubGarbageCollectionEvent, |
| isScavengerEvent, |
| isSubGarbageCollectionEvent, |
| isTopGarbageCollectionEvent, |
| isTopV8ExecuteEvent, |
| isV8Event, |
| isV8ExecuteEvent, |
| isV8RCSEvent, |
| isCompileRCSCategory, |
| isCompileOptimizeRCSCategory, |
| isCompileUnoptimizeRCSCategory, |
| isCompileParseRCSCategory, |
| mutatorUtilization, |
| rangeForMemoryDumps, |
| subGarbageCollectionEventName, |
| topGarbageCollectionEventName, |
| unionOfIntervals, |
| }; |
| }); |
| </script> |
