// Copyright 2022 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
import {TickLogEntry} from './log/tick.mjs';
const kForward = 1;
const kBackwards = -1;
/**
* The StackSorter sorts ticks by recursively grouping the most frequent frames
* at each stack-depth to the beginning. This is used to generate flame graphs.
*
* Example
* tick1 = [a1, b1]
* tick2 = [a0, b0]
* tick3 = [a1, b1, c1]
* tick4 = [a1, b0, c0, d0]
*
* If we sort this recursively from the beginning we get:
* tick1 = [a1, b1]
* tick3 = [a1, b1, c1]
* tick4 = [a1, b0, c0, d0]
* tick2 = [a0, b0]
*
* The idea is to group common stacks together to generate easily readable
* graphs where we can quickly discover which function is the highest incoming
* or outgoing contributor.
*/
export class StackSorter {
static fromTop(array, maxDepth) {
return new this(array, maxDepth, kForward).sorted();
}
static fromBottom(array, maxDepth) {
return new this(array, maxDepth, kBackwards).sorted();
}
constructor(array, maxDepth, direction) {
this.stacks = array;
this.maxDepth = maxDepth;
if (direction !== kForward && direction !== kBackwards) {
throw new Error('Invalid direction');
}
this.direction = direction;
}
sorted() {
const startLevel = this.direction == kForward ? 0 : this.maxDepth - 1;
this._sort(0, this.stacks.length, startLevel);
return this.stacks;
}
_sort(start, end, stackIndex) {
if (stackIndex >= this.maxDepth || stackIndex < 0) return;
const length = end - start;
if (length <= 1) return;
let counts;
{
const kNoFrame = -1;
let bag = new Map();
for (let i = start; i < end; i++) {
let code = this.stacks[i][stackIndex] ?? kNoFrame;
const count = bag.get(code) ?? 0;
bag.set(code, count + 1);
}
// If all the frames are the same at the current stackIndex, check the
// next stackIndex.
if (bag.size === 1) {
return this._sort(start, end, stackIndex + this.direction);
}
counts = Array.from(bag)
counts.sort((a, b) => b[1] - a[1]);
let currentIndex = start;
// Reuse bag since we've copied out the counts;
let insertionIndices = bag;
for (let i = 0; i < counts.length; i++) {
const pair = counts[i];
const code = pair[0];
const count = pair[1];
insertionIndices.set(code, currentIndex);
currentIndex += count;
}
// TODO do copy-less
let stacksSegment = this.stacks.slice(start, end);
for (let i = 0; i < length; i++) {
const stack = stacksSegment[i];
const entry = stack[stackIndex] ?? kNoFrame;
const insertionIndex = insertionIndices.get(entry);
if (!Number.isFinite(insertionIndex)) {
throw 'Invalid insertionIndex: ' + insertionIndex;
}
if (insertionIndex < start || insertionIndex >= end) {
throw 'Invalid insertionIndex: ' + insertionIndex;
}
this.stacks[insertionIndex] = stack;
insertionIndices.set(entry, insertionIndex + 1);
}
// Free up variables before recursing.
insertionIndices = bag = stacksSegment = undefined;
}
// Sort sub-segments
let segmentStart = start;
let segmentEnd = start;
for (let i = 0; i < counts.length; i++) {
const segmentLength = counts[i][1];
segmentEnd = segmentStart + segmentLength - 1;
this._sort(segmentStart, segmentEnd, stackIndex + this.direction);
segmentStart = segmentEnd;
}
}
}
export class ProfileNode {
constructor(codeEntry) {
this.codeEntry = codeEntry;
this.inCodeEntries = [];
// [tick0, framePos0, tick1, framePos1, ...]
this.ticksAndPosition = [];
this.outCodeEntries = [];
this._selfDuration = 0;
this._totalDuration = 0;
}
stacksOut() {
const slicedStacks = [];
let maxDepth = 0;
for (let i = 0; i < this.ticksAndPosition.length; i += 2) {
// tick.stack = [topN, ..., top0, this.codeEntry, bottom0, ..., bottomN];
const tick = this.ticksAndPosition[i];
const stackIndex = this.ticksAndPosition[i + 1];
// slice = [topN, ..., top0]
const slice = tick.stack.slice(0, stackIndex);
maxDepth = Math.max(maxDepth, slice.length);
slicedStacks.push(slice);
}
// Before:
// stack1 = [f4, f3, f2, f1]
// stack2 = [f2, f1]
// After:
// stack1 = [f4, f3, f2, f1]
// stack2 = [ , , f2, f1]
for (let i = 0; i < slicedStacks.length; i++) {
const stack = slicedStacks[i];
const length = stack.length;
if (length < maxDepth) {
// Pad stacks at the beginning
stack.splice(maxDepth - length, 0, undefined);
}
}
// Start sorting at the bottom-most frame: top0 => topN / f1 => fN
return StackSorter.fromBottom(slicedStacks, maxDepth);
}
stacksIn() {
const slicedStacks = [];
let maxDepth = 0;
for (let i = 0; i < this.ticksAndPosition.length; i += 2) {
// tick.stack = [topN, ..., top0, this.codeEntry, bottom0..., bottomN];
const tick = this.ticksAndPosition[i];
const stackIndex = this.ticksAndPosition[i + 1];
// slice = [bottom0, ..., bottomN]
const slice = tick.stack.slice(stackIndex + 1);
maxDepth = Math.max(maxDepth, slice.length);
slicedStacks.push(slice);
}
// Start storting at the top-most frame: bottom0 => bottomN
return StackSorter.fromTop(slicedStacks, maxDepth);
}
startTime() {
return this.ticksAndPosition[0].startTime;
}
endTime() {
return this.ticksAndPosition[this.ticksAndPosition.length - 2].endTime;
}
duration() {
return this.endTime() - this.startTime();
}
selfCount() {
return this.totalCount() - this.outCodeEntries.length;
}
totalCount() {
return this.ticksAndPosition.length / 2;
}
isLeaf() {
return this.selfCount() == this.totalCount();
}
totalDuration() {
let duration = 0;
for (let entry of this.ticksAndPosition) duration += entry.duration;
return duration;
}
selfDuration() {
let duration = this.totalDuration();
for (let entry of this.outCodeEntries) duration -= entry.duration;
return duration;
}
}
export class Flame {
constructor(time, logEntry, depth, duration = -1) {
this._time = time;
this._logEntry = logEntry;
this.depth = depth;
this._duration = duration;
this.parent = undefined;
this.children = [];
}
static add(time, logEntry, stack, flames) {
const depth = stack.length;
const newFlame = new Flame(time, logEntry, depth);
if (depth > 0) {
const parent = stack[depth - 1];
newFlame.parent = parent;
parent.children.push(newFlame);
}
flames.push(newFlame);
stack.push(newFlame);
}
stop(time) {
if (this._duration !== -1) throw new Error('Already stopped');
this._duration = time - this._time
}
get time() {
return this._time;
}
get logEntry() {
return this._logEntry;
}
get startTime() {
return this._time;
}
get endTime() {
return this._time + this._duration;
}
get duration() {
return this._duration;
}
get type() {
return TickLogEntry.extractCodeEntryType(this._logEntry?.entry);
}
get name() {
return this._logEntry?.name;
}
}
export class FlameBuilder {
static forTime(ticks, reverseDepth) {
return new this(ticks, true, reverseDepth);
}
static forTicks(ticks, reverseDepth = false) {
return new this(ticks, false, reverseDepth);
}
constructor(ticks, useTime, reverseDepth) {
this.maxDepth = 0;
let tempFlames = this.flames = [];
this.reverseDepth = reverseDepth;
if (ticks.length == 0) return;
if (!(ticks[0] instanceof TickLogEntry) && !Array.isArray(ticks[0])) {
throw new Error(
'Expected ticks array: `[TickLogEntry, ..]`, or raw stacks: `[[CodeEntry, ...], [...]]`');
}
// flameStack = [bottom, ..., top];
const flameStack = [];
let maxDepth = 0;
const ticksLength = ticks.length;
for (let tickIndex = 0; tickIndex < ticksLength; tickIndex++) {
const tick = ticks[tickIndex];
// tick is either a Tick log entry, or an Array
const tickStack = tick.stack ?? tick;
const tickStackLength = tickStack.length;
const timeValue = useTime ? tick.time : tickIndex;
maxDepth = Math.max(maxDepth, tickStackLength);
// tick.stack = [top, .... , bottom];
for (let stackIndex = tickStackLength - 1; stackIndex >= 0;
stackIndex--) {
const codeEntry = tickStack[stackIndex];
// Assume that all higher stack entries are undefined as well.
if (codeEntry === undefined) break;
// codeEntry is either a CodeEntry or a raw pc.
const logEntry = codeEntry?.logEntry ?? codeEntry;
const flameStackIndex = tickStackLength - stackIndex - 1;
if (flameStackIndex < flameStack.length) {
if (flameStack[flameStackIndex].logEntry === logEntry) continue;
// A lower frame changed, close all higher Flames.
for (let k = flameStackIndex; k < flameStack.length; k++) {
flameStack[k].stop(timeValue);
}
flameStack.length = flameStackIndex;
}
Flame.add(timeValue, logEntry, flameStack, tempFlames);
}
// Stop all Flames that are deeper nested than the current stack.
if (tickStackLength < flameStack.length) {
for (let k = tickStackLength; k < flameStack.length; k++) {
flameStack[k].stop(timeValue);
}
flameStack.length = tickStackLength;
}
}
this.maxDepth = maxDepth;
const lastTime = useTime ? ticks[ticksLength - 1].time : ticksLength - 1;
for (let k = 0; k < flameStack.length; k++) {
flameStack[k].stop(lastTime);
}
}
}