perfetto-ui: Merging small callsites in flamegraph
Adding API with unit tests for merging small callsites into one before
sending data to the flamegraph API so the number of callsites doesn't grow
too much.
All small callsites in the same depth and with same parent will be merged
to one callsite.
Test trace: ?s=a1bd404ed3138d203fabae47299b89d39c604e8da0a269b470c60fa5e228f
Change-Id: I8aa0f0488f570141e89b7cb78d8fc549a76076fa
diff --git a/ui/src/frontend/flamegraph.ts b/ui/src/frontend/flamegraph.ts
index 3cd0c6c..125d9f8 100644
--- a/ui/src/frontend/flamegraph.ts
+++ b/ui/src/frontend/flamegraph.ts
@@ -34,6 +34,16 @@
export const HEAP_PROFILE_COLOR = 'hsl(224, 45%, 70%)';
export const HEAP_PROFILE_HOVERED_COLOR = 'hsl(224, 45%, 55%)';
+export function findRootSize(data: CallsiteInfo[]) {
+ let totalSize = 0;
+ let i = 0;
+ while (i < data.length && data[i].depth === 0) {
+ totalSize += data[i].totalSize;
+ i++;
+ }
+ return totalSize;
+}
+
export class Flamegraph {
private isThumbnail = false;
private flamegraphData: CallsiteInfo[];
@@ -64,16 +74,6 @@
this.maxDepth = Math.max(...this.flamegraphData.map(value => value.depth));
}
- private findTotalSize() {
- let totalSize = 0;
- this.flamegraphData.forEach((value: CallsiteInfo) => {
- if (value.parentHash === -1) {
- totalSize += value.totalSize;
- }
- });
- return totalSize;
- }
-
hash(s: string): number {
let hash = 0x811c9dc5 & 0xfffffff;
for (let i = 0; i < s.length; i++) {
@@ -109,7 +109,7 @@
this.clickedCallsite = undefined;
this.findMaxDepth();
// Finding total size of roots.
- this.totalSize = this.findTotalSize();
+ this.totalSize = findRootSize(flamegraphData);
}
draw(
diff --git a/ui/src/frontend/frontend_local_state.ts b/ui/src/frontend/frontend_local_state.ts
index b9e4b5b..710c767 100644
--- a/ui/src/frontend/frontend_local_state.ts
+++ b/ui/src/frontend/frontend_local_state.ts
@@ -270,4 +270,10 @@
this._visibleState.resolution = globals.getCurResolution();
this.ratelimitedUpdateVisible();
}
+
+ updateResolution(pxStart: number, pxEnd: number) {
+ this.timeScale.setLimitsPx(pxStart, pxEnd);
+ this._visibleState.resolution = globals.getCurResolution();
+ this.ratelimitedUpdateVisible();
+ }
}
diff --git a/ui/src/frontend/viewer_page.ts b/ui/src/frontend/viewer_page.ts
index 37c0279..d9243b0 100644
--- a/ui/src/frontend/viewer_page.ts
+++ b/ui/src/frontend/viewer_page.ts
@@ -132,8 +132,7 @@
const frontendLocalState = globals.frontendLocalState;
const updateDimensions = () => {
const rect = vnode.dom.getBoundingClientRect();
- frontendLocalState.timeScale.setLimitsPx(
- 0, rect.width - TRACK_SHELL_WIDTH);
+ frontendLocalState.updateResolution(0, rect.width - TRACK_SHELL_WIDTH);
};
updateDimensions();
diff --git a/ui/src/tracks/heap_profile_flamegraph/controller.ts b/ui/src/tracks/heap_profile_flamegraph/controller.ts
index 9677b66..d679553 100644
--- a/ui/src/tracks/heap_profile_flamegraph/controller.ts
+++ b/ui/src/tracks/heap_profile_flamegraph/controller.ts
@@ -17,6 +17,7 @@
TrackController,
trackControllerRegistry
} from '../../controller/track_controller';
+import {findRootSize} from '../../frontend/flamegraph';
import {CallsiteInfo} from '../../frontend/globals';
import {
@@ -26,6 +27,70 @@
HeapProfileFlamegraphKey,
} from './common';
+const MIN_PIXEL_DISPLAYED = 1;
+
+// Merge callsites that have approximately width less than
+// MIN_PIXEL_DISPLAYED. All small callsites in the same depth and with same
+// parent will be merged to one callsite with size of the biggest merged
+// callsite.
+export function mergeCallsites(data: CallsiteInfo[], minSizeDisplayed: number) {
+ const mergedData: CallsiteInfo[] = [];
+ const mergedCallsites: Map<number, number> = new Map();
+ for (let i = 0; i < data.length; i++) {
+ // When a small callsite is found, it will be merged with other small
+ // callsites of the same depth. So if the current callsite has already been
+ // merged we can skip it.
+ if (mergedCallsites.has(data[i].hash)) {
+ continue;
+ }
+ const copiedCallsite = copyCallsite(data[i]);
+ copiedCallsite.parentHash =
+ getCallsitesParentHash(copiedCallsite, mergedCallsites);
+
+ // If current callsite is small, find other small callsites with same depth
+ // and parent and merge them into the current one, marking them as merged.
+ if (copiedCallsite.totalSize <= minSizeDisplayed && i + 1 < data.length) {
+ let j = i + 1;
+ let nextCallsite = data[j];
+ while (j < data.length && copiedCallsite.depth === nextCallsite.depth) {
+ if (copiedCallsite.parentHash ===
+ getCallsitesParentHash(nextCallsite, mergedCallsites) &&
+ nextCallsite.totalSize <= minSizeDisplayed) {
+ copiedCallsite.totalSize += nextCallsite.totalSize;
+ mergedCallsites.set(nextCallsite.hash, copiedCallsite.hash);
+ }
+ j++;
+ nextCallsite = data[j];
+ }
+ }
+ mergedData.push(copiedCallsite);
+ }
+ return mergedData;
+}
+
+function copyCallsite(callsite: CallsiteInfo): CallsiteInfo {
+ return {
+ hash: callsite.hash,
+ parentHash: callsite.parentHash,
+ depth: callsite.depth,
+ name: callsite.name,
+ totalSize: callsite.totalSize
+ };
+}
+
+function getCallsitesParentHash(
+ callsite: CallsiteInfo, map: Map<number, number>): number {
+ return map.has(callsite.parentHash) ? map.get(callsite.parentHash)! :
+ callsite.parentHash;
+}
+
+function getMinSizeDisplayed(flamegraphData: CallsiteInfo[]): number {
+ const timeState = globals.state.frontendLocalState.visibleState;
+ const width = (timeState.endSec - timeState.startSec) / timeState.resolution;
+ const rootSize = findRootSize(flamegraphData);
+ return MIN_PIXEL_DISPLAYED * rootSize / width;
+}
+
class HeapProfileFlameraphTrackController extends
TrackController<Config, Data> {
static readonly kind = HEAP_PROFILE_FLAMEGRAPH_TRACK_KIND;
@@ -36,6 +101,8 @@
private lastSelectedTs?: number;
private lastSelectedId?: number;
+ private flamegraphDatasets: Map<string, CallsiteInfo[]> = new Map();
+
async onBoundsChange(start: number, end: number, resolution: number):
Promise<Data> {
this.start = start;
@@ -51,7 +118,7 @@
end: -1,
resolution: this.resolution,
length: 0,
- flamegraph: new Array()
+ flamegraph: []
};
return data;
}
@@ -65,6 +132,7 @@
return;
}
const selectedId = selection.id;
+ const selectedUpid = selection.upid;
const selectedKind = selection.kind;
const selectedTs = selection.ts;
this.lastSelectedId = selection.id;
@@ -76,26 +144,46 @@
'TrackData',
{id: HeapProfileFlamegraphKey, data: this.generateEmptyData()});
- this.getFlamegraphData(selection.ts, selection.upid).then(flamegraph => {
- if (flamegraph !== undefined && selection &&
- selection.kind === selectedKind && selection.id === selectedId &&
- selection.ts === selectedTs) {
- globals.publish('TrackData', {
- id: HeapProfileFlamegraphKey,
- data: {
- start: this.start,
- end: this.end,
- resolution: this.resolution,
- length: this.length,
- flamegraph
+ const key = `${selectedUpid};${selectedTs}`;
+
+ // TODO(tneda): Prevent lots of flamegraph queries being queued if a user
+ // clicks lots of the markers quickly.
+ this.getFlamegraphData(key, selection.ts, selectedUpid)
+ .then(flamegraphData => {
+ if (flamegraphData !== undefined && selection &&
+ selection.kind === selectedKind &&
+ selection.id === selectedId && selection.ts === selectedTs) {
+ // TODO(tneda): Remove before submitting.
+ const mergedFlamegraphData = mergeCallsites(
+ flamegraphData, getMinSizeDisplayed(flamegraphData));
+
+ globals.publish('TrackData', {
+ id: HeapProfileFlamegraphKey,
+ data: {
+ start: this.start,
+ end: this.end,
+ resolution: this.resolution,
+ length: this.length,
+ flamegraph: mergedFlamegraphData
+ }
+ });
}
});
- }
- });
}
}
- async getFlamegraphData(ts: number, upid: number) {
+ async getFlamegraphData(key: string, ts: number, upid: number) {
+ let currentData;
+ if (this.flamegraphDatasets.has(key)) {
+ currentData = this.flamegraphDatasets.get(key);
+ } else {
+ currentData = await this.getFlamegraphDataFromTables(ts, upid);
+ this.flamegraphDatasets.set(key, currentData);
+ }
+ return currentData;
+ }
+
+ async getFlamegraphDataFromTables(ts: number, upid: number) {
// Collecting data for drawing flagraph for selected heap profile.
// Data needs to be in following format:
// id, name, parent_id, depth, total_size
@@ -169,8 +257,7 @@
from callsite_children
group by hash
order by depth, parent_hash, size desc, name`);
-
- const flamegraphData: CallsiteInfo[] = new Array();
+ const flamegraphData: CallsiteInfo[] = [];
for (let i = 0; i < callsites.numRecords; i++) {
const hash = callsites.columns[0].longValues![i];
const name = callsites.columns[1].stringValues![i];
diff --git a/ui/src/tracks/heap_profile_flamegraph/controller_unittest.ts b/ui/src/tracks/heap_profile_flamegraph/controller_unittest.ts
new file mode 100644
index 0000000..63853f1
--- /dev/null
+++ b/ui/src/tracks/heap_profile_flamegraph/controller_unittest.ts
@@ -0,0 +1,199 @@
+import {CallsiteInfo} from '../../frontend/globals';
+import {mergeCallsites} from './controller';
+
+test('zeroCallsitesMerged', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: -1, name: 'B', depth: 0, totalSize: 8},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 4},
+ {hash: 4, parentHash: 2, name: 'B4', depth: 1, totalSize: 4},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 5);
+
+ // Small callsites are not next ot each other, nothing should be changed.
+ expect(mergedCallsites).toEqual(callsites);
+});
+
+test('zeroCallsitesMerged2', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: -1, name: 'B', depth: 0, totalSize: 8},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 6},
+ {hash: 4, parentHash: 1, name: 'A4', depth: 1, totalSize: 4},
+ {hash: 5, parentHash: 2, name: 'B5', depth: 1, totalSize: 8},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 5);
+
+ // Small callsites are not next ot each other, nothing should be changed.
+ expect(mergedCallsites).toEqual(callsites);
+});
+
+test('twoCallsitesMerged', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: 1, name: 'A2', depth: 1, totalSize: 5},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 5},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 6);
+
+ expect(mergedCallsites).toEqual([
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: 1, name: 'A2', depth: 1, totalSize: 10},
+ ]);
+});
+
+test('manyCallsitesMerged', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: 1, name: 'A2', depth: 1, totalSize: 5},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 3},
+ {hash: 4, parentHash: 1, name: 'A4', depth: 1, totalSize: 1},
+ {hash: 5, parentHash: 1, name: 'A5', depth: 1, totalSize: 1},
+ {hash: 6, parentHash: 3, name: 'A36', depth: 2, totalSize: 1},
+ {hash: 7, parentHash: 4, name: 'A47', depth: 2, totalSize: 1},
+ {hash: 8, parentHash: 5, name: 'A58', depth: 2, totalSize: 1},
+ ];
+
+ const expectedMergedCallsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: 1, name: 'A2', depth: 1, totalSize: 5},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 5},
+ {hash: 6, parentHash: 3, name: 'A36', depth: 2, totalSize: 3},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 4);
+
+ // In this case, callsites A3, A4 and A5 should be merged since they are
+ // smaller then 4 and are on same depth with same parent. Callsites A36, A47
+ // and A58 should also be merged since their parents are merged.
+ expect(mergedCallsites).toEqual(expectedMergedCallsites);
+});
+
+test('manyCallsitesMergedWithoutChildren', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 5},
+ {hash: 2, parentHash: -1, name: 'B', depth: 0, totalSize: 5},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 3},
+ {hash: 4, parentHash: 1, name: 'A4', depth: 1, totalSize: 1},
+ {hash: 5, parentHash: 1, name: 'A5', depth: 1, totalSize: 1},
+ {hash: 6, parentHash: 2, name: 'B6', depth: 1, totalSize: 5},
+ {hash: 7, parentHash: 4, name: 'A47', depth: 2, totalSize: 1},
+ {hash: 8, parentHash: 6, name: 'B68', depth: 2, totalSize: 1},
+ ];
+
+ const expectedMergedCallsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 5},
+ {hash: 2, parentHash: -1, name: 'B', depth: 0, totalSize: 5},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 5},
+ {hash: 6, parentHash: 2, name: 'B6', depth: 1, totalSize: 5},
+ {hash: 7, parentHash: 3, name: 'A47', depth: 2, totalSize: 1},
+ {hash: 8, parentHash: 6, name: 'B68', depth: 2, totalSize: 1},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 4);
+
+ // In this case, callsites A3, A4 and A5 should be merged since they are
+ // smaller then 4 and are on same depth with same parent. Callsite A47
+ // should not be merged with B68 althought they are small because they don't
+ // have sam parent. A47 should now have parent A3 because A4 is merged.
+ expect(mergedCallsites).toEqual(expectedMergedCallsites);
+});
+
+test('smallCallsitesNotNextToEachOtherInArray', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 20},
+ {hash: 2, parentHash: 1, name: 'A2', depth: 1, totalSize: 8},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 1},
+ {hash: 4, parentHash: 1, name: 'A4', depth: 1, totalSize: 8},
+ {hash: 5, parentHash: 1, name: 'A5', depth: 1, totalSize: 3},
+ ];
+
+ const expectedMergedCallsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 20},
+ {hash: 2, parentHash: 1, name: 'A2', depth: 1, totalSize: 8},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 4},
+ {hash: 4, parentHash: 1, name: 'A4', depth: 1, totalSize: 8},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 4);
+
+ // In this case, callsites A3, A4 and A5 should be merged since they are
+ // smaller then 4 and are on same depth with same parent. Callsite A47
+ // should not be merged with B68 althought they are small because they don't
+ // have sam parent. A47 should now have parent A3 because A4 is merged.
+ expect(mergedCallsites).toEqual(expectedMergedCallsites);
+});
+
+test('smallCallsitesNotMerged', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: 1, name: 'A2', depth: 1, totalSize: 2},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 2},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 1);
+
+ expect(mergedCallsites).toEqual(callsites);
+});
+
+test('mergingRootCallsites', () => {
+ const callsites: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 10},
+ {hash: 2, parentHash: -1, name: 'B', depth: 0, totalSize: 2},
+ ];
+
+ const mergedCallsites = mergeCallsites(callsites, 20);
+
+ expect(mergedCallsites).toEqual([
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 12},
+ ]);
+});
+
+test('largerFlamegraph', () => {
+ const data: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 60},
+ {hash: 2, parentHash: -1, name: 'B', depth: 0, totalSize: 40},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 25},
+ {hash: 4, parentHash: 1, name: 'A4', depth: 1, totalSize: 15},
+ {hash: 5, parentHash: 1, name: 'A5', depth: 1, totalSize: 10},
+ {hash: 6, parentHash: 1, name: 'A6', depth: 1, totalSize: 10},
+ {hash: 7, parentHash: 2, name: 'B7', depth: 1, totalSize: 30},
+ {hash: 8, parentHash: 2, name: 'B8', depth: 1, totalSize: 10},
+ {hash: 9, parentHash: 3, name: 'A39', depth: 2, totalSize: 20},
+ {hash: 10, parentHash: 4, name: 'A410', depth: 2, totalSize: 10},
+ {hash: 11, parentHash: 4, name: 'A411', depth: 2, totalSize: 3},
+ {hash: 12, parentHash: 4, name: 'A412', depth: 2, totalSize: 2},
+ {hash: 13, parentHash: 5, name: 'A513', depth: 2, totalSize: 5},
+ {hash: 14, parentHash: 5, name: 'A514', depth: 2, totalSize: 5},
+ {hash: 15, parentHash: 7, name: 'A715', depth: 2, totalSize: 10},
+ {hash: 16, parentHash: 7, name: 'A716', depth: 2, totalSize: 5},
+ {hash: 17, parentHash: 7, name: 'A717', depth: 2, totalSize: 5},
+ {hash: 18, parentHash: 7, name: 'A718', depth: 2, totalSize: 5},
+ {hash: 19, parentHash: 9, name: 'A919', depth: 3, totalSize: 10},
+ {hash: 20, parentHash: 17, name: 'A1720', depth: 3, totalSize: 2},
+ ];
+
+ const expectedData: CallsiteInfo[] = [
+ {hash: 1, parentHash: -1, name: 'A', depth: 0, totalSize: 60},
+ {hash: 2, parentHash: -1, name: 'B', depth: 0, totalSize: 40},
+ {hash: 3, parentHash: 1, name: 'A3', depth: 1, totalSize: 25},
+ {hash: 4, parentHash: 1, name: 'A4', depth: 1, totalSize: 35},
+ {hash: 7, parentHash: 2, name: 'B7', depth: 1, totalSize: 30},
+ {hash: 8, parentHash: 2, name: 'B8', depth: 1, totalSize: 10},
+ {hash: 9, parentHash: 3, name: 'A39', depth: 2, totalSize: 20},
+ {hash: 10, parentHash: 4, name: 'A410', depth: 2, totalSize: 25},
+ {hash: 15, parentHash: 7, name: 'A715', depth: 2, totalSize: 25},
+ {hash: 19, parentHash: 9, name: 'A919', depth: 3, totalSize: 10},
+ {hash: 20, parentHash: 15, name: 'A1720', depth: 3, totalSize: 2},
+ ];
+
+ // In this case, on depth 1, callsites A4, A5 and A6 should be merged and
+ // initiate merging of their children A410, A411, A412, A513, A514. On depth2,
+ // callsites A715, A716, A717 and A718 should be merged.
+ const actualData = mergeCallsites(data, 16);
+
+ expect(actualData).toEqual(expectedData);
+});
diff --git a/ui/src/tracks/heap_profile_flamegraph/frontend.ts b/ui/src/tracks/heap_profile_flamegraph/frontend.ts
index 7dcbc6a..a3d39a6 100644
--- a/ui/src/tracks/heap_profile_flamegraph/frontend.ts
+++ b/ui/src/tracks/heap_profile_flamegraph/frontend.ts
@@ -42,7 +42,7 @@
constructor(trackState: TrackState) {
super(trackState);
- this.flamegraph = new Flamegraph(new Array());
+ this.flamegraph = new Flamegraph([]);
this.flamegraph.enableThumbnail(this.config.isMinimized);
}
@@ -53,7 +53,7 @@
private changeFlamegraphData() {
const data = this.data();
if (data === undefined) {
- this.flamegraph.updateDataIfChanged(new Array());
+ this.flamegraph.updateDataIfChanged([]);
} else {
this.flamegraph.updateDataIfChanged(data.flamegraph);
}