9 ms·
Fast UTF-8 validation
- sippingjippers 6y agoIs there any indication of the size of the lookup tables in question?
- vardump 6y agoSource code here: https://github.com/lemire/validateutf8-experiments/tree/master/src https://github.com/lemire/validateutf8-experiments/tree/mast... Looks like a very tiny LUT, perhaps it's all in SIMD registers. In any case, for anything to go at 12 GB/s, the LUT needs to be tiny and pretty much in SIMD register(s). Any indirect memory accesses would drastically slow things down, even if it's in L1 cache [0]. At least by an order of magnitude. Even when using something like x86 V[P]GATHER [0] (element-wise vector random access load). X86 gather is currently only slightly better than scalar code, even if all the data is on same cache line present in L1D! [0]: https://www.felixcloutier.com/x86/vpgatherdd:vpgatherqd https://www.felixcloutier.com/x86/vpgatherdd:vpgatherqd
- kevin_thibedeau 6y ago48 bytes
- deleted 6y ago[deleted]
- telotortium 6y agoTo be specific, three lookup tables of 16 bytes each, each table having 4-bit keys.
- thethirdone 6y agoFrom the paper: The first lookup table is 256 entries. I assume there are more lookup tables as well, but I haven't read far enough to kn9ow what they all are.
- stefan_ 6y agoThis is a cool post, but I'm still not convinced I want to do UTF-8 validation in the first place. UTF-8 text, even invalid, has the great property of failing gracefully in display that a boolean "valid" or "invalid" can never come close to.
- vardump 6y agoIt always depends, but most of the time it's better to fail fast. Invalid UTF-8 is a good indication something went wrong. The earlier the failure occurs, the easier it'll be to troubleshoot it. Of course there are situations where you want to make do with your input and try to interpret it the best you can. Sometimes you need to be lenient in what you accept [0]. That's how I'd expect, say, a web browser to operate. Default to not accepting invalid input. Just fail fast. [0]: Be liberal in what you accept, and conservative in what you send - Jon Postel
- jrochkind1 6y ago> Of course there are situations where you want to make do with your input and try to interpret it the best you can. Sometimes you need to be lenient in what you accept The best way to do this is to TURN the input into valid UTF8 though. Like replacing any uninterpretable-as-utf8 bytes with the unicode replacement character (U+FFFD). Which is what most well-behaved software I've seen does with bad UTF-8. I work with lots of text processing, including processing old legacy files etc. Just refusing to go forward with bad input ("just fail fast") would work a lot less well. Can you imagine if you tried to open up something in UTF8 in a text editor, and it just refused to open it, telling you nothing but "Bad UTF8" or maybe "Bad UTF8 at byte 19734"? Not super helpful. But yeah, you want to TURN it into valid UTF8 as early in the pipeline as possible, while logging/flagging/notifying what was done. You definitely don't want to let the bad UTF8 just continue through the pipeline like that unless you really really have to, that way lies madness.
- vardump 6y ago> Can you imagine if you tried to open up something in UTF8 in a text editor, and it just refused to open it, telling you nothing but "Bad UTF8" or maybe "Bad UTF8 at byte 19734"? Not super helpful. I think text editor is a good example where you need to be lenient. Furthermore, in that use case, any unnecessary modification of the data in any way is a bad idea. This includes replacing invalid code points with something else, unless they're edited by the user. The data might not even be UTF-8 in the first place.
- amelius 6y agoOne thing that is unsatisfactory here is that when you follow such a fast operation by another operation, you lose on memory access time if the string doesn't fit in the cache. So if you want to compute g(f(s)), then you will always have to optimize g and f together.
- vardump 6y agoGood point. In that case you might for example need to splice about 8-16 kB substrings to UTF-8 validate, to strike a reasonable balance between loop setup costs etc. and not spilling L1 cache. You'd of course need to check every splice ends at a valid UTF-8 boundary. Streaming operation composition while not sacrificing memory bandwidth or excessive overhead for CPU's liking is pretty cumbersome. You definitely don't want to spill cache, but you also need avoid overhead by ensuring vectorized code can take full advantage of the CPU performance. Anyone who tries to achieve high performance in this kind of operations without a profiler is doomed.
- VHRanger 6y agoThis is a validation step, though. I'd understand if it was a parser, but you want to validate UTF-8 to avoid reading into garbage (or evil code injection). So at least for this case it's mostly going to be validate(x) -> parse(x)
- pjscott 6y agoThe approach here can be used to process strings in chunks without too much added complexity, and it has low setup/teardown costs. The lookup tables fit in three 128-bit SIMD registers so there's minimal cache pollution, which is my usual worry with clever table-driven schemes for accelerating things.
- drummer 6y agoBob Steagall gave excellent talks at CppCon on using SIMD for utf8: https://youtube.com/watch?v=5FQ87-Ecb-A https://youtube.com/watch?v=5FQ87-Ecb-A https://youtube.com/watch?v=qejTqnxQRcw https://youtube.com/watch?v=qejTqnxQRcw
- petermcneeley 6y agoHere was my reply at the time (2018) for non-simd lookup table approach http://darkcephas.blogspot.com/2018/10/validating-utf8-strings-with-lookup.html http://darkcephas.blogspot.com/2018/10/validating-utf8-strin...
- a1369209993 6y ago> Thus you must validate that the strings you receive are valid UTF-8. Depending on your application, this is either unnecessary or insufficient. Consider a1="\xC3\xA4", a2="\x61\xCC\x88", a3="\xE0\x83\xA4". Assuming you're using a1 as your canonical representation of "ä", there's no legitimate difference between a2 and a3 despite the former being 'valid' UTF-8 and the latter not. (There are decent reasons why you might use a2 as your canonical representation instead, whereas the reasons for using a3 are satyrically flimsy (ironically they'd better support using a4="\xF0\x80\x83\xA4"), but that would just leave no legitimate difference between a1 and a3.)
- masklinn 6y agoThere are rather good reasons to not allow overlong encoding. For instance it allows smuggling data through unicode-unaware filters into unicode-aware applications, and while you should also catch the issue on the other side of the filter, overlong encoding allows trivially bypassing one line of defence for no reason. Such filters usually don't usually care much about precomposition or decomposition.
- a1369209993 6y agoThat's why I said: > > this is either unnecessary or insufficient. There are certainly plenty of circumstances where you don't want to allow non-canonical representations; my point was that there are more non-canonical representations than just the ones that UTF-8-level canonicality checks catch.
- kazinator 6y agoThat seems a bit like saying that there are more ways to die than just not wearing a seatbelt in an vehicular collision, so why bother with seatbelts.
- a1369209993 6y ago> so why bother with seatbelts. No, it is specifically not like that. It's like saying that, in any situation where you need a seatbelt, you also need airbags and a lack of ready-to-become-shrapnel sharp objects scattered around the inside of the vehicle.
- kyberias 6y agoThe author seems to have ended up in a silly debate when defending the use of SSE3 (and not SSE2). "You are absolutely not going to 100% SSE2 out in the real world. In fact, you have many 16-bit x86 systems out there. There are people running companies on Apple II computers." Right, "companies running business on Apple II computers" is a relevant argument for... absolutely nothing.
- cesarb 6y agoNote that the author is not defending the use of SSE3 (https://en.wikipedia.org/wiki/SSE3 https://en.wikipedia.org/wiki/SSE3), the author is defending the use of SSSE3 (https://en.wikipedia.org/wiki/SSSE3 https://en.wikipedia.org/wiki/SSSE3), which is something completely different. In fact, the whole point of this post is a novel use of the PSHUFB instruction, which comes from SSSE3. I happen to have a somewhat old laptop right next to me (it originally came with Windows Vista). According to /proc/cpuinfo, it does have SSE, SSE2, and SSSE3 (but not SSE3), so even that old laptop is already new enough to run the proposed algorithm.
- account42 6y agoAMD added SSSE3 with the FX processors, Phenom didn't have it. Not unreasonable to still expect there to be users without SSSE3 - e.g. across all Steam users over 1% don't have SSSE3. [0]. [0] https://store.steampowered.com/hwsurvey/ https://store.steampowered.com/hwsurvey/
- kevincox 6y ago> There are other standards. Some older programming languages like C# and Java rely on UTF-16. In UTF-16, you use two or four bytes per character. It seemed like a good idea at the time ... IIUC this isn't quite right. UTF-16 never seemed like a good idea on its own. These languages started with UCS-2 which did seem like a good idea. But then USC-2 ran out of bits and UTF-16 was the least-incompatible way to adopt Unicode. So as I understand it UTF-16 was always a compromise for backwards compatibility.
- TwoBit 6y agoRight. UTF-8 was intentionally created while UTF-16 was a known hack to deal with the mistake of UCS-2. Ideally neither should exist. There's at least some argument for the existence of UCS-4.
- asveikau 6y ago> There's at least some argument for the existence of UCS-4. I think advocacy for 4 bytes per codepoint misses the mark. People tend to erroneously assume that this takes away all complexity and brings us back to an ASCII-like reality of random access and 1 integer per glyph. However Unicode is full of complexities that mean that is not attainable. (Joiners, combining characters, and bi-di are a few.)
- chrismorgan 6y agoAnd the crazy thing is that UTF-8 came before UTF-16. https://en.wikipedia.org/wiki/UTF-8#History https://en.wikipedia.org/wiki/UTF-8#History, published in 1993. https://en.wikipedia.org/wiki/UTF-16#History https://en.wikipedia.org/wiki/UTF-16#History, published in 1996. And yet they ruined Unicode for everyone with surrogates in order to introduce UTF-16. (Surrogates and UTF-16 are by far the worst thing about Unicode, because they’re a pain and technically completely unnecessary, only having been introduced for poor social reasons.)
- br1 6y agoAnd UCS-2 run out of bits because the Unicode consortium keeps adding garbage like emojis to keep their job...
- zX41ZdbW 6y agoHow does it compare in performance with the optimized code from ClickHouse? https://github.com/ClickHouse/ClickHouse/blob/c0fef71507b43cc8021bea5a3d96de38505322a8/src/Functions/isValidUTF8.cpp#L144 https://github.com/ClickHouse/ClickHouse/blob/c0fef71507b43c...
- aqrit 6y agoThe algorithm used by ClickHouse was "inspired" by https://github.com/cyb70289/utf8/ https://github.com/cyb70289/utf8/ ... Which is known to be slower than this new method from simdjson.
- saagarjha 6y agoI like the (pseudo-?)code snippet in the article: simd8 classify(simd8 input, simd8 previous_input) { auto prev1 = input.prev<1>(previous_input); auto byte_1_high = prev1.shift_right <4>().lookup_16(table1); auto byte_1_low = (prev1 & 0x0F).lookup_16(table2); auto byte_2_high = input.shift_right <4>().lookup_16(table3); return (byte_1_high & byte_1_low & byte_2_high); } Is this coming from an existing library? If not, would it be generally possible to write something like this rather than dealing with some garbage like _mm_storeu_si128.
- innocenat 6y agoOn the other hand, I have absolutely no idea what this code is doing. I'd rather read the intrinsics or the actual assembly code. Like, what is `input.prev<1>(previous_input)` supposed to do? And with this syntax, I don't know where to start searching either.
- saagarjha 6y agoThere's actually a comment in the paper about what it does: > shift the input by 1 byte, shifting in the last byte of the previous input I'm unsure that I think the naming or parameter order is very good, but being able to lift the code into something nicer than intrinsics seemed nice to me.
- mikewarot 6y agoLong ago, I wrote a database program in Turbo Pascal to browse a 300k text database under MS-DOS. My search function took about 30 seconds or so, if you hard a hard drive. I was challenged to make it faster... I got it down to 3 seconds, in the days of 286s. I believe I could now get it down to 1millisecond on my laptop using the techniques shown. This hack amazes me.
- alblue 6y agoI had a follow up thread with the author on Twitter, and one part of the talk ventured into if UTF-8 made sense for Eastern scripts. I looped in one of my ex Apple colleagues who worked on the transition of Swift from UTF-16 (the Mac default) to UTF-8 for the rationale why this made sense. That led to a whole discussion of the benefits of self synchronising bytes in UTF-8 as well as a gratuitous self promotion of my “history of Unicode” talk at https://speakerdeck.com/alblue/a-brief-history-of-unicode https://speakerdeck.com/alblue/a-brief-history-of-unicode The end of the Twitter thread is here, if you’re interested: https://twitter.com/alblue/status/1319017092004315138 https://twitter.com/alblue/status/1319017092004315138