Prefixed Integer Encoding with SIMD10/21/2026 | 5 minutes to read | Open in Markdown
HTTP/3 uses QPACK to encode header fields. QPACK uses the prefixed integer encoding from RFC 7541.
In a previous post I explored this encoding and compared it with QUIC's Variable Length Integer Encoding. That comparison considered using SIMD for prefixed-integer decoding.
This post explores encoding prefixed integers using SIMD.
Prefixed Integer Encoding
Prefixed integer encoding can start at any bit position within a byte but always ends at a byte boundary. The "prefixed" part refers to the first byte that may contain a partial value. Typically, the prefix is a fixed number of bits N (an "N-bit prefixed number"). The example below shows a 5-bit prefix:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |---|---|---|---|---|---|---|---| | ? | ? | ? | Value |
A 5-bit prefix alone can represent values less than 2^N-1; here that is the 0–30 range inclusive. When all prefix bits are one (i.e., the prefix equals 2^N-1), the number continues in further bytes. Each subsequent byte uses the MSB as a continuation flag: MSB = 1 means more bytes follow; MSB = 0 means last byte. The remaining 7 bits per byte encode the value. The encoding algorithm defined by the RFC:
if I < 2^N - 1, encode I on N bits
else
encode (2^N - 1) on N bits
I = I - (2^N - 1)
while I >= 128
encode (I % 128 + 128) on 8 bits
I = I / 128
encode I on 8 bits
SIMD Prefixed Integer Encoding
Most modern CPUs support Single Instruction Multiple Data (SIMD) operations. These operations are typically implemented as an extension instruction set. On x86/x64 platforms one such instruction set is the AVX2. The goal is to implement the above Prefixed Integer Encoding with AVX2 and .NET using vector intrinsics. Then compare the performance of a non-SIMD implementation with the proposed SIMD one.
Preconditions:
- The input value is a non-negative 32-bit integer (
Int32). - Destination buffer is large enough for storing the encoded value.
The overall idea:
When the value can be encoded on a prefix, encode it normally. When the input number cannot be encoded on the prefix, set all the prefix bits to one, and decrease the input number with 2^N-1. Instead of a scalar while I >= 128 loop, unroll the loop into vector lanes. This can be done with AVX2 using 5 elements of the vector.
Broadcast the input value to a vector register.
Unroll I = I / 128 by dividing the input number with a vector of [2^0, 2^7, 2^14, 2^21, 2^28]. This division can be implemented with a variable bit operation.
var divisor = Vector256.Create([0u, 7u, 14u, 21u, 28u, 32u, 32u, 32u]); var vNumber = Avx2.ShiftRightLogicalVariable(Vector256.Create(number), divisor);
Calculate I % 128 + 128 with a (non-variable) right bitshift (to divide by 128), then left bitshift and subtraction to get the remainder. Finally, OR a vector where the value 128 is broadcasted.
var add128 = Vector256.Create(128); var quotient128 = Avx2.ShiftRightLogical(vNumber, 7); // div by 128 var vRemainder = Avx2.Or(vNumber - Avx2.ShiftLeftLogical(quotient128, 7), add128);
Now the vector contains the encoded Int32 values (between 128-255), that need to be casted to bytes before writing them to a destination. Notice that each integer in the vector contains only a single byte information and the remaining 3 bytes of the Int32 are set to zero. The vector cannot be just reinterpreted as bytes; it also needs to pack the values closer to each other by removing the zero bytes:
Vector128<short> packedShort = Avx2.PackSignedSaturate(vRemainder.GetLower(), vRemainder.GetUpper()); Vector128<byte> narrowBytes = Avx2.PackUnsignedSaturate(packedShort, packedShort); narrowBytes.StoreUnsafe(ref destination[1]); // the 0th byte is the prefix, written separately.
That store writes 16 bytes (Vector128<byte>), which is more than a single integer's encoded length. The final step computes the actual encoded length and returns it to the caller.
The vector "loop" continues until the remaining value is I >= 128. The number of irations can be calculated by comparing vNumber (divided / bitshifted values) with 128:
var vLength = Avx2.CompareGreaterThan(add128, vNumber).AsByte(); writtenCount = 2 + (int.TrailingZeroCount(Avx2.MoveMask(vLength)) >> 2); // Convert the vLength to actual length. destination[writtenCount - 1] -= 128;
Finally, subtract 128 from the last encoded byte because we added 128 to all lanes earlier using the OR operation; the last lane must have MSB = 0.
Performance Comparison
BenchmarkDotNet on .NET 10 was used for comparison. The tests included values that produce encoded lengths of 0, 3, 4, 5, 6, 7, 8, 9 bytes. In multiple runs, around 2098176 (encoded on 5 bytes) the SIMD implementation becomes comparable with the scalar one, and for larger values SIMD is faster.
| Method | Value | Mean | Error | StdDev | Code Size | |--------------- |---------------- |----------:|----------:|----------:|----------:| | EncodeLongSimd | 0 | 0.6533 ns | 0.0457 ns | 0.0427 ns | 414 B | | EncodeLong | 0 | 0.4602 ns | 0.0102 ns | 0.0095 ns | 210 B | | EncodeLongSimd | 1024 | 2.6770 ns | 0.0210 ns | 0.0196 ns | 281 B | | EncodeLong | 1024 | 0.9190 ns | 0.0168 ns | 0.0157 ns | 227 B | | EncodeLongSimd | 17408 | 2.6896 ns | 0.0353 ns | 0.0330 ns | 281 B | | EncodeLong | 17408 | 1.6179 ns | 0.0178 ns | 0.0158 ns | 227 B | | EncodeLongSimd | 2098176 | 2.6885 ns | 0.0389 ns | 0.0345 ns | 281 B | | EncodeLong | 2098176 | 2.3982 ns | 0.0402 ns | 0.0376 ns | 227 B | | EncodeLongSimd | 268436480 | 3.1444 ns | 0.0410 ns | 0.0363 ns | 281 B | | EncodeLong | 268436480 | 2.8964 ns | 0.0513 ns | 0.0455 ns | 230 B | | EncodeLongSimd | 34359739392 | 2.6716 ns | 0.0233 ns | 0.0206 ns | 281 B | | EncodeLong | 34359739392 | 2.9100 ns | 0.0530 ns | 0.0496 ns | 230 B | | EncodeLongSimd | 4398046512128 | 2.6902 ns | 0.0154 ns | 0.0144 ns | 281 B | | EncodeLong | 4398046512128 | 3.1787 ns | 0.0258 ns | 0.0201 ns | 230 B | | EncodeLongSimd | 562949953427456 | 2.6663 ns | 0.0223 ns | 0.0174 ns | 281 B | | EncodeLong | 562949953427456 | 3.7738 ns | 0.0444 ns | 0.0416 ns | 230 B |
The table above suggests that both the SIMD and non-SIMD algorithms have their own strengths. QPACK encoded fields are typically low values. For example, to encode a large, 16K long cookie, the encoded length field would be still below the threshold value of 2098176. In a known case when someone needs to encode long fields, a non-SIMD implementation could branch above a given input value (say 2098176), and switch to SIMD processing. This way smaller values are still encoded efficiently, and large values as well.