Figure out how Hangul NFD to NFC normalization can be made faster

[hsivonen]

The Hangul composition operation is just math and doesn't involve a data structure lookup. Yet, it's slow compared to ICU4C. I suspect it's because there's a loop jump between each composable character pair and because we don't have a dedicated Hangul-oriented fast loop over the input buffer.

[hsivonen]

From reasoning about the code:

The check for whether a first character in the composition is an LV syllable is expensive. We should keep around state when we do multiple compositions in a row and remember that we just formed an LV syllable.

Alternatively, we could mark valid LV syllables in the (upcoming) non-Hangul lookup trie, but I expect this to make the trie data considerably larger, since instead of just filling the Hangul syllable range with default values (reusing many times a data block of 2^6 default values), we'd instead have a non-default value for every 28th trie item.

When we are forming an LV syllable from L and V, v * HANGUL_T_COUNT is cheap: Multiplication by 28 optimizes to addition. However, l * HANGUL_N_COUNT is expensive: Multiplication by 588 compiles to an actual multiplication instruction.

We could have a 19-entry static array of u16 containing the result of (l * HANGUL_N_COUNT) + HANGUL_S_BASE. This would require a memory read instead of multiplication.

Alternatively, we could store l * HANGUL_N_COUNT in the (upcoming) non-Hangul lookup trie (with high bits set to 1 to distinguish from non-Hangul cases). This would allow using a memory read that we do anyway. However, if we use dynamically-loaded trie data, we then have to do a checked conversion from u32 to char where we currently do an unchecked one.

If we want to use the (upcoming) non-Hangul trie for any of this, we should do it in the same major release to avoid yet more data versioning. (I continue to doubt the wisdom of making non-CLDR Unicode Database data field-upgradeable thereby limiting our ability to optimize the data from release-to-release.)

[hsivonen]

Relying on knowing that we just formed an LV syllable doesn't work on the HarfBuzz case. Unclear, though, if HarfBuzz actually ends up calling the callback with Hangul LV and Hangul T.

I think HarfBuzz doesn't actually rely on the external compose function for Hangul even though its built-in implementation for the external callback supports Hangul.

See https://searchfox.org/firefox-main/rev/28398d11d39984cc5db08020671e7dd0d1408ec0/gfx/harfbuzz/src/hb-ot-shaper-hangul.cc#178-184
and
https://searchfox.org/firefox-main/rev/28398d11d39984cc5db08020671e7dd0d1408ec0/gfx/harfbuzz/src/hb-ot-shape-normalize.cc#435-438

It seems that lv % HANGUL_T_COUNT == 0 optimizes to a multiplication and avoids an actual division, so maybe it's not worthwhile to making the trie data larger to optimize the LV case regardless of what HarfBuzz needs.

But still, @behdad, @khaledhosny, does the performance of the external compose function matter for the Hangul LV and T case in HarfBuzz?

[behdad]

Relying on knowing that we just formed an LV syllable doesn't work on the HarfBuzz case. Unclear, though, if HarfBuzz actually ends up calling the callback with Hangul LV and Hangul T.

I think HarfBuzz doesn't actually rely on the external compose function for Hangul even though its built-in implementation for the external callback supports Hangul.

See https://searchfox.org/firefox-main/rev/28398d11d39984cc5db08020671e7dd0d1408ec0/gfx/harfbuzz/src/hb-ot-shaper-hangul.cc#178-184 and https://searchfox.org/firefox-main/rev/28398d11d39984cc5db08020671e7dd0d1408ec0/gfx/harfbuzz/src/hb-ot-shape-normalize.cc#435-438

It seems that lv % HANGUL_T_COUNT == 0 optimizes to a multiplication and avoids an actual division, so maybe it's not worthwhile to making the trie data larger to optimize the LV case regardless of what HarfBuzz needs.

But still, @behdad, @khaledhosny, does the performance of the external compose function matter for the Hangul LV and T case in HarfBuzz?

I think your assessment is correct, that we don't call the external compose function for most Hangul syllables.

[hsivonen]

I think your assessment is correct, that we don't call the external compose function for most Hangul syllables.

Thanks!

[hsivonen]

The trie-based aspect of this is part of #7528 and a more focused follow-up is #7516.