411615f · TreeTrace

perf: drop analyzeTree and buildTree from O(N^2) to O(N)

buildTree: replace indexOf-in-loop parent lookup with an index counter,
and sort the timestamp list once instead of twice per stats build.

analyzeTree: memoize tokenSet per run in a WeakMap (reset at each entry),
so the four nearest* helpers that scan all N nodes stop re-tokenizing.

411615f Zion Boggan committed on Jun 18, 2026 (4 days ago)

src/analyze.js +6 -1

		@@ -247,7 +247,7 @@ function badPathEpisode(node) {

		export function analyzeTree(tree) {
		if (tree.analysis) return tree.analysis;
	-
	+	_tokenCache = new WeakMap();
		const modelsSeen = new Set();
		let thinkingBlocks = 0;
		for (const node of tree.nodes) {
		@@ -833,7 +833,11 @@ function sharedFiles(a, b) {
		return false;
		}

	+	let _tokenCache = new WeakMap();
		function tokenSet(node) {
	+	if (!node) return new Set();
	+	const cached = _tokenCache.get(node);
	+	if (cached) return cached;
		const out = new Set();
		const harvest = (s) => {
		for (const raw of String(s \|\| '').toLowerCase().match(/[a-z][a-z0-9_-]{2,}/g) \|\| []) {
		@@ -847,6 +851,7 @@ function tokenSet(node) {
		for (const a of node.actions \|\| []) {
		if (a.file) harvest(String(a.file).replace(/[\\/.+_-]+/g, ' '));
		}
	+	_tokenCache.set(node, out);
		return out;
		}

src/tree.js +7 -6

		@@ -50,10 +50,10 @@ export function buildTree(sessions, nodes) {
		for (const session of ordered) {
		const sNodes = nodesBySession.get(session.sessionId) \|\| [];
		if (!sNodes.length) continue;
	-	for (const node of sNodes) {
	-	if (!node.parent && node !== sNodes[0]) {
	-
	-	node.parent = sNodes[sNodes.indexOf(node) - 1];
	+	for (let i = 0; i < sNodes.length; i++) {
	+	const node = sNodes[i];
	+	if (!node.parent && i > 0) {
	+	node.parent = sNodes[i - 1];
		}
		}
		if (!sNodes[0].parent && prevTail) {
		@@ -118,6 +118,7 @@ function computeStats(sessions, nodes) {
		if (s.lastTs) timestamps.push(s.lastTs);
		}

	+	const sortedTs = timestamps.length ? [...timestamps].sort() : [];
		return {
		promptCount: nodes.length,
		rawPromptCount: sessions.reduce((acc, s) => acc + (s.prompts ? s.prompts.length : 0), 0),
		@@ -133,7 +134,7 @@ function computeStats(sessions, nodes) {
		filesTouched: filesTouched.size,
		models: [...models],
		days: daySpan(timestamps),
	-	firstTs: timestamps.length ? timestamps.slice().sort()[0] : null,
	-	lastTs: timestamps.length ? timestamps.slice().sort().at(-1) : null,
	+	firstTs: sortedTs[0] ?? null,
	+	lastTs: sortedTs.at(-1) ?? null,
		};
		}