Repository navigation
perf(npa/npm/ruby): class-body walk copies the ancestor chain per nested class #1805
Description
npa and npm for Ruby copy the whole ancestor chain once per class body. Their cost therefore grows with depth × class count, which is quadratic for nested classes. Found reviewing PR #1804 (#1719). npm has done this on main since #1401. Since #1719, npa drives the same class-body walk and pays it too.
Where
src/metrics/npa/ruby.rs (Npa::compute) and src/metrics/npm/ruby.rs each start the shared walk with RubyBodyState::walk(code, ancestors.of_children(node), node, …). Ancestors::of_children materialises the chain from the root to node so the walk can push and pop below it. At nesting depth d that copy costs d, and a file of n nested classes pays it at every level: Σd = O(n²).
Measured
Dev build of 0612e31e (PR #1804). The input is n nested class C lines, one attr_reader :a in the innermost class, then n ends:
python3 -c "import sys;n=N;sys.stdout.write('class C\n'*n+' attr_reader :a\n'+'end\n'*n)" > nN.rb
bca metrics --metrics <m> -p nN.rb -O json -o out.json
| n | npa | npm | loc (control) |
|---|---|---|---|
| 4,000 | 0.06 s | 0.06 s | 0.07 s |
| 8,000 | 0.14 s | 0.14 s | 0.16 s |
| 16,000 | 0.34 s | 0.33 s | 0.40 s |
| 32,000 | 3.52 s | 2.24 s | 1.27 s |
| 64,000 | 10.15 s | 10.26 s | 4.36 s |
Up to 16,000 levels the member metrics track the control. Above that they pull away. These are single wall-clock runs, so the exponent is not established: a scaling probe should settle it (see below). Every run past 128 levels also hits the deliberate FuncSpace serialization limit on output. That cost is paid by all three columns equally, so it does not explain the gap.
Severity is low. No real Ruby nests classes anywhere near this deep, and the output cannot even be serialised past 128 levels. The cost is a large input that is slow to reject rather than a wrong answer.
Fix shape
Hand the walk the chain it is already on instead of a copy. ChildAncestors in big-code-analysis-ast would need a way to descend from a borrowed chain, the way ChildAncestors::descend / ascend already move one chain through nested ifs for npm/ruby-nested-if-defs. A shorter-chain shortcut was considered and rejected. It would be correct for today's gates but wrong for any future gate that reads further up the chain.
Add an npa/ruby-nested-classes probe (depth axis) to big-code-analysis-bench/src/shapes.rs. Record its exponent with and without the fix, as .claude/rules/testing.md asks for scaling probes.
Activity
dekobon commentedon Nov 5, 2026
Pre-implementation review (2026-11-04): the quadratic copy is in
of_children, not in two Ruby call sitesVerified on
main84a90e09, release build; held out of the 2026-11-04 batch (needs a solo branch).Ancestors::children_chain(node/ancestors.rs:446-449) is[chain, slice::from_ref(node)].concat(), a freshVecofdepth+1per body;perfon n=32000npaputs 68 % of samples inmemcpyunderchildren_chain. The Ruby walk itself does not re-descend into nested classes (shape()classifies a nestedclassasLeaf), so the chain copy is the only quadratic term.of_childrenis called once per container by ~25 language modules (npa/*.rs,npm/*.rs,npa.rs,npm.rs,checker/ruby.rs). 32k nested C++structs: npa 1.44 s vs loc 0.20 s; 32k nested Java classes: 0.73 vs 0.14. The fix belongs inof_children's representation, not in the two Ruby sites.Ancestors.chainis one contiguousOption<&[Node]>indexed as a flat slice byfold_down,lookup(depth key intoSiblingCache),FoldCache::fold,deepest_stored,AncestorIter. A borrowed prefix + pushable tail needs either a two-segment view threaded through every indexer (depth semantics must stay identical, or the fold slots and sibling-cache key silently misalign — use thefold_steps/sibling_cache_readscounters to detect) or&mutaccess to the walk's ownVec(acomputesignature change across 23 impls). The two-segment view localises the change toancestors.rsand fixes all ~25 sites at once.npa/ruby-nested-classesonAxis::DepthwithCONDITIONAL_PER_DEPTH_DEPTHS(4k/8k/16k) — onLINEAR_DEPTHSthe fit is ≈1.4, underLINEAR_BOUND, so the probe would pass with the defect present. Record the perturbed exponent per.claude/rules/testing.md. Runmake chain-audit.ChildAncestors/Ancestorsarepubinbig-code-analysis-astbut outsideSTABILITY.md's contract; CHANGELOG entry expected, no STABILITY edit.