Consider exposing sort keys

[Lucretiel]

It would be nice if icu_collator had exported sort key types, in addition to Collator::compare. This would allow sort keys to be computed once (via sort_by_key or similar utilities), after which they only need to be compared (which I understand to be much simpler than the computation step, and also not locale-sensitive).

[markusicu]

There are pros and cons.

• compare() can bail out as soon as there is a difference between the two strings.
• Sort keys have to be computed for the whole string and all requested levels (according to the strength), and since they tend to be stored semi-permanently, they want to be compressed to be small.
• As a result, computing sort keys is relatively slow, and gets amortized only when you sort really long lists of strings.
• And sort keys need to be recomputed whenever the locale or the Unicode version or the tailoring data changes.

See

• https://unicode-org.github.io/icu/userguide/collation/concepts#sortkeys-vs-comparison
• https://unicode-org.github.io/icu/userguide/collation/architecture#sort-keys

[Lucretiel]

That does all make sense. The main use case I'm interested isn't exactly a huge list of strings as much as a frequently sorted list of strings (essentially a React style UI system where elements are semi-frequently recomputed). However, I definitely understand that it may not be worth it (especially for strings that are more commonly dissimilar and therefore usually don't need a full sort key). I'll probably start by forking icu4x and doing some private benchmarking to see if there's any benefit before I re-open the proposal.

[mpalmer]

Any chance this could be considered for re-opening? I've got a use case where I can't do direct comparisons of the strings, and so sort keys are the only available solution.

[markusicu]

I've got a use case where I can't do direct comparisons of the strings, and so sort keys are the only available solution.

Could you please say more about your use case and why you “can't do direct comparisons of the strings”?

[mpalmer]

tl;dr: encryption.

Deep nerd dive:

I can't do direct comparisons of the strings because they're encrypted, and the service performing the comparison doesn't have the key to decrypt the strings in order to do a direct comparison (beyond the fact that decryption-for-comparison would be somewhat of a performance buzz-kill). Thus, just using compare isn't an option.

Of course, just encrypting the string and leaving the sort key unencrypted would be a massive information leak (because the sort key is a fairly close representation of the source string), but I'm also using an encryption scheme (order-revealing encryption) that can encrypt the numeric values in the sort key and allow them to be compared without revealing directly what the numbers are, which provides the ability to order the strings without directly knowing what they are.

Using order-revealing encryption on the source strings naturally won't work, because the numeric values of the octets in the string (which is all that ORE is able to work with) don't correspond to the desired sort order. The transformation provided by generating the sort key is precisely the operation I need to turn "unicode string" into "sortable value".

I've got a proof-of-concept of all this working, using the get_sort_key function from the rust_icu bindings, but it would be a lot simpler if I could stick to native Rust code, and avoid the need for users to manage having a compatible version of libicu on hand -- doubly so if they're using pre-built binaries.

(This is all to add orderable strings to the Enquo Project, in case you're after even more of a deep-dive into what I'm up to)

[sffc]

Re-opening to seek additional feedback from @markusicu and @hsivonen

[iantbutler01]

I'd also like to weigh in, sort keys are useful in data structures where you need a binary comparable key. I'm currently writing an adaptive radix tree implementation as an underlying index for a full text search database that needs just that to properly work on unicode strings and I'll have to use the rust_icu bindings for now which exposes the ability to generate the sort key.

[markusicu]

Re-opening to seek additional feedback from @markusicu and @hsivonen

I don’t have much to add to the discussion. Sort keys have a cost (extra code, processing time, storage) but some users need or want them.

We want to discourage the desire for sort keys for performance reasons alone, especially without the benefit of a performance test, but if there is real demand for use cases beyond “I have a hunch that sort keys would be faster” then we could consider them.

The comment about “an adaptive radix tree implementation” sounds like a request for something fancier than just “compute the complete sort key for this string”, as in ICU4C ucol_nextSortKeyPart().

If & when ICU4X adds APIs and code for sort keys, it would be nice for it to generate the same sort keys as ICU4C/J, at least for whole-string-to-complete-sort-key functions.

[iantbutler01]

Nope I just need the ability to compute a sort key from a string. To be precise I need the functionality equivalent to ucol_getSortKey for this purpose. Not having that rules out the use of this library in favor of the C/C++ bindings for me.

[mpalmer]

If & when ICU4X adds APIs and code for sort keys, it would be nice for it to generate the same sort keys as ICU4C/J

Undoubtedly compatibility with ICU4C/J would be useful, as I'm sure ICU4X is generally trying to be as compatible with ICU4C/J as possible. For my purposes, though, at least, I don't require compatibility between implementations, so my vote (for whatever little it may be worth) would be that if compatibility makes implementation harder, drop compatibility.

While that would, in general, make future compatibility more difficult (re-aligning sort keys to match ICU4C/J-generated keys would break comparison with keys previously generated by ICU4X), using a separate ICU4X-specific interface for ICU4X-specific sort keys would make this approach less fraught than it would otherwise be.

[hsivonen]

Re-opening to seek additional feedback from @markusicu and @hsivonen

• We shouldn't add sort keys at this time on performance grounds, as there is an obviously-imaginable unimplemented performance improvement that we should implement but haven't yet: Code unit-level identical prefix skipping (hopefully without new data structures): Implement identical prefix skipping without new data structures #2712 (The ICU4X collator trades away performance relative to ICU4C in the interest of size on three points: no separate data structure for identical prefix skipping, no canonical closure in data, and no separate "fast Latin" data.)
• The easiest way to implement sort keys would to avoid inventing a new scheme and to instead directly port the ICU4C algorithm for creating a collation key from a sequence of collation elements. It would still be prudent not to advertise compatibility: See the next point.
• We should be extremely clear that updates to ICU4X collator code and/or to the collation data invalidate previously-created and stored collation keys. (And even without collation keys, any kind of collation-based storage order has to be considered invalidated by an ICU4X/data update. That is, even without collation keys, building and storing a search tree based on the collation order is problematic. This isn't specific to ICU4X: This also applies to ICU4C and glibc, but evidence suggests that people still build stuff on top of ICU4C and glibc as if the order was frozen across updates.)
• For FFI purposes, we should consider if the last byte of collation keys should be zero to have C strcmp compatibility without an additional copy even if the additional zero byte would be unidiomatic and wasteful from a strict Rust perspective.
• If there are non-performance use cases (or if there remain performance use cases after implementing identical prefix skipping), I'm not opposed to a contribution to add sort keys (by porting the algorithm from ICU4C), but I don't volunteer to do the implementation myself at this time.