3 ms·

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.

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.
- BeeOnRope 7y ago
  > 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. Indeed, this is a good example of a problem with random bechmarks: no text really has the behavior of uniform random with 50% ASCII but no character-to-character correlation. In the real world you often expect bursts of ASCII, e.g., where a title is written in ASCII or where you have say structured data like HTML, ASCII, JSON, etc which often have lots of ASCII data mixed in with meant-for-human strings which may be non-ASCII, but it's very bursty. As you point out, for your algorithm, 50% ASCII but no burstiness basically means every vector takes the non-ASCII path, which is actually "good" compared to say 50% of vectors taking the ASCII shortcut (which would slow things down due to BP failures) - so a lot of the interesting design space is ignored (e.g., I think the ideal algorithm will choose between strategies in a branch-predictor aware fashion). > this doesn't matter very much for benchmarking, at least for the mostly-branchless SIMD algorithms like mine Right - but of course it matters a lot for existing algorithms (which tend to be branchy), which can come out looking much worse or much better depending on the distributions (not that I think any will be able to pass a good vectorized approach). Also, as above, the early-out for ASCII will matter for a lot of practical inputs, but neither benchmark stresses it. > 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. Right, well the ASCII one is a big one. I haven't looked at the details of your algorithm, but could the core loop be faster if say it never saw any 4-byte sequences, or certain other uncommon things? Then an adaptive approach would use an optimized kernel for that scenario if it was encountered for a while. "Adaptive" doesn't really mean more branches - just that you occasionally might switch to a different kernel based on the observed data. This shouldn't add many branches compared to e.g., the existing loop and failure branches, and evidently you have to do it in a branch-predictor aware way (e.g., you need some type of hysteresis in mode switches so you don't switch too often). Sometimes you can build the adaptivity into the existing branches, e.g., maybe you are taking a branch anyways (e.g., when you find non-ASCII text) and you can build the adaptive "state machine" directly into the code via duplication of code, w/o needing any explicit data counting the number of failures (effectively, the IP holds extra information recording something about the path you took to reach the current location).

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.

BeeOnRope 7y ago
> 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. Indeed, this is a good example of a problem with random bechmarks: no text really has the behavior of uniform random with 50% ASCII but no character-to-character correlation. In the real world you often expect bursts of ASCII, e.g., where a title is written in ASCII or where you have say structured data like HTML, ASCII, JSON, etc which often have lots of ASCII data mixed in with meant-for-human strings which may be non-ASCII, but it's very bursty. As you point out, for your algorithm, 50% ASCII but no burstiness basically means every vector takes the non-ASCII path, which is actually "good" compared to say 50% of vectors taking the ASCII shortcut (which would slow things down due to BP failures) - so a lot of the interesting design space is ignored (e.g., I think the ideal algorithm will choose between strategies in a branch-predictor aware fashion). > this doesn't matter very much for benchmarking, at least for the mostly-branchless SIMD algorithms like mine Right - but of course it matters a lot for existing algorithms (which tend to be branchy), which can come out looking much worse or much better depending on the distributions (not that I think any will be able to pass a good vectorized approach). Also, as above, the early-out for ASCII will matter for a lot of practical inputs, but neither benchmark stresses it. > 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. Right, well the ASCII one is a big one. I haven't looked at the details of your algorithm, but could the core loop be faster if say it never saw any 4-byte sequences, or certain other uncommon things? Then an adaptive approach would use an optimized kernel for that scenario if it was encountered for a while. "Adaptive" doesn't really mean more branches - just that you occasionally might switch to a different kernel based on the observed data. This shouldn't add many branches compared to e.g., the existing loop and failure branches, and evidently you have to do it in a branch-predictor aware way (e.g., you need some type of hysteresis in mode switches so you don't switch too often). Sometimes you can build the adaptivity into the existing branches, e.g., maybe you are taking a branch anyways (e.g., when you find non-ASCII text) and you can build the adaptive "state machine" directly into the code via duplication of code, w/o needing any explicit data counting the number of failures (effectively, the IP holds extra information recording something about the path you took to reach the current location).