Full Unicode Search at 50× ICU Speed with AVX‑512
ashvardanian.com
Full Unicode Search at 50× ICU Speed with AVX‑512
1–10 of 80 posts
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#2From 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.
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#3In 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.
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#4From 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.
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).
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#5In 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.
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).
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#6In 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.
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.
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#7In 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.
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).
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.
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#8Earlier quoted context omitted.
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).
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.
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.
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#9Is 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"?
Re: Full Unicode Search at 50× ICU Speed with AVX‑512
#10Earlier quoted context omitted.
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).
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.
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