Skip to content

Commit b3459f0

Browse files
committed
perf: don't scan long strings twice in decode_utf8_spark_lossy
decode_utf8_spark_lossy checked the whole value with is_ascii() and, when that failed, validated it again from the start with str::from_utf8. So a long value whose first non-ASCII byte came late was read twice: 4096-byte values ending in é converted 12-16% slower than on main on x86, and 35% slower on aarch64. On aarch64, is_ascii checks one word at a time and is slower than str::from_utf8 on long values, so long ASCII values were slower than on main too. Values of up to 32 bytes still get the inline is_ascii check. Longer values are checked out of line 32 bytes at a time, ORing each block's words, and str::from_utf8 validates them only from the first block that is not ASCII. The block check is out of line because inlining it made the shuffle's get_string too large to inline into its per-row loops, and the out-of-line function is cold so that those loops keep the short ASCII path as the fall-through.
1 parent b478aa7 commit b3459f0

1 file changed

Lines changed: 76 additions & 10 deletions

File tree

‎native/common/src/utils.rs‎

Lines changed: 76 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -56,21 +56,55 @@ pub fn bytes_to_i128(slice: &[u8]) -> i128 {
5656
// a time, get the ASCII check without a call.
5757
#[inline]
5858
pub fn decode_utf8_spark_lossy(bytes: &[u8]) -> Cow<'_, str> {
59-
// ASCII is valid UTF-8. `is_ascii` checks a word at a time, and on short strings it is several
60-
// times cheaper than `str::from_utf8`, whose cost dominated the JVM columnar shuffle's string
61-
// conversion.
62-
if bytes.is_ascii() {
59+
// ASCII is valid UTF-8, and on short strings checking for it is several times cheaper than
60+
// `str::from_utf8`, whose cost dominated the JVM columnar shuffle's string conversion. Longer
61+
// values are checked out of line: checking them here made the shuffle's `get_string` too large
62+
// to inline into its per-row loops.
63+
if bytes.len() <= ASCII_BLOCK && bytes.is_ascii() {
6364
// SAFETY: every ASCII byte sequence is valid UTF-8.
6465
return Cow::Borrowed(unsafe { std::str::from_utf8_unchecked(bytes) });
6566
}
66-
decode_non_ascii_utf8_spark_lossy(bytes)
67+
decode_long_or_non_ascii_utf8_spark_lossy(bytes)
6768
}
6869

69-
/// [`decode_utf8_spark_lossy`] for bytes that are not all ASCII.
70-
fn decode_non_ascii_utf8_spark_lossy(bytes: &[u8]) -> Cow<'_, str> {
70+
/// How many bytes [`decode_utf8_spark_lossy`] checks for ASCII at a time.
71+
const ASCII_BLOCK: usize = 32;
72+
73+
/// Whether every byte of `block` is ASCII. ORing its words keeps every byte's high bit and compiles
74+
/// to a few vector instructions. On aarch64, `<[u8]>::is_ascii` branches on each word instead, and
75+
/// on long values it is slower than `str::from_utf8`.
76+
#[inline]
77+
fn is_ascii_block(block: &[u8; ASCII_BLOCK]) -> bool {
78+
let (words, _) = block.as_chunks::<8>();
79+
let bits = words
80+
.iter()
81+
.fold(0, |acc, word| acc | u64::from_ne_bytes(*word));
82+
bits & 0x8080_8080_8080_8080 == 0
83+
}
84+
85+
/// [`decode_utf8_spark_lossy`] for bytes that are longer than an ASCII block or not all ASCII.
86+
// Cold so that callers lay the short ASCII path out as the fall-through. Without it, the shuffle's
87+
// per-row string loops took an extra jump for every short ASCII value.
88+
#[cold]
89+
fn decode_long_or_non_ascii_utf8_spark_lossy(bytes: &[u8]) -> Cow<'_, str> {
90+
// A long value is checked for ASCII a block at a time, and only the bytes from the first block
91+
// that is not ASCII are validated, so a value whose first non-ASCII byte comes late is not
92+
// scanned twice. An ASCII byte is a whole character, so those bytes validate on their own.
93+
let mut ascii_len = 0;
94+
if bytes.len() > ASCII_BLOCK {
95+
let (blocks, tail) = bytes.as_chunks::<ASCII_BLOCK>();
96+
let ascii_blocks = blocks.iter().take_while(|b| is_ascii_block(b)).count();
97+
if ascii_blocks == blocks.len() && tail.is_ascii() {
98+
// SAFETY: every ASCII byte sequence is valid UTF-8.
99+
return Cow::Borrowed(unsafe { std::str::from_utf8_unchecked(bytes) });
100+
}
101+
ascii_len = ascii_blocks * ASCII_BLOCK;
102+
}
103+
71104
// Fast path: well-formed UTF-8 borrows with zero copy (the overwhelmingly common case).
72-
if let Ok(s) = std::str::from_utf8(bytes) {
73-
return Cow::Borrowed(s);
105+
if std::str::from_utf8(&bytes[ascii_len..]).is_ok() {
106+
// SAFETY: ASCII followed by valid UTF-8 is valid UTF-8.
107+
return Cow::Borrowed(unsafe { std::str::from_utf8_unchecked(bytes) });
74108
}
75109

76110
const RC: char = '\u{FFFD}';
@@ -215,13 +249,15 @@ mod tests {
215249

216250
#[test]
217251
fn decode_utf8_spark_lossy_ascii_is_borrowed_zero_copy() {
218-
// Lengths below, at and above a machine word, so the word-at-a-time check sees partial words.
252+
// Lengths below and above a machine word and an ASCII block, so both the check of short
253+
// values and the block check of long ones run, the latter with bytes after the last block.
219254
for s in [
220255
"",
221256
"a",
222257
"value-1",
223258
"value-12345",
224259
"abcdefghijklmnopqrstuvwxyz0123456789",
260+
&"0123456789".repeat(10),
225261
] {
226262
match decode_utf8_spark_lossy(s.as_bytes()) {
227263
Cow::Borrowed(b) => assert_eq!(b, s),
@@ -234,6 +270,36 @@ mod tests {
234270
assert_eq!(decode_utf8_spark_lossy(&bytes), "abcdefghijk\u{FFFD}mnop");
235271
}
236272

273+
#[test]
274+
fn decode_utf8_spark_lossy_non_ascii_at_every_offset() {
275+
// A long value is validated from its first block that is not ASCII. Put a character or an
276+
// ill-formed byte at every offset of values up to a few blocks long, so it lands in short
277+
// values and in each block of long ones, across block boundaries and after the last block.
278+
let ascii = |n: usize| "x".repeat(n);
279+
for len in 1..=100 {
280+
for at in 0..len {
281+
for c in ["é", "日", "🦀"] {
282+
let s = format!("{}{c}{}", ascii(at), ascii(len - at));
283+
match decode_utf8_spark_lossy(s.as_bytes()) {
284+
Cow::Borrowed(b) => assert_eq!(b, s),
285+
Cow::Owned(_) => panic!("valid UTF-8 must borrow, not allocate"),
286+
}
287+
// An ill-formed byte after it still makes the value take the lossy decode.
288+
let mut bytes = s.as_bytes().to_vec();
289+
bytes.push(0xFF);
290+
assert_eq!(decode_utf8_spark_lossy(&bytes), format!("{s}\u{FFFD}"));
291+
}
292+
// 0xFF is never valid, and 0x80 is a continuation byte with no lead byte.
293+
for b in [0xFF, 0x80] {
294+
let mut bytes = ascii(len).into_bytes();
295+
bytes[at] = b;
296+
let expected = format!("{}\u{FFFD}{}", ascii(at), ascii(len - at - 1));
297+
assert_eq!(decode_utf8_spark_lossy(&bytes), expected);
298+
}
299+
}
300+
}
301+
}
302+
237303
#[test]
238304
fn decode_utf8_spark_lossy_valid_multibyte_around_invalid_bytes_decodes() {
239305
// 'a' | é (C3 A9) | stray 0xFF | 'b' | 🦀 (F0 9F A6 80) -> valid chars preserved, one FFFD.

0 commit comments

Comments
 (0)