Skip to content

Commit 01f4796

Browse files
alambclaudejayzhan211
authored
refactor: Improve float_semantics::normalize, consolidate ownership (apache#27202)
## Which issue does this PR close? - Related tof apache#27121 - Split out of apache#27181 ## Rationale for this change DataFusion normalizes `-0.0` to `+0.0` via `float_semantics::normalize_floats(&ArrayRef)`. @mkleen centralized the float normalization in - apache#26595 Thanks to @jayzhan211 for responding However, because it borrows its argument, any array that contains `-0.0` is copied into a new buffer, even if there are no other users. Also it forces a bunch of unecessary (Arc) clones; It would be nice to reuse the allocation if possible ## What changes are included in this PR? Add `float_semantics::normalize` that takes an owned array and reuses the allocation if possible deprecaate the old dversion ## What is the testing strategy for this PR? Added some new tests ## Are there any user-facing changes? * `float_semantics::normalize_floats` is deprecated in favor of `float_semantics::normalize`, * `ColumnarValue::normalize` is new. ## Follow ons - I think we can clean up a non trivial amount of apache#25186 with this function, specifically: https://github.com/apache/datafusion/pull/25186/changes#r4501319899 --------- Co-authored-by: Claude Fable 5.1 <[email protected]> Co-authored-by: Jay Zhan <[email protected]>
1 parent 6dc8d41 commit 01f4796

14 files changed

Lines changed: 289 additions & 113 deletions

File tree

‎datafusion/common/src/float_semantics.rs‎

Lines changed: 112 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -7,15 +7,15 @@
77
//! Arrow's comparison kernels work on the bit pattern of a float,
88
//! i.e. IEEE 754 totalOrder. DataFusion deviates from that in one
99
//! respect: `+0.0` and `-0.0` are equal, hash the same and fall into the same
10-
//! group. See [`normalize_float`], [`normalize_floats`] and
10+
//! group. See [`normalize_float`], [`normalize`] and
1111
//! [`ScalarValue::normalize`]. Ordering still follows totalOrder, so
1212
//! [`compare_floats`] sorts `-0.0` before `+0.0`.
1313
//!
1414
//! Every comparison, hash or grouping boundary should be built from these
1515
//! helpers rather than inspecting float bits itself:
1616
//!
1717
//! - Equality and grouping: normalize first ([`normalize_float`],
18-
//! [`normalize_floats`], [`ScalarValue::normalize`]), then compare bits or
18+
//! [`normalize`], [`ScalarValue::normalize`]), then compare bits or
1919
//! call Arrow's `eq`, `RowConverter` or `make_comparator`. Hash
2020
//! [`hash_input`].
2121
//! - Ordering: use [`compare_floats`], [`float_lt`] or [`float_gt`]. Sorting
@@ -119,11 +119,14 @@ pub fn hash_input<T: FloatSemantics>(v: T) -> T {
119119
/// Callers use this before handing float data to Arrow kernels that compare
120120
/// bit patterns, so that `+0.0 = -0.0` holds.
121121
///
122-
/// The common case - nothing to normalize - is allocation-free: a single
123-
/// read-only scan of the values buffer (auto-vectorizable to an OR-reduction)
124-
/// decides whether to fall through to the rewriting path. Only arrays that
125-
/// contain values to normalize pay for a new buffer.
126-
pub fn normalize_floats(array: &ArrayRef) -> ArrayRef {
122+
/// Optimized for the common case of nothing to normalize, by searching for such
123+
/// values in a vectorized way. If noting needs normalization, the original
124+
/// array is returned unchanged.
125+
///
126+
/// If the values do require normalization, attempts to rewrite in place when
127+
/// possible (when the underlying buffers are not shared). Thus, passing
128+
/// `Arc::clone(&array)` therefore always copies if normalization is required.
129+
pub fn normalize(array: ArrayRef) -> ArrayRef {
127130
match array.data_type() {
128131
DataType::Float16 => normalize_primitive::<Float16Type>(array),
129132
DataType::Float32 => normalize_primitive::<Float32Type>(array),
@@ -133,14 +136,14 @@ pub fn normalize_floats(array: &ArrayRef) -> ArrayRef {
133136
let children = data
134137
.child_data()
135138
.iter()
136-
.map(|child| normalize_floats(&make_array(child.clone())).to_data())
139+
.map(|child| normalize(make_array(child.clone())).to_data())
137140
.collect::<Vec<_>>();
138141
if children
139142
.iter()
140143
.zip(data.child_data())
141144
.all(|(new, old)| new.ptr_eq(old))
142145
{
143-
return Arc::clone(array);
146+
return array;
144147
}
145148
make_array(
146149
data.into_builder()
@@ -149,20 +152,39 @@ pub fn normalize_floats(array: &ArrayRef) -> ArrayRef {
149152
.expect("rewriting float leaves preserves the array layout"),
150153
)
151154
}
152-
_ => Arc::clone(array),
155+
_ => array,
153156
}
154157
}
155158

156-
fn normalize_primitive<T>(array: &ArrayRef) -> ArrayRef
159+
/// Like [`normalize`], but borrows the array and so always copies the values
160+
/// buffer when there is something to normalize.
161+
#[deprecated(
162+
since = "57.0.0",
163+
note = "use `datafusion_common::float_semantics::normalize` instead"
164+
)]
165+
pub fn normalize_floats(array: &ArrayRef) -> ArrayRef {
166+
normalize(Arc::clone(array))
167+
}
168+
169+
/// Takes an owned array and tries to reuse its allocation when possible
170+
fn normalize_primitive<T>(array: ArrayRef) -> ArrayRef
157171
where
158172
T: ArrowPrimitiveType,
159173
T::Native: FloatSemantics,
160174
{
161175
let arr = array.as_primitive::<T>();
162176
if !arr.values().iter().any(|v| v.needs_normalization()) {
163-
return Arc::clone(array);
177+
return array;
164178
}
165-
Arc::new(arr.unary::<_, T>(normalize_float))
179+
// Drop the `ArrayRef` so the values buffer is uniquely owned (when nothing
180+
// else refers to it) and can be rewritten in place.
181+
let arr = arr.clone();
182+
drop(array);
183+
let normalized = match arr.unary_mut(normalize_float) {
184+
Ok(normalized) => normalized, // updated in place
185+
Err(arr) => arr.unary::<_, T>(normalize_float), // needed to copy
186+
};
187+
Arc::new(normalized)
166188
}
167189

168190
/// Whether `data_type` is a float or contains a float at any depth of its
@@ -246,23 +268,20 @@ mod tests {
246268

247269
#[test]
248270
fn normalize_floats_rewrites_negative_zero() {
249-
let array: ArrayRef =
250-
Arc::new(Float64Array::from(vec![Some(-0.0), None, Some(1.0)]));
251-
let result = normalize_floats(&array);
252-
let result = result.as_primitive::<Float64Type>();
253-
assert_eq!(result.value(0).to_bits(), 0.0_f64.to_bits());
254-
assert!(result.is_null(1));
255-
assert_eq!(result.value(2), 1.0);
271+
let floats = &[Some(5.0), Some(-0.0), None, Some(2.0)];
272+
let (array, _) = float64_array_fixture(floats);
273+
let result = normalize(Arc::clone(&array));
274+
assert_float64_values(&result, &[Some(5.0), Some(0.0), None, Some(2.0)]);
256275

257276
let array: ArrayRef = Arc::new(Float32Array::from(vec![-0.0_f32]));
258-
let result = normalize_floats(&array);
277+
let result = normalize(Arc::clone(&array));
259278
assert_eq!(
260279
result.as_primitive::<Float32Type>().value(0).to_bits(),
261280
0.0_f32.to_bits()
262281
);
263282

264283
let array: ArrayRef = Arc::new(Float16Array::from(vec![f16::NEG_ZERO]));
265-
let result = normalize_floats(&array);
284+
let result = normalize(Arc::clone(&array));
266285
assert_eq!(
267286
result.as_primitive::<Float16Type>().value(0).to_bits(),
268287
f16::ZERO.to_bits()
@@ -272,10 +291,38 @@ mod tests {
272291
#[test]
273292
fn normalize_floats_reuses_normalized_input() {
274293
let array: ArrayRef = Arc::new(Float64Array::from(vec![0.0, 1.0, f64::NAN]));
275-
assert!(Arc::ptr_eq(&normalize_floats(&array), &array));
294+
assert!(Arc::ptr_eq(&normalize(Arc::clone(&array)), &array));
276295

277296
let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2]));
278-
assert!(Arc::ptr_eq(&normalize_floats(&array), &array));
297+
assert!(Arc::ptr_eq(&normalize(Arc::clone(&array)), &array));
298+
}
299+
300+
#[test]
301+
fn normalize_floats_rewrites_in_place_when_unique() {
302+
let floats = &[Some(5.0), Some(-0.0), None, Some(2.0)];
303+
let expected = &[Some(5.0), Some(0.0), None, Some(2.0)];
304+
let (array, values_ptr) = float64_array_fixture(floats);
305+
let (result, result_values_ptr) = normalize_fixture(array);
306+
assert_eq!(result_values_ptr, values_ptr);
307+
assert_float64_values(&result, expected);
308+
309+
// A shared buffer is copied and the original is left as it is
310+
let (array, values_ptr) = float64_array_fixture(floats);
311+
let (result, result_values_ptr) = normalize_fixture(Arc::clone(&array));
312+
assert_ne!(result_values_ptr, values_ptr);
313+
assert_float64_values(&result, expected);
314+
assert_float64_values(&array, floats);
315+
}
316+
317+
#[test]
318+
fn normalize_floats_copies_shared_slice() {
319+
let floats = &[Some(5.0), Some(-0.0), None, Some(2.0)];
320+
let (parent, values_ptr) = float64_array_fixture(floats);
321+
let slice = parent.slice(1, 3);
322+
let (result, result_values_ptr) = normalize_fixture(slice);
323+
assert_ne!(result_values_ptr, values_ptr.wrapping_add(1));
324+
assert_float64_values(&result, &[Some(0.0), None, Some(2.0)]);
325+
assert_float64_values(&parent, floats);
279326
}
280327

281328
#[test]
@@ -285,7 +332,7 @@ mod tests {
285332
None,
286333
]);
287334
let array: ArrayRef = Arc::new(list);
288-
let result = normalize_floats(&array);
335+
let result = normalize(Arc::clone(&array));
289336
assert!(!Arc::ptr_eq(&result, &array));
290337
let values = result.as_list::<i32>().value(0);
291338
assert_eq!(
@@ -297,27 +344,30 @@ mod tests {
297344
let list =
298345
ListArray::from_iter_primitive::<Int32Type, _, _>(vec![Some(vec![Some(1)])]);
299346
let array: ArrayRef = Arc::new(list);
300-
assert!(Arc::ptr_eq(&normalize_floats(&array), &array));
347+
assert!(Arc::ptr_eq(&normalize(Arc::clone(&array)), &array));
301348
}
302349

303350
#[test]
304-
fn normalize_floats_in_dictionary_arrays_and_scalars() -> Result<()> {
351+
fn normalize_in_dictionary_arrays_and_scalars() -> Result<()> {
305352
let nan = f64::from_bits(0x7ff8_0000_0000_0001);
306353
let keys = Int8Array::from(vec![Some(0), Some(1), None, Some(2)]);
307354
let array: ArrayRef = Arc::new(DictionaryArray::try_new(
308355
keys.clone(),
309356
Arc::new(Float64Array::from(vec![-0.0, nan, 1.0])),
310357
)?);
311358

312-
let normalized = normalize_floats(&array);
359+
let normalized = normalize(Arc::clone(&array));
313360
let dictionary = normalized.as_dictionary::<Int8Type>();
314361
assert_eq!(dictionary.keys(), &keys);
315362
let values = dictionary.values().as_primitive::<Float64Type>();
316363
assert_eq!(values.value(0).to_bits(), 0.0_f64.to_bits());
317364
assert_eq!(values.value(1).to_bits(), nan.to_bits());
318365
assert_eq!(values.value(2), 1.0);
319366

320-
assert!(Arc::ptr_eq(&normalize_floats(&normalized), &normalized));
367+
assert!(Arc::ptr_eq(
368+
&normalize(Arc::clone(&normalized)),
369+
&normalized
370+
));
321371

322372
assert_eq!(
323373
ScalarValue::try_from_array(&array, 0)?.normalize(),
@@ -395,4 +445,37 @@ mod tests {
395445
assert_eq!(child.value(1).to_bits(), nan.to_bits());
396446
assert!(child.is_null(2));
397447
}
448+
449+
/// Creates a float64 array and returns it with a pointer to its values
450+
fn float64_array_fixture(input: &[Option<f64>]) -> (ArrayRef, *const f64) {
451+
let array: ArrayRef = Arc::new(Float64Array::from(input.to_vec()));
452+
let values_ptr = array.as_primitive::<Float64Type>().values().as_ptr();
453+
(array, values_ptr)
454+
}
455+
456+
/// Calls `normalize` and returns the normalized array and a pointer to its values
457+
fn normalize_fixture(array: ArrayRef) -> (ArrayRef, *const f64) {
458+
let result = normalize(array);
459+
let values_ptr = result.as_primitive::<Float64Type>().values().as_ptr();
460+
(result, values_ptr)
461+
}
462+
463+
/// Asserts that the values in a float64 array match the expected values
464+
fn assert_float64_values(array: &ArrayRef, expected: &[Option<f64>]) {
465+
let array = array.as_primitive::<Float64Type>();
466+
// Note don't use the eq on FloatArray to ensure we are comparing using
467+
// bitwise equality (not normalized equality).
468+
assert_eq!(array.len(), expected.len());
469+
assert_eq!(
470+
array.null_count(),
471+
expected.iter().filter(|value| value.is_none()).count()
472+
);
473+
for (index, (actual, expected)) in array.iter().zip(expected).enumerate() {
474+
assert_eq!(
475+
actual.map(f64::to_bits),
476+
expected.map(f64::to_bits),
477+
"value at index {index}"
478+
);
479+
}
480+
}
398481
}

0 commit comments

Comments
 (0)