Rust 1.24
blog.rust-lang.org
Rust 1.24
1–10 of 215 posts
Re: Rust 1.24
#2Incremental compilation turned on by default :-)
Re: Rust 1.24
#3> 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?
Re: Rust 1.24
#4> 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?
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.
Re: Rust 1.24
#5> 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?
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.
Re: Rust 1.24
#6> 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?
Sure, and the code deals with that case.
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 -- 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.)
Re: Rust 1.24
#7> 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?
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)
Re: Rust 1.24
#8> 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?
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)
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.
Re: Rust 1.24
#9> 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?
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.
Re: Rust 1.24
#10> 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?
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)
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.