mirror of
https://github.com/colbymchenry/codegraph.git
synced 2026-10-18 22:02:49 +08:00
Colby Mchenry
8f0766cc50
go-ethereum's `codegraph init` sat in "Resolving refs" for good on Node 22 (killed after 1 h 55 min and 9,203 CPU-seconds). It was not Go: two resolver pool workers each sat on one 500-ref chunk of graphql/internal/graphiql/graphiql.min.js, a 980 KB bundle on one line (18,388 refs, 2,234 functions). Whether a JS function binds a name itself (jsFunctionLocalScope, #2226) is read off its comment-stripped code with a parameter-list regex that starts with a `(?<!\b(?:if|while|for|switch|with)\s*)` lookbehind. Node 22's V8 compiles new regexes without optimization once a process has generated about a megabyte of regex code and holds 16 MB of executable memory, which a pool worker reaches after some 30,000 refs. Unoptimized, the lookbehind runs at every position and its `\s*` reads back through the whole run of blanks before it, so a run of n blanks costs n^2/2 steps. The comment stripper, which doesn't know regex literals, reads the `//` that closes `/Trident\//` as a comment and blanks the remaining 961,968 characters of the line. In a worker's state the regex took 36 ms over 16 K characters of that line, 5.1 s over 32 K and 54 s over 64 K, against 0.23 ms over 128 K in a fresh process. Compiling 20,000 throwaway regexes first reproduces it in a bare Node 22 process, and --no-regexp-optimization reproduces it anywhere. Node 24's V8, the runtime release bundles ship, kept optimizing after 60,000, so released installs finish: 1.6.2 indexes go-ethereum on its bundled Node 24 and stalls the same way on Node 22. The stall is as old as #2226. - A leading `(?=\()` keeps the lookbehind to where a parameter list opens. Every match starts with `(` anyway, so the regex matches exactly what it did. - The jsx-render pass split the file, sliced a function's lines and scanned them for tags once per function: 2,234 times over the bundle's line, 25 of the 28 s its linking passes took on Node 22 (9 of 13 on Node 24), for no edges. Functions that span the same lines now share one scan, and the file is split once. Graph: go-ethereum dumps (nodes, edges, unresolved refs, files) are byte-identical between main on Node 24 (main never finishes on Node 22) and this change on Node 22 and on Node 24. Main and this change also match byte for byte on bootstrap4, legend-state, takenote, mantis, excalidraw (482 jsx-render edges), qwik, gin, prometheus, etcd and hugo. Time, go-ethereum: on Node 22 main never finishes and this change takes 36 s; on Node 24 (three interleaved rounds, medians) 42.1 s -> 38.3 s wall, with resolution 17.7 s -> 12.7 s and the linking passes 6.5 s -> 1.5 s. Tests: js-local-binding-backtracking forces V8's unoptimized mode and indexes a function with a 60,000-character comment before a call (69 s on main, 1.4 s now); jsx-render-work counts the tag scans of 60 components on one line (60 on main, 1 now). Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
74 lines
3.2 KiB
TypeScript
74 lines
3.2 KiB
TypeScript
/**
|
|
* Whether a JS function binds a name itself (jsFunctionLocalScope, #2226) is
|
|
* read off the function's comment-stripped code with a parameter-list regex.
|
|
* Its `(?<!\b(?:if|while|for|switch|with)\s*)` lookbehind is cheap only while
|
|
* V8 optimizes the regex, and Node 22's V8 stops optimizing new regexes once a
|
|
* process has generated about a megabyte of regex code — which a resolver pool
|
|
* worker does early, compiling patterns per receiver and per name. Unoptimized,
|
|
* the lookbehind runs at every position and reads back through each whitespace
|
|
* run before it, so a long blanked comment cost time in its length squared.
|
|
*
|
|
* go-ethereum's bundled `graphiql.min.js` is one 980 KB line, and the
|
|
* stripper, which doesn't know regex literals, read the `//` that ends
|
|
* `/Trident\//` as a comment and blanked the remaining 962 KB of it. Two pool
|
|
* workers sat on one such check each until the run was killed (`codegraph
|
|
* init` never finished resolving).
|
|
*
|
|
* The cost lives inside one regex execution, where there is nothing to count,
|
|
* so this is timed — with V8's unoptimized mode forced, on any Node version,
|
|
* and a bound far above the fix's cost and far below the quadratic one.
|
|
*/
|
|
import { describe, it, expect, afterEach } from 'vitest';
|
|
import * as fs from 'fs';
|
|
import * as os from 'os';
|
|
import * as path from 'path';
|
|
import * as v8 from 'v8';
|
|
import { CodeGraph } from '../src';
|
|
|
|
describe('JS local-binding check on a long comment (go-ethereum graphiql.min.js)', () => {
|
|
let tmpDir: string | undefined;
|
|
let cg: CodeGraph | undefined;
|
|
|
|
afterEach(() => {
|
|
cg?.close();
|
|
cg = undefined;
|
|
if (tmpDir) fs.rmSync(tmpDir, { recursive: true, force: true, maxRetries: 5 });
|
|
tmpDir = undefined;
|
|
});
|
|
|
|
const callees = (graph: CodeGraph, name: string): string[] => {
|
|
const from = graph.getNodesByName(name).find((n) => n.kind === 'function')!;
|
|
return graph.getOutgoingEdges(from.id).filter((e) => e.kind === 'calls')
|
|
.map((e) => graph.getNode(e.target)!.name);
|
|
};
|
|
|
|
it('stays linear when V8 stops optimizing regexes', async () => {
|
|
// Blanked by the comment stripper into one 60,000-character run of spaces.
|
|
const comment = `/* ${'word '.repeat(12_000)} */`;
|
|
tmpDir = fs.mkdtempSync(path.join(os.tmpdir(), 'cg-js-lookbehind-'));
|
|
fs.writeFileSync(path.join(tmpDir, 'paint.js'), [
|
|
'function paintWidget() {\n return 1;\n}',
|
|
// Calls the file's own paintWidget: the check scans all of host's code and finds no binding.
|
|
`function host() {\n ${comment}\n return paintWidget();\n}`,
|
|
// Calls its parameter, which shadows the file's paintWidget.
|
|
`function shadow(paintWidget) {\n ${comment}\n return paintWidget();\n}`,
|
|
'',
|
|
].join('\n'));
|
|
|
|
v8.setFlagsFromString('--no-regexp-optimization');
|
|
const started = Date.now();
|
|
try {
|
|
cg = CodeGraph.initSync(tmpDir);
|
|
await cg.indexAll();
|
|
} finally {
|
|
v8.setFlagsFromString('--regexp-optimization');
|
|
}
|
|
const elapsed = Date.now() - started;
|
|
|
|
expect(callees(cg, 'host')).toEqual(['paintWidget']);
|
|
expect(callees(cg, 'shadow')).toEqual([]);
|
|
// About a second with the fix; minutes when the lookbehind reads back through the run at every position.
|
|
expect(elapsed).toBeLessThan(20_000);
|
|
}, 300_000);
|
|
});
|