Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

ashvardanian.com

Post reply on HN
Print view View original

61–70 of 80 posts

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

#61

Post by Sesse__ »

happytoexplain wrote: post #54
Sesse__ wrote: post #40

Earlier quoted context omitted.

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 us…

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

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).

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

#62

Post by Sesse__ »

ashvardanian wrote: post #19

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 by…

> I grouped all Unicode 17 case-folding rules

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

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

#63

Post by kbolino »

fatty_patty89 wrote: post #55
kbolino wrote: post #53

Earlier quoted context omitted.

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 langua…

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/env…

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

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

#64

Post by ashvardanian »

Sesse__ wrote: post #62
ashvardanian wrote: post #19

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 by…

> I grouped all Unicode 17 case-folding rules But why are you using the case-folding rules and not the collation rules?

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...

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

#65

Post by infogulch »

shiomiru wrote: post #56
infogulch wrote: post #52

Earlier quoted context omitted.

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.

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.)

[flagged]

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

#66

Post by adrian_b »

mxmlnkn wrote: post #22
andersa wrote: post #2

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.

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…

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".

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

#67

Post by shiomiru »

infogulch wrote: post #65
shiomiru wrote: post #56

Earlier quoted context omitted.

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.)

[flagged]

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

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

#68

Post by kahirsch »

shiomiru wrote: post #56
infogulch wrote: post #52

Earlier quoted context omitted.

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.

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.)

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

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

#69

Post by bawolff »

bbminner wrote: post #45

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 “K”, which is distinct from the Latin upp…

> 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.

Post reply on HN