moonbitlang / core / 5859

91%

push

github

perf(base64): vectorize encode and decode with @v128

Adds SIMD encode and decode paths for the linear-memory backends, gated
`#cfg(any(target="native", target="wasm"))` like the scanners in builtin.
The scalar implementations stay as `encode_scalar` / `decode_scalar` and
remain the implementation on js and wasm-gc.

Encode follows Muła's SSE algorithm: one `i8x16_shuffle` spreads twelve
source bytes over four 32-bit lanes, uniform shifts slice each group into
four sextets, and an `i8x16_swizzle` over a 16-entry offset table maps
sextets to characters. SIMD128 has no `mulhi_epu16`, so the bit-slicing
uses shifts and masks rather than the multiply trick.

Decode classifies characters with the perfect hash `(c >> 4) - (c == '/')`
described in mcyoung.xyz/2023/11/27/simd-base64, which needs one shift, one
compare and one swizzle. The fast path only accepts canonical input, and
hands the final group plus anything unusual to `decode_scalar`, so the
padding and trailing-bit rules keep a single definition.

A MoonBit `String` is UTF-16, so encode widens its sixteen output
characters to thirty-two bytes, and decode reads thirty-two bytes per
sixteen characters and narrows them with `i8x16_narrow_i16x8_u`. That
narrowing doubles as a range check: code units above 0xFF saturate to
values outside the alphabet and are rejected by the same mask that catches
ordinary invalid characters.

Native, release, mean of three rounds:

    encode     n=64      204 ns  ->   34 ns    6.0x
    encode   n=1024     2.72 us  ->  193 ns   14.1x
    encode  n=65536      145 us  -> 16.4 us    8.9x
    decode     n=64      174 ns  ->   66 ns    2.6x
    decode   n=1024     2.32 us  ->  241 ns    9.6x
    decode  n=65536      257 us  -> 12.0 us   21.5x

Differential whitebox tests pin both vector paths against the scalar ones
over every length below 200, five large sizes, non-zero view offsets, and
every single-character corruption of a canonical encoding.

117 of 119 new or added lines in 4 files covered. (98.32%)

16079 of 17788 relevant lines covered (90.39%)

128983.26 hits per line