perf(metrics): fast hasher for loc line sets; reserve the nesting map

[dekobon]

Summary

Two follow-ups the #1062 hasher work identified but deliberately left out of
scope. Both are the same shape as that change: self-produced integer keys
paying for hash-flooding resistance they cannot use, plus an allocation that
does not need to happen.

1. loc's line-number sets still use SipHash

src/metrics/loc.rs:169,241,249 hold HashSet<usize> keyed by line
numbers, constructed with HashSet::default() at :258-259 and hit on
every line inserted, unioned or extended. The argument from NodeIdHasher
(src/spaces.rs) applies verbatim — self-produced integers, never
attacker-chosen — and FxHash is a particularly good fit here: consecutive
line numbers times an odd multiplier is a bijection on the low bits, so
distribution is ideal.

Loc is default-selected and an MI input, so this is a hotter path than the
cognitive map that motivated the hasher.

2. NestingMap has no capacity reserve

src/spaces/compute.rs builds NestingMap::default() fresh per file with no
with_capacity_and_hasher. A 50 000-node file rehashes roughly 14 times
mid-walk. Either reserve from a node-count estimate, or hoist one map across
files and clear() it — clear keeps the allocation, which is the point.

This was flagged as plausibly worth more than the hash-function swap itself,
and it is cheaper to write.

Measure, do not assume

The hasher change taught this the hard way: the first numbers quoted for it
were unsupportable, and the corpus was misdescribed. Anything done here
should come with an interleaved before/after and a control metric, and
ideally wait for the harness in #1068 so the numbers are reproducible rather
than living in a commit message.

---

Resolution

Status: Fixed (pending merge)
Commit: 9b33344 on branch fix/issue-1069

Both sub-parts landed, both measured with an interleaved paired
protocol and controls (see the fix-summary comment for the full table):

• loc line sets — Ploc/Cloc now key on IntKeyHasher
  (NodeIdHasher moved to src/int_hash.rs and renamed, since it is no
  longer node-id specific). corpus/walk/loc -7.1% (19/20 rounds,
  sign-test p < 0.0001), shape/walk/loc/nested-while -8.7% (19/20,
  p < 0.0001).
• nesting map reserve — sized from Node::descendant_count() when
  Cognitive is selected and the grammar's impl actually seeds slots
  (new Cognitive::SEEDS_NESTING, false for the Preproc /
  Ccomment no-ops so their map stays unallocated).
  shape/walk/cognitive/nested-while -12.2% (17/20, p = 0.0026).
  Not resolvable on the corpus slice (median file ~5 KiB): two runs
  read -4.4% (p = 0.057) and +0.2% (p = 1.0). Reported as unresolved,
  not as a number.

Controls (corpus/walk/tokens, shape/walk/tokens/nested-paren,
shape/walk/nom/nested-while) sat at +0.7% to +6.6% — cross-build code
layout, which bounds the precision at roughly +/-7 points and is why
the direction and the round-by-round consistency, not the magnitude,
are the claim.

The "Measure, do not assume" requirement also produced a doc change:
the sequential --save-baseline / --baseline recipe in
docs/development/benchmarking.md reported 23% and 19% swings on
benchmarks the change cannot reach, so that doc now carries the
interleaved protocol used here.

Behaviour is bit-identical — no metric value or snapshot moved.

[dekobon]

Fix Summary

Both sub-parts landed. Both are measured, interleaved, with controls.

Root cause: two collections on the metric walk paying for work they
cannot use.

1. Ploc::lines and Cloc's two line-number sets in
   src/metrics/loc.rs were plain HashSet<usize>, so every insert and
   every contains ran a full SipHash-1-3 keyed round on a key this
   crate produced itself. Loc is default-selected and an MI input, and
   the catch-all arm of every per-language Loc::compute probes the set
   once per AST node.
2. NestingMap in src/spaces/compute.rs was built with
   NestingMap::default() and grown a doubling at a time, even though
   every real Cognitive::compute ends by writing its own node's slot —
   so the final size is one entry per visited node and is known in O(1)
   before the walk starts.

Changes:

• src/int_hash.rs (new): IntKeyHasher, moved out of src/spaces.rs
  and renamed from NodeIdHasher — it is no longer node-id-specific.
  Adds IntKeyHashMap / IntKeyHashSet aliases. Algorithm unchanged
  (FxHash as of rustc-hash 2.x, including the finish rotate).
• src/metrics/loc.rs: the three line-number sets become
  LineSet = IntKeyHashSet<usize>.
• src/spaces.rs: NestingMap is now IntKeyHashMap<usize, Nesting>;
  the hasher definition and its two tests move to the new module.
• src/spaces/compute.rs: metrics_inner reserves the nesting map from
  Node::descendant_count() when Cognitive is selected and the
  grammar's impl actually seeds slots.
• src/metrics/cognitive.rs, src/macros/mod.rs: new
  Cognitive::SEEDS_NESTING associated const, false for the two
  macro-generated no-op impls (Preproc, Ccomment). Without it the
  reserve would allocate a map those grammars never fill, undoing the
  "no map, no allocation" property propagate_nesting_to_children
  documents.
• src/node.rs: Node::descendant_count() (an O(1) field read on the
  tree_sitter subtree).
• docs/development/benchmarking.md: an interleaved-A/B section, see
  below.
• .bca-baseline.toml: Node<'a> nom 31 -> 32 for the new accessor.

No behaviour change: hashing and capacity are not observable. No
snapshot moved and no metric value changed.

Measurement

Host: 16 cores, sustained background load (load average ~7), so the
sequential --save-baseline / --baseline recipe in the benchmarking
doc is unusable here — one such pair reported corpus/walk/tokens 23%
faster and corpus/walk/halstead 19% slower between two builds that
differ only in a hash function neither benchmark reaches. That pair is
not the evidence below and should not be quoted.

Protocol instead: both bench binaries built once and kept, then
alternated round by round (order flipped each round) pinned to one core
with taskset, criterion at --sample-size 30 --warm-up-time 1 --measurement-time 3. One after/before ratio per round; headline is the
median ratio and a two-sided sign test over the rounds, which survives
the single-round 5x outliers a preempted core produces. 20 rounds, run
against the exact committed tree.

Input (printed by the harness before measuring):

corpus slice: 177 files, 903 KiB, from 3 root(s)
  root  tests/repositories/serde
  root  tests/repositories/pdf.js
  root  tests/repositories/DeepSpeech

benchmark	role	median after/before	rounds faster	sign-test p
corpus/walk/loc	effect (hasher)	0.929 (−7.1%)	19/20	0.0000
shape/walk/loc/nested-while	effect (hasher)	0.913 (−8.7%)	19/20	0.0000
shape/walk/cognitive/nested-while	effect (reserve)	0.878 (−12.2%)	17/20	0.0026
corpus/walk/tokens	control	1.007 (+0.7%)	6/20	0.1153
shape/walk/tokens/nested-paren	control	1.022 (+2.2%)	3/20	0.0026
shape/walk/nom/nested-while	control, same shape as the cognitive probe	1.066 (+6.6%)	4/20	0.0118

Reading it honestly:

• The controls are not at zero. Two of them are consistently slower
  in the post-change binary (+2.2% and +6.6%) even though neither
  selects Loc or Cognitive and neither can reach a changed line.
  That is cross-build code layout, and it is the precision floor: treat
  every figure above as ±7 points on magnitude. What the controls do
  establish is direction — all three effects move the other way and
  further.
• corpus/walk/loc and shape/walk/loc/nested-while replicate an
  earlier 14-round run (−6.9%, 13/14, p = 0.0018) taken on a different
  build of the same change.
• shape/walk/cognitive/nested-while replicates a separate 20-round
  run (−12.0%, 18/20, p = 0.0004).

What could not be measured. The nesting-map reserve does not resolve
on the corpus slice: corpus/walk/cognitive read −4.4% (11/14 rounds,
p = 0.057) in one run and +0.2% (12/24, p = 1.0) in another. That is the
expected shape of the effect rather than a contradiction — the slice's
median file is about 5 KiB, so the map only doubles its way up to a
couple of thousand entries and the rehash saving is below this host's
noise. It shows up on the depth-1000 shape, which is what the deep-file
case looks like. The corpus number is therefore reported as
unresolved, not as zero and not as −4%.

shape/walk/cognitive/nested-if (the quadratic is_else_if probe,
51 ms) moved −1.4% at p = 0.82 — no effect, as expected: the ancestor
walk dominates it, not the map.

Languages affected: n/a — the change is in shared walk machinery and
is language-neutral. SEEDS_NESTING distinguishes only the two
macro-generated no-op grammars (Preproc, Ccomment).

Tests:

• int_hash::tests::int_key_hasher_integer_writes_agree and
  ..._finish_rotates_entropy_down — moved with the hasher, narrowed so
  each width is only compared for values it can represent.
• int_hash::tests::int_key_hasher_spreads_consecutive_line_numbers
  (new) — the property that justifies reusing a node-id hasher for line
  numbers: 1 000 consecutive keys reach at least 900 of 2 048 buckets
  with at most 3 per bucket, where a random hash reaches ~813 with 4.
• metrics::cognitive::tests::seeds_nesting_matches_what_compute_writes
  (new) — drives compute for four real impls and both no-ops and
  asserts SEEDS_NESTING equals what each observably wrote. Verified by
  reverting: flipping the macro's const to true fails it with
  a.h: SEEDS_NESTING disagrees with what compute wrote.
• node::tests::descendant_count_matches_the_walked_node_population
  (new) — pins that descendant_count counts the same nodes the walk
  visits, including anonymous tokens, so a future narrowing to named
  nodes cannot silently halve the reserve.
• make pre-commit green; make bench-scaling re-run (traversal
  change) with every probe inside its declared bound.

Documentation

docs/development/benchmarking.md gains a
"When the host is not idle" section
recording the interleaved paired protocol above, because the sequential
recipe it previously documented is what produced the discarded
23%/19% pair.

Commit: 9b33344 on branch fix/issue-1069