Consider compile-time constraints on collator options

[hsivonen]

@sffc wrote:

Thought: I see that CollatorOptions has a lot of knobs in the form of runtime functions. I am wondering whether there is room to move more of these options to compile-time type parameters, so that we can do static code analysis and identify what code and/or data we can remove. At runtime, you load smaller chunks of data, which is good, but where possible we'd like to go further and make things as good as possible for dead-code elimination.

I replied:

In principle, the run-time flags can alternatively come as defaults from language-specific collation data. That makes me generally pessimistic about compile-time type parameters.

If you want to eliminate alternate shifted at compile time, you need to promise not to collate Thai. If you want to eliminate backward second level at compile time, you need to promise not to collate Canadian French. If you want to eliminate case first handling, you need to promise not to collate Danish or Maltese.

Even strength has potential to be overridden by a language-specific default for Japanese. Currently, CLDR explicitly states the tertiary strength for Japanese, which is also the general default, so it's now a no-op. As I understand it, tertiary for Japanese is for performance but for de jure correctness, it should be the identical level.

[hsivonen]

So far the NonPrimary type exist so that Collator::compare_impl could be specialized for run-time space usage and performance when we know we aren't going to look at the primaries after the primary-level. However, this idea was at the expense of code size: i.e. my expectation was that neither specialization would be eliminated statically and instead both would be generated and the applicable one chosen at run-time.

The comparison needs access to the primary weights after the primary level if either of the following is true:

• Backward second level is enabled. (fr-CA by default or via the options API.)
• Unclear to me if just "quaternary level is enabled" or "quaternary level is enabled AND alternate shifted is enabled" (alternate shifted is the default for Thai)

Anyway, the default configuration is tertiary without alternate shifted and without backward second level, so the common case could omit the storage of the primary weight. That is, the tail of current compare_impl would be split out and parametrized over either CollationElement or NonPrimary to store primary weights or not to store them, respectively.

Except for the identical level, being able to statically omit the higher (higher than primary-only) comparison levels doesn't look particularly useful in terms of code size savings. Even though each level seems to take many lines of code, what the code does looks like it should compile to very tight instructions. I haven't godbolted this, though.

However, again without actually measuring, the identical level looks like it generates a lot of code in each of the UTF-specialized comparison functions by instantiating the NFD normalization code (example). My expectation is that being able to statically eliminate the identical comparison level would have the best code size benefit relative to the parametrization complexity introduced.