Full Unicode Search at 50× ICU Speed with AVX‑512

Posted by ashvardanian 1 day ago

Comments

Comment by bbminner 5 hours ago

I was really confused about the case folding, this page explained the motivation well https://jean.abou-samra.fr/blog/unicode-misconceptions

""" Continuing with the previous example of “ß”, one has lowercase("ss") != lowercase("ß") but uppercase("ss") == uppercase("ß"). Conversely, for legacy reasons (compatibility with encodings predating Unicode), there exists a Kelvin sign “K”, which is distinct from the Latin uppercase letter “K”, but also lowercases to the normal Latin lowercase letter “k”, so that uppercase("K") != uppercase("K") but lowercase("K") == lowercase("K").

The correct way is to use Unicode case folding, a form of normalization designed specifically for case-insensitive comparisons. Both casefold("ß") == casefold("ss") and casefold("K") == casefold("K") are true. Case folding usually yields the same result as lowercasing, but not always (e.g., “ß” lowercases to itself but case-folds to “ss”). """

One question I have is why have Kelvin sign that is distinct from Latin K and other indistinguishable symbols? To make quantified machine readable (oh, this is not a 100K license plate or money amount, but a temperature)? Or to make it easier for specialized software to display it in correct placed/units?

Comment by bee_rider 5 hours ago

They seem to have (if I understand correctly) degree-Celsius and degree-Fahrenheit symbols. So maybe Kelvin is included for consistency, and it just happens to look identical to Latin K?

IMO the confusing bit is giving it a lower case. It is a symbol that happens to look like an upper case, not an actual letter…

Comment by bigwheels 5 hours ago

And why can't the symbol be a regular old uppercase "K"? Who is this helping?

Comment by infogulch 5 hours ago

Unicode wants to be able to preserve round-trip re-encoding from this other standard which has separate letter-K and degree-K characters. Making these small sacrifices for compatibility is how Unicode became the defacto world standard.

Comment by shiomiru 4 hours ago

The "other standard" in this case being IBM-944. (At least looking at https://www.unicode.org/versions/Unicode1.0.0/ch06.pdf p. 574 (=110 in the PDF) I only see a mapping from U+212A to that one.)

Comment by infogulch 2 hours ago

A deeper explanation by Grok:

> The Kelvin sign (K, Unicode U+212A) is included as a distinct character in certain legacy East Asian character encodings, including those based on the South Korean national standard KS X 1001 (formerly KS C 5601), which influenced IBM code pages supporting Korean text. ... The Kelvin sign was added to support distinct representation of the kelvin unit in scientific contexts, possibly reflecting typographic conventions where a stylized or script-like "K" distinguished the unit from the ordinary letter "K".

- https://grok.com/share/bGVnYWN5_62023ec2-efb0-4897-b8cf-6f71...

Comment by shiomiru 1 hour ago

That "deeper explanation" seems incorrect, considering that the KSC column is empty in the mapping linked above.

Comment by kahirsch 1 hour ago

The ICU mappings files have entries for U212A in the following files:

    gb18030.ucm
    ibm-1364_P110-2007.ucm
    ibm-1390_P110-2003.ucm
    ibm-1399_P110-2003.ucm
    ibm-16684_P110-2003.ucm
    ibm-933_P110-1995.ucm
    ibm-949_P110-1999.ucm
    ibm-949_P11A-1999.ucm

Comment by bee_rider 5 hours ago

I think just using uppercase Latin K is the recommendation.

But, I dunno. Why would anybody apply upper or lower case operators to a temperature measurement? It just seems like a nonsense thing to do.

Comment by zygentoma 4 hours ago

Maybe not for text to be read again, but might be sensible e.g. for slug or file name generation and the like...

Comment by Eisenstein 4 hours ago

I wonder if you can register a domain with it in the name.

Comment by bawolff 50 minutes ago

> One question I have is why have Kelvin sign that is distinct from Latin K and other indistinguishable symbols?

Unicode has the goal of being a 1:1 mapping for all other character encodings. Usually weird things like this is so there can be a 1:1 reversible mapping to some ancient character encoding.

Comment by ashvardanian 8 hours ago

This article is about the ugliest — but arguably the most important — piece of open-source software I’ve written this year. The write-up ended up long and dense, so here’s a short TL;DR:

I grouped all Unicode 17 case-folding rules and built ~3K lines of AVX-512 kernels around them to enable fully standards-compliant, case-insensitive substring search across the entire 1M+ Unicode range, operating directly on UTF-8 bytes. In practice, this is often ~50× faster than ICU, and also less wrong than most tools people rely on today—from grep-style utilities to products like Google Docs, Microsoft Excel, and VS Code.

StringZilla v4.5 is available for C99, C++11, Python 3, Rust, Swift, Go, and JavaScript. The article covers the algorithmic tradeoffs, benchmarks across 20+ Wikipedia dumps in different languages, and quick starts for each binding.

Thanks to everyone for feature requests and bug reports. I'll do my best to port this to Arm as well — but first, I'm trying to ship one more thing before year's end.

Comment by dboon 4 hours ago

This is exactly the kind of thankless software which the world operates on. It’s unfortunate that such fundamental code hasn’t already been vectorized or the gills, but thank you for doing so! It’s excellent work

Comment by Sesse__ 3 hours ago

> I grouped all Unicode 17 case-folding rules

But why are you using the case-folding rules and not the collation rules?

Comment by ashvardanian 3 hours ago

Yes, CaseFolding.txt. I'm considering using the collation rules for sorting. Now they only target lexicographic comparisons and seem to be 4x faster than Rust's standard quick-sort implementation, but few people use it: https://github.com/ashvardanian/StringWars?tab=readme-ov-fil...

Comment by adzm 7 hours ago

This is a truly amazing accomplishment. Reading these kernels is a joy!

Comment by fatty_patty89 7 hours ago

Thank you

do the go bindings require cgo?

Comment by ashvardanian 7 hours ago

The GoLang bindings – yes, they are based on cGo. I realize it's suboptimal, but seems like the only practical option at this point.

Comment by fatty_patty89 7 hours ago

In a normal world the Go C FFI wouldn't have insane overhead but what can we do, the language is perfect and it will stay that way until morale improves.

Thanks for the work you do

Comment by kbolino 6 hours ago

There are undoubtedly still some optimizations lying around, but the biggest source of Go's FFI overhead is goroutines.

There's only two "easy" solutions I can see: switch to N:N threading model or make the C code goroutine-aware. The former would speed up C calls at the expense of slowing down lots of ordinary Go code. Personally, I can still see some scenarios where that's beneficial, but it's pretty niche. The latter would greatly complicate the use of cgo, and defeat one of its core purposes, namely having access to large hard-to-translate C codebases without requiring extensive modifications of them.

A lot of people compare Go's FFI overhead to that of other natively compiled languages, like Zig or Rust, or to managed runtime languages like Java (JVM) or C# (.NET), but those alternatives don't use green threads (the general concept behind goroutines) as extensively. If you really want to compare apples-to-apples, you should compare against Erlang (BEAM). As far as I can tell, Erlang NIFs [1] are broadly similar to purego [2] calls, and their runtime performance [3] has more or less the same issues as CGo [4].

[1]: https://www.erlang.org/doc/system/nif.html

[2]: https://pkg.go.dev/github.com/ebitengine/purego

[3]: https://erlang.org/documentation/doc-10.1/doc/efficiency_gui...

[4]: https://www.reddit.com/r/golang/comments/12nt2le/when_dealin...

Comment by fatty_patty89 5 hours ago

Java has green threads and c#/.net has logical threads

Comment by kbolino 5 hours ago

Yes, I have cleaned up the wording a bit. Also, the common implementation of Rust's async is comparable to green threads, and I think Zig is adopting something like it too.

However, the "normal" execution model on all of them is using heavyweight native threads, not green threads. As far as I can tell, FFI is either unsupported entirely or has the same kind of overhead as Go and Erlang do, when used from those languages' green threads.

Comment by fatty_patty89 4 hours ago

Genuine question, you make it seem as this is a limitation and they're all in the same bucket but how was Java for example able to scale all the enterprises while having multi threading and good ffi, same with .net.

My impression is that the go ffi is with big overhead because of the specific choices made to not care about ffi because it would benefit the go code more?

My point was that there's other gc languages/envorionments that have good ffi and were somehow able all these decades to create scalable multithreaded applications.

Comment by kbolino 3 hours ago

I would suggest gaining a better understanding of the M:N threading model versus the N:N threading model. I do not know that I can do it justice here.

Both Java and Rust flirted with green threads in their early days. Java abandoned them because the hardware wasn't ready yet, and Rust abandoned them because they require a heavyweight runtime that wasn't appropriate for many applications Rust was targeting. And yet, both languages (and others besides) ended up adding something like them in later anyway, albeit sitting beside, rather than replacing, the traditional N:N threading they primarily support.

Your question might just be misdirected; one could view it as operating systems, and not programming languages per se, that screwed it all up. Their threads, which were conservatively designed to be as compatible as possible with existing code, have too much overhead for many tasks. They were good enough for awhile, especially as multicore systems started to enter the scene, but their limitations became apparent after e.g. nginx could handle 10x the requests of Apache httpd on the same hardware. This gap would eventually be narrowed, to some extent, but it required a significant amount of rework in Apache.

If you can answer the question of why ThreadPoolExecutor exists in Java, then you are about halfway to answering the question about why M:N threading exists. The other half is mostly ergonomics; ThreadPoolExecutor is great for fanning out pieces of a single, subdividable task, but it isn't great for handling a perpetual stream of unrelated tasks that ebb and flow over time. EDIT: See the Project Loom proposal for green threads in Java today, which also brings up the ForkJoinPool, another approach to M:N threading: https://cr.openjdk.org/~rpressler/loom/Loom-Proposal.html

Comment by neonsunset 3 hours ago

[dead]

Comment by kardianos 7 hours ago

In a real (not "normal") world, trade-offs exist and Go choose a specific set of design points that are consequential.

Comment by unwind 8 hours ago

Very cool and impressive performance.

I was worried (I find it confusing when Unicode "shadows" of normal letters exist, and those are of course also dangerous in some cases when they can be mis-interpreted for the letter they look more or less exactly like) by the article's use of U+212A (Kelvin symbol) as sample text, so I had to look it up [1].

Anyway, according to Wikipedia the dedicated symbol should not be used:

However, this is a compatibility character provided for compatibility with legacy encodings. The Unicode standard recommends using U+004B K LATIN CAPITAL LETTER K instead; that is, a normal capital K.

That was comforting, to me. :)

[1]: https://en.wikipedia.org/wiki/Kelvin#Orthography

Comment by jjmarr 7 hours ago

> I find it confusing when Unicode "shadows" of normal letters exist, and those are of course also dangerous in some cases when they can be mis-interpreted for the letter they look more or less exactly like

Isn't this why Unicode normalization exists? This would let you compare Unicode letters and determine if they are canonically equivalent.

Comment by Sesse__ 6 hours ago

It's why the Unicode Collation Algorithm exists.

If you look in allkeys.txt (the base UCA data, used if you don't have language-specific stuff in your comparisons) for the two code points in question, you'll find:

  004B  ; [.2514.0020.0008] # LATIN CAPITAL LETTER K
  212A  ; [.2514.0020.0008] # KELVIN SIGN

The numbers in the brackets are values on level 1 (base), level 2 (typically used for accents), level 3 (typically used for case). So they are to compare identical under the UCA, in almost every case except for if you really need a tiebreaker.

Compare e.g. :

  1D424 ; [.2514.0020.0005] # MATHEMATICAL BOLD SMALL K

which would compare equal to those under a case-insensitive accent-sensitive collation, but _not_a case-sensitive one (case-sensitive collations are always accent-sensitive, too).

Comment by happytoexplain 5 hours ago

Are the meanings for the levels for each code point defined somewhere (accent, casing, etc)?

Comment by Sesse__ 3 hours ago

Typically it is defined by the collation. For the default collation, where all the weights are as in the file, it's none/accent/accent+case. But if you go to e.g. Japanese, you can have a fourth level of “kana-sensitive” (which distinguishes between e.g. katakana and hiragana).

Comment by ComputerGuru 7 hours ago

Normalization wouldn’t address this.

Comment by happytoexplain 6 hours ago

What do you mean? All four normal forms of the Kelvin 'K' are the Latin 'K', as far as I can tell.

Comment by nwellnhof 6 hours ago

Normalization forms NFKC and NFKD that also handle compatibility equivalence do.

Comment by mananaysiempre 6 hours ago

A few deprecated characters, including the Kelvin and Ångström symbols, are in fact canonically equivalent to their replacements and not just compatibility equivalent, so plain NFC/NFD is enough. (It’s generally better to avoid NFKC/NFKD normalizations unless you fully understand the implications, as they do lose meaning and at the same time do not account for all possible confusables.)

Comment by bawolff 48 minutes ago

While this is definitely really cool, wouldn't people who need this type of speed usually just store the text to be searched already case folded?

Comment by orthoxerox 8 hours ago

Is it possible to extend this to support additional transformation rules like Any-Latin;Latin-ASCII? To make it possible to find "Վարդանյան" in a haystack by searching for "vardanyan"?

Comment by ashvardanian 8 hours ago

Yes — fuzzy and phonetic matching across languages is part of the roadmap. That space is still poorly standardized, so I wanted to start with something widely understood and well-defined (ICU-style transforms) before layering on more advanced behavior.

Also, as shown in the later tables, the Armenian and Georgian fast paths still have room for improvement. Before introducing higher-level APIs, I need to tighten the existing Armenian kernel and add a dedicated one for Georgian. It’s not a true bicameral script, but some characters are folding fold targets for older scripts, which currently forces too many fallbacks to the serial path.

Comment by mgaunard 9 hours ago

In practice you should always normalize your Unicode data, then all you need to do is memcmp + boundary check.

Interestingly enough this library doesn't provide grapheme cluster tokenization and/or boundary checking which is one of the most useful primitive for this.

Comment by stingraycharles 8 hours ago

That’s not practical in many situations, as the normalization alone may very well be more expensive than the search.

If you’re in control of all data representations in your entire stack, then yes of course, but that’s hardly ever the case and different tradeoffs are made at different times (eg storage in UTF-8 because of efficiency, but in-memory representation in UTF-32 because of speed).

Comment by mgaunard 8 hours ago

That doesn't make sense; the search is doing on-the-fly normalization as part of its algorithm, so it cannot be faster than normalization alone.

Comment by ashvardanian 8 hours ago

I get why it sounds that way, but it’s not actually true.

StringZilla added full Unicode case folding in an earlier release, and had a state-of-the-art exact case-sensitive substring search for years. However, doing a full fold of the entire haystack is significantly slower than the new case-insensitive search path.

The key point is that you don’t need to fully normalize the haystack to correctly answer most substring queries. The search algorithm can rule out the vast majority of positions using cheap, SIMD-friendly probes and only apply fold logic on a very small subset of candidates.

I go into the details in the “Ideation & Challenges in Substring Search” section of the article

Comment by Const-me 8 hours ago

> it cannot be faster than normalization alone

Modern processors are generally computing stuff way faster than they can load and store bytes from main memory.

The code which does on the fly normalization only needs to normalize a small window. If you’re careful, you can even keep that window in registers, which have single CPU cycle access latency and ridiculously high throughput like 500GB/sec. Even if you have to store and reload, on-the-fly normalization is likely to handle tiny windows which fit in the in-core L1D cache. The access cost for L1D is like ~5 cycles of latency, and equally high throughput because many modern processors can load two 64-bytes vectors and store one vector each and every cycle.

Comment by mgaunard 7 hours ago

The author published the bandwidth of its algo, it's one fifth of a typical memory bandwidth (it's not possible to go faster than memory obviously for this benchmark, since we're assuming the data is not in cache).

Comment by stingraycharles 8 hours ago

It can, because of how CPUs work with registers and hot code paths and all that.

First normalizing everything and then comparing normalized versions isn’t as fast.

And it also enables “stopping early” when a match has been found / not found, you may not actually have to convert everything.

Comment by mgaunard 7 hours ago

Running more code per unit of data does not make the code hotter or reduce the register pressure, quite the opposite...

Comment by stingraycharles 7 hours ago

You’re misunderstanding: you just convert to 32 bits once and reuse that same register all the time.

You’re running the exact same code, but are more more efficient in terms of “I immediately use the data for comparison after converting it”, which means it’s likely either in a register or L1 cache already.

Comment by orthoxerox 8 hours ago

In practice the data is not always yours to normalize. You're not going to case-fold your library, but you still want to be able to search it.

Comment by moralestapia 6 hours ago

Ash is amazing!

Also very cool and approachable guy.

(Best wishes if you're reading this.)

Comment by hans_castorp 6 hours ago

Would be cool if that could be integrated into Postgres :)

Comment by ashvardanian 5 hours ago

I was just about to ask some friends about it. If I’m not mistaken, Postgres began using ICU for collation, but not string matching yet. Curious if someone here is working in that direction?

Comment by kardianos 6 hours ago

Looks neat. What are all the genomic sequence comparisons in there for? Is this a grab bag of interesting string methods or is there a motivation for this?

Comment by ashvardanian 6 hours ago

Levenshtein distance calculations are a pretty generic string operation, Genomics happens to be one of the domains where they are most used... and a passion of mine :)

Comment by anonnon 5 hours ago

> ICU has bindings for Rust that provide case-folding functionality, but not case-insensitive substring search.

> ICU has many bindings. The Rust one doesn’t expose any substring search functionality, but the Python one does:

Python's ICU support is based on ICU4C. Rust's ICU "bindings" are actually a new implementation called ICU4X, by developers who worked on i18n at Mozilla and Google and on ICU4C, with the goal of a cleaner, more performant implementation that is also memory safe. Maybe not relevant (as in substantially altering the benchmarks), but it's at least worth noting that the ICU backends aren't consistent throughout.

Comment by ashvardanian 5 hours ago

Thanks a lot for the correction! I'll adjust the references in a bit.

Comment by xking5205 8 hours ago

its good

Comment by andersa 9 hours ago

From a German user perspective, ICU and your fancy library are incorrect, actually. Mass is not a different casing of Maß, they are different characters. Google likely changed this because it didn't do what users wanted.

Comment by Arnt 8 hours ago

Ah, let's have a long discussion of this.

Unicode avoids "different" and "same", https://www.unicode.org/reports/tr15/ uses phrases like compatibility equivalence.

The whole thing is complicated, because it actually is complicated in the real world. You can spell the name of Gießen "Giessen" and most Germans consider it correct even if not ideal, but spelling Massachusetts "Maßachusetts" is plainly wrong in German text. The relationship between ß and ss isn't symmetric. Unicode captures that complexity, when you get into the fine details.

Comment by pjmlp 8 hours ago

It isn't until it is, how would you write it when ß isn't available on the keyboard?

Which is why we also have to deal with the ue, ae, oe kind of trick, also known as Ersatzschreibweise.

Then German language users from de-CH region, consider Mass the correct way.

Yeah, localization and internalization is a mess to get right.

Comment by wat10000 8 hours ago

Case insensitivity is localized like anything else. I and i are equivalent, right? Not if you’re doing Turkish, then it’s I and ı, and İ and i.

In practice you can do pretty well with a universal approach, but it can’t be 100% correct.

Comment by ashvardanian 7 hours ago

This is a very good example! Still, “correct” needs context. You can be 100% “correct with respect to ICU”. It’s definitely not perfect, but it’s the best standard we have. And luckily for me, it also defines the locale-independent rules. I can expand to support locale-specific adjustments in the future, but waiting for the adoption to grow before investing even more engineering effort into this feature. Maybe worth opening a GitHub issue for that :)

Comment by wat10000 7 hours ago

Right, nothing wrong with delegating the decision to a bunch of people who have thought long and hard about the best compromise, as long as it’s understood that it’s not perfect.

Comment by mxmlnkn 7 hours ago

I never understood why the recommended replacement for ß is ss. It is a ligature of sz (similar to & being a ligature of et) and is even pronounced ess-zet. The only logical replacement would have been sz, and it would have avoided the clash of Masse (mass) and Maße (measurements). Then again, it only affects whether the vowel before it is pronounced short or long, and there are better ways to encode that in written language in the first place.

Comment by adrian_b 1 hour ago

I agree that writing it "sz" might have created less problems.

However, it is likely that it has never been pronounced "sz", but always "ss" and the habit of writing "sz" for the double consonant may have had the same reason as the writing of "ck" instead of the double "kk".

Comment by looperhacks 8 hours ago

MASS is allowed casing of Maß, but not the preferred casing: https://www.rechtschreibrat.com/DOX/RfdR_Amtliches-Regelwerk... Page 48

Comment by b2ccb2 8 hours ago

The confusion likely stems from the relatively new introduction of the capitalized ẞ https://de.wikipedia.org/wiki/Gro%C3%9Fes_%C3%9F

Maß capitalized (used to be) MASS.

Funnily enough, Mass means one liter beer (think Oktoberfest).

Comment by looperhacks 8 hours ago

Both Maß and Mass are valid spellings for a liter of beer ;) Not to confuse it with Maß, which just means any measurement, of course.

Comment by andersa 8 hours ago

It's strange, because I would expect "maß" as the case insensitive search to match "MASS" in the search text, but "mass" should not match "Maß".