11 ms·

Show HN: Faster UTF-8 validator

122 points by zwegner 7y ago

vardump 7y ago
Pretty nice. Always nice to see better optimized commonly required algorithms. If this is really faster than previous implementations (no reason to doubt, but don't have time to validate right now), this might save megawatts of power world wide. (Disclaimer: Would need to actually check with power measurement tools, but generally faster consumes less power.) A small nitpick: not sure whether those macros bought anything, I guess the optimizer could inline function calls to intrinsic wrappers just fine as well?
- zwegner 7y ago
  > this might save megawatts of power world wide That'd sure be neat! I really have no idea, though. > A small nitpick: not sure whether those macros bought anything, I guess the optimizer could inline function calls to intrinsic wrappers just fine as well? Yeah, that's a bit weird. It's my hacky generics-in-C method, that allows both AVX2 and SSE4 implementations to be compiled in one codebase, while keeping the base algorithm clean. The idea is that you can compile both versions by including multiple times, like so: #define AVX2 #include "z_validate.c" #undef AVX2 #define SSE4 #include "z_validate.c" #undef SSE4 ...which would allow a later runtime dispatch based on CPUID, etc.
  - thechao 7y ago
    How much faster than a "naive" scalar implementation is this?
    - zwegner 7y ago
      It depends on the implementation. A good starting point would be looking at the various implementations benchmarked here: https://github.com/lemire/fastvalidate-utf-8 https://github.com/lemire/fastvalidate-utf-8 It looks like the main naive validator there (validate_utf8) clocks in at 1.25 cycles/byte for ASCII and 11 cycles/byte for UTF-8, which is respectively a 15.8x and 41.5x slowdown from my code.
- FpUser 7y ago
  ...this might save megawatts of power world wide... Since when saved megawatts bothered programmers? If that was the case we would see far smaller usage of scripting languages and electron apps.
  - marmada 7y ago
    It takes effort to not use electron. It doesn't take effort to have your library update its dependencies to use a faster utf-8 validator
    - F-0X 7y ago
      > It takes effort to not use electron. Why do you believe this? I don't think it is quite that ubiquitous.
      - jimsmart 7y ago
        Let's say I want to build a cross-platform app. I could use Electron (it's somewhat of a known quantity), or I could start doing some research into what else is available, and then evaluate the various offerings - not only to ensure they do what I need, but to also ensure that they use less power/resources than Electron. The effort here is (at least some kind of) unavoidable up-front cost/time. To switch existing code to use some particular UTF-8 decoding library should be as simple as changing some imports, and perhaps some other (search/replace) code tweaks or implementing a quick shim/adapter. If it doesn't work out, rollback or abandon the branch. On most codebases, even larger ones, this whole process is probably an easier thing to do, requiring less effort than finding a decent (and more power efficient) alternative to Electron — seems to be the GP's gist. And personally I'd agree.
        FpUser 7y ago
        "Let's say I want to build a cross-platform app. I could use Electron (it's somewhat of a known quantity), or I could start doing some research into what else is available, and then evaluate the various offerings - not only to ensure they do what I need, but to also ensure that they use less power/resources than Electron. The effort here is (at least some kind of) unavoidable up-front cost/time." Yup that's right. Any sign of inconvenience and efficiency be damned. Why do we even bother trying to fix environment. This cost money and inconveniences so many people. Also it depends on your background. I have no problem doing without Electron. I would have to apply your exact logic to even look at it.
aqrit 7y ago
how does this differ from here: https://github.com/lemire/simdjson/pull/365 https://github.com/lemire/simdjson/pull/365
- zwegner 7y ago
  Oh interesting, I hadn't seen that. It looks like it uses the same idea of shuffle-lookups on the first three nibbles. That's a fairly large patch though, I don't think I've fully grokked it. At the very least, my code differs from that in that mine does less byte stream shifting, instead doing shifts in the scalar domain. Their code also needs to deal with quotes, escaping, etc. due to being part of a JSON validator.
- ysleepy 7y ago
  Just today I stumbled on lemire works when looking through the dependencies of jgit and found the java ewah bitset implemenation and ended up browsing his code seeing the utf8 validator and simdjson. Coincedences..
SlowRobotAhead 7y ago
I like the way you write and comment your C code. Very nicely written. Except all those spaces between the # and “define”, no sir I don’t like that :)
- zwegner 7y ago
  Well how else are you supposed to nest your preprocessor macros? :P Thanks though! I like taking the time to make my code as clean as I can. Glad others appreciate it!
  - usr1106 7y ago
    I have used the same "indendation" in the past. Because there are always review comments that his would be weird/confusing/unconventional I have given up on using it :(
    - kevin_thibedeau 7y ago
      It used to be the only valid way to indent macros. It has the advantage that macro lines always get highlighted in column-1 and stand out more from regular structured code.
  - brandmeyer 7y ago
    Honestly? Give clang-format a try. There's tons of options available. Futz with them until you get a set that is to your liking, and then write them down in your repo's `.clang-format` file. After that, the answer to "does this pull request comply with my formatting guidelines?" gets reduced to "does clang-format change this file?"
  - leetcrew 7y ago
    I think it's more common to put the indentation before the '#'. either way it ends up looking a little weird, but I prefer to see some visual indication of nesting.
  - speps 7y ago
    The # doesn't need to be first on the line, looks better in my opinion.
CodesInChaos 7y ago
Do the instructions you use cause downclocking on Intel CPUs?
- eyegor 7y ago
  (not op) Somewhat, although it's fairly minimal for avx2. The serious downclocking problem comes from avx512 instructions, which the author seems interested in: > This algorithm should map fairly nicely to AVX-512, and should in fact be a bit faster than 2x the speed of AVX2 since a few instructions can be saved In general, you aren't going to make a faster wheel without some trickery (vectorization usually). All the obvious optimizations have already been made in the stdlibs.
- oconnor663 7y ago
  I can't remember where I read this, but there was an argument somewhere that worrying about downclocking only really makes sense when the instruction set in question is new. (Which AVX-512 certainly is, to be fair.) Eventually, when the instruction set is more widely used, you'll probably already be paying the downclocking penalty anyway because of someone else's code, and you might as well go ahead and use the fancy instructions in your own code. Do you think that's valid?
  - oconnor663 7y ago
    (I remembered what it was: https://blog.cr.yp.to/20190430-vectorize.html https://blog.cr.yp.to/20190430-vectorize.html)
- littlestymaar 7y ago
  There's a really good comment on reddit on the subject: https://www.reddit.com/r/rust/comments/dx6e0h/comment/f7o8avf https://www.reddit.com/r/rust/comments/dx6e0h/comment/f7o8av... TL;DR; yes but not too much if your CPU is high-end and if the number of AVX instructions is low enough (and the slowdown is negligible in front of the gains if the number of instructions is high).
- BeeOnRope 7y ago
  No, because non-"FMA unit" (mostly SIMD FP) AVX2 instructions don't cause license-based downclocking on recent Intel CPUs. To get downclocking to L1 license (the middle speed tier), you need to use either FMA unit AVX/AVX2 insructions or any AVX-512 instructions. This algo doesn't use any of this, staying in the integer domain. Here's a longer description: https://stackoverflow.com/a/56861355 https://stackoverflow.com/a/56861355 Of course this doesn't address say power or temperature based throttling which might be more likely to occur when wide SIMD is used, but it's not possible to give a precise answer there, other than many low or moderate core count setups won't see this kind of throttling outside of extreme use cases.
eyegor 7y ago
I'm not sure if the compiler is smart enough to do it for you, but you might be able to squeak a bit more performance by precomputing a partial sum (data + V_LEN - 1) outside the loop for this statement: > v_load(data + offset + V_LEN - 1); Other than that, this is incredibly clean code and I doubt you can get much more performance without dropping into assembly. I wish my coworkers made code this well documented :/
- zwegner 7y ago
  At least my compiler (LLVM 10) is smart enough to know that "data" isn't modified, and thus fold the addresses of the two vector loads inside the main loop into single instructions: 1a0: c5 fe 6f 6c 31 ff vmovdqu ymm5,YMMWORD PTR [rcx+rsi*1-0x1] 1a6: c5 fe 6f 24 31 vmovdqu ymm4,YMMWORD PTR [rcx+rsi*1] I'd expect most modern compilers to get this right with optimizations on, but if somebody finds one that doesn't, I'd like to know. In general, I read through the disassembly a decent amount when developing this. That's how I noticed the "req += (vmask2_t)set << n;" (instead of |=) trick, which gets compiled to one lea instruction. The disassembly got a little bit hairy when I added the code to handle trailing bytes, though... Thanks for the kind words, though! It warms my heart :)
- vardump 7y ago
  > I'm not sure if the compiler is smart enough to do it for you, but you might be able to squeak a bit more performance by precomputing a partial sum (data + V_LEN - 1) outside the loop for this statement: I don't remember last time when a compiler did not do this for me. Compilers are generally pretty smart nowadays.
BeeOnRope 7y ago
Good stuff. The key to a solid claim, especially for something as bold as "fastest in the world", is a complete specification of the inputs to the benchmark. You mention random ASCII bytes and "random UTF-8 bytes". The former is definitely an really important case but also the least interesting. I can write on a napkin a UTF-8-but-is-actually-ASCII decoder that approaches 256 bytes a cycle cached (with a fallback routine when the ASCII assumption fails). So then what about the random UTF-8 bytes. What does it mean? Do you generate random bytes and then exclude invalid sequences? Do you generate a uniform random codepoint in the 21-bit codepoint space and then concert it to utf-8? At a minimum it would good to see a benchmark with random distributions that approximate common languages. The true fastest decoders on such realistic data will be adaptive and more complicated than yours.
- zwegner 7y ago
  Well, to be fair, my claim was that it was the fastest in the world that I'm aware of, which is a much weaker statement. :) The random UTF-8 in the benchmark was generated from the code in Daniel Lemire's fastvalidate-utf-8 repository, specifically this code: https://github.com/lemire/fastvalidate-utf-8/blob/ed53c0c64b3e5ef767eeea8f8f1c205f75c377af/benchmarks/benchmark.c#L93-L141 https://github.com/lemire/fastvalidate-utf-8/blob/ed53c0c64b... Looking closer at it, I think that the distribution of random UTF-8 is not as uniform as it should be: it generates one byte first, and then generates continuation bytes depending on the value of that byte. Which means that half the code points will just be ASCII. But I think this doesn't matter very much for benchmarking, at least for the mostly-branchless SIMD algorithms like mine. For each vector of input bytes, there's three branches that can get taken: the early exit for ASCII-only, and two branches that exit the loop due to validation failures, which don't really matter for benchmarking. Even though the distribution of code points will be roughly half ASCII, for a 32-byte AVX2 vector, the probability of a pure ASCII vector is something less than 2^-32 (since non-ASCII initial bytes translate into more than one byte of output, and the probability of 32 ASCII code points in a row is 2^-32, the probability of 32 bytes in a row is less, by an amount I'd rather not try to calculate). So for this particular benchmark, random UTF-8 should be roughly equivalent to "no ASCII". To verify, I disabled generating ASCII in the linked code, and the numbers came out pretty much identical. If anything, even more ASCII bytes would be a more interesting test, since that would make the quick-ASCII branch less predictable. If you know of any good UTF-8 corpora for common use cases, I'd be happy to benchmark them. Given that different sets of "random UTF-8 bytes" generated with this method will virtually always follow the same path, the exact distribution doesn't really matter when measuring cycles/byte. Input that is purely 2-byte code points will be faster in terms of cycles/code point than purely 4-byte input, but that's mostly a property of UTF-8 being variable length. I doubt there's much speed to be gained by adding any sort of adaptive behavior beyond the ASCII check. Generally these days you want as few branches as you can manage, and this algorithm has only one that matters.
pabs3 7y ago
I wonder if the authors plan to get this merged into commonly used implementations of UTF-8 validators so that folks can benefit from their work. Anyone have any ideas about which open source codebases UTF-8 validators exist in?
- zwegner 7y ago
  I don't have any particular plans for that, beyond getting a bit of publicity for it here :). Or really any plans at all, besides adding AVX-512 support. It was just something I hacked together in a couple days as I began thinking about adding UTF-8 support to the text editor I've been writing. That said, I'm happy to help anyone get it integrated into their codebase if they need it. There's generally other concerns in large projects, though, like portability, that I don't care as much about.
- nitwit005 7y ago
  There's not as big a niche as you might think. A lot of the software that needs valid UTF-8 don't validate upfront, but do it as part of a parsing process. An example would be something like an XML or JSON parser. For more mundane uses like opening a big text file, you often want to tolerate invalid bytes and show a replacement character. You could use the technique, but you'd have to modify it to work for that usage.
  - pdkl95 7y ago
    [re: upfront parsing - a PSA about validating input] > A lot of the software ... don't validate upfront They almost always should be validating all input up front. Deferring validation tends to become many different pieces of code all informally parsing fragments of the input that are needed locally. Without upfront validation of the complete unit of input, the resulting fragmented parsers are just a weird machine waiting to be programmed by a malicious attacker. For a much better explanation, I strongly recommend Meredith and Sergey's 28c3 talk[1] about The Science of Insecurity. > you often want to tolerate invalid bytes and show a replacement character While this validator wouldn't be useful in that situation, it is still important to validate the input upfront. When showing replacement characters, the "invalid bytes" that will be supported with a replacement character should be formally defined and added to the validation grammar, because they are no longer "invalid", but instead will be handled as a special case. Postel's robustness principle shouldn't be used as an excuse to skip validation. Being "liberal in what you accept" should still be well-defined and validated. [1] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...
vmurthy 7y ago
Sorry if this is slightly off topic but a great time to revisit this great primer on Unicode [0] by Joel Spolsky. [0] https://www.joelonsoftware.com/2003/10/08/the-absolute-minimum-every-software-developer-absolutely-positively-must-know-about-unicode-and-character-sets-no-excuses/ https://www.joelonsoftware.com/2003/10/08/the-absolute-minim...
- matheusmoreira 7y ago
  Also: https://utf8everywhere.org/ https://utf8everywhere.org/
andrewf 7y ago
Hi! I took a shot at vectorized UTF-8 validation in 2012. I just put this faster validator, and Daniel Lemire's code, into my test harness at https://github.com/andrewffff/utf8fuzz/tree/2019_compare https://github.com/andrewffff/utf8fuzz/tree/2019_compare On an i7-7800X (clang 6.0.0-1ubuntu2, WSL, don't trust my numbers) my benchmarks showed about the same relationship between SSE4, AVX2 and Lemire's code, as your benchmarks did. My own attempt is about half as fast. https://raw.githubusercontent.com/andrewffff/utf8fuzz/2019_compare/rough-benchmark.png https://raw.githubusercontent.com/andrewffff/utf8fuzz/2019_c... A few examples of invalid UTF-8 from Markus Kuhn's suite pass this validator right now, specifically 4.1.3, 4.2.3 and 4.3.3. My randomized tests, which compare the results from different validators, also fail a small percentage of the time, I'd guess for the same reason. https://www.cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt https://www.cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt I'm really interested in the different approaches taken here. Fortunately both Daniel and you've communicated what you were doing, I think it's going to take longer for me to re-comprehend my own approach! Thanks for sharing this.
- zwegner 7y ago
  Oh wow, that is most definitely a bug. Thank you very much for reporting that, before this spreads too much. How embarrassing... I was in a bit of a rush to stick this up on HN before the weekend, as otherwise I'd probably never get around to it. Evidently I got a bit sloppy making the error table. Luckily, that's a very easy bug to fix--it was just caused by a mistake constructing the error tables. The only annoying part is having to renumber the error bits and write the tables again by hand :) Thanks too for benchmarking! I see you tried out make.py, but it didn't work? I should probably add a Makefile for people that don't want to deal with yet another random build system...

122 points by zwegner 7y ago

Pretty nice. Always nice to see better optimized commonly required algorithms. If this is really faster than previous implementations (no reason to doubt, but don't have time to validate right now), this might save megawatts of power world wide. (Disclaimer: Would need to actually check with power measurement tools, but generally faster consumes less power.) A small nitpick: not sure whether those macros bought anything, I guess the optimizer could inline function calls to intrinsic wrappers just fine as well?

zwegner 7y ago
> this might save megawatts of power world wide That'd sure be neat! I really have no idea, though. > A small nitpick: not sure whether those macros bought anything, I guess the optimizer could inline function calls to intrinsic wrappers just fine as well? Yeah, that's a bit weird. It's my hacky generics-in-C method, that allows both AVX2 and SSE4 implementations to be compiled in one codebase, while keeping the base algorithm clean. The idea is that you can compile both versions by including multiple times, like so: #define AVX2 #include "z_validate.c" #undef AVX2 #define SSE4 #include "z_validate.c" #undef SSE4 ...which would allow a later runtime dispatch based on CPUID, etc.
- thechao 7y ago
  How much faster than a "naive" scalar implementation is this?
  - zwegner 7y ago
    It depends on the implementation. A good starting point would be looking at the various implementations benchmarked here: https://github.com/lemire/fastvalidate-utf-8 https://github.com/lemire/fastvalidate-utf-8 It looks like the main naive validator there (validate_utf8) clocks in at 1.25 cycles/byte for ASCII and 11 cycles/byte for UTF-8, which is respectively a 15.8x and 41.5x slowdown from my code.
FpUser 7y ago
...this might save megawatts of power world wide... Since when saved megawatts bothered programmers? If that was the case we would see far smaller usage of scripting languages and electron apps.
- marmada 7y ago
  It takes effort to not use electron. It doesn't take effort to have your library update its dependencies to use a faster utf-8 validator
  - F-0X 7y ago
    > It takes effort to not use electron. Why do you believe this? I don't think it is quite that ubiquitous.
    - jimsmart 7y ago
      Let's say I want to build a cross-platform app. I could use Electron (it's somewhat of a known quantity), or I could start doing some research into what else is available, and then evaluate the various offerings - not only to ensure they do what I need, but to also ensure that they use less power/resources than Electron. The effort here is (at least some kind of) unavoidable up-front cost/time. To switch existing code to use some particular UTF-8 decoding library should be as simple as changing some imports, and perhaps some other (search/replace) code tweaks or implementing a quick shim/adapter. If it doesn't work out, rollback or abandon the branch. On most codebases, even larger ones, this whole process is probably an easier thing to do, requiring less effort than finding a decent (and more power efficient) alternative to Electron — seems to be the GP's gist. And personally I'd agree.
      - FpUser 7y ago
        "Let's say I want to build a cross-platform app. I could use Electron (it's somewhat of a known quantity), or I could start doing some research into what else is available, and then evaluate the various offerings - not only to ensure they do what I need, but to also ensure that they use less power/resources than Electron. The effort here is (at least some kind of) unavoidable up-front cost/time." Yup that's right. Any sign of inconvenience and efficiency be damned. Why do we even bother trying to fix environment. This cost money and inconveniences so many people. Also it depends on your background. I have no problem doing without Electron. I would have to apply your exact logic to even look at it.

aqrit 7y ago

how does this differ from here: https://github.com/lemire/simdjson/pull/365 https://github.com/lemire/simdjson/pull/365

zwegner 7y ago
Oh interesting, I hadn't seen that. It looks like it uses the same idea of shuffle-lookups on the first three nibbles. That's a fairly large patch though, I don't think I've fully grokked it. At the very least, my code differs from that in that mine does less byte stream shifting, instead doing shifts in the scalar domain. Their code also needs to deal with quotes, escaping, etc. due to being part of a JSON validator.
ysleepy 7y ago
Just today I stumbled on lemire works when looking through the dependencies of jgit and found the java ewah bitset implemenation and ended up browsing his code seeing the utf8 validator and simdjson. Coincedences..

SlowRobotAhead 7y ago

I like the way you write and comment your C code. Very nicely written. Except all those spaces between the # and “define”, no sir I don’t like that :)

zwegner 7y ago
Well how else are you supposed to nest your preprocessor macros? :P Thanks though! I like taking the time to make my code as clean as I can. Glad others appreciate it!
- usr1106 7y ago
  I have used the same "indendation" in the past. Because there are always review comments that his would be weird/confusing/unconventional I have given up on using it :(
  - kevin_thibedeau 7y ago
    It used to be the only valid way to indent macros. It has the advantage that macro lines always get highlighted in column-1 and stand out more from regular structured code.
- brandmeyer 7y ago
  Honestly? Give clang-format a try. There's tons of options available. Futz with them until you get a set that is to your liking, and then write them down in your repo's `.clang-format` file. After that, the answer to "does this pull request comply with my formatting guidelines?" gets reduced to "does clang-format change this file?"
- leetcrew 7y ago
  I think it's more common to put the indentation before the '#'. either way it ends up looking a little weird, but I prefer to see some visual indication of nesting.
- speps 7y ago
  The # doesn't need to be first on the line, looks better in my opinion.

CodesInChaos 7y ago

Do the instructions you use cause downclocking on Intel CPUs?

eyegor 7y ago
(not op) Somewhat, although it's fairly minimal for avx2. The serious downclocking problem comes from avx512 instructions, which the author seems interested in: > This algorithm should map fairly nicely to AVX-512, and should in fact be a bit faster than 2x the speed of AVX2 since a few instructions can be saved In general, you aren't going to make a faster wheel without some trickery (vectorization usually). All the obvious optimizations have already been made in the stdlibs.
oconnor663 7y ago
I can't remember where I read this, but there was an argument somewhere that worrying about downclocking only really makes sense when the instruction set in question is new. (Which AVX-512 certainly is, to be fair.) Eventually, when the instruction set is more widely used, you'll probably already be paying the downclocking penalty anyway because of someone else's code, and you might as well go ahead and use the fancy instructions in your own code. Do you think that's valid?
- oconnor663 7y ago
  (I remembered what it was: https://blog.cr.yp.to/20190430-vectorize.html https://blog.cr.yp.to/20190430-vectorize.html)
littlestymaar 7y ago
There's a really good comment on reddit on the subject: https://www.reddit.com/r/rust/comments/dx6e0h/comment/f7o8avf https://www.reddit.com/r/rust/comments/dx6e0h/comment/f7o8av... TL;DR; yes but not too much if your CPU is high-end and if the number of AVX instructions is low enough (and the slowdown is negligible in front of the gains if the number of instructions is high).
BeeOnRope 7y ago
No, because non-"FMA unit" (mostly SIMD FP) AVX2 instructions don't cause license-based downclocking on recent Intel CPUs. To get downclocking to L1 license (the middle speed tier), you need to use either FMA unit AVX/AVX2 insructions or any AVX-512 instructions. This algo doesn't use any of this, staying in the integer domain. Here's a longer description: https://stackoverflow.com/a/56861355 https://stackoverflow.com/a/56861355 Of course this doesn't address say power or temperature based throttling which might be more likely to occur when wide SIMD is used, but it's not possible to give a precise answer there, other than many low or moderate core count setups won't see this kind of throttling outside of extreme use cases.

eyegor 7y ago

I'm not sure if the compiler is smart enough to do it for you, but you might be able to squeak a bit more performance by precomputing a partial sum (data + V_LEN - 1) outside the loop for this statement: > v_load(data + offset + V_LEN - 1); Other than that, this is incredibly clean code and I doubt you can get much more performance without dropping into assembly. I wish my coworkers made code this well documented :/

zwegner 7y ago
At least my compiler (LLVM 10) is smart enough to know that "data" isn't modified, and thus fold the addresses of the two vector loads inside the main loop into single instructions: 1a0: c5 fe 6f 6c 31 ff vmovdqu ymm5,YMMWORD PTR [rcx+rsi*1-0x1] 1a6: c5 fe 6f 24 31 vmovdqu ymm4,YMMWORD PTR [rcx+rsi*1] I'd expect most modern compilers to get this right with optimizations on, but if somebody finds one that doesn't, I'd like to know. In general, I read through the disassembly a decent amount when developing this. That's how I noticed the "req += (vmask2_t)set << n;" (instead of |=) trick, which gets compiled to one lea instruction. The disassembly got a little bit hairy when I added the code to handle trailing bytes, though... Thanks for the kind words, though! It warms my heart :)
vardump 7y ago
> I'm not sure if the compiler is smart enough to do it for you, but you might be able to squeak a bit more performance by precomputing a partial sum (data + V_LEN - 1) outside the loop for this statement: I don't remember last time when a compiler did not do this for me. Compilers are generally pretty smart nowadays.

BeeOnRope 7y ago

Good stuff. The key to a solid claim, especially for something as bold as "fastest in the world", is a complete specification of the inputs to the benchmark. You mention random ASCII bytes and "random UTF-8 bytes". The former is definitely an really important case but also the least interesting. I can write on a napkin a UTF-8-but-is-actually-ASCII decoder that approaches 256 bytes a cycle cached (with a fallback routine when the ASCII assumption fails). So then what about the random UTF-8 bytes. What does it mean? Do you generate random bytes and then exclude invalid sequences? Do you generate a uniform random codepoint in the 21-bit codepoint space and then concert it to utf-8? At a minimum it would good to see a benchmark with random distributions that approximate common languages. The true fastest decoders on such realistic data will be adaptive and more complicated than yours.

zwegner 7y ago
Well, to be fair, my claim was that it was the fastest in the world that I'm aware of, which is a much weaker statement. :) The random UTF-8 in the benchmark was generated from the code in Daniel Lemire's fastvalidate-utf-8 repository, specifically this code: https://github.com/lemire/fastvalidate-utf-8/blob/ed53c0c64b3e5ef767eeea8f8f1c205f75c377af/benchmarks/benchmark.c#L93-L141 https://github.com/lemire/fastvalidate-utf-8/blob/ed53c0c64b... Looking closer at it, I think that the distribution of random UTF-8 is not as uniform as it should be: it generates one byte first, and then generates continuation bytes depending on the value of that byte. Which means that half the code points will just be ASCII. But I think this doesn't matter very much for benchmarking, at least for the mostly-branchless SIMD algorithms like mine. For each vector of input bytes, there's three branches that can get taken: the early exit for ASCII-only, and two branches that exit the loop due to validation failures, which don't really matter for benchmarking. Even though the distribution of code points will be roughly half ASCII, for a 32-byte AVX2 vector, the probability of a pure ASCII vector is something less than 2^-32 (since non-ASCII initial bytes translate into more than one byte of output, and the probability of 32 ASCII code points in a row is 2^-32, the probability of 32 bytes in a row is less, by an amount I'd rather not try to calculate). So for this particular benchmark, random UTF-8 should be roughly equivalent to "no ASCII". To verify, I disabled generating ASCII in the linked code, and the numbers came out pretty much identical. If anything, even more ASCII bytes would be a more interesting test, since that would make the quick-ASCII branch less predictable. If you know of any good UTF-8 corpora for common use cases, I'd be happy to benchmark them. Given that different sets of "random UTF-8 bytes" generated with this method will virtually always follow the same path, the exact distribution doesn't really matter when measuring cycles/byte. Input that is purely 2-byte code points will be faster in terms of cycles/code point than purely 4-byte input, but that's mostly a property of UTF-8 being variable length. I doubt there's much speed to be gained by adding any sort of adaptive behavior beyond the ASCII check. Generally these days you want as few branches as you can manage, and this algorithm has only one that matters.

pabs3 7y ago

I wonder if the authors plan to get this merged into commonly used implementations of UTF-8 validators so that folks can benefit from their work. Anyone have any ideas about which open source codebases UTF-8 validators exist in?

zwegner 7y ago
I don't have any particular plans for that, beyond getting a bit of publicity for it here :). Or really any plans at all, besides adding AVX-512 support. It was just something I hacked together in a couple days as I began thinking about adding UTF-8 support to the text editor I've been writing. That said, I'm happy to help anyone get it integrated into their codebase if they need it. There's generally other concerns in large projects, though, like portability, that I don't care as much about.
nitwit005 7y ago
There's not as big a niche as you might think. A lot of the software that needs valid UTF-8 don't validate upfront, but do it as part of a parsing process. An example would be something like an XML or JSON parser. For more mundane uses like opening a big text file, you often want to tolerate invalid bytes and show a replacement character. You could use the technique, but you'd have to modify it to work for that usage.
- pdkl95 7y ago
  [re: upfront parsing - a PSA about validating input] > A lot of the software ... don't validate upfront They almost always should be validating all input up front. Deferring validation tends to become many different pieces of code all informally parsing fragments of the input that are needed locally. Without upfront validation of the complete unit of input, the resulting fragmented parsers are just a weird machine waiting to be programmed by a malicious attacker. For a much better explanation, I strongly recommend Meredith and Sergey's 28c3 talk[1] about The Science of Insecurity. > you often want to tolerate invalid bytes and show a replacement character While this validator wouldn't be useful in that situation, it is still important to validate the input upfront. When showing replacement characters, the "invalid bytes" that will be supported with a replacement character should be formally defined and added to the validation grammar, because they are no longer "invalid", but instead will be handled as a special case. Postel's robustness principle shouldn't be used as an excuse to skip validation. Being "liberal in what you accept" should still be well-defined and validated. [1] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...

vmurthy 7y ago

Sorry if this is slightly off topic but a great time to revisit this great primer on Unicode [0] by Joel Spolsky. [0] https://www.joelonsoftware.com/2003/10/08/the-absolute-minimum-every-software-developer-absolutely-positively-must-know-about-unicode-and-character-sets-no-excuses/ https://www.joelonsoftware.com/2003/10/08/the-absolute-minim...

matheusmoreira 7y ago
Also: https://utf8everywhere.org/ https://utf8everywhere.org/

andrewf 7y ago

Hi! I took a shot at vectorized UTF-8 validation in 2012. I just put this faster validator, and Daniel Lemire's code, into my test harness at https://github.com/andrewffff/utf8fuzz/tree/2019_compare https://github.com/andrewffff/utf8fuzz/tree/2019_compare On an i7-7800X (clang 6.0.0-1ubuntu2, WSL, don't trust my numbers) my benchmarks showed about the same relationship between SSE4, AVX2 and Lemire's code, as your benchmarks did. My own attempt is about half as fast. https://raw.githubusercontent.com/andrewffff/utf8fuzz/2019_compare/rough-benchmark.png https://raw.githubusercontent.com/andrewffff/utf8fuzz/2019_c... A few examples of invalid UTF-8 from Markus Kuhn's suite pass this validator right now, specifically 4.1.3, 4.2.3 and 4.3.3. My randomized tests, which compare the results from different validators, also fail a small percentage of the time, I'd guess for the same reason. https://www.cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt https://www.cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt I'm really interested in the different approaches taken here. Fortunately both Daniel and you've communicated what you were doing, I think it's going to take longer for me to re-comprehend my own approach! Thanks for sharing this.

zwegner 7y ago
Oh wow, that is most definitely a bug. Thank you very much for reporting that, before this spreads too much. How embarrassing... I was in a bit of a rush to stick this up on HN before the weekend, as otherwise I'd probably never get around to it. Evidently I got a bit sloppy making the error table. Luckily, that's a very easy bug to fix--it was just caused by a mistake constructing the error tables. The only annoying part is having to renumber the error bits and write the tables again by hand :) Thanks too for benchmarking! I see you tried out make.py, but it didn't work? I should probably add a Makefile for people that don't want to deal with yet another random build system...