KNN benchmarks

Uniform voting

Existing calls retain uniform votes and serial CPU execution. The updated implementation avoids ordering selected neighbors when a uniform prediction needs only their votes.

Distance weighting

The fitted inverse-distance policy uses the same Euclidean neighbors and explicit query workers. Ordered weighted accumulation preserves the same arithmetic order across worker counts.

Additional workloads

Small queries, larger neighbor sets and selecting every fitted row can behave differently. These complete observations remain part of the comparison.

With k=32, distance-weighted four-worker prediction is 2.98× faster than its updated serial policy. When every fitted row is selected, uniform four-worker prediction is 21.32× faster than the original serial implementation. That includes a 10.14× improvement in the updated serial algorithm; four workers contribute 2.10× relative to that updated serial time. The denominators separate implementation changes from pool scaling.

Tiny queries and pool setup

N=32, Q=1, D=4, k=5. One query supplies one independent lane, even when a context owns four workers. A parallel pool adds scheduling cost here; more requested workers do not create additional query rows.

Cold calls include creating and destroying their pool. Reused calls exclude that setup. These are separately timed modes; their difference is not an isolated measurement of thread startup.

Workspace memory

The separate native probe checks the exact admission boundary on the recorded 64-bit ABI: each prediction call accepts the reported byte budget and rejects one byte less. The table reports charged workspace in KiB (1 KiB = 1,024 bytes), including result storage, lane buffers and admission metadata.

On this ABI, charged prediction bytes are 344 + 8Q + P × (136 + 16N + 8C + (distance ? 24C : 0)), with P=1 for serial and P=min(requested workers,Q) for a context. The fixed and lane terms include control metadata. This formula is specific to the recorded ABI and vector capacities.

Charged workspace is not peak process RSS. It excludes fitted model storage, input/host caches, executor internals, thread stacks, allocator overhead and other process memory. The default 64 MiB (67,108,864 bytes) is a cap, not a fixed allocation. More admitted lanes need their own scratch; requests that exceed the budget fail rather than silently reducing requested concurrency.

Both original and updated models retain the same vector-capacity payload: 8ND + 16N bytes in this harness. That is 288 KiB for Batch and 2,112 KiB for Wide. The fitted-state object grows from 96 to 104 bytes on this ABI, including flag padding; the change adds no new N-element model buffer.

The new serial uniform prediction retains the original numerical-buffer payload: 34,856 bytes for Batch and 66,088 bytes for Wide. The charged totals also include control metadata, so comparing a charged total directly with an old payload figure would mix accounting scopes. Distance weighting adds 24C bytes of scratch per active lane: 120 bytes for these five-class cases.

Workspace memory was probed for the two primary workloads only. The other three workloads have timing evidence, with no additional memory measurement presented here.

Determinism and numerical checks

Both uniform and distance modes independently match their own serial results bitwise. Successful labels, probabilities, neighbor indices and distances were compared bit for bit across admitted 1, 2 and 4 worker contexts in the same binary and floating-point environment. The workspace probe checks prediction labels at each exact admitted budget; probabilities, neighbor indices and neighbor distances are compared with serial at the default budget. This does not promise agreement across different platform math libraries.

The recorded validation includes 107427 native checks and 165 language checks, plus sanitizer and independent numerical tests. A 1,100-digit Decimal reference checked 39 weighted cases and 132 probabilities. Maximum observed errors were 2 ULPs for normal outputs and 0 for the tested subnormal outputs; enforced fixture bounds were 4 and 1 ULP respectively. These are tested observations, not a universal correctly-rounded guarantee.

Distance ties retain fitting-row order, and exact computed class-score ties choose the smallest class ID. Only selected exact-zero-distance neighbors vote in a weighted exact-match case. Cancellation returns no partial successful Tensor, and numerical failures report the lowest failing query row after workers join.

Timing scope and reproduction

These are prediction-only native-call times on macOS arm64 with AppleClang 21, Release -O3, matched ThinLTO and strict -fno-fast-math / -ffp-contract=off. Fitting, input creation, independent verification and process startup are outside the primary timer. Cold modes additionally include context creation and destruction. The linked timing report retains raw samples, source/binary identities, commands and exploratory history; this page uses only the five integrated-* primary groups.

The recorded apple-m1 target is a compiler instruction baseline, not identification of the physical CPU model. Worker counts are admitted concurrency, not a claim of pinned or dedicated cores. These local observations do not establish GPU, cluster, other-platform or universal speedups.

Every query still calculates distance to every fitted row. For fixed k, average total work remains O(QND); parallel execution changes elapsed time, not the exhaustive distance count. Workspace grows with active lanes: O(P(N + C) + Q) for prediction. Neither GPU nor cluster KNN is implemented, and these native library kernels do not extend the bounded aner build Tensor/model subset.

See the KNN contract, implementation and validation notes, and complete local execution example. The benchmark driver, native timing harness, and high-precision verification tool are available for independent inspection.

The workspace probe source reproduces the two-workload admission checks. Build it against the same Release Aner headers and libraries with C++20 and the recorded strict floating-point flags; its formula requires the documented ABI and admission for four CPU workers. It verifies prediction budget-minus-one rejection and exact-budget acceptance. All four readouts are also compared with serial at the default budget. It does not collect prediction timings or process RSS.