Don't stop early: Case-folding source code at memory speed
Comments
lukasgelbmann
zX41ZdbW
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
pistoriusp
I think this is less about the actual use-case and more about the approach; so a comparison is moot.
claudetard
This is good technical content, but it's obvious that an AI wrote it.
nextaccountic
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
Groxx
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...
agency
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?
inigyou
Yes.
> This is genuinely interesting
Are you sure you're not an LLM yourself?
throwaway17_17
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.
agency
I thought I wasn't, but you're making me second-guess myself.
inigyou
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.
RossBencina
+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.
gwking
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.
Georgelemental
> 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
goalieca
Curious if his isn’t some Over-optimization since how often do those characters ever come up.
RossBencina
If you can kill-off the extra buffer allocation code path that's got to be a win.
persedes
This is a nice follow up to the other SIMD article that was posted here a week or so ago hah.
RossBencina
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.
pixelesque
> 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?
codebje
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.
pyentropy
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.
nomel
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...
chuckadams
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.
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.