Decoding UTF-8. Part V: Benchmarking Sequence Length Calculations

In Parts II, III, and IV of this series on decoding UTF-8, we examined several methods for determining the length of a UTF-8 encoded byte sequence. We presented the algorithms and inspected the generated assembly, but we did not measure performance. In this post we run simple tests to compare the throughput of the three methods.

Test Descriptions

To recap, the three methods we compare here are:

The “bitmask” method, described in Decoding UTF-8. Part II: Determining Sequence Length - a Straightforward Approach:

int utf8_sequence_length(unsigned char lead_byte) { if ((lead_byte & 0x80) == 0) { // Single byte (0opqrstu) return 1; } else if ((lead_byte & 0xE0) == 0xC0) { // Two-byte sequence (110xxxxx) return 2; ... }

The “lookup” method, described in Decoding UTF-8. Part III: Determining Sequence Length - A Lookup Table:

int utf8_sequence_length(unsigned char lead_byte) { // Hard-coded lookup table for UTF-8 lead byte lengths static const unsigned char lookup[256] = { ... };

// Access the hard-coded table to determine the sequence length return lookup[lead_byte]; }

The “countlz” method, which uses hardware support for counting leading zeros in a byte, described in Decoding UTF-8. Part IV: Determining Sequence Length - Counting Leading Bits:

int utf8_sequence_length(unsigned char lead_byte) { switch (std::countl_one(lead_byte)) { case 0: return 1; case 2: return 2; case 3: return 3; case 4: return 4; default: return 0; // invalid lead } }

There are two sets of data in the test:

Pure ASCII text.

Cyrillic text with ASCII HTML tags.

I used two different compilers:

Clang 18.1.3

GCC 13.3.0

The results presented in this article were obtained on a Microsoft Surface laptop with a Snapdragon X1E80100 12-core CPU @ 3.40 GHz and 16 GB RAM, running Ubuntu 22.04 under WSL 2.

The code for the benchmarks can be found at: github.com/nemtrif/utfbench/tree/main/seqlen

My expectations based on the generated assembly were:

For the ASCII text, I expected the stra…