mkleen commented on code in PR #26595: URL: https://github.com/apache/datafusion/pull/26595#discussion_r4367117112
########## datafusion/common/src/float_semantics.rs: ########## @@ -0,0 +1,347 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Float semantics for DataFusion. +//! +//! Arrow's comparison kernels work on the bit pattern of a float, +//! i.e. IEEE 754 totalOrder. DataFusion deviates from that in one +//! respect: `+0.0` and `-0.0` are equal, hash the same and fall into the same +//! group. See [`normalize_float`], [`normalize_floats`] and +//! [`normalize_float_scalar`]. Ordering still follows totalOrder, so +//! [`compare_floats`] sorts `-0.0` before `+0.0`. +//! +//! Every comparison, hash or grouping boundary should be built from these +//! helpers rather than inspecting float bits itself: +//! +//! - Equality and grouping: normalize first ([`normalize_float`], +//! [`normalize_floats`], [`normalize_float_scalar`]), then compare bits or +//! call Arrow's `eq`, `RowConverter` or `make_comparator`. Hash +//! [`hash_input`]. +//! - Ordering: use [`compare_floats`], [`float_lt`] or [`float_gt`]. Sorting +//! does not normalize yet, so `-0.0` still sorts before `+0.0`. +//! + +use std::cmp::Ordering; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, make_array}; +use arrow::datatypes::{ + ArrowPrimitiveType, DataType, Float16Type, Float32Type, Float64Type, +}; +use half::f16; + +use crate::ScalarValue; + +/// The floating point types the functions in this module are defined for: +/// [`f16`](struct@f16), [`f32`] and [`f64`]. +pub trait FloatSemantics: Copy { + /// Whether [`normalize_float`] would change this value. This is a cheap + /// check that lets callers skip rewriting data which is already + /// normalized. + fn needs_normalization(self) -> bool; + + /// See [`normalize_float`]. + fn normalize(self) -> Self; + + /// See [`compare_floats`]. + fn compare(self, other: Self) -> Ordering; +} + +macro_rules! impl_float_semantics { + ($(($t:ty, $bits:ty, $zero:expr)),+ $(,)?) => { + $(impl FloatSemantics for $t { + #[inline] + fn needs_normalization(self) -> bool { + // `-0.0` has only the sign bit set; no other value shares + // this bit pattern. + self.to_bits() == 1 << (<$bits>::BITS - 1) + } + + #[inline] + fn normalize(self) -> Self { + if self.needs_normalization() { $zero } else { self } + } + + #[inline] + fn compare(self, other: Self) -> Ordering { + self.total_cmp(&other) + } + })+ + }; +} +impl_float_semantics!((f16, u16, f16::ZERO), (f32, u32, 0.0), (f64, u64, 0.0)); + +/// `-0.0` becomes `0.0`, so two values that DataFusion treats as equal also +/// have the same bits. All other values, including NaN payloads, are kept as +/// they are. +#[inline] +pub fn normalize_float<T: FloatSemantics>(v: T) -> T { + v.normalize() +} + +/// Compares two values in the order DataFusion sorts them. +/// +/// This is IEEE 754 totalOrder (`total_cmp`), which matches Arrow's sort +/// kernels and row encoding. Note that it orders `-0.0` before `+0.0`. +/// The grouped `MIN`/`MAX` accumulators start from the extremes of this +/// order, so they must change together with it. +#[inline] +pub fn compare_floats<T: FloatSemantics>(left: T, right: T) -> Ordering { + left.compare(right) +} + +/// Whether `left` sorts before `right`, the same as +/// `compare_floats(left, right).is_lt()`. +#[inline] +pub fn float_lt<T: FloatSemantics>(left: T, right: T) -> bool { + compare_floats(left, right).is_lt() +} + +/// Whether `left` sorts after `right`, the same as +/// `compare_floats(left, right).is_gt()`. +#[inline] +pub fn float_gt<T: FloatSemantics>(left: T, right: T) -> bool { + compare_floats(left, right).is_gt() +} + +/// The value that DataFusion hashes in place of a float. Values that DataFusion +/// treats as equal hash the same, so this is the value [`normalize_float`] +/// returns. +#[inline] +pub fn hash_input<T: FloatSemantics>(v: T) -> T { + normalize_float(v) +} + +/// Applies [`normalize_float`] to every float in `array`, including floats +/// nested inside lists, structs, maps, unions, dictionaries and run-end +/// encoded arrays. Arrays without floats are returned unchanged. +/// +/// Callers use this before handing float data to Arrow kernels that compare +/// bit patterns, so that `+0.0 = -0.0` holds. +/// +/// The common case - nothing to normalize - is allocation-free: a single +/// read-only scan of the values buffer (auto-vectorizable to an OR-reduction) +/// decides whether to fall through to the rewriting path. Only arrays that +/// contain values to normalize pay for a new buffer. +pub fn normalize_floats(array: &ArrayRef) -> ArrayRef { + match array.data_type() { + DataType::Float16 => normalize_primitive::<Float16Type>(array), + DataType::Float32 => normalize_primitive::<Float32Type>(array), + DataType::Float64 => normalize_primitive::<Float64Type>(array), + dt if has_float_leaf(dt) => { + let data = array.to_data(); + let children = data + .child_data() + .iter() + .map(|child| normalize_floats(&make_array(child.clone())).to_data()) + .collect::<Vec<_>>(); + if children + .iter() + .zip(data.child_data()) + .all(|(new, old)| new.ptr_eq(old)) + { + return Arc::clone(array); + } + make_array( + data.into_builder() + .child_data(children) + .build() + .expect("rewriting float leaves preserves the array layout"), + ) + } + _ => Arc::clone(array), + } +} + +fn normalize_primitive<T>(array: &ArrayRef) -> ArrayRef +where + T: ArrowPrimitiveType, + T::Native: FloatSemantics, +{ + let arr = array.as_primitive::<T>(); + if !arr.values().iter().any(|v| v.needs_normalization()) { + return Arc::clone(array); + } + Arc::new(arr.unary::<_, T>(normalize_float)) +} + +/// Applies [`normalize_float`] to a `Float16`, `Float32` or `Float64` scalar. +/// Other scalars are returned as is. +pub fn normalize_float_scalar(scalar: ScalarValue) -> ScalarValue { Review Comment: You want this in this pr or as a follow-up ? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
