Ship fast tries in icu_normalizer_data by default

[hsivonen]

Changing from the small trie type to the fast trie type doubles the throughput for figuring out that already-NFC UTF-16 is indeed already in NFC for Japanese and Chinese. Korean becomes even faster. It seems reasonable to assume that other languages whose bulk of characters is between U+1000 and U+FFFF would get doubled throughput, too.

It seems bad to offer worse performance by default for this part of the BMP.

For nfd, databake claims 27948B vs. 34748B. (Fast is 6.6 KB larger.)

For nfkd, databake claims 43132B vs. 51324B. (Fast is 8.0 KB larger.)

For uts46d, databake claims 56200B vs 69488B. It seems bad to pessimize widely-used languages to save 13 KB in binary size, but people already complain about having to carry any IDNA data as a side effect of depending on url, and it seems unlikely that IDNA processing is a perf bottleneck, so perhaps we should keep defaulting to the small trie type for this one.

For the Harfbuzz supplement, databake claims 4486B vs. 6382B, but in the U+1000 to U+FFFF range that result in a query to this trie, so perhaps it makes sense to keep the small trie type for this one. (But we should check, if there are characters of interest in the relevant range.)

[sffc]

I'm fine taking the size hit if the performance boost is sufficiently compelling. There isn't a particularly good formula for that, but I would be compelled to take the 14 KB hit if end-to-end Chinese NFD and NFKD improved by 30-40%. If we're talking less than 10%, then 14 KB hit is unlikely to be compelling to me.

[hsivonen]

(Looks like above I mistakenly claimed the numbers to be for the non-writing case, but this run indicates I was probably looking at the writing case yesterday. Sorry.)

Here are the results for Chinese for switching datagen from small to fast (with #6825 applied in both cases). The TL;DR is that Chinese NFD and NFKD are improved by as much as you said they would need to.

Note that the str case isn't as carefully optimized as the UTF-16 case. The trie design is such that it should be possible to plug UTF-8 bytes in an UTF-8-oriented getter that would result in fewer bitwise ops than our current code, which first decodes UTF-8 into a char and then the trie getter splits out the bits that in UTF-8 were already split out in the last byte of the UTF-8 sequence.

The str cases exercise the Cow code path, so they end up exercising the non-writing case. _already_utf16 is a non-writing UTF-16 case and the other UTF-16 cases are unconditionally-writing.

zh_nfc_to_nfc_str/icu4x time:   [7.8043 µs 7.8058 µs 7.8076 µs]                                     
                        thrpt:  [701.85 MiB/s 702.02 MiB/s 702.15 MiB/s]
                 change:
                        time:   [-28.875% -28.850% -28.826%] (p = 0.00 < 0.05)
                        thrpt:  [+40.502% +40.547% +40.597%]
                        Performance has improved.

zh_nfc_to_nfd_str/icu4x time:   [8.5329 µs 8.5402 µs 8.5476 µs]                                     
                        thrpt:  [641.10 MiB/s 641.65 MiB/s 642.20 MiB/s]
                 change:
                        time:   [-24.958% -24.903% -24.845%] (p = 0.00 < 0.05)
                        thrpt:  [+33.059% +33.161% +33.259%]
                        Performance has improved.

zh_nfd_to_nfd_str/icu4x time:   [8.3541 µs 8.3568 µs 8.3597 µs]                                     
                        thrpt:  [655.62 MiB/s 655.84 MiB/s 656.06 MiB/s]
                 change:
                        time:   [-24.365% -24.232% -24.146%] (p = 0.00 < 0.05)
                        thrpt:  [+31.832% +31.981% +32.214%]
                        Performance has improved.

zh_nfd_to_nfc_str/icu4x time:   [8.0978 µs 8.1180 µs 8.1385 µs]                                     
                        thrpt:  [673.43 MiB/s 675.14 MiB/s 676.82 MiB/s]
                 change:
                        time:   [-26.037% -25.819% -25.586%] (p = 0.00 < 0.05)
                        thrpt:  [+34.383% +34.805% +35.203%]
                        Performance has improved.

zh_nfd_to_nfkc_str/icu4x                                                                             
                        time:   [12.639 µs 12.651 µs 12.662 µs]
                        thrpt:  [432.86 MiB/s 433.22 MiB/s 433.63 MiB/s]
                 change:
                        time:   [-19.337% -19.264% -19.195%] (p = 0.00 < 0.05)
                        thrpt:  [+23.755% +23.860% +23.973%]
                        Performance has improved.

zh_nfd_to_nfkd_str/icu4x                                                                             
                        time:   [11.171 µs 11.176 µs 11.182 µs]
                        thrpt:  [490.14 MiB/s 490.39 MiB/s 490.62 MiB/s]
                 change:
                        time:   [-22.637% -22.509% -22.422%] (p = 0.00 < 0.05)
                        thrpt:  [+28.903% +29.047% +29.261%]
                        Performance has improved.

zh_nfc_to_nfkc_str/icu4x                                                                             
                        time:   [12.537 µs 12.553 µs 12.572 µs]
                        thrpt:  [435.89 MiB/s 436.52 MiB/s 437.09 MiB/s]
                 change:
                        time:   [-19.164% -19.042% -18.906%] (p = 0.00 < 0.05)
                        thrpt:  [+23.314% +23.521% +23.706%]
                        Performance has improved.

zh_nfc_to_nfkd_str/icu4x                                                                             
                        time:   [11.182 µs 11.185 µs 11.189 µs]
                        thrpt:  [489.76 MiB/s 489.91 MiB/s 490.07 MiB/s]
                 change:
                        time:   [-22.370% -22.329% -22.287%] (p = 0.00 < 0.05)
                        thrpt:  [+28.678% +28.748% +28.816%]
                        Performance has improved.

zh_nfc_to_nfc_already_utf16/icu4x                                                                             
                        time:   [3.5096 µs 3.5133 µs 3.5174 µs]
                        thrpt:  [582.25 Melem/s 582.93 Melem/s 583.54 Melem/s]
                 change:
                        time:   [-42.568% -42.524% -42.476%] (p = 0.00 < 0.05)
                        thrpt:  [+73.839% +73.985% +74.120%]
                        Performance has improved.

zh_nfc_to_nfc_utf16/icu4x                                                                             
                        time:   [3.5934 µs 3.5958 µs 3.5985 µs]
                        thrpt:  [569.12 Melem/s 569.55 Melem/s 569.93 Melem/s]
                 change:
                        time:   [-50.675% -50.647% -50.619%] (p = 0.00 < 0.05)
                        thrpt:  [+102.51% +102.62% +102.74%]
                        Performance has improved.

zh_nfc_to_nfd_utf16/icu4x                                                                             
                        time:   [3.6977 µs 3.6994 µs 3.7012 µs]
                        thrpt:  [553.33 Melem/s 553.60 Melem/s 553.85 Melem/s]
                 change:
                        time:   [-49.097% -49.076% -49.056%] (p = 0.00 < 0.05)
                        thrpt:  [+96.292% +96.371% +96.451%]
                        Performance has improved.

zh_nfd_to_nfd_utf16/icu4x                                                                             
                        time:   [3.6982 µs 3.6999 µs 3.7018 µs]
                        thrpt:  [553.24 Melem/s 553.53 Melem/s 553.78 Melem/s]
                 change:
                        time:   [-49.147% -49.061% -48.999%] (p = 0.00 < 0.05)
                        thrpt:  [+96.074% +96.314% +96.644%]
                        Performance has improved.

zh_nfd_to_nfc_utf16/icu4x                                                                             
                        time:   [3.6131 µs 3.6152 µs 3.6174 µs]
                        thrpt:  [566.44 Melem/s 566.77 Melem/s 567.10 Melem/s]
                 change:
                        time:   [-50.661% -50.613% -50.541%] (p = 0.00 < 0.05)
                        thrpt:  [+102.19% +102.48% +102.68%]
                        Performance has improved.

[hsivonen]

The trie design is such that it should be possible to plug UTF-8 bytes in an UTF-8-oriented getter that would result in fewer bitwise ops than our current code, which first decodes UTF-8 into a char and then the trie getter splits out the bits that in UTF-8 were already split out in the last byte of the UTF-8 sequence.

Filed #6838 about this.

[hsivonen]

uts46d

Using the fast trie type for this, too, would make it easy to change the normalizer internals to fast-only in 3.0.

[Manishearth]

• @hsivonen CPT in ICU4C has a specific property: when you choose fast, the boundary between fast lookup and slow lookup lines up with the common UTFs (BMP-vs-non-BMP, so 1-vs-2 code units in UTF-16, or 1..3-vs-4 in UTF-8). So when you know this is your data, you really want the fast trie type, because then you have branchless lookup.
• @hsivonen Previously in 1.0, 2.0 we didn't have broad enough awareness of this (unknown if @echeran was aware, but Henri wasn't).
• @hsivonen Fusing with UTF decoding is relevant to the normalizer. In the utf-16 case it's very directly relevant to whether in the Gecko case ICU4X is competitive or not.From the perspective of pitching ICU4X normalizer as a replacement, it's super important that the perf bar is the same order of magnitude.
• @hsivonen: Not enough to look at ICU4X and whether it is sufficiently fast, comparison is important. Then in the UTF8 case, I don't currently have a Gecko use case; I feel the urge to make the str case even faster, but I can't prioritize that.
• @Manishearth So we default to small tries just because that's what we chose as a default
• @Manishearth do you see any reason to use small here? is small appreciably smaller?
• @hsivonen: If we have an app that uses both non-k and k; we're talking about 14.6kB (baseline ~43kB + ~28kb) larger. And an app that only cares about collation or the non-k forms, it's 6.6kB (baseline ~28kB).
• @Manishearth I think this is fine for the default data we ship.
• @hsivonent normalizer has multiple tries, we're talking about nfd/nfkd here. Harfbuzz I believe we should ship small a trie; but we have not measured. IDNA we should keep small because rust-url users care about codesize.

Conclusion: ship fast tries by default for for nfd/nfkd data. No decision on IDNA/harfbuzz tries, which we have not yet verified.

Agreed: @Manishearth @hsivonen

Followup: Datagen configurability.

• @Manishearth Right now datagen has a global toggle for trie types. This can be changed
• (a) Add a --trie-type auto that is the default. .with_trie_type(TrieType: Fast | Small | Auto) or .with_small_trie() / .with_fast_trie()
• (a1) Add --trie-type auto and add an additional datagen API for customizing trie types per-key
• (b) Have nfd/nfkd always use fast tries with no datagen option to use small tries; add one if requested
• @robertbastian (clarifying datagen API choices)
• @hsivonen I imagine there are other APIs like this
• @robertbastian must this be user selectable? I imagine we have this because nobody has put in the work. We should ignore all user configurability for markers where we know better
• @Manishearth Okay, so perhaps we document with_trie_type as only overriding tries where we have not done performance work. If there are cases where there are multiple valid options, we can add an auto setting, or per-key overrides. We document trie type on every trie in a provider module as either fast, small, or "set by datagen, small by default".

Conclusion:

• Datagen --trie-type only affects tries where we have not selected a type.
• We document trie type selection on every trie (whether it is selected or not, what it is selected to be if so)
• No Datagen API changes

Agreed: @Manishearth @robertbastian @hsivonen

[sffc]

Conclusion: ship fast tries by default for for nfd/nfkd data. No decision on IDNA/harfbuzz tries, which we have not yet verified.

LGTM. Just wanted to say that we have (or at least I have) been aware of the difference between small and fast from the get-go and previously decided that we would prioritize size over speed for CJK+, with the idea that CJK heavy users would opt for fast tries. This decision departs from that previously held position.

Datagen --trie-type only affects tries where we have not selected a type.

Not sure about this one. I think nfd/nfkd users should still be able to select small tries. There are legitimate use cases such as "my app only processes Latin, Greek, and Cyrillic so I don't need fast tries" and "I need to reduce size at all costs". In other words, I'm open to changing the default but I am not convinced enough that we should both change the default and block out the previous behavior from being reachable from datagen.

[sffc]

(a) Add a --trie-type auto that is the default.

This seems like a good approach. I expect that the minority of users who wish to opt into a specific trie type generally will wish to do so globally, due to their app's constraints (size-at-all-costs or CJK-heavy). If a client asks for key level selection in the future, we can add the API at that time, but for now auto/small/fast seems right to me.