This is an automated email from the ASF dual-hosted git repository.
voonhous pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/hudi.git
The following commit(s) were added to refs/heads/master by this push:
new 377fc0419ae8 perf(common): avoid UTF-8 allocations in string
comparator (#19414)
377fc0419ae8 is described below
commit 377fc0419ae81db92ee5ab2dd862c2554902a383
Author: Shuo Cheng <[email protected]>
AuthorDate: Fri Jul 31 16:58:36 2026 +0800
perf(common): avoid UTF-8 allocations in string comparator (#19414)
* perf(common): avoid UTF-8 allocations in string comparator
* fix(common): address UTF-8 comparator review feedback
Preserve the null-rejection contract, document malformed surrogate
behavior, add Firebase attribution, and strengthen the HFile-ordering tests.
---
LICENSE | 12 ++++
.../org/apache/hudi/common/util/StringUtils.java | 37 +++++++----
.../apache/hudi/common/util/TestStringUtils.java | 72 ++++++++++++++++++++++
3 files changed, 109 insertions(+), 12 deletions(-)
diff --git a/LICENSE b/LICENSE
index 301ea869628b..f0d0759bd101 100644
--- a/LICENSE
+++ b/LICENSE
@@ -349,6 +349,18 @@ Copyright (c) 2005, European Commission project OneLab
under contract 034819 (ht
-------------------------------------------------------------------------------
+ This product includes code from the Google Firebase Android SDK
+
+ * org.apache.hudi.common.util.StringUtils#compareUtf8Bytes ported from
+ com.google.firebase.firestore.util.Util#compareUtf8Strings
+
+ Copyright 2018 Google LLC
+
+ Home page: https://github.com/firebase/firebase-android-sdk
+ License: https://www.apache.org/licenses/LICENSE-2.0
+
+
-------------------------------------------------------------------------------
+
This product includes code from StreamSets Data Collector
* com.streamsets.pipeline.lib.util.avroorc.AvroToOrcRecordConverter copied
and modified to org.apache.hudi.common.util.AvroOrcUtils
diff --git a/hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java
b/hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java
index bd8af56094dc..cacbc3854371 100644
--- a/hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java
+++ b/hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java
@@ -137,23 +137,36 @@ public class StringUtils {
* <p>Neither argument may be {@code null}; like {@link
String#compareTo(String)}, a {@code null}
* argument throws {@link NullPointerException}.
*
- * <p>Assumes well-formed UTF-16 input: {@code String#getBytes(UTF_8)}
replaces unpaired surrogates
- * with {@code '?'}, so strings differing only in unpaired surrogates
compare equal.
+ * <p>This comparison does not materialize the UTF-8 byte arrays. It
compares UTF-16 code units
+ * directly and handles supplementary characters specially to preserve UTF-8
byte order.
*
- * <p>Note: encodes both strings to UTF-8 on every call; for very large
sorts consider
- * pre-encoding keys to byte arrays once and comparing those.
+ * <p>Assumes well-formed UTF-16 input. For strings containing unpaired
surrogates the result no
+ * longer matches {@code String#getBytes(UTF_8)} byte order: the encoder
replaces an unpaired
+ * surrogate with {@code '?'} while this method sorts it after every BMP
character. Production
+ * callers derive keys by decoding UTF-8, which cannot produce unpaired
surrogates.
+ *
+ * <p>Ported from Google Firebase Firestore's {@code compareUtf8Strings}.
*/
public static int compareUtf8Bytes(String s1, String s2) {
- byte[] b1 = getUTF8Bytes(s1);
- byte[] b2 = getUTF8Bytes(s2);
- int len = Math.min(b1.length, b2.length);
- for (int i = 0; i < len; i++) {
- int cmp = (b1[i] & 0xFF) - (b2[i] & 0xFF);
- if (cmp != 0) {
- return cmp;
+ // Source:
https://github.com/firebase/firebase-android-sdk/blob/f05e4bcb7f86f3b21833b1e0960d793b800d38d1/firebase-firestore/src/main/java/com/google/firebase/firestore/util/Util.java#L76-L132
+ // The identity check intentionally avoids scanning when both references
point to the same
+ // non-null String while preserving the method's fail-fast null contract.
+ if (s1 == s2 && s1 != null) {
+ return 0;
+ }
+
+ final int length = Math.min(s1.length(), s2.length());
+ for (int i = 0; i < length; i++) {
+ final char char1 = s1.charAt(i);
+ final char char2 = s2.charAt(i);
+ if (char1 != char2) {
+ return (Character.isSurrogate(char1) == Character.isSurrogate(char2))
+ ? Character.compare(char1, char2)
+ : Character.isSurrogate(char1) ? 1 : -1;
}
}
- return b1.length - b2.length;
+
+ return Integer.compare(s1.length(), s2.length());
}
public static String fromUTF8Bytes(byte[] bytes) {
diff --git
a/hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java
b/hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java
index 265ebbf305ef..49e29cd75fb9 100644
--- a/hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java
+++ b/hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java
@@ -19,6 +19,8 @@
package org.apache.hudi.common.util;
+import org.apache.hudi.io.hfile.UTF8StringKey;
+
import org.junit.jupiter.api.Test;
import java.io.ByteArrayInputStream;
@@ -321,6 +323,74 @@ public class TestStringUtils {
assertTrue(StringUtils.compareUtf8Bytes("ab", "abc") < 0);
assertTrue(StringUtils.compareUtf8Bytes("abc", "ab") > 0);
assertEquals(0, StringUtils.compareUtf8Bytes("abc", "abc"));
+ assertEquals(0, StringUtils.compareUtf8Bytes(new String("abc"), new
String("abc")));
+ }
+
+ @Test
+ public void testCompareUtf8BytesDocumentsUnpairedSurrogateBehavior() {
+ String unpairedSurrogate = String.valueOf((char) 0xD800);
+ String replacementCharacter = String.valueOf((char) 0xFFFD);
+
+ // Java's UTF-8 encoder replaces the unpaired surrogate with '?' while the
Firestore-derived
+ // comparator orders all surrogate code units after BMP characters.
Production callers decode
+ // UTF-8 into well-formed UTF-16, so malformed strings are outside this
method's contract.
+ assertTrue(StringUtils.compareUtf8Bytes(unpairedSurrogate,
replacementCharacter) > 0);
+ assertTrue(StringUtils.compareUtf8Bytes(unpairedSurrogate, "?") > 0);
+ }
+
+ @Test
+ public void testCompareUtf8BytesMatchesEncodedByteOrder() {
+ String[] alphabet = {
+ // One-byte UTF-8 characters, including the upper boundary.
+ "?",
+ "a",
+ String.valueOf((char) 0x007F),
+ // Two-byte UTF-8 lower and upper boundaries.
+ String.valueOf((char) 0x0080),
+ String.valueOf((char) 0x07FF),
+ // Three-byte UTF-8 boundaries around the surrogate range, plus U+FFFD.
+ String.valueOf((char) 0x0800),
+ String.valueOf((char) 0xD7FF),
+ String.valueOf((char) 0xE000),
+ String.valueOf((char) 0xFFFD),
+ // Four-byte UTF-8 supplementary characters, including two sharing a
high surrogate.
+ "😀", // U+1F600
+ new String(Character.toChars(0x20000)),
+ new String(Character.toChars(0x20001)),
+ new String(Character.toChars(0x10FFFF))
+ };
+
+ // Generate every sequence of zero to three code points from the alphabet.
This covers cases
+ // where strings differ before, within, or after a supplementary character.
+ List<String> values = new ArrayList<>();
+ values.add("");
+ for (String first : alphabet) {
+ values.add(first);
+ for (String second : alphabet) {
+ values.add(first + second);
+ for (String third : alphabet) {
+ values.add(first + second + third);
+ }
+ }
+ }
+
+ // Pre-encode each value once, then use the production HFile key
comparator as the oracle.
+ UTF8StringKey[] hfileKeys = values.stream()
+ .map(UTF8StringKey::new)
+ .toArray(UTF8StringKey[]::new);
+
+ // Compare only the sign because Comparator does not prescribe the
magnitude of its result.
+ for (int leftIndex = 0; leftIndex < values.size(); leftIndex++) {
+ String left = values.get(leftIndex);
+ for (int rightIndex = 0; rightIndex < values.size(); rightIndex++) {
+ String right = values.get(rightIndex);
+ assertEquals(
+
Integer.signum(hfileKeys[leftIndex].compareTo(hfileKeys[rightIndex])),
+ Integer.signum(StringUtils.compareUtf8Bytes(left, right)),
+ () -> "left=" + Arrays.toString(left.codePoints().toArray())
+ + " right=" + Arrays.toString(right.codePoints().toArray()));
+ }
+ }
}
@Test
@@ -328,6 +398,8 @@ public class TestStringUtils {
public void testUtf8LexicographicComparatorSerializableAndRejectsNull()
throws Exception {
// Like String.compareTo, a null argument is rejected.
assertThrows(NullPointerException.class, () ->
StringUtils.UTF8_LEXICOGRAPHIC_COMPARATOR.compare(null, "a"));
+ assertThrows(NullPointerException.class, () ->
StringUtils.UTF8_LEXICOGRAPHIC_COMPARATOR.compare("a", null));
+ assertThrows(NullPointerException.class, () ->
StringUtils.UTF8_LEXICOGRAPHIC_COMPARATOR.compare(null, null));
// The comparator is declared as (Comparator<String> & Serializable) so
Spark can capture it inside
// serialized closures. Round-trip it through Java serialization and
confirm the deserialized
