@@ -56,21 +56,55 @@ pub fn bytes_to_i128(slice: &[u8]) -> i128 {
5656// a time, get the ASCII check without a call.
5757#[ inline]
5858pub 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