A single minified JavaScript file stopped CGraph from finishing a build. Indexing element-hq/element-web ran for 2 hours 9 minutes before it was killed, and the culprit was one 2.9 MB file, docs/lib/mermaid.min.js, with lines up to 278,302 characters long. The fix took that file to 17-28 seconds with an identical graph. It was the fourth quadratic loop found in CGraph's extractors in two weeks, and all four share a shape worth recognizing in your own code: a lookup that is cheap per call and runs once per thing in the file.
How it was found
Nobody went looking. The hang surfaced in the ContextBench run, which indexes the repositories behind 500 benchmark tasks, from 59 projects, each at its base commit. 499 of the 500 builds finished inside the first 51 minutes. The last one ran 2 h 9 min and was killed, with ps showing 2 h 1 min of CPU on a single thread. A per-file scan isolated the file, and a gdb sample of the stuck process gave the stack:
ts_node_parent <- branch_path <- exclusive_branches <- local_values
<- collect_url_template <- analyze_client_call <- http_call_handler
That is the code that finds HTTP calls in JavaScript, so fetch(url) can become a consumer of an endpoint in cross-service impact analysis. To know what URL a call hits, it has to know what value the variable url holds at that point, which means looking at the writes to it.
Three costs that multiply
The fix, #204, names three causes, and the problem is that they compound:
- A scope walk per read.
local_valueswalked the variable's whole scope for every read of it. - A block rescan per lookup.
local_bindingrescanned the enclosing block's statements on every lookup. - O(i) child access. Both walked children with tree-sitter's
ts_node_named_child(node, i), which costs O(i), so a loop over a node's children is itself quadratic.
In ordinary source, a function's scope is a few dozen lines and these costs are invisible. In a minified bundle, the "scope" is most of the 2.9 MB file and the reads number in the thousands. The PR names the three costs; together they made a fetch-heavy minified bundle the worst case for every one of them.
The fix indexes once and looks up after. A per-parse ExtractionMemo records each scope's writes by the name each write can affect, and each block's first declarator of each name. Child walks use a tree cursor, which is linear. The per-write logic did not change at all, which is why the graph did not either.
| Before | After | |
|---|---|---|
mermaid.min.js alone | killed after 60 s, 5 min and 2 h | 17-28 s |
| Synthetic, N = 500 | 1.74 s | 0.26 s |
| Synthetic, N = 1500 | 14.2 s | 0.23 s |
| Scale test, N = 3000 | 62.9 s, fails | 0.15 s, passes |
Synthetic N means N let locals, N unrelated writes and N fetch(local) calls in one function. Proving the output unchanged needed a trick, because the old code never finished the real file: the graph was compared across the steps of the fix instead. The memo alone took 51.5 seconds, and it and the final code produced identical graphs, 8,318 nodes and 180,429 links.
The same bug, three more times
#204 was the last of four. The three before it landed on one day, October 2. The first came out of a review of the env-contract work, and each of the next two was found by a gdb sample taken while fixing the one before:
| PR | Where | Cause | Synthetic file, before → after (median) |
|---|---|---|---|
| #170 | env-var reads | every Enum.MEMBER or env.X walked every enclosing function body for a hoisted var | 266,277 → 19,967 ms |
| #174 | adding a symbol | make_id (two Unicode normalizations) ran inside a find_if over every node already in the file, and id uniqueness was checked by a scan too; the fix indexes node ids | 82,963 → 295 ms |
| #177 | env and DynamoDB facts | "one fact per symbol and name" checked by a linear scan of every relation so far | 9,101 → 1,545 ms (4x file) |
| #204 | HTTP client calls | scope walk per read, block rescan per lookup, O(i) child access | killed at 2 h → 17-28 s |
The chain is the interesting part. #170 fixed the env walk and left 20 seconds on its synthetic file. Its PR said where they were, in a stack sample: add_symbol_node, a different file and pattern, listed as a non-goal. #174 fixed that, and its PR noted the env file was still superlinear at 731 / 2,829 / 8,590 ms for 1x / 2x / 4x sizes, in a third place. #177 fixed that one, and the scaling per doubling went from 3.7x and 3.3x, which is quadratic, to 2.16x and 2.12x. The first two fixes each named the next bottleneck in their own PR before they merged.
What the probe repositories said
Here is the result that would have hidden all of this. On the real service repositories CGraph is developed against, the fixes were modest at best: #174 made extraction 12-30% faster, #170 made "no measurable change", and #177's one apparent gap disappeared when that repository was re-run ten more times. Extraction runs one worker per core, and none of those repositories has a file large enough for a quadratic walk to show.
So a quadratic loop in an extractor is not a performance problem until it meets the one file that makes it one, and then it is not slow, it is a hang. You do not find it with a benchmark of typical code. You find it with a large public corpus, or with a synthetic file built to be the worst case.
Guards, not stopwatches
Each fix landed with a test, and only one of them times anything. The others count work:
- #174's test builds a Python class with 400 fields and 400 methods and fails if
make_idruns more than 16 times per node. - #177's tests build 300 functions with 900 env reads, and 200 functions with DynamoDB writes, and fail if the fact check reads more relations than the file has. Forced back onto the old path, they fail loudly:
cached reads 269700 of 600 relations. - #204's test builds 3,000 locals, writes and calls in one function and fails over 10 seconds, a bound loose enough to survive a slow CI machine and tight enough to catch a 62.9-second regression.
#174's PR says why it added no wall-clock bound: it would be flaky. Counting operations is deterministic, which is the same reason the graph itself is.
What is still open
The remaining 17-28 seconds on mermaid.min.js sit in ordinary pipeline stages: community layout, exports and call resolution. CGraph has no minified-file skip, only an 8 MB per-file cap, so a 2.9 MB bundle is indexed in full. Whether minified bundles should be indexed at all is, in #204's words, "a separate policy question", and a September change that met a one-line 649 kB file rejected a general minified-file heuristic in favor of skipping the directory the test runner wrote it to. The ContextBench numbers are also still pinned to the build before #204; the 500-instance rerun has not been done.
Measure your own
Every build writes stats.json, and phase_ms.extract_ms is the extraction wall time. It covers the whole parallel extraction, so to time one suspicious file, put it alone in a directory and point the build there:
mkdir /tmp/one && cp path/to/suspect.min.js /tmp/one/
cgraph --root /tmp/one --out /tmp/one-out
jq '.phase_ms' /tmp/one-out/stats.json
If a file takes seconds alone, double it and time again. A ratio near 2x is linear. A ratio near 4x is the bug in this post, and the CGraph issue tracker wants the file.