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

31–40 of 80 posts

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

#31

Post by wat10000 »

ashvardanian wrote: post #27
wat10000 wrote: post #20

Earlier quoted context omitted.

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…

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.

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

#32

Post by stingraycharles »

mgaunard wrote: post #28
stingraycharles wrote: post #8

Earlier quoted context omitted.

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

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.

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

#33

Post by kardianos »

fatty_patty89 wrote: post #26
ashvardanian wrote: post #25

Earlier quoted context omitted.

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

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

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

#34

Post by ComputerGuru »

jjmarr wrote: post #24
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.

Normalization wouldn’t address this.

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

#36

Post by happytoexplain »

ComputerGuru wrote: post #34
jjmarr wrote: post #24

Earlier quoted context omitted.

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

Normalization wouldn’t address this.

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

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

#37

Post by ashvardanian »

kardianos wrote: post #35

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?

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

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

#38

Post by nwellnhof »

ComputerGuru wrote: post #34
jjmarr wrote: post #24

Earlier quoted context omitted.

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

Normalization wouldn’t address this.

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

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

#39

Post by mananaysiempre »

nwellnhof wrote: post #38
ComputerGuru wrote: post #34

Earlier quoted context omitted.

Normalization wouldn’t address this.

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

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

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

#40

Post by Sesse__ »

jjmarr wrote: post #24
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.

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