Don't stop early: Case-folding source code at memory speed
github.blog79 points by sbulaev 6 days ago
79 points by sbulaev 6 days ago
There’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.
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.
If anything, the word STRASSE is a great example why case-folding followed by string comparison is not the same as a case-independent string comparison
Or if you really want to do it, your case-folding needs to map certain lowercase characters to to other lowercase characters (lowercase ß to ss, lowercase ı to i, etc), losing some of the meaning
> If anything, the word STRASSE is a great example why case-folding followed by string comparison is not the same as a case-independent string comparison
s/case-folding/lowercasing/
Proper Unicode case-folding absolutely does map ß to ss, ς to σ, etc. Moreover, there are some scripts (IIRC Georgian) where for historical reasons case-folding yields uppercase letters, not lowercase ones. The case-folding mapping is specifically designed in concert with the comparison rules to yield the same result, that’s why it’s a separate operation from lowercasing.
(I believe the thing described in TFA is supposed to be proper case-folding in that sense, but given TFA is AI-written I wouldn’t trust its descriptions either way.)
That said, if you want to match the sort order customary in a specific language, you need to use language-specific rules for producing collation keys rather than generic case-folding. There’s no way out of this because different users of e.g. the Latin alphabet want contradictory results. And if you think you do want generic casefolding, then you probably actually want NFKC_Casefold instead unless your input is pre-normalized.
In some cases your're also lost ng all of the meaning. For example: aß/Ass, Maß/Mass, Buße/Busse, Floß/floss
This is good technical content, but it's obvious that an AI wrote it.
I actually came to the comments to share this snippet
> The hot operation isn’t really “fold this character,” it’s “does this character fold?” Almost always no.
Really that's distracting. If you must use LLMs, also do a rewrite pass that removes most LLMisms
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.
Yes, they say genuinely and honestly a lot. Because RLHF thinks that means they're genuine and honest.
I thought I wasn't, but you're making me second-guess myself.
It's just like when you're about to leave the store and suddenly wonder if you haven't accidentally left a 55" TV stashed into your backpocket. Gets me every time. :)
Yea, it's terse and clipped in some sentences, and then changes tone abruptly and randomly, and paragraphs really don't flow together at all. It feels awkward to read, and there is a lot more to read here than there needs to be...
Even the title sounds clunky: "Don't stop early", its correct but I think a human would have chosen something else.
TLDR: 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.
It does not look like the author posted this here since it was posted on the blog last week. So would probably be a better idea to suggest / recommend this at https://github.com/github/rust-gems/tree/main/crates/casefol...
Don't see why I should go out of my way to improve Microsoft shareholder value.
I wonder if making the index uppercase is strictly better in this sense, or if both upper and lowercase have chars that take more bytes.
> The search index won't only consist of lowercase characters any more
This isn't the case anyway. Unicode case-folding has a few lowercase-to-uppercase mappings, e.g. Cherokee
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.
This is a nice follow up to the other SIMD article that was posted here a week or so ago hah.
> We deal mostly with source code, so the text we fold is overwhelmingly ASCII and making it run at memory speed is the single most important thing we can do. Everything else just has to keep the rare non-ASCII path from spoiling it.
Semi-on-topic: I've noticed that many LLMs via coding agents (ChatGPT and Claude at work with my CoPilot account, and DeepSeek 4 and ChatGPT in pi.dev at home) really seem to like using unicode / emoji characters for things like arrows (for things like test value ranges), crosses and ticks (for pass vs fail in test comments), instead of plain ASCII. Codebases are almost exclusively ASCII chars to my knowledge, although they're UTF-8 files.
I'm not yet using agents to write code (only do code reviews, write example prototypes I then copy bits of, and helping craft tests), but I'm likely to get there soon, and I'm sure it's possible to prompt them NOT to do this, but has anyone else noticed this? I wonder if that changes things over time for them if this is a common theme of increased non-ASCII output?
Codebases written by native English speakers are almost exclusively ASCII, but codebases written by speakers of languages other than English frequently have non-ASCII content, even if only in the comments, but languages which support it often wind up with non-ASCII identifiers, too.
I do not believe that emoji like crosses and ticks are particularly common at all, for any language, but LLMs seem to have picked up heavy use of them from somewhere and inserted them into code (and everything else) they generate.
LLM training sets will very likely include the massive corpos of non-English open source code from sites like Gitee, but would be unlikely to generate responses heavily influenced by them unless you've done specific things to make that happen - prompt in Chinese, try to make use of a library only available with Chinese source and/or documentation, perhaps. I've not seen it happen, but I am a light user of LLMs.
A lot of good repos (CLIs, frameworks) had 'tree' unicode directory structure with like ├──, └──, and │ , as well as emojis for passing/failed tests and README docs maybe a unicode arrow or two, but LLMs absolutely overuse it.
I don't know why chatbots prefer → over -> so much. It's becoming a countersignal compared to the old terminal customization era, where arrow ligatures were a signal of effort.
Perhaps there was heavy weighting of swift code [1] ;)
I would just paste the example, but HN code block display appears to think it's as unreasonable as I do.
[1] https://wolfmcnally.com/121/programming-with-fruit-using-emo...
Using emoji for status indicators on the console is a trend that pre-dates LLMs. First mainstream app I can recall doing it was Yarn.
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
I think this is less about the actual use-case and more about the approach; so a comparison is moot.
That'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.
One 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.
[flagged]
[flagged]
[dead]