Repository: jorgecarleitao/arrow2
Pull request #1004 (2022-05-22 06:22:09)

Rewrite `min_max_string` and `min_max_binary`
Signed-off-by: remzi <13716567376yh@gmail.com>

# Changes in the PR
1. Replace `fold` with `reduce`
2. use macro to abstract the common expression
3. Add test to cover the `no null` cases.
4. Add benchmark for `min utf8`
5. Less code is better
6. Functional style

# No obvious performance impact
```
min 2^10 utf8           time:   [33.766 ns 33.786 ns 33.810 ns]                           
                        change: [+0.0167% +0.2385% +0.4298%] (p = 0.02 < 0.05)
                        Change within noise threshold.
Found 7 outliers among 100 measurements (7.00%)
  3 (3.00%) high mild
  4 (4.00%) high severe

min null 2^10 utf8      time:   [33.352 ns 33.370 ns 33.391 ns]                                
                        change: [-4.7561% -4.6289% -4.5317%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  4 (4.00%) high mild
  4 (4.00%) high severe
```

codecov[bot]: # [Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1004?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) Report
> Merging [#1004](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1004?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) (845b1c8) into [main](https://codecov.io/gh/jorgecarleitao/arrow2/commit/a10db3a4f6237a145fd58629800baa82f7a8ab94?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) (a10db3a) will **increase** coverage by `0.01%`.
> The diff coverage is `92.30%`.

```diff
@@            Coverage Diff             @@
##             main    #1004      +/-   ##
==========================================
+ Coverage   71.42%   71.44%   +0.01%     
==========================================
  Files         356      356              
  Lines       19784    19779       -5     
==========================================
  Hits        14131    14131              
+ Misses       5653     5648       -5     
```


| [Impacted Files](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1004?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) | Coverage Δ | |
|---|---|---|
| [src/compute/aggregate/min\_max.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1004/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2NvbXB1dGUvYWdncmVnYXRlL21pbl9tYXgucnM=) | `72.95% <92.30%> (+2.22%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1004?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1004?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao). Last update [a10db3a...845b1c8](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1004?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao).


Patch:
diff --git a/benches/aggregate.rs b/benches/aggregate.rs
index d515fff128..f157550d15 100644
--- a/benches/aggregate.rs
+++ b/benches/aggregate.rs
@@ -42,6 +42,18 @@ fn add_benchmark(c: &mut Criterion) {
         c.bench_function(&format!("min null 2^{} f32", log2_size), |b| {
             b.iter(|| bench_min(&arr_a))
         });
+
+        let arr_a = create_string_array::<i32>(1, size, 0.0, 0);
+
+        c.bench_function(&format!("min 2^{} utf8", log2_size), |b| {
+            b.iter(|| bench_min(&arr_a))
+        });
+
+        let arr_a = create_string_array::<i32>(1, size, 0.1, 0);
+
+        c.bench_function(&format!("min null 2^{} utf8", log2_size), |b| {
+            b.iter(|| bench_min(&arr_a))
+        });
     });
 }
 
diff --git a/src/compute/aggregate/min_max.rs b/src/compute/aggregate/min_max.rs
index 2c6478cff4..54c9e7d504 100644
--- a/src/compute/aggregate/min_max.rs
+++ b/src/compute/aggregate/min_max.rs
@@ -30,86 +30,6 @@ pub trait SimdOrd<T> {
     fn new_max() -> Self;
 }
 
-/// Helper to compute min/max of [`BinaryArray`]
-fn min_max_binary<O: Offset, F: Fn(&[u8], &[u8]) -> bool>(
-    array: &BinaryArray<O>,
-    cmp: F,
-) -> Option<&[u8]> {
-    let null_count = array.null_count();
-
-    if null_count == array.len() || array.len() == 0 {
-        return None;
-    }
-    let value = if array.validity().is_some() {
-        array.iter().fold(None, |mut acc: Option<&[u8]>, v| {
-            if let Some(item) = v {
-                if let Some(acc) = acc.as_mut() {
-                    if cmp(acc, item) {
-                        *acc = item
-                    }
-                } else {
-                    acc = Some(item)
-                }
-            }
-            acc
-        })
-    } else {
-        array
-            .values_iter()
-            .fold(None, |mut acc: Option<&[u8]>, item| {
-                if let Some(acc) = acc.as_mut() {
-                    if cmp(acc, item) {
-                        *acc = item
-                    }
-                } else {
-                    acc = Some(item)
-                }
-                acc
-            })
-    };
-    value
-}
-
-/// Helper to compute min/max of [`Utf8Array`]
-fn min_max_string<O: Offset, F: Fn(&str, &str) -> bool>(
-    array: &Utf8Array<O>,
-    cmp: F,
-) -> Option<&str> {
-    let null_count = array.null_count();
-
-    if null_count == array.len() || array.len() == 0 {
-        return None;
-    }
-    let value = if array.validity().is_some() {
-        array.iter().fold(None, |mut acc: Option<&str>, v| {
-            if let Some(item) = v {
-                if let Some(acc) = acc.as_mut() {
-                    if cmp(acc, item) {
-                        *acc = item
-                    }
-                } else {
-                    acc = Some(item)
-                }
-            }
-            acc
-        })
-    } else {
-        array
-            .values_iter()
-            .fold(None, |mut acc: Option<&str>, item| {
-                if let Some(acc) = acc.as_mut() {
-                    if cmp(acc, item) {
-                        *acc = item
-                    }
-                } else {
-                    acc = Some(item)
-                }
-                acc
-            })
-    };
-    value
-}
-
 fn nonnull_min_primitive<T>(values: &[T]) -> T
 where
     T: NativeType + Simd,
@@ -278,24 +198,52 @@ where
     })
 }
 
+/// Helper to compute min/max of [`BinaryArray`] and [`Utf8Array`]
+macro_rules! min_max_binary_utf8 {
+    ($array: expr, $cmp: expr) => {
+        if $array.null_count() == $array.len() {
+            None
+        } else if $array.validity().is_some() {
+            $array
+                .iter()
+                .reduce(|v1, v2| match (v1, v2) {
+                    (None, v2) => v2,
+                    (v1, None) => v1,
+                    (Some(v1), Some(v2)) => {
+                        if $cmp(v1, v2) {
+                            Some(v2)
+                        } else {
+                            Some(v1)
+                        }
+                    }
+                })
+                .unwrap_or(None)
+        } else {
+            $array
+                .values_iter()
+                .reduce(|v1, v2| if $cmp(v1, v2) { v2 } else { v1 })
+        }
+    };
+}
+
 /// Returns the maximum value in the binary array, according to the natural order.
 pub fn max_binary<O: Offset>(array: &BinaryArray<O>) -> Option<&[u8]> {
-    min_max_binary(array, |a, b| a < b)
+    min_max_binary_utf8!(array, |a, b| a < b)
 }
 
 /// Returns the minimum value in the binary array, according to the natural order.
 pub fn min_binary<O: Offset>(array: &BinaryArray<O>) -> Option<&[u8]> {
-    min_max_binary(array, |a, b| a > b)
+    min_max_binary_utf8!(array, |a, b| a > b)
 }
 
 /// Returns the maximum value in the string array, according to the natural order.
 pub fn max_string<O: Offset>(array: &Utf8Array<O>) -> Option<&str> {
-    min_max_string(array, |a, b| a < b)
+    min_max_binary_utf8!(array, |a, b| a < b)
 }
 
 /// Returns the minimum value in the string array, according to the natural order.
 pub fn min_string<O: Offset>(array: &Utf8Array<O>) -> Option<&str> {
-    min_max_string(array, |a, b| a > b)
+    min_max_binary_utf8!(array, |a, b| a > b)
 }
 
 /// Returns the minimum value in the boolean array.


Test patch:
diff --git a/tests/it/compute/aggregate/min_max.rs b/tests/it/compute/aggregate/min_max.rs
index 224a245ae7..3cfc8b675f 100644
--- a/tests/it/compute/aggregate/min_max.rs
+++ b/tests/it/compute/aggregate/min_max.rs
@@ -112,12 +112,11 @@ fn min_max_f64_edge_cases() {
     assert_eq!(Some(f64::INFINITY), max_primitive(&a));
 }
 
-// todo: convert me
 #[test]
 fn test_string_min_max_with_nulls() {
     let a = Utf8Array::<i32>::from(&[Some("b"), None, None, Some("a"), Some("c")]);
-    assert_eq!("a", min_string(&a).unwrap());
-    assert_eq!("c", max_string(&a).unwrap());
+    assert_eq!(Some("a"), min_string(&a));
+    assert_eq!(Some("c"), max_string(&a));
 }
 
 #[test]
@@ -127,6 +126,13 @@ fn test_string_min_max_all_nulls() {
     assert_eq!(None, max_string(&a));
 }
 
+#[test]
+fn test_string_min_max_no_null() {
+    let a = Utf8Array::<i32>::from(&[Some("abc"), Some("abd"), Some("bac"), Some("bbb")]);
+    assert_eq!(Some("abc"), min_string(&a));
+    assert_eq!(Some("bbb"), max_string(&a));
+}
+
 #[test]
 fn test_string_min_max_1() {
     let a = Utf8Array::<i32>::from(&[None, None, Some("b"), Some("a")]);
@@ -192,8 +198,20 @@ fn test_boolean_min_max_smaller() {
 #[test]
 fn test_binary_min_max_with_nulls() {
     let a = BinaryArray::<i32>::from(&[Some(b"b"), None, None, Some(b"a"), Some(b"c")]);
-    assert_eq!("a".as_bytes(), min_binary(&a).unwrap());
-    assert_eq!("c".as_bytes(), max_binary(&a).unwrap());
+    assert_eq!(Some("a".as_bytes()), min_binary(&a));
+    assert_eq!(Some("c".as_bytes()), max_binary(&a));
+}
+
+#[test]
+fn test_binary_min_max_no_null() {
+    let a = BinaryArray::<i32>::from(&[
+        Some("abc".as_bytes()),
+        Some(b"acd"),
+        Some(b"aabd"),
+        Some(b""),
+    ]);
+    assert_eq!(Some("".as_bytes()), min_binary(&a));
+    assert_eq!(Some("acd".as_bytes()), max_binary(&a));
 }
 
 #[test]