Interesting, how does it compare with StringZilla? It has highly optimized case-fold and case-insensitive Unicode search kernels as well: https://github.com/ashvardanian/Stringzilla
Don't stop early: Case-folding source code at memory speed
21–30 of 40 posts
Re: Don't stop early: Case-folding source code at memory speed
#22Earlier quoted context omitted.
Agreed. This is genuinely interesting content, but there is no doubt in my mind that "The two operations diverge on real characters—ß, İ, final sigma—which is why lowercasing as a stand-in silently produces wrong matches." is LLM output. Are we doomed to spend the rest of our professional and personal lives reading AI output?
Yes. > This is genuinely interesting Are you sure you're not an LLM yourself?
Has this become a ‘smell’? I tend to start my HN comments that are going be negative with versions of this, or my habitual “Genuine question, ..”; but if this is going to flag readers’ internal LLM-detector I will have to find some other way to indicate I’m actually interested in a dialogue (versus the shit posting that a more brief reply might signal).
I was talking with a junior at the office today about LLM output and mentioned em dashes, to which responded “oh, I thought that was just where formatting for hyphens was going, I guess I learned something from the AI writing instead of the other way around” and god, his acceptance of it was just deprrsssing.
Re: Don't stop early: Case-folding source code at memory speed
#23[dead]
Re: Don't stop early: Case-folding source code at memory speed
#24There’s some interesting information in there. Unfortunately the person or LLM writing this got pretty confused right in the introduction already.
> “Suppose […] they type straße and you’ve stored STRASSE. To make these count as matches, you need […]”
Really bad example, because as the article says later on, this casefold crate won’t match those two strings because the ß → ss conversion isn’t done.
> “[str::to_lowercase and case folding] diverge on real characters—ß, İ, final sigma”
The main point is true (case folding is different from lowercasing), but two of the three examples are wrong. The casefold operation that they use maps ß to itself, as does str::to_lowercase. The casefold operation maps İ to U+0069 U+0307 regardless of locale, as does str::to_lowercase.
When I’m reading an article, these kind of mistakes in the introduction make me doubt the accuracy of the whole article. Which is a shame, because again, it’s an interesting write-up. The mistakes also make the article harder to follow, since the examples imply ß is folded to ss.
Re: Don't stop early: Case-folding source code at memory speed
#25Interesting, how does it compare with StringZilla? It has highly optimized case-fold and case-insensitive Unicode search kernels as well: https://github.com/ashvardanian/Stringzilla
I think this is less about the actual use-case and more about the approach; so a comparison is moot.
Re: Don't stop early: Case-folding source code at memory speed
#26TLDR: they implemented case folding with a lot more SIMD via autovectorization. > almost every fold preserves the UTF-8 length or shrinks it, but two outliers grow—U+023A (Ⱥ) and U+023E (Ɀ) are 2 bytes each yet fold to 3-byte characters (ⱥ, ɀ) Fix this by reversing it. Fold ⱥ to Ⱥ instead of the other way around. The search index won't only consist of lowercase characters any more, but that never mattered.
+1 great idea. I get the impression that some of my sibling comments thought that you meant fold all code points in the opposite direction, but it it's clear you mean change the fold direction for only those two code points.
Re: Don't stop early: Case-folding source code at memory speed
#27TLDR: they implemented case folding with a lot more SIMD via autovectorization. > almost every fold preserves the UTF-8 length or shrinks it, but two outliers grow—U+023A (Ⱥ) and U+023E (Ɀ) are 2 bytes each yet fold to 3-byte characters (ⱥ, ɀ) Fix this by reversing it. Fold ⱥ to Ⱥ instead of the other way around. The search index won't only consist of lowercase characters any more, but that never mattered.
Curious if his isn’t some Over-optimization since how often do those characters ever come up.
If you can kill-off the extra buffer allocation code path that's got to be a win.
Re: Don't stop early: Case-folding source code at memory speed
#28One thing that wasn't tried is that the ASCII path could build a block-wise bitmap of non-ASCII blocks. Then the unicode pass need only process the contiguous ranges within the bitmap. This would be simpler to implement when combined with inigyou's no-reallocate suggestion.
Re: Don't stop early: Case-folding source code at memory speed
#29There’s some interesting information in there. Unfortunately the person or LLM writing this got pretty confused right in the introduction already. > “Suppose […] they type straße and you’ve stored STRASSE. To make these count as matches, you need […]” Really bad example, because as the article says later on, this casefold crate won’t match those two strings because the ß → ss conversion isn’t done. > “[str::to_lowerc…
Too late to edit, but the situation with İ is more complicated, and I got the mapping wrong for this specific casefold implementation.
What I should have said is that in the case of İ/i/I/ı, using str::to_lowercase for string matching wouldn’t be any less correct than using their locale-independent casefold.
The third character in the list, final sigma, is a good example that illustrates why using str::to_lowercase for string matching isn’t good.
Re: Don't stop early: Case-folding source code at memory speed
#30That's the first time I've seen some SIMD code reach more than about 10GB/s. 45 GiB/s is quite something, ASCII only. Of course they're not running the final code on an M4 mac, it will be on a server CPU of some kind. No mention of what sku of M4 mac they're using, it might not matter for single-thread code.