Skip to content

Commit 3361fd0

Browse files
authored
perf: speed up string, map and array conversion in JVM columnar shuffle (#6604)
* perf: speed up string, map and array conversion in JVM columnar shuffle The JVM columnar shuffle converts Spark UnsafeRows to Arrow natively, and three per-value costs dominated its string, map and array conversion: - decode_utf8_spark_lossy validated every string with str::from_utf8, which costs several times more than an is_ascii check on short strings. ASCII strings now skip it, and the check is inlined into callers in other crates. - append_map_elements built a MapFieldNames, allocating and freeing six strings, for every map value just to read the key and value fields. - Nullable element arrays were always appended one element at a time. An array of eight or more elements with no nulls is now copied in one go. The timestamp and date appenders, which duplicated the macro, now use it. * 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 0dec857 commit 3361fd0

4 files changed

Lines changed: 256 additions & 142 deletions

File tree

‎native/common/src/utils.rs‎

Lines changed: 104 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -52,10 +52,59 @@ pub fn bytes_to_i128(slice: &[u8]) -> i128 {
5252
/// per-class malformed lengths below (E0/ED overlong & surrogate handling, F0/F4 range checks)
5353
/// match the observable replacement behavior of the JDK UTF-8 decoder; they were determined from
5454
/// observed `new String(bytes, UTF_8)` output, not by reviewing the OpenJDK source.
55+
// Inlined so that callers in other crates, such as the JVM columnar shuffle converting one value at
56+
// a time, get the ASCII check without a call.
57+
#[inline]
5558
pub fn decode_utf8_spark_lossy(bytes: &[u8]) -> Cow<'_, str> {
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() {
64+
// SAFETY: every ASCII byte sequence is valid UTF-8.
65+
return Cow::Borrowed(unsafe { std::str::from_utf8_unchecked(bytes) });
66+
}
67+
decode_long_or_non_ascii_utf8_spark_lossy(bytes)
68+
}
69+
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+
56104
// Fast path: well-formed UTF-8 borrows with zero copy (the overwhelmingly common case).
57-
if let Ok(s) = std::str::from_utf8(bytes) {
58-
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) });
59108
}
60109

61110
const RC: char = '\u{FFFD}';
@@ -198,6 +247,59 @@ mod tests {
198247
}
199248
}
200249

250+
#[test]
251+
fn decode_utf8_spark_lossy_ascii_is_borrowed_zero_copy() {
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.
254+
for s in [
255+
"",
256+
"a",
257+
"value-1",
258+
"value-12345",
259+
"abcdefghijklmnopqrstuvwxyz0123456789",
260+
&"0123456789".repeat(10),
261+
] {
262+
match decode_utf8_spark_lossy(s.as_bytes()) {
263+
Cow::Borrowed(b) => assert_eq!(b, s),
264+
Cow::Owned(_) => panic!("ASCII must borrow, not allocate"),
265+
}
266+
}
267+
// A single byte past ASCII anywhere still takes the validating paths.
268+
let mut bytes = b"abcdefghijklmnop".to_vec();
269+
bytes[11] = 0xFF;
270+
assert_eq!(decode_utf8_spark_lossy(&bytes), "abcdefghijk\u{FFFD}mnop");
271+
}
272+
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+
201303
#[test]
202304
fn decode_utf8_spark_lossy_valid_multibyte_around_invalid_bytes_decodes() {
203305
// 'a' | é (C3 A9) | stray 0xFF | 'b' | 🦀 (F0 9F A6 80) -> valid chars preserved, one FFFD.

‎native/shuffle/src/spark_unsafe/list.rs‎

Lines changed: 127 additions & 109 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,13 @@ use arrow::array::{
3232
use arrow::datatypes::{DataType, TimeUnit};
3333
use datafusion_comet_jni_bridge::errors::CometError;
3434

35+
/// Element count from which a nullable array with no null elements is appended with one copy
36+
/// instead of element by element. Below it the loop is as fast: checking the null bitset and
37+
/// calling `append_slice` cost about as much as a few appends, and arrays of up to five elements
38+
/// with some null elements got slower with the copy. Arrays of 16 elements take about 40% of the
39+
/// time with the copy, and arrays of 50 about a fifth.
40+
const MIN_BULK_APPEND_ELEMENTS: usize = 8;
41+
3542
/// Generates bulk append methods for primitive types in SparkUnsafeArray.
3643
///
3744
/// # Safety invariants for all generated methods:
@@ -46,7 +53,8 @@ macro_rules! impl_append_to_builder {
4653
return;
4754
}
4855

49-
if NULLABLE {
56+
// A nullable array without nulls takes the copy below too, once it is long enough.
57+
if NULLABLE && (num_elements < MIN_BULK_APPEND_ELEMENTS || self.has_null()) {
5058
let mut ptr = self.element_offset as *const $element_type;
5159
let null_words = self.null_bitset_ptr();
5260
debug_assert!(!null_words.is_null(), "null_bitset_ptr is null");
@@ -167,6 +175,16 @@ impl SparkUnsafeArray {
167175
(self.row_addr + 8) as *const i64
168176
}
169177

178+
/// Returns true if any element is null, checking the null bitset a word at a time.
179+
#[inline]
180+
fn has_null(&self) -> bool {
181+
let null_words = self.null_bitset_ptr();
182+
// SAFETY: the null bitset holds ceil(num_elements/64) words. Spark zeroes the bits past
183+
// the last element, and a stray one would only send the array down the per-element path.
184+
(0..self.num_elements.div_ceil(64))
185+
.any(|word| unsafe { null_words.add(word).read_unaligned() } != 0)
186+
}
187+
170188
/// Checks whether the null bit at `idx` is set in the given null bitset pointer.
171189
///
172190
/// # Safety
@@ -185,6 +203,12 @@ impl SparkUnsafeArray {
185203
impl_append_to_builder!(append_bytes_to_builder, Int8Builder, i8);
186204
impl_append_to_builder!(append_floats_to_builder, Float32Builder, f32);
187205
impl_append_to_builder!(append_doubles_to_builder, Float64Builder, f64);
206+
impl_append_to_builder!(
207+
append_timestamps_to_builder,
208+
TimestampMicrosecondBuilder,
209+
i64
210+
);
211+
impl_append_to_builder!(append_dates_to_builder, Date32Builder, i32);
188212

189213
/// Bulk append boolean values to builder.
190214
/// Booleans are stored as 1 byte each in SparkUnsafeArray, requiring special handling.
@@ -230,114 +254,6 @@ impl SparkUnsafeArray {
230254
}
231255
}
232256
}
233-
234-
/// Bulk append timestamp values to builder (stored as i64 microseconds).
235-
pub(crate) fn append_timestamps_to_builder<const NULLABLE: bool>(
236-
&self,
237-
builder: &mut TimestampMicrosecondBuilder,
238-
) {
239-
let num_elements = self.num_elements;
240-
if num_elements == 0 {
241-
return;
242-
}
243-
244-
if NULLABLE {
245-
let mut ptr = self.element_offset as *const i64;
246-
let null_words = self.null_bitset_ptr();
247-
debug_assert!(
248-
!null_words.is_null(),
249-
"append_timestamps: null_bitset_ptr is null"
250-
);
251-
debug_assert!(
252-
!ptr.is_null(),
253-
"append_timestamps: element_offset pointer is null"
254-
);
255-
for idx in 0..num_elements {
256-
// SAFETY: null_words has ceil(num_elements/64) words, idx < num_elements
257-
let is_null = unsafe { Self::is_null_in_bitset(null_words, idx) };
258-
259-
if is_null {
260-
builder.append_null();
261-
} else {
262-
// SAFETY: ptr is within element data bounds
263-
builder.append_value(unsafe { ptr.read_unaligned() });
264-
}
265-
// SAFETY: ptr stays within bounds, iterating num_elements times
266-
ptr = unsafe { ptr.add(1) };
267-
}
268-
} else {
269-
// SAFETY: element_offset points to contiguous i64 data of length num_elements
270-
debug_assert!(
271-
self.element_offset != 0,
272-
"append_timestamps: element_offset is null"
273-
);
274-
let ptr = self.element_offset as *const i64;
275-
if (ptr as usize).is_multiple_of(std::mem::align_of::<i64>()) {
276-
let slice = unsafe { std::slice::from_raw_parts(ptr, num_elements) };
277-
builder.append_slice(slice);
278-
} else {
279-
let mut ptr = ptr;
280-
for _ in 0..num_elements {
281-
builder.append_value(unsafe { ptr.read_unaligned() });
282-
ptr = unsafe { ptr.add(1) };
283-
}
284-
}
285-
}
286-
}
287-
288-
/// Bulk append date values to builder (stored as i32 days since epoch).
289-
pub(crate) fn append_dates_to_builder<const NULLABLE: bool>(
290-
&self,
291-
builder: &mut Date32Builder,
292-
) {
293-
let num_elements = self.num_elements;
294-
if num_elements == 0 {
295-
return;
296-
}
297-
298-
if NULLABLE {
299-
let mut ptr = self.element_offset as *const i32;
300-
let null_words = self.null_bitset_ptr();
301-
debug_assert!(
302-
!null_words.is_null(),
303-
"append_dates: null_bitset_ptr is null"
304-
);
305-
debug_assert!(
306-
!ptr.is_null(),
307-
"append_dates: element_offset pointer is null"
308-
);
309-
for idx in 0..num_elements {
310-
// SAFETY: null_words has ceil(num_elements/64) words, idx < num_elements
311-
let is_null = unsafe { Self::is_null_in_bitset(null_words, idx) };
312-
313-
if is_null {
314-
builder.append_null();
315-
} else {
316-
// SAFETY: ptr is within element data bounds
317-
builder.append_value(unsafe { ptr.read_unaligned() });
318-
}
319-
// SAFETY: ptr stays within bounds, iterating num_elements times
320-
ptr = unsafe { ptr.add(1) };
321-
}
322-
} else {
323-
// SAFETY: element_offset points to contiguous i32 data of length num_elements
324-
debug_assert!(
325-
self.element_offset != 0,
326-
"append_dates: element_offset is null"
327-
);
328-
let ptr = self.element_offset as *const i32;
329-
if (ptr as usize).is_multiple_of(std::mem::align_of::<i32>()) {
330-
let slice = unsafe { std::slice::from_raw_parts(ptr, num_elements) };
331-
builder.append_slice(slice);
332-
} else {
333-
let mut ptr = ptr;
334-
for _ in 0..num_elements {
335-
builder.append_value(unsafe { ptr.read_unaligned() });
336-
ptr = unsafe { ptr.add(1) };
337-
}
338-
}
339-
}
340-
}
341257
}
342258

343259
pub fn append_to_builder<const NULLABLE: bool>(
@@ -494,3 +410,105 @@ pub fn append_list_element(
494410

495411
Ok(())
496412
}
413+
414+
#[cfg(test)]
415+
mod test {
416+
use super::*;
417+
use arrow::array::builder::PrimitiveBuilder;
418+
use arrow::datatypes::{
419+
ArrowPrimitiveType, Date32Type, Int16Type, Int32Type, Int64Type, Int8Type,
420+
TimestampMicrosecondType,
421+
};
422+
423+
/// Lays `values` out as a Spark `UnsafeArrayData` of `width`-byte elements: the element
424+
/// count, the null bitset, then the elements.
425+
fn unsafe_array_bytes(values: &[Option<i64>], width: usize) -> Vec<u8> {
426+
let bitset_words = values.len().div_ceil(64);
427+
let mut bitset = vec![0u64; bitset_words];
428+
let mut data = vec![0u8; (values.len() * width).div_ceil(8) * 8];
429+
for (i, value) in values.iter().enumerate() {
430+
match value {
431+
None => bitset[i / 64] |= 1 << (i % 64),
432+
Some(v) => {
433+
data[i * width..(i + 1) * width].copy_from_slice(&v.to_le_bytes()[..width])
434+
}
435+
}
436+
}
437+
let mut bytes = (values.len() as u64).to_le_bytes().to_vec();
438+
bitset
439+
.iter()
440+
.for_each(|word| bytes.extend_from_slice(&word.to_le_bytes()));
441+
bytes.extend_from_slice(&data);
442+
bytes
443+
}
444+
445+
/// Appends `values`, laid out `shift` bytes past an 8-byte boundary, through
446+
/// `append_to_builder::<true>` and reads them back.
447+
fn round_trip<T>(data_type: DataType, values: &[Option<i64>], shift: usize) -> Vec<Option<i64>>
448+
where
449+
T: ArrowPrimitiveType,
450+
T::Native: Into<i64>,
451+
{
452+
let bytes = unsafe_array_bytes(values, std::mem::size_of::<T::Native>());
453+
let mut words = vec![0u64; (shift + bytes.len()).div_ceil(8)];
454+
// SAFETY: `words` covers `shift + bytes.len()` bytes.
455+
let base = unsafe { (words.as_mut_ptr() as *mut u8).add(shift) };
456+
unsafe { std::ptr::copy_nonoverlapping(bytes.as_ptr(), base, bytes.len()) };
457+
let array = SparkUnsafeArray::new(base as i64);
458+
let mut builder = PrimitiveBuilder::<T>::new();
459+
append_to_builder::<true>(&data_type, &mut builder, &array).unwrap();
460+
builder.finish().iter().map(|v| v.map(Into::into)).collect()
461+
}
462+
463+
#[test]
464+
fn nullable_primitive_arrays_round_trip_on_every_append_path() {
465+
let long: Vec<Option<i64>> = (0..70).map(Some).collect();
466+
let mut null_in_second_bitset_word = long.clone();
467+
null_in_second_bitset_word[66] = None;
468+
let cases = [
469+
vec![],
470+
// Shorter than MIN_BULK_APPEND_ELEMENTS: element by element.
471+
vec![Some(1), Some(-2), Some(3)],
472+
// Holds a null: element by element.
473+
vec![Some(1), None, Some(3), Some(-4), Some(5)],
474+
// No nulls and long enough: one copy.
475+
vec![Some(-1), Some(2), Some(-3), Some(4)],
476+
long,
477+
// The null is only in the second bitset word, which the copy check must read.
478+
null_in_second_bitset_word,
479+
];
480+
for values in &cases {
481+
// An 8-byte boundary, as inside an UnsafeRow, and a misaligned one for every width.
482+
for shift in [0, 1, 4] {
483+
assert_eq!(
484+
round_trip::<Int8Type>(DataType::Int8, values, shift),
485+
*values
486+
);
487+
assert_eq!(
488+
round_trip::<Int16Type>(DataType::Int16, values, shift),
489+
*values
490+
);
491+
assert_eq!(
492+
round_trip::<Int32Type>(DataType::Int32, values, shift),
493+
*values
494+
);
495+
assert_eq!(
496+
round_trip::<Int64Type>(DataType::Int64, values, shift),
497+
*values
498+
);
499+
assert_eq!(
500+
round_trip::<Date32Type>(DataType::Date32, values, shift),
501+
*values
502+
);
503+
assert_eq!(
504+
round_trip::<TimestampMicrosecondType>(
505+
DataType::Timestamp(TimeUnit::Microsecond, None),
506+
values,
507+
shift
508+
),
509+
*values
510+
);
511+
}
512+
}
513+
}
514+
}

0 commit comments

Comments
 (0)