Comment by Sidnicious | Hacker News Reader

Comment by Sidnicious | Hacker News Reader

I ran into the same UTF-8 decoder that you did (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

Benchmarks: https://gist.github.com/s4y/344a355f8c1f99c6a4cb2347ec4323cc

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

The simplest thing to do there is to issue a read if you have less than 4 bytes remaining to decode. This guarantees that you always have at least one well formed character, or an EOF coming up.

Mmap doesn't work with pipes, which hugely reduces the utility of this kind of program.

You aren’t reading a byte at a time, it’s a block. You have no guarantee that you just ended on yet another partial sequence. It usually makes more sense to just rewind to the last complete sequence (though with streams that is not always an option).

> You have no guarantee that you just ended on yet another partial sequence

Which is why you don't read to the end (until you have an EOF). You can just sidestep the partial sequence problem by getting more data before there's potential for a partial sequence to show up. The longest possible sequence is 4 bytes, so as long as you ensure you have 4 bytes available, partial sequences are impossible on well formed input.

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

A couple of years ago, I made the same exercise and, when benchmarking several real-world languages, I got similar results. On a slowish Intel CPU (from my memory):

  DFA-based decoder: ~400 MB/s
  Naive decoder with ASCII: ~1.2 GB/s
  Naive decoder with with most Western languages: ~1.0 GB/s
  Naive decoder with with Russian, Chinese, Japanese: ~800 MB/s

Branch prediction of modern CPUs is so good that it's hard to beat the naive if-else chain with real-world data. Interestingly, I got the worst performance with heavily accented Eastern European languages like Czech where performance dropped to 600-700 MB/s.

> Branch prediction of modern CPUs is so good

Modern x86 CPUs. ARM branch prediction is much worse, unfortunately.

Your decoder accepts lone surrogates and overlong sequences.

This probably helps a bit for speed.

Reply on news.ycombinator.com