cshuo opened a new pull request, #19414:
URL: https://github.com/apache/hudi/pull/19414
### Describe the issue this Pull Request addresses
Closes #19409.
The UTF-8 string comparator introduced in #18941 encodes both operands on
every comparison, allocating two temporary `byte[]` arrays before scanning them
in unsigned byte order. Sorting invokes the comparator `O(N log N)` times, so
large metadata record-index operations generate substantial short-lived
allocations and GC pressure.
The same UTF-8 ordering can be derived directly from well-formed UTF-16 code
units. This avoids encoding and allocation while preserving the
HFile-compatible ordering required for non-ASCII and supplementary record keys.
### Summary and Changelog
#### Commit 1: perf: avoid UTF-8 allocations in string comparator
(`d9e0157b4aa5`)
- Port the allocation-free `compareUtf8Strings` algorithm from Google
Firebase Firestore, with the source recorded next to the implementation.
- Compare UTF-16 code units directly and handle supplementary characters
specially instead of materializing UTF-8 byte arrays.
- Add exhaustive tests over 2,380 valid Unicode strings, comparing every
pair against the unsigned order of their encoded UTF-8 bytes.
- Cover one-, two-, three-, and four-byte UTF-8 boundaries, BMP characters,
supplementary characters, common prefixes, and two supplementary code points
sharing a high surrogate.
#### Local benchmark
Environment: Java 11.0.27, macOS ARM64, G1 GC. Each microbenchmark result is
the median of five measured trials and was repeated across three independent
JVM forks. The benchmark harness is local-only and not included in this PR.
| Comparator scenario | Existing implementation | This PR | Speedup |
Existing allocation | This PR allocation |
| --- | ---: | ---: | ---: | ---: | ---: |
| 32-character UUID-like ASCII | 19.50 ns/op | 2.69 ns/op | 7.25x | 96 B/op
| 0 B/op |
| BMP Unicode | 134.95 ns/op | 2.90 ns/op | 46.5x | 348.3 B/op | 0 B/op |
| Supplementary Unicode | 132.95 ns/op | 3.52 ns/op | 37.8x | 348.5 B/op | 0
B/op |
| ASCII with 64-character common prefix | 60.62 ns/op | 33.38 ns/op | 1.82x
| 224 B/op | 0 B/op |
End-to-end `Arrays.sort` results:
| Sort scenario | Existing implementation | This PR | Speedup | Existing
allocation | This PR allocation |
| --- | ---: | ---: | ---: | ---: | ---: |
| 250K UUID-like ASCII keys | 159.2 ms | 59.7 ms | 2.67x | 381.8 MiB | 1.0
MiB |
| 250K ASCII keys with 64-character common prefix | 310.5 ms | 219.7 ms |
1.41x | 889.7 MiB | 1.0 MiB |
The approximately 1 MiB remaining in the sort benchmark comes from the
sorting implementation's temporary storage; the new comparator itself allocates
0 B/op.
Validation:
```text
mvn -pl hudi-io -am \
-Dtest=TestStringUtils \
-Dsurefire.failIfNoSpecifiedTests=false \
-DskipITs -DskipSparkTests -DskipScalaTests \
test
```
Result: 24 tests run, 0 failures, 0 errors, 0 skipped; Checkstyle reported 0
violations.
### Impact
- **Functional impact**: No ordering change for well-formed strings. UTF-8
byte ordering remains compatible with HFile ordering, including supplementary
characters.
- **Performance impact**: Removes two UTF-8 byte-array allocations per
comparator invocation and improves both comparator throughput and end-to-end
sorting performance.
- **Public API and storage format**: No public API, configuration, or
storage-format change.
### Risk Level
Low. The implementation is ported from Firebase Firestore and is validated
exhaustively against encoded unsigned UTF-8 byte order for valid Unicode
strings. Like the Firestore implementation, it assumes well-formed UTF-16
input; malformed/unpaired surrogates are outside the expected Spark/Avro
ingestion path.
### Documentation Update
none
### Contributor's checklist
- [ ] Read through [contributor's
guide](https://hudi.apache.org/contribute/how-to-contribute)
- [x] Enough context is provided in the sections above
- [x] Adequate tests were added if applicable
--
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]
