Conservative output slicing fragments safe UTF-16 conversion

perfloop/simdutf · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_tksym8s1mb

Verdict

VERIFIED · settled 2026-07-31 · pull request opened as simdutf/simdutf#1019

What happened: The paired measurements met the required improvement.

Hypothesis

The source loop uses `read_len = min(len, utf8_len / 3)` and calls `convert_utf16_to_utf8` once per slice before retrying with the remaining capacity. For valid ASCII with an exact output buffer, each slice writes exactly `read_len`, so the remaining capacity shrinks by about one third each pass rather than completing in one traversal. The repository benchmark itself supplies this exact-capacity shape by computing `budget = utf8_length_from_utf16(data, size)` before calling the safe API; the safe-conversion tests do the same. The removed delta is therefore repeated backend entries and their independent tails, not any UTF-16 bytes that must be copied twice. On the Haswell path, each backend entry first invokes the AVX2 converter and then invokes the scalar converter for its unprocessed tail (src/haswell/implementation.cpp:678-696), so fragmentation can also multiply tail handling.

I ran a recurrence probe reproducing lines 1974-1999 for ASCII with `utf8_len == len`: it produced 1 vector call at 64 code units, then 5 at 256, 8 at 1,024, 18 at 65,536, and 25 at 1,048,576 before the checked scalar finish. Thus the real cadence is several backend conversions per one public safe conversion for medium exact-capacity inputs, rather than a per-element claim. I also built the library in Release and ran a seven-sample local ASCII microbenchmark with the same exact-capacity setup. `convert_utf16_to_utf8_safe` versus the unbounded converter measured 40.5 versus 13.8 ns at N=64, 97.7 versus 22.4 ns at N=256, and 170.3 versus 61.5 ns at N=1,024; the ratios narrowed to 1.06 at N=65,536 and 1.00 at N=1,048,576. The unbounded comparator does not preserve output-capacity semantics, so these measurements isolate a candidate cost and do not prove that a safe replacement can attain them. They do support restricting the hypothesis to predominantly low-expansion UTF-16 with exact or near-exact output capacity and roughly tens to low-thousands of code units; no broad large-input win is claimed.

A case session should implement a capacity-aware block prototype and benchmark end-to-end `convert_utf16_to_utf8_safe` latency, CPU cycles/code unit, backend-entry count, and scalar-tail bytes across input sizes around the observed crossover, ASCII/1-3/3-4-byte mixes, and capacity ratios from insufficient through exact to worst-case. It must differentially verify emitted prefixes, output counts, OUTPUT_BUFFER_TOO_SMALL behavior, and invalid/split surrogate cases. Improvement is predicted only when this public API is invoked at that exact/near-exact-capacity cadence.

Change to test: Prototype a capacity-aware vector conversion path that reserves bounded output space per block and leaves only one checked scalar tail, instead of repeatedly slicing at one third of remaining capacity. Gate any preflight alternative behind a measured crossover, and preserve partial-output, output-limit, and malformed-surrogate behavior.

Where it lives

perfloop/simdutf · src/implementation.cpp

Evidence

Haswell ASCII UTF-16-to-UTF-8 safe conversion, 256 code units, exact output capacity · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 139.9 42.5 −69.7% (−97.49) −98.96 to −95.78 < 0 PASSED

Checks: 3 of 3 passed. Verification: no defect found.

Timeline