avro: the nominal field-resolution rung is quadratic — 208us per drilled hop on a 66-field snake_cased record #103

The nominal rung added in #98 (AvroWalk.totalNominalIndex / nominalIndex) resolves a field's schema name in time quadratic in the record's field count — on exactly the population it was built to serve.

Mechanism

totalNominalIndex calls nominalIndex once per case field (AvroWalk.scala:531):

case n :: t =>
  val idx = nominalIndex(record, n)

and nominalIndex (AvroWalk.scala:541) tries the O(1) hash lookup first, then falls back to a full linear scan with a char-wise comparator:

val exact = record.getField(scalaName)
if exact != null then exact.pos
else
  val fields = record.getFields
  @tailrec def loop(i: Int, found: Int): Int =
    if i >= fields.size then found
    else if sameFieldName(fields.get(i).name, scalaName) then
      if found >= 0 then -1 else loop(i + 1, i)
    else loop(i + 1, found)
  loop(0, -1)

There is no early exit: the scan runs to the end even after a match, deliberately, to detect ambiguity. So:

• Exact-name codecs (identity AvroConfig): arity × O(1) — fine, and this is what the existing 2-field benchmark measures.
• Any name transform (withSnakeCaseFieldNames, vulcan rename maps, custom transforms): every lookup misses the hash and scans. Cost is arity × fields.size × nameLength. On a 66-field record that is ~66 × 66 × ~15 ≈ 65,000 char comparisons per drilled hop.

The transformed case is precisely the population the nominal rung exists for — the identity case was already correct under positional resolution.

Measured

208,730 ns per drilled hop on a 66-field snake-cased record, against the ~264 ns the #98 PR body quotes for its 2-field construction benchmark. (Box is noisy — project policy is that ns/op here is ±15–50% — but three orders of magnitude is well outside that, and the structural argument above is independent of the measurement.)

Two multipliers on top:

1. The map is recomputed per drilled hop. A chain of k hops into the same record rebuilds the same full name→index map k times.
2. Resolution is once per optic only when the optic is a held val. A def-shaped or parameterised-given optic re-resolves per operation — measured 100,000 resolutions across 100,000 operations, ~208 ns/op on a 12-field record.

Fix

Pre-index once instead of scanning per name: build the normalised-name → position map for the record schema in one O(n) pass, then answer each case field with a lookup. Cache it keyed on schema identity so repeated hops into the same record are free.

Ambiguity detection is preserved — a normalised key colliding during construction of the index is the same signal the current found >= 0 branch produces, detected once rather than per query.

The all-or-nothing totality/injectivity discipline must not change: this is a constant-factor fix, and ResolutionFalsePositiveSpec / AvroNominalResolutionSpec / ResolutionResidualSpec must stay green with identical verdicts.

Found while investigating whether compile-time schema metadata could guard the #98 residual (it cannot — see #100).