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
157171where
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