Optimize UTF-8 string comparison to avoid per-comparison byte array allocations

[cshuo]

Task Description

What needs to be done:

Optimize StringUtils.compareUtf8Bytes(String, String) so that comparing two strings in unsigned UTF-8 byte order does not encode both strings into temporary byte[] arrays on every invocation.

The implementation introduced by #18941 currently follows this pattern for every comparison:

byte[] b1 = getUTF8Bytes(s1);
byte[] b2 = getUTF8Bytes(s2);
// Compare b1 and b2 as unsigned bytes.

This creates two new byte arrays per comparator invocation. Sorting N keys requires O(N log N) comparisons, so large record-index operations can generate a substantial amount of short-lived memory, increase GC pressure, and cause a performance regression.

There are existing open-source implementations that compare Java strings in UTF-8 byte order without materializing their UTF-8 encodings. For example, Google Firestore uses an allocation-free implementation in Order.compareUtf8Strings, with a randomized test that compares one million string pairs against their encoded UTF-8 byte order.

The same approach can be applied here by scanning the UTF-16 code units directly and handling supplementary characters specially:

• If the first differing code units are both non-surrogates, compare them directly.
• If both are members of valid surrogate pairs, their UTF-16 order is consistent with the corresponding UTF-8 byte order.
• If one is a surrogate and the other is not, the supplementary character sorts after the BMP character in UTF-8 byte order.
• If one string is a prefix of the other, the shorter string sorts first.

Why this task is needed:

UTF8_LEXICOGRAPHIC_COMPARATOR is used in sorting paths for metadata record-index writes, lookups, and compaction. Comparator allocation is multiplied by the number of sort comparisons, making the current encode-on-every-comparison implementation unfriendly to GC for large datasets. Avoiding those allocations should improve throughput while preserving the HFile-compatible unsigned UTF-8 ordering fixed by #18941.

Task Type

Performance optimization

Acceptance Criteria

• The comparator hot path does not allocate UTF-8 byte[] arrays.
• Results match unsigned lexicographical comparison of String#getBytes(UTF_8) for supported inputs.
• Tests cover ASCII, BMP boundaries, supplementary characters, and common prefixes.
• Include a benchmark or allocation measurement comparing the existing and optimized implementations.

Related Issues

Parent feature issue: N/A

Related issues: #18941