4 ms·

High speed Unicode routines using SIMD

126 points by Peter5 4y ago

erk__ 4y ago
IBM's Z/Architecture mainframes have native support for some of these functions, it could be interesting to see how the speed compares
- aqrit 4y ago
  One of the authors/contributors was looking into it: https://old.reddit.com/r/mainframe/comments/wevyvg/whats_the_performance_of_cu12_and_cu21_on_modern/iitbyu4/ https://old.reddit.com/r/mainframe/comments/wevyvg/whats_the... I don't think this project was ready for a public announcement, yet.
vanderZwan 4y ago
The readme has a link to a technical paper on arxiv that was uploaded last year[0], has that perhaps been discussed before? (not meant as a complaint that this might have been submitted before already, I'm just curious about what might have already been said about it) [0] https://arxiv.org/abs/2109.10433 https://arxiv.org/abs/2109.10433
- deleted 4y ago
  [deleted]
- michelb 4y ago
  Mabye this? https://news.ycombinator.com/item?id=26887438 https://news.ycombinator.com/item?id=26887438
  - vanderZwan 4y ago
    Thanks! That looks more like an name-adjacent repo tackling the same topic than a direct port. However, that doesn't really matter since most of the discussion is still relevant given the overlap :)
- belter 4y ago
  "Fast UTF-8 validation" - https://news.ycombinator.com/item?id=24839113 https://news.ycombinator.com/item?id=24839113
  - vanderZwan 4y ago
    Thank you, looks like a satisfyingly meaty discussion from a technical standpoint too.
- Peter5 4y ago
  I searched for it and couldn't find a match. I chose the code instead of the document, as the repository links to the paper too, and almost always, code is more welcome than a paper.
jansan 4y ago
I do not know about the real world implications of this, but just reading of a 20x performance increase for standard cases makes me excited.
- dhosek 4y ago
  There are some basic things that can give huge performance increases without even parallelization: I wrote a Unicode crate because I needed a different interface to getting grapheme clusters from a string than the existing crates offered. I wrote a character category crate as well because I thought I would need it for this purpose (I didn’t). I managed to get double the performance of the existing segmentation crate and 10–20x the performance of the existing Unicode category crate. https://crates.io/crates/finl_unicode https://crates.io/crates/finl_unicode
  - rurban 4y ago
    All with two-step tables instead of range- and binary search? That's extremely interesting, as I'm still favoring range- and binary search for most cases, just normalization lookup with two-step tables.
    - dhosek 4y ago
      Yes. The two-step tables are really not that expensive and they enable features not possible with range and binary search, like identifying the category of a character cheaply.
dragontamer 4y ago
I dunno much about Unicode, but I imagine it is a regular language? (Aka: acception / rejection can be determined by regular expressions / finite state machines) If so, regular languages are one of those 'surprising things that can be parallelized'. It doesn't seem possible at first thought though.
- lifthrasiir 4y ago
  Just in case, here "Unicode routines" refer to Unicode encoding routines, not other more complex things like normalization. They are pretty regular but their automata would be relatively simple. (By the way, SIMD-accelerated regular expression parsing is indeed a thing [1], if anyone wondered.) [1] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
  - wooosh 4y ago
    Intel has an implementation of this technique here as well: https://github.com/intel/hyperscan https://github.com/intel/hyperscan
  - nextaccountic 4y ago
    ripgrep also uses simd https://news.ycombinator.com/item?id=19271497 https://news.ycombinator.com/item?id=19271497
- yxhuvud 4y ago
  That a regular language may be parallelized does not mean all can be. That said, there are techniques around to evaluate a context free grammars (and thus also regular grammars) in parallel. One way to do it is as follows: Break up the input string into n separate strings. The processing of the first string starts at a single state, the starting state. Each other string starts at the set of possible states, with the output being a mapping between state at the first character to the state after the last. Then at the end the output is stitched together.
  - 4y ago
Genbox 4y ago
I'm at the point where I can no longer see any reason to use UTF-16. UTF-8 is used everywhere today and constantly converting between the two is not only inefficient, but also introduce a risk of bugs/corruption.
- jahewson 4y ago
  Yes it’s annoying that we’re stuck with UTF-16 inside many programming languages. Still, I think it’s better than having two types of string (C, C++) or introducing a breaking change (looking at you Python 3).

126 points by Peter5 4y ago

IBM's Z/Architecture mainframes have native support for some of these functions, it could be interesting to see how the speed compares

aqrit 4y ago
One of the authors/contributors was looking into it: https://old.reddit.com/r/mainframe/comments/wevyvg/whats_the_performance_of_cu12_and_cu21_on_modern/iitbyu4/ https://old.reddit.com/r/mainframe/comments/wevyvg/whats_the... I don't think this project was ready for a public announcement, yet.

vanderZwan 4y ago

The readme has a link to a technical paper on arxiv that was uploaded last year[0], has that perhaps been discussed before? (not meant as a complaint that this might have been submitted before already, I'm just curious about what might have already been said about it) [0] https://arxiv.org/abs/2109.10433 https://arxiv.org/abs/2109.10433

deleted 4y ago
[deleted]
michelb 4y ago
Mabye this? https://news.ycombinator.com/item?id=26887438 https://news.ycombinator.com/item?id=26887438
- vanderZwan 4y ago
  Thanks! That looks more like an name-adjacent repo tackling the same topic than a direct port. However, that doesn't really matter since most of the discussion is still relevant given the overlap :)
belter 4y ago
"Fast UTF-8 validation" - https://news.ycombinator.com/item?id=24839113 https://news.ycombinator.com/item?id=24839113
- vanderZwan 4y ago
  Thank you, looks like a satisfyingly meaty discussion from a technical standpoint too.
Peter5 4y ago
I searched for it and couldn't find a match. I chose the code instead of the document, as the repository links to the paper too, and almost always, code is more welcome than a paper.

jansan 4y ago

I do not know about the real world implications of this, but just reading of a 20x performance increase for standard cases makes me excited.

dhosek 4y ago
There are some basic things that can give huge performance increases without even parallelization: I wrote a Unicode crate because I needed a different interface to getting grapheme clusters from a string than the existing crates offered. I wrote a character category crate as well because I thought I would need it for this purpose (I didn’t). I managed to get double the performance of the existing segmentation crate and 10–20x the performance of the existing Unicode category crate. https://crates.io/crates/finl_unicode https://crates.io/crates/finl_unicode
- rurban 4y ago
  All with two-step tables instead of range- and binary search? That's extremely interesting, as I'm still favoring range- and binary search for most cases, just normalization lookup with two-step tables.
  - dhosek 4y ago
    Yes. The two-step tables are really not that expensive and they enable features not possible with range and binary search, like identifying the category of a character cheaply.

dragontamer 4y ago

I dunno much about Unicode, but I imagine it is a regular language? (Aka: acception / rejection can be determined by regular expressions / finite state machines) If so, regular languages are one of those 'surprising things that can be parallelized'. It doesn't seem possible at first thought though.

lifthrasiir 4y ago
Just in case, here "Unicode routines" refer to Unicode encoding routines, not other more complex things like normalization. They are pretty regular but their automata would be relatively simple. (By the way, SIMD-accelerated regular expression parsing is indeed a thing [1], if anyone wondered.) [1] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- wooosh 4y ago
  Intel has an implementation of this technique here as well: https://github.com/intel/hyperscan https://github.com/intel/hyperscan
- nextaccountic 4y ago
  ripgrep also uses simd https://news.ycombinator.com/item?id=19271497 https://news.ycombinator.com/item?id=19271497
yxhuvud 4y ago
That a regular language may be parallelized does not mean all can be. That said, there are techniques around to evaluate a context free grammars (and thus also regular grammars) in parallel. One way to do it is as follows: Break up the input string into n separate strings. The processing of the first string starts at a single state, the starting state. Each other string starts at the set of possible states, with the output being a mapping between state at the first character to the state after the last. Then at the end the output is stitched together.
- 4y ago

Genbox 4y ago

I'm at the point where I can no longer see any reason to use UTF-16. UTF-8 is used everywhere today and constantly converting between the two is not only inefficient, but also introduce a risk of bugs/corruption.

jahewson 4y ago
Yes it’s annoying that we’re stuck with UTF-16 inside many programming languages. Still, I think it’s better than having two types of string (C, C++) or introducing a breaking change (looking at you Python 3).