Comment by zwegner | Hacker News Reader

Comment by zwegner | Hacker News Reader

Parent Full thread

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/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.

> If you know of any good UTF-8 corpora for common use cases, I'd be happy to benchmark them.

I think a reasonable approach is the first N bytes of wikipedia for various interesting languages which stress the UTF-8 continuum, e.g., English, French, maybe something in Cyrillic, Greek, Korean, Japanese, Mandarin.

Those are in html IIRC so you should have a good mix of ASCII plus UTF-8.

Definitely a good idea. I had already downloaded a Mandarin Wikipedia page to look for test sequences, but hadn't benchmarked them. Getting some more pages there is a great place to start.

> 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).

Ah, thanks for the reply. I understand you better now, and for the most part I agree. Taking out the early exit for ASCII can speed up the frequently-changing case to avoid the misprediction penalty, as long as sufficiently many chunks of input need to take the long validation path.

Thinking about this more, I think there's at least one way that an adaptive approach might be beneficial without too much extra complexity: keeping two copies of the main kernel for ASCII-checking and non-ASCII checking. It should be pretty cheap to add a counter that is incremented or decremented based on the ASCII-only mask, and split the outer loop into N-byte chunks, with a branch for each chunk determining whether we should take the branchless path or not.

> 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.

I started out thinking this wouldn't really work, but I think there might be some potential here. My initial problem was that even if some work could be saved if there weren't 4 byte sequences, we still need to detect them every time. But, because my algorithm uses lookup tables for error flags which have some free bits, and because the 4 byte sequences can be detected in the same indices that are used for these lookups, we can set another error bit that means "take the 4-byte slow path". Then, when some input fails validation, we only do the work there to check whether it's really a failure. This gets complicated, though: first off, the check for the proper number of continuation bytes is before the table lookup, so we'd need to put some logic in there. Secondly, this lookup table gets validation failures one byte later in the stream than the initial byte. So in the case that the 4-byte sequence starts on the last byte of a vector, we'd need to have special handling.

It'd probably be a good idea to also have some hysteresis in this approach too... So overall, I think there might be some nice gains from adaptive behavior. There are two big concerns that make me skeptical, though: code size/I$ pressure, and code complexity. While code size wouldn't be much of an issue in microbenchmarks, in real applications it matters a lot more--I don't want the size overhead to get too big. Right now the full validation algorithm is about 600 bytes of code for AVX2, I'd rather not make that explode by a large factor by adding several specializations. And I'm already reaching the limits of what little generic programming can be done in the C preprocessor... This sort of specialization is really better done with C++ templates (or maybe Rust or something). I had wanted to keep this a pure-C library, but maybe C++ might be better.

Hope some of that makes sense... I'm mostly thinking out loud here. In any case, you've given me a lot to think about, so thanks very much!

Thanks for the reply. I put some more thoughts on github.

BTW, I opened an issue to track this topic: https://github.com/zwegner/faster-utf8-validator/issues/3

Reply on news.ycombinator.com