encoding_rs Performance, November 2016

I’m working on a new character encoding converter library for Gecko. The new library is written in Rust and is called encoding_rs. Here are some performance numbers as of the end of November 2016.

Reading the Tables

The columns are grouped into decode results and into encode results. Those groups, in turn, are grouped into using UTF-16 as the internal Unicode representation and into using UTF-8 as the internal Unicode representation. (Both are supported in encoding_rs in order to cater for both the legacy UTF-16 needs of Gecko and for Rust code normally using UTF-8.) Then there is a column for each library whose performance is being compared with. uconv is Gecko’s current encoding converter library. ICU is ICU 55. kernel32 is kernel32.dll included in Windows 10. stdlib is Rust’s standard library. rust-encoding is rust-encoding. glibc is glibc’s iconv.

Each row names a language and an external encoding to convert from or to. The numbers are factors relative to the library named in the column. 2.0 means that encoding_rs is twice as fast as the reference library. 0.5 means that the reference library is twice as fast as encoding_rs. 0.00 means that encoding_rs is really slow and the non-zero decimals didn’t show up in the second decimal position.

Workloads

When decoding from UTF-8, the test case is the Wikipedia article for Mars, the planet, for the language in question.

Reasons for choosing Wikipedia were:

• Wikipedia is an actual top site that’s relevant to users.
• Wikipedia has content in all the languages that were relevant for testing.
• Wikipedia content is human-authored.
• Wikipedia content is suitably licensed.

The topic Mars, the planet, was chosen, because it is the most-featured topic across the different-language Wikipedias and, indeed, had non-trivial articles in all the languages needed. Trying to choose a typical-length article for each language separately wasn’t feasible in the Wikidata data set.

When decoding from a non-UTF-8 encoding, the test case is synthetized from the UTF-8 test case by converting the Wikipedia article to the encoding in question and replacing unmappable characters with numeric character references (and in the case of Big5 removing a couple of characters that glibc couldn’t deal with).

When testing x-user-defined decode, the test case is a JPEG image, because loading binary data over XHR is the main performance-sensitive use case for x-user-defined.

Decoding JS or CSS wasn’t tested, but it’s safe to assume that the result would be faster than English, since JS and CSS tend to be 100% ASCII but English Wikipedia isn’t quite.

The encoder work loads use plain text extracts from the decoder test cases in order to simulate form submission (textarea) workloads.

The other Web-relevant case for the encoders is the parsing of URL query strings. In the absence of errors, the query strings are ASCII, so it’s safe to assume that the result would be faster than English as above.

Why These Reference Libraries?

ICU and glibc are tested in the form shipped by Ubuntu 16.04. While both Chrome and Safari use ICU, it is possible that the compiler and compiler options of ICU as shipped by Ubuntu cause the performance of ICU as tested here to differ from actual performance as used in competing browsers. Still, hopefully ICU as shipped by Ubuntu gives a ballpark understanding of performance relative to Chrome and Safari. The entry point to kernel32.dll appears to be a non-streaming API. Logically, Edge and IE need streaming encoding converters and it’s not clear if the underlying converters used by Edge and IE are the same as the converters exposed by kernel32.dll, but hopefully the comparison with kernel32.dll gives a ballpark understanding of performance relative to Edge and IE. Comparing with rust-encoding is relevant to understanding performance relative to Servo and the Rust ecosystem in general. glibc is included mainly as a matter of curiosity but could be considered relevant in terms of writing Linux apps in C using the Linux C ecosystem libraries vs. writing Linux apps in Rust using encoding_rs. The Rust standard library isn’t interesting for now, since encoding_rs delegates UTF-8 validation to the Rust standard library at the moment. Any deviation from a factor of 1.00 is more likely to be jitter in the tests than anything substantive.

Apples to Oranges Comparisons

Some the comparisons could be considered to compare things that aren’t commensurable. In particular:

• Except for kernel32, the measurements exclude the initialization and destruction of the converter. This is to the advantage of uconv, ICU and glibc, which perform more work during converter initialization than encoding_rs does. kernel32 does not expose converter initialization is a distinct operation and it’s not clear if there is an initialization cost the first time a given converter is used or every time.

• When converting to and from UTF-8, in the comparison with rust-encoding, rust-encoding targets String and Vec<u8> while encoding_rs uses Cows. In this case, instead of trying to make the comparison fair by making encoding_rs make a useless copy, the comparison demonstrates the benefits of conditionally copy-free Rust API design.

• Since a reference libraries do not fully conform to the Encoding Standard, the work being performed isn’t exactly the same. Instead, the closest approximation of a given legacy encoding is used.

• Arguably, UTF-8 isn’t the native application-side Unicode representation of glibc. However, since e.g. glib (the infrastructure library used by GTK+) uses UTF-8 as its native application-side Unicode representation and wraps glibc for the conversions, testing glibc’s performance to and from UTF-8 is relevant even if arguably unfair.

• When encoding from UTF-8, encoding_rs and rust-encoding assume the input is valid, but glibc does not.

• The windows-1258 numbers might be bogus due to mismatches between NFC and windows-1258 using combining characters for some diacritics.

Notable Observations

• For decode performance with SSE2 enabled, encoding_rs outperforms uconv already, except for UTF-16LE and UTF-16BE.

• UTF-16LE and UTF-16BE are rare on the Web and, therefore, good performance for them isn’t a goal for encoding_rs. The implementation is totally naïve direcly from spec. There is a lot of room for optimization, but it makes sense to address other concerns first.

• Decoding UTF-8-encoded English to UTF-16 is slower in encoding_rs without SSE2 than in uconv (which uses SSE2 for UTF-8 to UTF-16 conversion). Since this is the most performance-sensitive conversion for Firefox startup and for Web performance, without a way to use explicit SIMD code in Rust in Firefox, it seems that landing encoding_rs is blocked. (Solutions could involve explicit SIMD being allowed on release-channel Rust or Firefox allowing the use of nightly-channel Rust.)

• Conversion from UTF-8 needs more work, since the current algorithm didn’t outperform Rust standard library, which is why encoding_rs currently delegates to the standard library for UTF-8 to UTF-8 decode, which is why explicit SIMD in encoding_rs makes no difference in the perf numbers for UTF-8 decode.

• Conversion from UTF-16 to UTF-8 fails to outperform uconv for many languages. Clearly needs more work even though I thought the code was pretty good.

• Legacy encode is expected to be slow in encoding_rs, because unlike the other libraries, encoding_rs uses decode-optimized data structure even on the encoders side in the interest of binary size / initialization speed, since the need for non-ASCII legacy encode occurs only in two places in the Web platform: form submission (between user interaction and waiting for network) and in URL parsing but only for error correction. (It’s unclear if letting the legacy encoders be slow is the right call. Chinese and Korean encoders are currently extremely slow.)

• Even though encoding_rs doesn’t have encode-specific data structures and uses the decode-optimized data structures for encode, it still outperforms uconv for single-byte encode except for Thai. (And Russian, but Russian is almost at the same speed.) The reason why Thai is slower is that the search order is the same for all single-byte encodings and the structure of windows-874 differs from the windows-125* series.

• EUC-KR decode is really slow in uconv.

• Big5 in uconv isn’t like the rest of uconv, because I rewrote it recently. It’s closer to encoding_rs than the rest of uconv in structure.

• The ARM numbers show that conversion to and from UTF-8 needs more care. The ALU-based ASCII acceleration code needs more attention, especially on 32-bit systems.

• encoding_rs hasn’t undergone CJK lookup table compaction yet. Simply moving Hiragana and Katakana to conversion by range check followed by an offset could bring Japanese legacy encode to par with uconv.

• Encoding from UTF-8 to UTF-8 is so fast compared to rust-encoding thanks to there being no copy in the encoding_rs case. (When comparing with glibc, the encoding_rs side is basically a memcpy.)

• When decoding from UTF-8 to UTF-8, in comparison with rust-encoding, encoding_rs just validates and borrows, but rust-encoding copies.

The Numbers

Finally, here are the numbers.

x86_64 (Haswell) with explicit SSE2 in encoding_rs

x86_64 (Haswell) without explicit SSE2 in encoding_rs

ARMv7 code running on an ARMv8 CPU (Raspberry Pi 3) without explicit NEON in encoding_rs