Small-only and Fast-only getters for CodePointTrie

[hsivonen]

Currently, the getters for CodePointTrie branch multiple times on the trie type.

There should be a set of getters that statically assume the trie type is "small", another set that statically assumes trie type "fast", a public getter for the type, and then the current set of getters should branch on the type once and then delegate to the statically-assuming getters.

See #2431.

[hsivonen]

The statically-assuming getters should probably be generic over TrieType so that code that wishes to hoist the branch out of a loop can make the loop generic over TrieType.

[sffc]

Working group discussion:

• @sffc Does this show up in the benchmarks? How much?
• @hsivonen Integer percentages, close to 10%. The difference was notable.
• @sffc You asked whether we should be able to select at runtime wehther we want "fast" or "small". What I don't want to have happen is that someone uses the "slow" type constructor and uses the "fast" type getter. Could we have different types of tries to avoid that? But the risk of that is that we duplicate data. Or instead could we just use the "fast" type getter always? I don't want the outcome to allow for panics because users create a trie of one type and then mistakenly uses the getter for the other type, thereby causing a panic.
• @hsivonen The way I envision this is, assuming we have runtime selection of trie type, instead of saying you always have a specific trie type, there would be two copies of the innermost loop. So the check has been hoisted out of the loop.
• @sffc OK, that's an internal change
• @hsivonen Yes except that this needs to be exported from the utils crate. Developers could have the potential to misuse the CodePointTrie. If we allow the Noramlizer is allowed to be built with a particular CodePointTrie type, then in the loop body (of the normalization), we can statically know and dispatch according to that trie type. I want the NFD and NFKD tries to be type fast, and the UTS46 supplement and ? as trie type small. That could change in the future. Until we know that Investigate making trie type small know about constant values for CJK Unified Ideographs and Hangul Syllables #5820 is a win, I think we should do what I'm suggesting to hoist the trie type check out of the innermost loop.
• @sffc CodePointTrie is an icu::collections component. CodePointTrie is one of those things where our bar for modifying the API is a little bit higher. My concern about constructing a trie of one type and calling the getter of another type is also on that same level, so we should be concerned about Normalizer changes like CPT changes. If we do make this change we should make it with intentinoality by parameterizing the CPT by the trie type, which requires API design. Those are things that I want to do. I just want to ensure that we're aligned on that.
• @hsivonen It's a problem if our CPT is a port of the ICU4C CPT and yet performs worse. The reason is that the lookup branches thrice on the character, but the ICU4C lookup uses a macro that does need to branch. It's a bad story if the Rust thing is slower than the C equivalent.
• @sffc I see your argument, and I think it's justified. I think it's best if we enforce this through the type system, either through a type parameter. We can have 3 options (fast, slow, any) which is like what we've done in other places, via an enum. The "any" type parameter would do the branching. The constructor would also check that the trie type matches the type parameter.
• @hsivonen I'm not sure if I can get this done in the v2.0 timeframe.
• @sffc We can do this for v3.0, and also mark it as a stretch for v2.0 just in case.
• @sffc Can we call it 'auto' because it automatically selects from the locale?
• @Manishearth With AnyCalendar, we allow people to select from multiple calendars.
• @sffc When naming, do we name what it is, or what it does? I'm just wondering what to name the type parameter.
• @sffc I'd like to put this issue in 2.0-stretch.