5 ms·

> If you’re a fan of str::find, which is used to find a given char inside of a &str, you’ll be happy to see this pull request: it’s now 10x faster! This is than

> If you’re a fan of str::find, which is used to find a given char inside of a &str, you’ll be happy to see this pull request: it’s now 10x faster! This is thanks to memchr. Wait, how is that safe? Aren't Rust strings UTF-8? Even if you search for a ASCII character, couldn't it conflict with the second byte of a different unicode codepoint?

wolf550e 9y ago
An ASCII char would have its MSB 0 in UTF-8, and any byte in UTF-8 which is not a single ASCII char has its MSB as 1.
stouset 9y ago
https://github.com/rust-lang/rust/pull/46735 https://github.com/rust-lang/rust/pull/46735 TL;DR, it's not a naive straight `memchr`. `memchr` will generate false positives, then they use knowledge of UTF-8 to weed out the false positives. The pathological case is worse, but the overwhelming majority of cases are better.
Manishearth 9y ago
Sure, and the code deals with that case. https://github.com/rust-lang/rust/blob/5cf55165fae5c8538db5c00e252ad9ba42aaf246/src/libcore/str/pattern.rs#L314-L340 https://github.com/rust-lang/rust/blob/5cf55165fae5c8538db5c... This does mean you have some somewhat pathological cases, but they're relatively rare because most strings come from only a couple unicode blocks, so all bytes other than the first will be from a really small set. A further optimization could be to fall back to the original find code if we realize we're hitting a pathological case. (Also, FWIW, searching for an ASCII char can never cause this because of how UTF8's streaming property -- https://en.wikipedia.org/wiki/UTF-8#Description https://en.wikipedia.org/wiki/UTF-8#Description -- but given that we only search for the last byte, searching for a multibyte codepoint can lead to false positives with a shared last byte. We handle that.)
Felk 9y ago
If I'm not wrong, UTF-8 continuation bytes always start with binary 10, where ASCII always starts with 0 and multi-byte starts start with either 11 (2 bytes), 111 (3 bytes) or 1111 (4 bytes)
- paulddraper 9y ago
  Correct. This is what makes UTF-8 is "self-correcting", in that you can always find which code unit you are at for a code point.
- Manishearth 9y ago
  That doesn't solve the problem of searching for multibyte character AB and finding multibyte character CB instead :) Or, searching for multibyte character ABB (like U+A041 YI SYLLABLE PA) and finding the first "B" instead of the second "B". Sadly there's no memchr for consecutive sequences of characters. memchr2/memchr3 let you search for multiple needles in the haystack, not a bigger needle.
  - comex 9y ago
    There’s memmem...
    - burntsushi 9y ago
      memmem is substring search. You could use it for char search, but does memmem know about UTF-8? If, say, memmem uses memchr internally in a skip loop and it happens to look at the first byte in the UTF-8 encoded codepoint, then it is going to perform a lot worse in most cases involving the search of text that is in a language other than English (because it will wind up searching for a very common byte). Or maybe memmem does something else clever for shorter needles. Dunno. Best to benchmark it. But it's not an obvious win a priori.
      - Manishearth 9y ago
        I do want to see if a 2/3/4-byte memchr can be written that uses the same bitmasking as regular memchr but extended to more bits (perhaps via SIMD). That would be pretty neat.
        burntsushi 9y ago
        Yeah that's what I was thinking memmem might do. But yeah, I bet you that Hyperscan has a vectorized algorithm for this somewhere. It is just a matter of finding it.
masklinn 9y ago
UTF8 streams are self-synchronizing: an ASCII byte starts with 0, a most-significant byte starts with 11 and a continuation byte starts with 10. You can memchr for the last byte (either 0xxxxxxx for only byte or 10xxxxxx), then in the latter case go backwards to the MSB to see if the entire codepoint matches.
pixelbeat__ 9y ago
You can use strchr() for ascii, or strstr() otherwise. See utf8, searching section in http://www.pixelbeat.org/docs/utf8_programming.html http://www.pixelbeat.org/docs/utf8_programming.html

wolf550e 9y ago

An ASCII char would have its MSB 0 in UTF-8, and any byte in UTF-8 which is not a single ASCII char has its MSB as 1.

stouset 9y ago

https://github.com/rust-lang/rust/pull/46735 https://github.com/rust-lang/rust/pull/46735 TL;DR, it's not a naive straight `memchr`. `memchr` will generate false positives, then they use knowledge of UTF-8 to weed out the false positives. The pathological case is worse, but the overwhelming majority of cases are better.

Manishearth 9y ago

Sure, and the code deals with that case. https://github.com/rust-lang/rust/blob/5cf55165fae5c8538db5c00e252ad9ba42aaf246/src/libcore/str/pattern.rs#L314-L340 https://github.com/rust-lang/rust/blob/5cf55165fae5c8538db5c... This does mean you have some somewhat pathological cases, but they're relatively rare because most strings come from only a couple unicode blocks, so all bytes other than the first will be from a really small set. A further optimization could be to fall back to the original find code if we realize we're hitting a pathological case. (Also, FWIW, searching for an ASCII char can never cause this because of how UTF8's streaming property -- https://en.wikipedia.org/wiki/UTF-8#Description https://en.wikipedia.org/wiki/UTF-8#Description -- but given that we only search for the last byte, searching for a multibyte codepoint can lead to false positives with a shared last byte. We handle that.)

Felk 9y ago

If I'm not wrong, UTF-8 continuation bytes always start with binary 10, where ASCII always starts with 0 and multi-byte starts start with either 11 (2 bytes), 111 (3 bytes) or 1111 (4 bytes)

paulddraper 9y ago
Correct. This is what makes UTF-8 is "self-correcting", in that you can always find which code unit you are at for a code point.
Manishearth 9y ago
That doesn't solve the problem of searching for multibyte character AB and finding multibyte character CB instead :) Or, searching for multibyte character ABB (like U+A041 YI SYLLABLE PA) and finding the first "B" instead of the second "B". Sadly there's no memchr for consecutive sequences of characters. memchr2/memchr3 let you search for multiple needles in the haystack, not a bigger needle.
- comex 9y ago
  There’s memmem...
  - burntsushi 9y ago
    memmem is substring search. You could use it for char search, but does memmem know about UTF-8? If, say, memmem uses memchr internally in a skip loop and it happens to look at the first byte in the UTF-8 encoded codepoint, then it is going to perform a lot worse in most cases involving the search of text that is in a language other than English (because it will wind up searching for a very common byte). Or maybe memmem does something else clever for shorter needles. Dunno. Best to benchmark it. But it's not an obvious win a priori.
    - Manishearth 9y ago
      I do want to see if a 2/3/4-byte memchr can be written that uses the same bitmasking as regular memchr but extended to more bits (perhaps via SIMD). That would be pretty neat.
      - burntsushi 9y ago
        Yeah that's what I was thinking memmem might do. But yeah, I bet you that Hyperscan has a vectorized algorithm for this somewhere. It is just a matter of finding it.

masklinn 9y ago

UTF8 streams are self-synchronizing: an ASCII byte starts with 0, a most-significant byte starts with 11 and a continuation byte starts with 10. You can memchr for the last byte (either 0xxxxxxx for only byte or 10xxxxxx), then in the latter case go backwards to the MSB to see if the entire codepoint matches.

pixelbeat__ 9y ago

You can use strchr() for ascii, or strstr() otherwise. See utf8, searching section in http://www.pixelbeat.org/docs/utf8_programming.html http://www.pixelbeat.org/docs/utf8_programming.html