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

21–30 of 80 posts

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

#21

Post by Arnt »

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.

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.

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

#22

Post by mxmlnkn »

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 language in the first place.

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

#23

Post by fatty_patty89 »

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…

Thank you

do the go bindings require cgo?

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

#24

Post by jjmarr »

unwind wrote: post #16

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…

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

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

#25

Post by ashvardanian »

fatty_patty89 wrote: post #23
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…

Thank you do the go bindings require cgo?

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

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

#26

Post by fatty_patty89 »

ashvardanian wrote: post #25
fatty_patty89 wrote: post #23

Earlier quoted context omitted.

Thank you do the go bindings require cgo?

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

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

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

#27

Post by ashvardanian »

wat10000 wrote: post #20
pjmlp wrote: post #15

Earlier quoted context omitted.

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.

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.

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

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

#28

Post by mgaunard »

stingraycharles wrote: post #8
mgaunard wrote: post #7

Earlier quoted context omitted.

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.

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

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

#29

Post by adzm »

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…

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

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

#30

Post by mgaunard »

Const-me wrote: post #13
mgaunard wrote: post #7

Earlier quoted context omitted.

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

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).
Post reply on HN