cshuo opened a new issue, #19409: URL: https://github.com/apache/hudi/issues/19409
## 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: ```java 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. The strings can instead be compared directly without materializing their UTF-8 encodings. For well-formed UTF-16 input, UTF-8 byte order can be determined by scanning the UTF-16 code units 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. Google Firestore uses this allocation-free approach in [`Order.compareUtf8Strings`](https://github.com/googleapis/google-cloud-java/blob/dfa56264aaa9473b43cdc23471f2338251ccf0c1/java-firestore/google-cloud-firestore/src/main/java/com/google/cloud/firestore/Order.java#L140-L201), with a randomized test that compares one million string pairs against their encoded UTF-8 byte order. The optimized implementation should also explicitly document and test the intended behavior for malformed UTF-16 input containing unpaired surrogates. `String#getBytes(UTF_8)` replaces such input during encoding, while the simplified Firestore algorithm assumes well-formed strings. **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, common prefixes, and malformed/unpaired surrogate behavior. - Include a benchmark or allocation measurement comparing the existing and optimized implementations. ## Related Issues **Parent feature issue:** N/A **Related issues:** #18941 -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
