John Keiser, Daniel Lemire
2020 · arXiv
The majority of text is stored in UTF-8, which must be validated on ingestion. We present the lookup algorithm, which outperforms UTF-8 validation routines used in many libraries and languages by more than 10 times using commonly available SIMD instructions. To ensure reproducibility, our work is freely available as open source software.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
3 selected excerpts · 3 total mentions
Good paper on UTF-8 validation performance: https://arxiv.org/pdf/2010.03090 The relatively simple algorithm (lookup) can be several times faster than conventional algorithms at a common task using nothing more than the instructions available on commodity processors. It requires fewer than an instruction per input byte in the worst case.
From https://github.com/websockets/utf-8-validate/tree/master/dep... > This C++ library is part of the JavaScript package utf-8-validate. The utf-8-validate package is routinely downloaded more than a million times per week. > If you are using Node JS (19.4.0 or better), you already have access to this function as buffer.isUtf8(input). And at https://github.com/websockets/utf-8-validate/tree/master/dep... > # Reference > John Keiser, Daniel Lemire, [Validating UTF-8 In Less Than One Instruction Per Byte](https://arxiv.org/abs/2010.03090), Software: Practice & Experience 51 (5), 2021
Modern CPUs can look ahead in the instruction stream and run 4 or more instructions simultaneously. This isn't easy: you have to respect data dependencies where one instruction depends on the output of a previous one. When something depends on a load instruction that missed in the cache, CPUs can keep going farther ahead and do some other work while waiting for load to complete. This "speculative out-of-order execution" requires a huge number of transistors to consider various combinations of future instructions it might be able to execute every clock cycle, and burns some extra power doing that. So although most of the basic ideas were known by the late 90s, adding more…
transistors in every generation lets it do more and more in parallel. Also, faster and larger caches cause fewer stalls. Also, modern cores are better at predicting branches, so they can proceed to start executing instructions past a branch before knowing which way the branch is going to go. If it guessed wrong about the branch, it has to undo the results of some instructions. So it adds a lot of complexity to track each side-effect that might need to be canceled. Also, SIMD parallel has gotten much better. Some modern cores can do 8 floating point operations per cycle using AVX2 or Neon. While older SIMD systems had very limited instructions sets, you can do a lot with modern ones. x86 SIMD instructions can process 32 bytes at a time. With a great deal of cleverness, you can do some byte stream operations in less than one cycle per byte. See https://arxiv.org/abs/2010.03090 GPUs generally do 32 parallel floating point operations per core per cycle, with hundreds of cores. Also, main memory is gradually getting slightly faster and wider. Lastly, more cores are good. Back when the most cores you could get was 4, it was barely worth writing parallel software because all the locking slowed things down almost as much as the 4 cores speeded things up. But high-end Xeons can have 40+ cores, which makes it worth the hassle of writing parallel code. And GPUs have 1000s of cores, so it's worth a lot of complication to make use of them.
More from the same topics.
Anders Sandberg, Eric Drexler, Toby Ord
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
Donald E. Knuth
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.