This is an automated email from the ASF dual-hosted git repository.
uros-b pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/master by this push:
new 2e66189e9f64 [SPARK-59379][CORE] Add an ASCII fast-path to UTF8String
position lookups, warmed by numChars()
2e66189e9f64 is described below
commit 2e66189e9f6425321df4beb35ee4219620858b9e
Author: david-mollitor-db <[email protected]>
AuthorDate: Thu Oct 1 10:44:49 2026 +0000
[SPARK-59379][CORE] Add an ASCII fast-path to UTF8String position lookups,
warmed by numChars()
### What changes were proposed in this pull request?
This combines the two halves of a single optimization that only pays off
together (per uros-b's review):
1. **`numChars()` caches the full-ASCII flag** as a byproduct of its
existing scan — the scan already reads every lead byte, so it sets
`isFullAscii` (when still `UNKNOWN`) at no extra cost; any lead byte `>= 0x80`
is non-ASCII.
2. **Four char↔byte "locate" methods gain an ASCII fast-path** —
`substring(int, int)`, `getChar(int)`, `charPosToByte(int)`,
`bytePosToChar(int)`. For full-ASCII, character index == byte index, so the
O(n) per-code-point walk becomes O(1) arithmetic. The fast-path only *reads*
the cached flag (never forces a scan), so cold (`UNKNOWN`) strings fall back to
the existing scan with no regression. Because `numChars()` now warms the flag,
the natural callers here (`getChar()`'s bounds chec [...]
Originally split as #58667 (SPARK-59378, the caching) and #58668
(SPARK-59379, the fast-path). As uros-b noted, each is correct but incomplete
on its own — the pair is the unit of value — so they're merged here and #58667
is closed.
### Does this PR introduce _any_ user-facing change?
No.
### How was this patch tested?
`UTF8StringSuite` passes (53 tests). `numCharsCachesAsciiness` verifies the
flag `numChars()` caches matches `isFullAscii()` (incl. invalid UTF-8).
`asciiLocateFastPathMatchesScan` compares a cold (scan) vs warmed (fast-path)
instance for all four methods across ASCII/empty/multi-byte/invalid inputs and
boundary positions.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Opus 4.8
Closes #58668 from david-mollitor-db/utf8-ascii-locate-fastpath.
Authored-by: david-mollitor-db <[email protected]>
Signed-off-by: Uros Bojanic <[email protected]>
---
.../org/apache/spark/unsafe/types/UTF8String.java | 56 ++++++++++++++----
.../apache/spark/unsafe/types/UTF8StringSuite.java | 68 ++++++++++++++++++++++
2 files changed, 112 insertions(+), 12 deletions(-)
diff --git
a/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java
b/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java
index c1ec1cc38a34..5318cd8d11c2 100644
--- a/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java
+++ b/common/unsafe/src/main/java/org/apache/spark/unsafe/types/UTF8String.java
@@ -293,12 +293,24 @@ public final class UTF8String implements
Comparable<UTF8String>, Externalizable,
* Private helper method to calculate the number of code points in the UTF-8
string. Counting
* the code points is a linear time operation, as we need to scan the entire
UTF-8 string.
* Hence, this method should generally only be called once for non-empty
UTF-8 strings.
+ *
+ * Because the scan reads every lead byte, it also caches ASCII-ness for
free (see
+ * {@link #isFullAscii()}): any lead byte >= 0x80 (a multi-byte or invalid
byte) is non-ASCII.
+ * The flag is only set when still UNKNOWN, preserving a value already
computed elsewhere.
*/
private int getNumChars() {
int len = 0;
- for (int i = 0; i < numBytes; i += numBytesForFirstByte(getByte(i))) {
+ boolean ascii = true;
+ int i = 0;
+ while (i < numBytes) {
+ byte b = getByte(i);
+ ascii &= b >= 0;
+ i += numBytesForFirstByte(b);
len += 1;
}
+ if (isFullAscii == IsFullAscii.UNKNOWN) {
+ isFullAscii = ascii ? IsFullAscii.FULL_ASCII : IsFullAscii.NOT_ASCII;
+ }
return len;
}
@@ -635,21 +647,29 @@ public final class UTF8String implements
Comparable<UTF8String>, Externalizable,
return EMPTY_UTF8;
}
- int i = 0;
- int c = 0;
- while (i < numBytes && c < start) {
- i += numBytesForFirstByte(getByte(i));
- c += 1;
- }
-
- int j = i;
- if (until == Integer.MAX_VALUE) {
- i = numBytes;
+ int i;
+ int j;
+ if (isFullAscii == IsFullAscii.FULL_ASCII) {
+ // ASCII fast-path: code point index == byte index, so locate directly.
The scan below
+ // clamps a negative start to 0 and stops at numBytes; replicate that
with min/max.
+ j = Math.max(start, 0);
+ i = (until == Integer.MAX_VALUE) ? numBytes : Math.min(until, numBytes);
} else {
- while (i < numBytes && c < until) {
+ i = 0;
+ int c = 0;
+ while (i < numBytes && c < start) {
i += numBytesForFirstByte(getByte(i));
c += 1;
}
+ j = i;
+ if (until == Integer.MAX_VALUE) {
+ i = numBytes;
+ } else {
+ while (i < numBytes && c < until) {
+ i += numBytesForFirstByte(getByte(i));
+ c += 1;
+ }
+ }
}
if (i > j) {
@@ -716,6 +736,10 @@ public final class UTF8String implements
Comparable<UTF8String>, Externalizable,
*/
public int getChar(int charIndex) {
Objects.checkIndex(charIndex, numChars());
+ if (isFullAscii == IsFullAscii.FULL_ASCII) {
+ // ASCII: byte index == char index, and checkIndex guarantees it is in
range.
+ return codePointFrom(charIndex);
+ }
int charCount = 0, byteCount = 0;
while (charCount < charIndex) {
byteCount += numBytesForFirstByte(getByte(byteCount));
@@ -1390,6 +1414,10 @@ public final class UTF8String implements
Comparable<UTF8String>, Externalizable,
if (charPos < 0) {
return -1;
}
+ if (isFullAscii == IsFullAscii.FULL_ASCII) {
+ // ASCII: byte index == char index, clamped to the end of the string.
+ return Math.min(charPos, numBytes);
+ }
int i = 0;
int c = 0;
@@ -1401,6 +1429,10 @@ public final class UTF8String implements
Comparable<UTF8String>, Externalizable,
}
public int bytePosToChar(int bytePos) {
+ if (isFullAscii == IsFullAscii.FULL_ASCII) {
+ // ASCII: char index == byte index, clamped to [0, numBytes].
+ return Math.max(0, Math.min(bytePos, numBytes));
+ }
int i = 0;
int c = 0;
while (i < numBytes && i < bytePos) {
diff --git
a/common/unsafe/src/test/java/org/apache/spark/unsafe/types/UTF8StringSuite.java
b/common/unsafe/src/test/java/org/apache/spark/unsafe/types/UTF8StringSuite.java
index 5ab9775572e7..c871b785abb0 100644
---
a/common/unsafe/src/test/java/org/apache/spark/unsafe/types/UTF8StringSuite.java
+++
b/common/unsafe/src/test/java/org/apache/spark/unsafe/types/UTF8StringSuite.java
@@ -70,6 +70,36 @@ public class UTF8StringSuite {
checkBasic("\uD83E\uDD19", 1); // 4 bytes char
}
+ @Test
+ public void numCharsCachesAsciiness() {
+ // numChars() determines ASCII-ness as a byproduct of its scan and caches
it. Verify it
+ // agrees with getIsFullAscii() (reached via a fresh isFullAscii()),
including for invalid
+ // UTF-8 where the code-point count equals the byte count but a byte is >=
0x80 (not ASCII).
+ byte[][] inputs = new byte[][] {
+ {0x68, 0x65, 0x6c, 0x6c, 0x6f}, // "hello" - full
ASCII
+ {}, // empty
+ {0x61, (byte) 0x80}, // 'a' + stray
continuation (invalid)
+ {(byte) 0x80}, // lone continuation
byte (invalid)
+ {(byte) 0xC3, (byte) 0xA9}, // valid 2-byte char
U+00E9
+ {0x61, (byte) 0xE5, (byte) 0xA4, (byte) 0xA7, 0x62} // 'a' + 3-byte char
+ 'b'
+ };
+ for (byte[] bytes : inputs) {
+ // Reference: a fresh string computes ASCII-ness via getIsFullAscii().
+ boolean expected = fromBytes(bytes).isFullAscii();
+ // Under test: numChars() runs first and must cache the identical answer.
+ UTF8String s = fromBytes(bytes);
+ s.numChars();
+ assertEquals(expected, s.isFullAscii(),
+ "numChars() cached wrong ASCII flag for " + Arrays.toString(bytes));
+ }
+
+ // The specific invalid case a naive `numChars == numBytes` test would
misflag as ASCII:
+ // the count equals the byte count, but the 0x80 byte is not ASCII.
+ UTF8String invalid = fromBytes(new byte[] {0x61, (byte) 0x80});
+ assertEquals(invalid.numBytes(), invalid.numChars());
+ assertFalse(invalid.isFullAscii());
+ }
+
@Test
public void emptyStringTest() {
assertEquals(EMPTY_UTF8, fromString(""));
@@ -228,6 +258,44 @@ public class UTF8StringSuite {
assertEquals(fromString("ߵ梷"), fromString("ߵ梷").substring(0, 2));
}
+ @Test
+ public void asciiLocateFastPathMatchesScan() {
+ // substring, getChar, charPosToByte and bytePosToChar take an ASCII
fast-path when the
+ // isFullAscii flag is already FULL_ASCII. For each input, compare a cold
instance (flag
+ // UNKNOWN -> general scan) against a warmed instance (isFullAscii()
called -> fast-path for
+ // ASCII) and assert identical results. Covers ASCII, empty, multi-byte,
and invalid UTF-8.
+ byte[][] inputs = new byte[][] {
+ "hello world".getBytes(StandardCharsets.UTF_8), // full ASCII ->
exercises the fast-path
+ {}, // empty (vacuously ASCII)
+ {0x61, (byte) 0xC3, (byte) 0xA9, 0x62}, // 'a' + U+00E9 (2-byte) + 'b'
(not ASCII)
+ {0x61, (byte) 0x80, 0x62} // invalid UTF-8, stray continuation (not
ASCII)
+ };
+ int[] positions = {Integer.MIN_VALUE, -3, -1, 0, 1, 2, 3, 5, 100,
Integer.MAX_VALUE};
+
+ for (byte[] bytes : inputs) {
+ UTF8String cold = fromBytes(bytes);
+ UTF8String warm = fromBytes(bytes);
+ warm.isFullAscii(); // warm the cached flag; fast-path branches read it
without recomputing
+ String label = Arrays.toString(bytes);
+
+ for (int a : positions) {
+ for (int b : positions) {
+ assertEquals(cold.substring(a, b), warm.substring(a, b),
+ "substring(" + a + ", " + b + ") on " + label);
+ }
+ assertEquals(cold.charPosToByte(a), warm.charPosToByte(a),
+ "charPosToByte(" + a + ") on " + label);
+ assertEquals(cold.bytePosToChar(a), warm.bytePosToChar(a),
+ "bytePosToChar(" + a + ") on " + label);
+ }
+
+ for (int idx = 0; idx < warm.numChars(); idx++) {
+ assertEquals(cold.getChar(idx), warm.getChar(idx),
+ "getChar(" + idx + ") on " + label);
+ }
+ }
+ }
+
@Test
public void trims() {
assertEquals(fromString("1"), fromString("1").trim());
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
