8 ms·
Validating UTF-8 strings using as little as 0.7 cycles per byte
- MichaelGG 9y agoFast checking is really useful in things like HTTP/SIP parsing. Rust should expose such a function as well seeing as their strings must be UTF-8 validated. Though it's even faster if you can just avoid utf8 strings and work only on a few known ASCII bytes, it means you might push garbage further down the line.
- masklinn 9y ago> Rust should expose such a function as well seeing as their strings must be UTF-8 validated. That's more or less what std::str::from_utf8 is: it runs UTF8 validation on the input slice, and just casts it to an &str if it's valid: https://doc.rust-lang.org/src/core/str/mod.rs.html#332-335 https://doc.rust-lang.org/src/core/str/mod.rs.html#332-335 from_utf8_unchecked nothing more than an unsafe (c-style) cast: https://doc.rust-lang.org/src/core/str/mod.rs.html#437 https://doc.rust-lang.org/src/core/str/mod.rs.html#437 and so should be a no-op at runtime.
- MichaelGG 9y agoI meant Rust should have a SIMD optimised version that assumes mostly ASCII. I'm guessing there is a trade-off involved depending on the content of the string.
- masklinn 9y agosimd support in Rust was only recently accepted and is being implemented so it currently relies on the vectorisation abilities on the compiler (it might get revisited soon-ish I guess). As for the assumption of mostly-ascii, the validation function has a "striding" fast path for ascii which checks 2 words at a time (so 128 bits per iteration on 64b platforms) until it finds a non-ascii byte: https://doc.rust-lang.org/src/core/str/mod.rs.html#1541 https://doc.rust-lang.org/src/core/str/mod.rs.html#1541
- scottlamb 9y agoThe linked implementation assumes mostly ASCII. It doesn't use SIMD. SIMD in Rust is a work in progress - the next version (1.27) will stabilize x86-64-specific SIMD intrinsics. There's an rfc (https://github.com/rust-lang/rfcs/pull/2366 https://github.com/rust-lang/rfcs/pull/2366) for portable SIMD types.
- chrismorgan 9y agostd::str::from_bytes is that API. Rust’s current implementation of full validation: https://github.com/rust-lang/rust/blob/2a3f5367a23a769a068c37460db336de427c4b48/src/libcore/str/mod.rs#L1458-L1578 https://github.com/rust-lang/rust/blob/2a3f5367a23a769a068c3... I have a vague feeling there’s an even faster path for probably-ASCII out there, but I can’t immediately recall where and am going to bed. Doubtless someone else will answer before I get up. The core team will be amenable to replacing this algorithm with something faster presuming it’s still correct.
- kzrdude 9y agoGiven the new simd features, it's probably time to revisit that now
- MichaelGG 9y agoThere is probably a trade-off depending on the content of the string, right? So the API probably needs a general-purpose and a "this should be all ASCII" version?
- simias 9y agoI don't know if it really makes a lot of sense to have such a specialized version of a method in the standard library. Effectively from_str and from_str_mostlyascii would be functionally identical except for a small performance difference depending on the encoding of the string data which wouldn't matter in 99% of programs. Having that as a 3rd party crate would make complete sense however.
- Retra 9y agoIf there's a canonical, obvious, and low maintenance way to do something that there's a common need for, then there's no reason it shouldn't be in std. If it needs to be hacked at and redesigned every few years, then yeah, leave it out.
- 9y ago
- KMag 9y agoWith such a high percentage of text on the web in UTF-8, and many uses for variable-length integers, I hope that we'd see single instructions for reading and writing Unicode codepoints to/from UTF-8, as well as reading/writing 128-bit variable length integers (preferably prefix-encoded[0] rather than LEB128). A while back, I read that the Chinese Longson processors were a (subset?) of the MIPS instruction set with added instructions for Unicode handling, but that's all I've heard of processors with Unicode accelerating instructions, and I'm not sure which encoding(s) was/were accelerated. [0]https://news.ycombinator.com/item?id=11263378 https://news.ycombinator.com/item?id=11263378
- chrisseaton 9y ago> With such a high percentage of text on the web in UTF-8, and many uses for variable-length integers, I hope that we'd see single instructions for reading and writing Unicode codepoints to/from UTF-8 If we took this attitude with every new technology, we'd have a large number of instructions that are now useless. At one time it probably seemed a good idea to have custom instructions for parsing XML, and people really were doing custom instructions for interpreting JVM bytecode.
- mywittyname 9y agoI disagree. It's reasonable to assume UTF-8 will is here to stay. It will likely outlive any processor architectures designed today. Plus, there are already several instructions on x86 that for string manipulation.
- loeg 9y ago> Plus, there are already several instructions on x86 that for string manipulation. Also SHA1, AES, CRC32, and other specialized functions that may have less staying power than UTF-8 (SHA1 in particular, but also AES being a block cipher has some nuisances that means it is not always used in new algorithms).
- GolDDranks 9y ago
- SloopJon 9y agoMy first thought on seeing this was Bjoern Hoehrmann's UTF-8 decoder, which encodes a finite state machine into a byte array: http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ I happened to come across this decoder again recently in Niels Lohmann's JSON library for C++: https://github.com/nlohmann/json https://github.com/nlohmann/json I see that this is mentioned in a previous post: https://lemire.me/blog/2018/05/09/how-quickly-can-you-check-that-a-string-is-valid-unicode-utf-8/ https://lemire.me/blog/2018/05/09/how-quickly-can-you-check-... One thing I'd like to check in the new code is whether it's as picky about things like overlong sequences as Bjoern's code is.
- loeg 9y ago> One thing I'd like to check in the new code is whether it's as picky about things like overlong sequences as Bjoern's code is. I believe that's what checkContinuation() is doing, based on its use of the "counts" parameters. I don't understand how it works, but I don't see any other reason for count_nibbles() to compute the '->count' member.
- kwillets 9y agoThe counts are actually to find the length of the following continuation bytes, and mark them to look for overlaps or underlaps between the end of one code point and the next.
- loeg 9y agoUnderlaps and overlaps would occur if sequences are invalid, i.e., overly long (or short) compared to the initial byte's prefix.
- kwillets 9y agoIt checks overlongs. It's not too hard -- a few bits in the first byte, and a few in the second for some lengths.
- zbjornson 9y agoI'm confused how the ASCII check works. It's checking if any byte is greater than zero. Wouldn't you want to check if the 8th bit in any byte is set?
- aeruder 9y agoThe trick here is that each byte is treated as a signed 8-bit number. When the top bit is set, the number is negative.
- zbjornson 9y agoOh duh, thanks. (Checking less than zero, read it wrong.) I think it would be faster to OR the entire string with itself, then finally check the 8th bit though. On Skylake that would cut it to 0.33 cycles per 16 bytes (HSW 1 per 16). https://github.com/lemire/fastvalidate-utf-8/pull/2 https://github.com/lemire/fastvalidate-utf-8/pull/2
- vardump 9y ago> I think it would be faster to OR the entire string with itself, then finally check the 8th bit though. The string could have NUL (zero) bytes in between.
- deleted 9y ago[deleted]
- nabla9 9y agoThere is validating and "validating", what is this code doing? For example, valid utf-8 must always use the shortest possible sequence or it's invalid. Validator must check against decoding invalid sequences. example of invalid sequence: 0xF0 0x80 0x80 0x8A
- jwilk 9y agoThe test suite includes these as "bad" sequences: * \xc0\x9f (overlong U+001F) * \xed\xa0\x81 (surrogate)
- SloopJon 9y agoI was too lazy to look up what these sequences represented, but I did a quick test with the Euro symbol example from Wikipedia, and it did indeed reject the overlong sequence: #include <stdbool.h> #include <string.h> #include <stdio.h> #include "simdutf8check.h" int main(int argc, char *argv[]) { const char euro[] = "\xe2\x82\xac"; const char eurolong[] = "\xf0\x82\x82\xac"; bool valid = validate_utf8_fast(euro, sizeof euro); printf("validate_utf8_fast(euro): %d\n", valid); valid = validate_utf8_fast(eurolong, sizeof eurolong); printf("validate_utf8_fast(eurolong): %d\n", valid); return 0; }
- Someone 9y ago”For example, valid utf-8 must always use the shortest possible sequence or it's invalid.” nabla9 likely knows this, but for those wondering: utf8 can’t contain overlong encodings (https://en.m.wikipedia.org/wiki/UTF-8#Overlong_encodings https://en.m.wikipedia.org/wiki/UTF-8#Overlong_encodings), but need not use precomposed characters (https://en.m.wikipedia.org/wiki/Precomposed_character https://en.m.wikipedia.org/wiki/Precomposed_character) whenever possible (another way in which a shorter sequence is possible)
- rspeer 9y agoThis is built on UTF-8 described as a state machine. The state machine already rejects overlong sequences. There is no sense of "validator" in which an expression that accepts overlong sequences could be called a UTF-8 validator.
- ozzmotik 9y agohow exactly do you use a fraction of a cycle? i would assume that it would be fractional on average, but then again I can't exactly speak for my expertise on how instructions map to cycles and if it's solely an integer mapping
- kizer 9y agoI believe he means on average, as you said.
- mcguire 9y agoYou handle multiple bytes at once; it's fractional on average. He's using vectorized operations to handle 16 bytes at a time, basically: __m128i has_error = _mm_setzero_si128(); __m128i zero = _mm_setzero_si128(); for (...) { __m128i current_bytes = _mm_loadu_si128(src); has_error = _mm_or_si128(has_error, _mm_cmpgt_epi8(zero,current_bytes)); } return _mm_testz_si128(has_error, has_error); Each of the _mm* "functions" becomes 1 (?) vector instruction.
- dragontamer 9y ago> I can't exactly speak for my expertise on how instructions map to cycles and if it's solely an integer mapping 1. Standard ALUs on modern processors are 64-bits at a time. So right there, you're 8x faster on a per-byte basis. 2. He's using vectorized operations, so he can work with 128-bits, 256-bits (or potentially even 512-bits on high-end processors like Skylake-X). So 16x, 32x, or 64x at a time per operation. 3. Modern processors are super-scalar with multiple ALUs and multiple execution ports. I forget what the precise theoretical limit is, but Intel AND AMD machines can execute something like 4 or 5 operations per clock, depending on circumstances. That assumes that all operations have been decoded into micro-ops (uops), they fit inside the uop cache (think of a uop cache as a L0 cache: beyond even the L1 cache), that they perfectly line up to available execution ports, that your data has no dependencies, and a whole host of other conditions. But its theoretically possible. --------- In practice: your code will be limited by memory (even L1 cache is slower than the CPU), by decoding speed (not everything fits in the uOp cache, and only loops really benefit from the uop cache), dependencies (a = x + 1. a = a+2. The 2nd instruction depends on the 1st one to execute first, so the two instructions can't be done in parallel / superscalar). The CPU is pretty good at trying to figure out how to optimally reorder and out-of-order execute your code. But that means that predicting the performance of the CPU is incredibly difficult: you have to keep in mind all of the parts of the CPU while thinking of the assembly code.
- kizer 9y agoShould strings be represented as codepoint arrays in memory? In C, for example, should I always decode input and work with that, or convert to utf8?
- steveklabnik 9y agoIt's always tradeoffs. If by "arrays of codepoints" you mean "each element of the array is a single codepoint", then you get O(1) indexing regarding codepoints, but may use up to 4x the memory as the variable-length encoding.
- bumblebritches5 9y agoWhich is fine when you're doing nothing but a simple operation on a string, then reencoding it. Seriously, how many strings have you ever ran across that are more than 1kb? how many strings have you ran across that are more than 256 codepoints?
- steveklabnik 9y agoSure. It's fine sometimes, and not fine other times. That's why it's called a tradeoff. I see strings larger than that all the time, and care about using low RSS. YMMV.
- nirvdrum 9y agoPeople routinely read text files larger than 1 KB into memory. HTTP responses are often larger than 1 KB. Serialized data (JSON, XML, etc.) is often larger than 1 KB.
- bumblebritches5 9y agoHTTP headers are not anywhere near 1kb of text. the packet's themselves are only 1.5kb.
- nirvdrum 9y ago