Fixing ill-formed UTF-16 strings with SIMD instructions
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Fixing ill-formed UTF-16 strings with SIMD instructions".
Jane: Here's the gist of the paper. Fixing ill-formed UTF-16 strings with SIMD instructions is a proposal to use Single Instruction, Multiple Data (SIMD) instructions to handle multiple code units in parallel, enabling faster and more efficient execution The paper introduces a novel SIMD algorithm for in-place and copy-based UTF-16 correction, implemented with optimizations for ARM NEON and x64 SSE instructions to achieve up to eight-fold speedups over scalar methods.
Tom: Problem Statement Ill-formed UTF-16 strings arise when surrogate pairs are mismatched, such as a high surrogate not followed by a low surrogate or a low surrogate appearing without a preceding high surrogate.
Jane: Such errors can result from data corruption, improper encoding conversions, or malicious inputs, potentially leading to security vulnerabilities or application crashes.
Tom: Conventional scalar algorithms for fixing ill-formed UTF-16 strings process code units sequentially, which is computationally expensive for large strings.
Paper summary: Tom: So, looking at the whole thing, "Fixing ill-formed UTF-sixteen strings with SIMD instructions" by Robert Clausecker and Daniel Lemire is about using parallel processing to fix broken UTF-sixteen strings efficiently <ref:2601.06349#pg1,Fixing ill-formed UTF-16 strings with SIMD instructions>.
Jane: They show that this approach gets them up to eight times faster on ARM NEON and xsixty-four SSE compared to the old scalar methods, with throughputs reaching eighteen point nine gigabytes per second on the Apple M4 processor.
Lu: It’s fundamentally about taking a sequential problem of fixing mismatched surrogates and transforming it into a highly parallel operation that scales well across different hardware.
Meng: For those of us shipping models to production, the implication is that if you are dealing with massive text streams in your AI applications, this could mean a much lower latency for preprocessing steps.
Jane: And they’ve demonstrated results on both Apple M4 and Intel Xeon systems, showing effectiveness across different architectures.
Tom: The paper also details how they handle boundary conditions by using lookback mechanisms to check for pairs that span across data blocks.
Lalam: They showed that while the performance is great, the authors also have to consider the implementation complexity involving mask registers on xsixty-four systems.
Lu: And another point they make is that this method relies on high operational intensity, requiring at least five arithmetic-logic SIMD instructions per iteration compared to just two loads and one store operation.
Jane: So, the paper proves that for this specific task, leveraging SIMD can lead to significant speedups when you are looking for maximum performance.
Conclusion: Tom: So we’re wrapping up this look at fixing ill-formed UTF-sixteen strings with SIMD instructions by Clausecker and Lemire, and what it actually means for us in the real world.
Jane: It boils down to taking a really messy problem—these broken character pairs in text—and using parallel processing, or SIMD, to fix them way faster than the old sequential ways.
Lu: The core idea is using these special instructions on the computer, like AVX-five hundred twelve for xsixty-four or NEON for ARM, to check and replace those bad characters simultaneously across big chunks of data.
Meng: For us shipping models, that means if we’re dealing with massive text inputs every second, this could mean our preprocessing steps don't become a bottleneck.
Tom: Exactly. The authors show it gets up to eight times faster than the standard methods on architectures like ARM NEON and xsixty-four SSE. That's a big jump in raw speed for string manipulation.
Jane: But they also talk about how they handle those tricky cases where the bad characters are split across different data blocks, which needs some clever lookback logic to get right.
Lalam: I see that part too. They use this lookback mechanism to make sure they catch every pair, even if it spans a boundary between what the computer loads in one go and what it loads in the next.
Lu: And they point out that their performance comes from being super busy with calculations—at least five arithmetic-logic SIMD instructions for every iteration compared to just a couple of simple data loads.
Tom: That high operational intensity is what drives the speedup; you’re not wasting cycles waiting for data, you’re doing work constantly.
Jane: So when we look at the conclusion, they confirm these results on Apple M4 and Intel Xeon systems, showing it scales well across different hardware.
Meng: It's good to see it works on both big desktop systems and mobile chips; that suggests a pretty robust solution for production environments.
Lalam: The paper concludes that this SIMD approach offers significant performance gains over traditional scalar methods while keeping the error rate at zero percent for their test cases.
Tom: So, in simple terms, they’ve taken a tedious task of checking and fixing broken text and made it much quicker by using specialized parallel hardware instructions.
Jane: It really changes how we think about the efficiency of processing huge amounts of text data on modern chips.
Lu: If this technique can be generalized beyond just UTF-sixteen strings, we could see similar gains in other areas of data handling that involve checking patterns across large sequences.
Zuse Institute Berlin · Université du Québec (TELUQ)
cs.OH, cs.PF
Submitted: 2026-01-09
Updated: 2026-08-24
Journal ref: Software: Practice and Experience 56(12), 2026
DOI: 10.1002/spe.70105
Code: https://github.com/simdutf/simdutf
Project page: https://lemire.github.io/browserwellformed
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: Fixing ill-formed UTF-16 strings with SIMD instructions is a proposal to use Single Instruction, Multiple Data (SIMD) instructions to handle multiple code units in parallel…
Key concepts
- Ill-formed UTF-16 strings
- These are corrupted text sequences where Unicode surrogate pairs are improperly paired, such as a high surrogate not being followed by a low one. This error can happen due to data corruption or bad encoding and causes application crashes or security risks.
- SIMD (Single Instruction, Multiple Data)
- SIMD allows a single CPU instruction to operate on multiple pieces of data simultaneously. By using SIMD instructions, the algorithm can examine many 16-bit code units in parallel rather than processing them one by one, drastically increasing speed.
- Surrogate Pairs
- In UTF-16 encoding, characters outside the Basic Multilingual Plane are represented by two 16-bit units: a high surrogate and a low surrogate. Correctly pairing these two units is essential for valid Unicode representation.
Terminology
Summary
Fixing ill-formed UTF-16 strings with SIMD instructions is a proposal to use Single Instruction, Multiple Data (SIMD) instructions to handle multiple code units in parallel, enabling faster and more efficient execution The paper introduces a novel SIMD algorithm for in-place and copy-based UTF-16 correction, implemented with optimizations for ARM NEON and x64 SSE instructions to achieve up to eight-fold speedups over scalar methods. p. 1 We propose a SIMD-based algorithm to accelerate UTF-16 correction, leveraging ARM NEON and
x64 Streaming SIMD Extensions (SSE) instructions to process 16-bit code units in blocks, achieving significant performance gains. Our contributions include a novel SIMD algorithm for in-place and copy-based UTF-16 correction, implementations optimized for ARM NEON and x64 SSE, and a comprehensive experimental evaluation demonstrating up to
eight-fold speedups over scalar methods.Where the paper says it
Problem Statement
Ill-formed UTF-16 strings arise when surrogate pairs are mismatched, such as a high surrogate not followed by a low surrogate or a low surrogate appearing without a preceding high surrogate. Such errors can result from data corruption, improper encoding conversions, or malicious inputs, potentially leading to security vulnerabilities or application crashes. p. 1 Ill-formed UTF-16 strings occur when surrogate pairs are mismatched, such as a high surrogate not followed
by a low surrogate or a low surrogate appearing without a preceding high surrogate. Such errors can result from
data corruption, improper encoding conversions, or malicious inputs, potentially leading to security vulnerabilities or
application crashes [1, 2]. Conventional scalar algorithms for fixing ill-formed UTF-16 strings process code units sequentially, as shown in
Fig. While straightforward, these methods are computationally expensive for large strings, limiting their suitability for high-throughput applications like web browsers or databases.Where the paper says it
Where the paper says it
Algorithm Design
The proposed SIMD algorithm processes UTF-16 strings in blocks of at least 8 code units (16 bytes) using SIMD instructions, correcting mismatched surrogates by replacing them with the Unicode replacement character U+FFFD. The algorithm works in three steps: first, it loads two vectors of 16-bit code units with an offset of one word from the input, checking for high and low surrogates in separate vectors. p. 3 3) works in three steps: first, we load two vectors of 16-bit code units with an offset of one word
from the input. The earlier vector (the lookback) is checked for the presence of high surrogates, the later vector (the
block) for the presence of low surrogates, yielding two vectors of booleans lb_is_high and block_is_low. The earlier vector (the lookback) is checked for the presence of high surrogates, the later vector (the
block) for the presence of low surrogates, yielding two vectors of booleans lb_is_high and block_is_low. In the second
step, we compute the element-wise exclusive-or of these two vectors of booleans. If the result is all zeros,
the current block is correctly sequenced and we copy it to the output. 2
Otherwise we proceed to the third step, which involves detecting which specific 16-bit code units are illegally
sequenced and replacing them with the Unicode replacement character U+FFFD prior to writing the block vector to
the output buffer.Where the paper says it
Where the paper says it
Where the paper says it
SIMD Implementation Details
The SIMD implementation for x64 utilizes AVX-512 instructions, leveraging 512-bit ZMM registers and mask registers for efficient conditional operations. The architecture-specific adjustments include using mask registers instead of vectors of FFFF or 0000 for boolean results, and employing mask-driven blend instructions and masked stores instead of bitwise operations. p. 8 The
AVX-512 implementation of the utf16fix_block function leverages 512-bit ZMM registers to process thirty-two
UTF-16 code units (64 bytes) in parallel, utilizing AVX-512’s mask registers for efficient conditional operations. Other
than being cast in architecture-specific intrinsics, these are the differences in utf16fix_block procedure compared
to our generic algorithm:
• instead of using vectors of FFFF or 0000 for boolean results, we use mask registers,
• the various blend operations are realised by mask-driven blend instructions and masked stores instead of bitoperations,
• instead of fixing up out[−1] by extracting lb from lb_illseq into a scalar, we perform a 64 byte store into out − 1
masked with just the first bit of lb_illseq, guaranteeing that it stores either one code unit or none and in particular
does not overlap the subsequent store to out. If the result is all zeros,
the current block is correctly sequenced and we copy it to the output. 2
Otherwise we proceed to the third step, which involves detecting which specific 16-bit code units are illegally
sequenced and replacing them with the Unicode replacement character U+FFFD prior to writing the block vector to
the output buffer.Where the paper says it
Where the paper says it
Performance Evaluation
Experimental results on Apple M4 and Intel Xeon systems confirm the scalability and effectiveness of the approach, with throughputs reaching 18.9 GB/s on Apple M4 processor and 7. p. 2 0
F I G U R E 2 Speed of the String. toWellFormed JavaScript function using a 1024-character string on different
browsers with an Apple M4 processor. 0
F I G U R E 2 Speed of the String. toWellFormed JavaScript function using a 1024-character string on different
browsers with an Apple M4 processor. As a bonus, for in-place operation, writing to the buffer can be avoided
entirely for valid UTF-16. 2 | AVX-512 (x64) implementation
Intel and AMD 64-bit processors (x86-64), which dominate the market for Windows PCs and servers, support a range
of SIMD instruction set extensions, falling into the four families of MMX (64-bit vectors, of historical interest only),
SSE (128-bit vectors), AVX (256-bit vectors), and AVX-512 (512-bit vectors). We propose a SIMD-based algorithm to accelerate UTF-16 correction, leveraging ARM NEON and
x64 Streaming SIMD Extensions (SSE) instructions to process 16-bit code units in blocks, achieving significant performance gains. Our contributions include a novel SIMD algorithm for in-place and copy-based UTF-16 correction, implementations optimized for ARM NEON and x64 SSE, and a comprehensive experimental evaluation demonstrating up to
eight-fold speedups over scalar methods. For example, the UTF-16 decoder of CPython 3. 3 failed to update an internal bound
after invoking its error handler—which is triggered by ill-formed sequences such as an unpaired surrogate—so that
ill-formed input caused the decoder to read past the end of its buffer, disclosing process memory or crashing the
application [2].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
By leveraging SIMD instructions, the proposed algorithm achieves significant performance improvements over traditional scalar methods, with up to eightfold speedups on ARM NEON and x64 SSE architectures. Experimental results on Apple M4 and Intel Xeon systems confirm the scalability and effectiveness of our approach, with throughputs reaching 18.9 GB/s on Apple M4 processor and 7.5 GB/s on an Intel Ice Lake processor, alongside reduced instruction counts. p. 6 As a bonus, for in-place operation, writing to the buffer can be avoided
entirely for valid UTF-16. 2 | AVX-512 (x64) implementation
Intel and AMD 64-bit processors (x86-64), which dominate the market for Windows PCs and servers, support a range
of SIMD instruction set extensions, falling into the four families of MMX (64-bit vectors, of historical interest only),
SSE (128-bit vectors), AVX (256-bit vectors), and AVX-512 (512-bit vectors). 2 Robert Clausecker and Daniel Lemire
size_t replace_invalid_surrogates(char16_t *dst, const char16_t *src, size_t src_size) {
size_t src_idx = 0, dst_idx = 0;
const char16_t replacement = 0xFFFD; /* U+FFFD Replacement Character */
while (src_idx < src_size) {
char16_t c = src[src_idx];
/* not a surrogate */
if (c < 0xD800 || c > 0xDFFF) {
dst[dst_idx++] = c;
src_idx++;
} else if (c >= 0xD800 && c <= 0xDBFF) { /* high surrogate */
/* check if there is a next unit and it is a valid low surrogate */
if (src_idx + 1 < src_size && src[src_idx + 1] >= 0xDC00 && src[src_idx + 1] <= 0xDFFF) {
/* Valid surrogate pair, copy both units */
dst[dst_idx++] = c;
dst[dst_idx++] = src[src_idx + 1];
src_idx += 2;
} else {
/* invalid: lone high surrogate or no low surrogate */
dst[dst_idx++] = replacement;
src_idx++;
}
} else { /* low surrogate without high surrogate */
dst[dst_idx++] = replacement;
src_idx++;
}
}
return dst_idx;
}
F I G U R E 1 Scalar C function to replace invalid UTF-16 surrogates with the replacement character
U+DBFF) followed by a low surrogate (U+DC00–U+DFFF). The code point is computed from a surrogate pair (h, l ) as:
Code point = ( (h − 0xD800) ≪ 10) + (l − 0xDC00) + 0x10000
where h is the high surrogate and l is the low surrogate.Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The paper proposes using Single Instruction, Multiple Data (SIMD) instructions to handle multiple code units in parallel, enabling faster and more efficient execution.
How the training signal is built
The algorithm checks for valid surrogate pairs by examining high and low surrogates across block boundaries using a lookback mechanism to handle pairs spanning blocks. The lookback vector with its leading U+0000 is shown in the second column of Figure 4. p. 4 There is also a correctly sequenced surrogate pair D83D DE0A at positions 29–30 encoding U+1F60A smiling face with
smiling eyes marked in green. The lookback vector with its leading U+0000 is shown in the second column.Where the paper says it
Where the gains come from
The operational intensity of our main routine is high, as it needs at least five arithmetic-logic SIMD instructions for each iteration compared to at most two load operations and up to one store operation. Using overlapping vectors instead of shifting masks avoids having to carry over values from the previous iteration for “lookback” or “lookahead”. p. 6 In the best scenario,
we need at least five arithmetic-logic SIMD instructions for each iteration compared to at most two load operations
and up to one store operation. Using overlapping vectors instead of shifting masks avoids having to carry over values from the previous iteration
for “lookback” or “lookahead.Where the paper says it
The paper introduces a novel SIMD algorithm for in-place and copy-based UTF-16 correction, implemented with optimizations for ARM NEON and x64 SSE instructions to achieve up to eight-fold speedups over scalar methods.
The algorithm checks for valid surrogate pairs by examining high and low surrogates across block boundaries using a lookback mechanism to handle pairs spanning blocks.
The operational intensity of our main routine is high, as it needs at least five arithmetic-logic SIMD instructions for each iteration compared to at most two load operations and up to one store operation.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
SIMD-based UTF-16 correction for high throughput processing allows AI systems to handle large volumes of text data with up to eightfold speedups compared to traditional scalar methods, achieving throughputs reaching 18.9 GB/s on Apple M4 processors and 7.5 GB/s on Intel Ice Lake processors.
-
The algorithm can perform in-place and copy-based UTF-16 correction using SIMD instructions, enabling faster and more efficient execution for string operations within applications like web browsers or databases.
-
Architecture-specific optimizations, such as leveraging ARM NEON or x64 SSE/AVX-512 instructions, allow the system to achieve significant performance gains by tailoring the algorithm to specific processor microarchitectures.
-
The system can be optimized for error-free scenarios by skipping the expensive step of determining incorrect surrogates unless a quick check shows a need to do so, as
we define the operational intensity of our main routine as the ratio of arithmetic-logic SIMD instructions (e.g., comparisons, bitwise-AND) to the number of SIMD register loads and stores.
Abstract
UTF-16 is a widely used Unicode encoding representing characters with one or two 16-bit code units. The format relies on surrogate pairs to encode characters beyond the Basic Multilingual Plane, requiring a high surrogate followed by a low surrogate. Ill-formed UTF-16 strings -- where surrogates are mismatched -- can arise from data corruption or improper encoding, posing security and reliability risks. Consequently, programming languages such as JavaScript include functions to fix ill-formed UTF-16 strings by replacing mismatched surrogates with the Unicode replacement character (U+FFFD). We propose using Single Instruction, Multiple Data (SIMD) instructions to handle multiple code units in parallel, enabling faster and more efficient execution. Our software is part of the Google JavaScript engine (V8) and thus part of several major Web browsers.