Small-set scanning crossed over at 32 to 48 bytes.

We investigated one whole-buffer call that returns the first array index whose byte equals any byte in a small set. Load, comparison, compact-mask extraction, and first-match selection needed to remain inside one loop.

We did not expose the nibble tables as a general byte class

The first candidate used one 16-entry table for each nibble. A byte matched when the selected low-table and high-table bytes had a common set bit.

That representation is not an arbitrary 256-byte class. Each bit describes one rectangle in the 16-by-16 nibble matrix. Eight bits can describe at most eight such rectangles. A 16-byte diagonal class can require 16 rectangles, so the two byte tables cannot encode it exactly.

The representation can encode any set of up to eight bytes by assigning one bit to each member. It can also encode some larger structured sets. That narrower contract did not justify a public class type, especially because baseline x86-64 has SSE2 but no byte-shuffle instruction.

The retained API expresses an exact small set

Algorithms.Runtime.Find_First_Of accepts a byte array and a byte-array set. It returns the first matching Ada index. An empty input or empty set returns (Found => False, Index => 0). Duplicate set members do not change the result.

For sets of one through four bytes, each complete 16-byte block in the static Native path uses a fused vector loop. The loop loads the block once, compares it with pre-splatted set members, combines the compact masks, and selects the first set bit. The exact scalar tail touches only valid input bytes.

Larger sets retain the same exact result through a scalar membership loop. This boundary keeps the public operation useful without pretending that every set size benefits from the same vector mechanism.

We compared complete calls with an ordinary Ada table loop

The set contained four bytes: horizontal tab, line feed, carriage return, and space. The ordinary Ada candidate used a precomputed 256-entry Boolean membership table. Set construction occurred outside each timed batch.

Each comparison included the ordinary Ada loop, scalar reference backend, static native backend, and default runtime route. No-match and last-match inputs both forced a complete scan.

Library build

-O2 -ftree-vectorize, with assertions enabled.

Benchmark build

-O3 -ftree-vectorize.

Schedule

Balanced rounds with equal measurement time for each candidate.

Samples

75 samples after a 250 ms warmup, during three seconds per comparison.

Timer

Estimated timer cost was not subtracted.

Placement

Uncontrolled. The benchmark thread was not pinned and CPU quiescence was not required.

The ordinary loop won below 32 bytes on this machine

Static NEON first had a clear lower median at 32 bytes for no-match input. The last-match case was effectively tied at 32 bytes and first clearly favored static NEON at 48 bytes. Runtime selection first had a clear lower median at 48 bytes in both scenarios.

The scalar reference backend was slower than the ordinary Ada table loop at every measured size. It exists to define and check semantics; this run did not support using it as a performance route.

A complete vector was faster than a nearly complete vector plus a scalar tail

The 127-byte case took 53.88 ns with static NEON and the 128-byte case took 36.00 ns in the no-match scenario. The current loop handles the 15-byte remainder scalarly, which explains the reversal.

This result changed our API decision, but not into a universal SIMD claim. The measurements supported the exact small-set operation for repeated full scans of medium and large buffers. An ordinary table loop remained the better measured choice for the shortest buffers on this host.

Correctness and generated code had separate checks

Differential tests covered empty arrays, empty and duplicate sets, non-one lower bounds, every relevant lane position, randomized inputs, and exact no-match results. Guard-page tests placed valid tails immediately before a protected page for lengths 1 through 160.

The AArch64 code-generation gate found the required native load, comparison, mask extraction, and first-set-bit work. It also rejected per-vector calls to backend primitives from the whole-buffer loop.

Scalar and AArch64 tests executed on this host. AddressSanitizer passed for the scalar configuration. The AVX2 source received a semantic compiler check, but no x86-64 or AVX2 binary ran on this AArch64 machine.

The crossover depends on the processor, compiler, switches, set size, match position, and tail length. This campaign used one four-byte set and retained medians, not its complete raw sample stream. Repeat the campaign before making a deployment decision.

Run the focused benchmark

cd benchmarks
alr build --release
FLYOLOGY_BENCH_OUTPUT=terminal alr run --skip-build class_scan_benchmark

Set FLYOLOGY_SIMD_BENCH_CPU to request thread placement. Set FLYOLOGY_BENCH_QUIESCENCE=1 to require an idle interval before each comparison. Use CSV or JSON output when raw reports must survive the run.