11 ms·
A Branchless UTF-8 Decoder
- kuwze 9y agoI'm an idiot in this area. Why would you decode utf8?
- fra 9y agoIn order to look up glyph in your font, you'll typically need a 32bit unicode code-point. A utf-8 string encodes those code-points using a variable-number-of-bytes scheme, so you need to decode each code-point before you can render it.
- amelius 9y agoYes, but this code expands it to a 32-bit array. That seems a bit silly because you'd be wasting a lot of memory bandwidth there. I suspect the loss could even be greater than what you've gained from removing those branches.
- amaranth 9y agoNot quite, it's expanded to a 32-bit integer, one codepoint at a time.
- grzm 9y agoPerhaps you're misinterpreting what a decoder does. From the article: > This week I took a crack at writing a branchless UTF-8 decoder: a function that decodes a single UTF-8 code point from a byte stream…
- chrisseaton 9y agoTo print it to the screen for example.
- smegel 9y agoSome languages represent unicode strings as objects quite separate to their binary encoding, e.g. Python.
- kutkloon7 9y agoTo get the unicode codepoint. For example, you need this when you want to render a character, or convert it to another representation.
- ot 9y ago> My primary — and totally arbitrary — goal was to beat the performance of Bjoern Hoehrmann’s DFA-based decoder. The thing is, that decoder could be already branchless. The core of the algorithm is: *codep = (*state != UTF8_ACCEPT) ? (byte & 0x3fu) | (*codep << 6) : (0xff >> type) & (byte); Which can be compiled with a conditional move (CMOV) instead of a branch. In fact: > With GCC 6.3.0 on an i7-6700, my decoder is about 20% faster than the DFA decoder in the benchmark. With Clang 3.8.1 it’s just 1% faster. There's a chance that when inlined into the benchmark Clang uses a CMOV while GCC uses a branch. As he correctly points out, his benchmark is the worst case for branch prediction: > The even distribution of lengths greatly favors a branchless decoder. The random distribution inhibits branch prediction.
- tedunangst 9y agoCMOV isn't necessarily faster than no branches. There's still data dependencies which can prevent reordering. But considerably faster than a misprediction.
- ot 9y agoSure, but if you look at the implementation in the article, that's a much longer dependency chain: *c = (uint32_t)(s[0] & masks[len]) << 18; *c |= (uint32_t)(s[1] & 0x3f) << 12; *c |= (uint32_t)(s[2] & 0x3f) << 6; *c |= (uint32_t)(s[3] & 0x3f) << 0; *c >>= shiftc[len]; /* Accumulate the various error conditions. */ *e = (*c < mins[len]) << 6; *e |= ((*c >> 11) == 0x1b) << 7; // surrogate half? *e |= (s[1] & 0xc0) >> 2; *e |= (s[2] & 0xc0) >> 4; *e |= (s[3] ) >> 6; *e ^= 0x2a; // top two bits of each tail byte correct? *e >>= shifte[len]; Plus, all those loads are not making it easy for the processor to pipeline. And *e = (*c < mins[len]) << 6; is really a CMOV in disguise :)
- userbinator 9y agois really a CMOV in disguise :) I don't see how using CMOV would be appropriate there --- I'd compile it as something more like this: ; eax = *c, ebx = mins[len] cmp eax, ebx sbb eax, eax and eax, 64 ; eax = (*c < mins[len]) << 6
- ant6n 9y agoSeems like a fun project! One thing I stumbled over: > unsigned char *next = s + len + !len; > Originally this expression was the return value, computed at the very end of the function. However, after inspecting the compiler’s assembly output, I decided to move it up, and the result was a solid performance boost. That’s because it spreads out dependent instructions. With the address of the next code point known so early, the instructions that decode the next code point can get started early. If there's no change in the actual logic, I feel like the compiler should be able to move up expressions in order to make them available earlier. I wonder whether this was tested/inspected with some optimizations turned off.
- jacobush 9y agoSo optimising code feels like playing chess now?
- logicallee 9y agodid you mean because computers can do it better? I can't see anything else in their comment that you could have referred to, but the quoted part shows that the author did it better than the compiler output...
- jacobush 9y agoNo, not really. I meant by the prose description of how to optimise the code. It felt like how chess masters may discuss their strategies after a game of chess. Very high level and far from what a layperson may really understand about chess (or optimising), but very true and distinct nonetheless. It gives a glimpse into the mind of the chess master (or optimiser) even when you yourself don't possess these skills.
- logicallee 9y agoOh okay. I see the similarity now - it does look like prose discussion of chess games. The analogy can be pretty deep, like strategic considerations ("opposite-colored bishops" vs "spread-out dependent instructions" in the prose you replied to). Thanks for the clarification, this was insightful.
- smegel 9y agoWeird to talk so much about branch prediction for branchless code.
- tedunangst 9y ago1. Understanding how branches work is important to understanding the motivation for branchless code. 2. It's not entirely branch less. Consistent branching is equally important.
- deleted 9y ago[deleted]
- twoodfin 9y agoA constant reminder: Be wary when microbenchmarking functions that make relatively heavy use of lookup tables vs. those that don’t. You may not see the effects of the pressure this adds to the data cache, but a real program using many functions and other data will. The same is true for long vs. short functions and the instruction cache.
- Animats 9y agoIf that bothers you, there's this approach: #define VALIDTAB (0x7f00ffff) #define LENTAB (0x000000003a550000) inline bool isvalidutf8start(char c) { return((VALIDTAB >> (c>>3)) & 1); } inline unsigned utf8length(char c) { return(1+((LENTAB >> ((c>>3)*2)) & 2)); } The 32-entry table of lengths can be coded up as a 64-bit value. The "is valid" table is stored as a separate constant.
- Aardwolf 9y agoYou need to have padding bytes at the end of the stream. What if you don't have them and got a const pointer to a buffer provided by a user? Then you need to copy the entire buffer again with the padding bytes behind it. Are there any tricks to avoid this being costly?
- ChuckMcM 9y agoPresumably !len is a test and set instruction which has the same impact on the pipeline. But that said branchless code that fits in a couple of cache lines seems like it would be the best you could do.
- asveikau 9y agoI don't know the answer to this. Say on x86, if you do "test eax, eax", then "setz eax", then use eax in further arithmetic - obviously there is no jump involved, but does that stall the pipeline? At any rate the caller needs to check for errors coming out of this function (the int *e parameter) and zero termination, so there will be conditional jumps somewhere in the use of this thing. (And reading the code it seems to assume s[3] is safe to dereference...)
- userbinator 9y agoThe core of the algorithm shows that UTF-8 is actually big-endian in its ordering of the bits, making it somewhat more difficult to implement efficiently on the usual little-endian machine --- the first byte, at the lowest address, actually contains the most sigificant bits. Had it been the other way around, the final shift would not be length-dependent. Also, none of the compilers I tried at https://godbolt.org/ https://godbolt.org/ were able to combine the 4 s[0...3] 8-bit reads into one 32-bit read, which is somewhat disappointing. They generated 4 separate byte-read instructions, one for each s[0..3]. Yes, I know it could be unaligned, but this is x86 where it would still be faster than 4 separate reads. You would need to do this instead (and sacrifice endianness/alignment-independence): uint32_t v = *(uint32_t*)s; *c = (uint32_t)(v & masks[len]) << 18; *c |= (uint32_t)((v>>8) & 0x3f) << 12; *c |= (uint32_t)((v>>16) & 0x3f) << 6; *c |= (uint32_t)((v>>24) & 0x3f) << 0; *c >>= shiftc[len]; We're still left with a bunch of shifts, ands, and ors, the purpose of which is to essentially "compact" the 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx bitstring into one 21-bit codepoint by removing the bits in the middle. All the compilers I tried weren't so clever as to do this (assuming eax = v from above after masking, and cl = slightly modified shiftc[len]) at any optimisation level: bswap eax mov ebx, eax and ebx, 00FF00FFh lea ebx, [ebx + ebx*2] add eax, ebx shr eax, 2 shl ax,4 shr eax, cl I played around with optimising UTF-8 decoding a while ago, and the above resembles one of the fastest and smallest ways to "compact" the 4 bytes into a codepoint. Of course, this bit string manipulation would be much faster and trivial in hardware (essentially rearranging wires), which makes me want a LODSUTF8 instruction that operates like LODSB but reads a whole codepoint instead, and sets CF on error...
- Dylan16807 9y ago> Yes, I know it could be unaligned, but this is x86 where it would still be faster than 4 separate reads. You have to worry about memory access violations too.
- zAy0LfpBZLC8mAC 9y agoWhere in the C standard are memory access violations specified as a language feature?!
- Sidnicious 9y agoI ran into the same UTF-8 decoder that you did (http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ http://bjoern.hoehrmann.de/utf-8/decoder/dfa/) and tried to better understand why it was fast. In the process, I wrote a naive UTF-8 parser that turned out to be significantly faster. I used a version of the original benchmark (the current Hindi Wikipedia dump as one big XML file). My original benchmark read the file as a stream — no guarantee that you'll get whole characters in each read — so I modified it a bit to read the whole file into memory, parse it, and print out the number of characters decoded and an XOR "hash". Here's what happened (looking at the "user" line of `time` output): - Bjoern Hoehrmann’s decoder: 2.159s - This post’s decoder: 2.754s (27.6% slower) - Naive decoder: 1.453s (32.7% faster) I'm curious whether this test makes sense and, if so, why there's such a big difference. Currently my best guess is the data cache pressure mentioned in twoodfin's comment. I guess I should write a blog post, too. Naive parser: https://gist.github.com/s4y/7c95f1ebeb2c069cfb09db3c3251eca3 https://gist.github.com/s4y/7c95f1ebeb2c069cfb09db3c3251eca3 Benchmarks: https://gist.github.com/s4y/344a355f8c1f99c6a4cb2347ec4323cc https://gist.github.com/s4y/344a355f8c1f99c6a4cb2347ec4323cc
- ori_b 9y agoAlmost all the text is ascii, so the branch predictor gets things right. Correctly predicted branches are nearly free, costing about as much as their decode overhead. It'd be interesting to see the results where you have randomly shuffled characters of all lengths, although it's likely to be something you see in reality.
- ComputerGuru 9y agoDealing with situations like this where you can’t guarantee you read a complete decode sequence is exactly where memory mapped files are gold. Replacing read, test sequence end, buffer, drop buffer if it exceeds certain length without sequence end but record sequence start, seek until end sequence is found, and process that mess in a safe, passably-efficient manner with memory mapped files made my cross-platform tac a breeze to write: https://neosmart.net/blog/2017/a-high-performance-cross-platform-tac-rewrite/ https://neosmart.net/blog/2017/a-high-performance-cross-plat...
- Tuna-Fish 9y agoUTF-8-decode and encode are basically the only things that could be done by a single instruction, are common enough for implementing this instruction to make sense, yet still don't exist in x86. I wonder why.
- spullara 9y agoEvery time I have worked for a company that had a tight relationship with Intel I've gotten the opportunity to meet with them and ask for chips features. I always ask for encoding / decoding Unicode. So far I've been ignored for 15 years or so.
- goldenkey 9y agoHe can also add the restrict keyword on his pointer arguments to squeeze out some more of the compiler's optimizations. https://en.m.wikipedia.org/wiki/Restrict https://en.m.wikipedia.org/wiki/Restrict
- kazinator 9y agoI don't see where this is catching encoding errors, like overlong forms. That has security implications. It's useful when there is some assurance that the UTF-8 is error-free. E.g. tdata bundled with the program or otherwise trusted.
- __s 9y agoBenchmarks should've included random ASCII. I understand they hinted at that with labeling their benchmark synthetic, but it'd give a idea of the impact of branch mispredicts
- exabrial 9y agoSorry dumb question, why branchless?
- umanwizard 9y agoThe article answers this in detail, but the TLDR is that branches slow down execution on modern CPUs
- zaxomi 9y agoWhy branchless? Because branches can kill performance. For an explanation, see this answer on branch prediction: https://stackoverflow.com/a/11227902 https://stackoverflow.com/a/11227902
- Too 9y agoSo the classic lookup-tables are faster than switch/case? *c >>= shiftc[len]; could probably be replaced by switch(len) and would result in equal code. My guess is that the speed increase comes from the trailing 3 bytes potential overread and the somewhat odd error handling, not the lookups.
- ogoffart 9y agoSimilarily, I made a couple of year ago a UTF8 decoder using SIMD. It is almost branchless. (The branches are there only to detect errors) https://woboq.com/blog/utf-8-processing-using-simd.html https://woboq.com/blog/utf-8-processing-using-simd.html
- 2sk21 9y agoThis appears to be a descendant of Duff's device (https://en.wikipedia.org/wiki/Duff's_device https://en.wikipedia.org/wiki/Duff's_device)