Repository: jorgecarleitao/arrow2
Pull request #1348 (2022-12-30 11:15:58)

fix: correct for endiannes in leading ones compute
Fix a bug introduced with the filter optimization. Trailing `trailing_ones` goes from LSB to MSB whilst I mentally mapped it L -> R. 

This fixes that.

codecov[bot]: # [Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) Report
Base: **83.16**% // Head: **83.18**% // Increases project coverage by **`+0.01%`** :tada:
> Coverage data is based on head [(`8c3ec60`)](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) compared to base [(`0dd5680`)](https://codecov.io/gh/jorgecarleitao/arrow2/commit/0dd56805afa06ac4f75dac3c32401364758a1c68?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao).
> Patch coverage: 85.71% of modified lines in pull request are covered.

> :exclamation: Current head 8c3ec60 differs from pull request most recent head baa2618. Consider uploading reports for the commit baa2618 to get more accurate results

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main    #1348      +/-   ##
==========================================
+ Coverage   83.16%   83.18%   +0.01%     
==========================================
  Files         371      371              
  Lines       40299    40304       +5     
==========================================
+ Hits        33514    33525      +11     
+ Misses       6785     6779       -6     
```


| [Impacted Files](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) | Coverage Δ | |
|---|---|---|
| [src/compute/filter.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2NvbXB1dGUvZmlsdGVyLnJz) | `74.02% <85.71%> (+3.22%)` | :arrow_up: |
| [src/bitmap/utils/slice\_iterator.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2JpdG1hcC91dGlscy9zbGljZV9pdGVyYXRvci5ycw==) | `97.56% <0.00%> (-1.22%)` | :arrow_down: |
| [src/array/utf8/mod.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2FycmF5L3V0ZjgvbW9kLnJz) | `84.94% <0.00%> (-1.01%)` | :arrow_down: |
| [src/io/ipc/read/file.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2lvL2lwYy9yZWFkL2ZpbGUucnM=) | `96.87% <0.00%> (ø)` | |
| [src/types/bit\_chunk.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL3R5cGVzL2JpdF9jaHVuay5ycw==) | `100.00% <0.00%> (+8.33%)` | :arrow_up: |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1348?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao).


Patch:
diff --git a/src/compute/filter.rs b/src/compute/filter.rs
index a293695b85..0299e5045f 100644
--- a/src/compute/filter.rs
+++ b/src/compute/filter.rs
@@ -12,6 +12,15 @@ use crate::{array::*, types::NativeType};
 /// Function that can filter arbitrary arrays
 pub type Filter<'a> = Box<dyn Fn(&dyn Array) -> Box<dyn Array> + 'a + Send + Sync>;
 
+#[inline]
+fn get_leading_ones(chunk: u64) -> u32 {
+    if cfg!(target_endian = "little") {
+        chunk.trailing_ones()
+    } else {
+        chunk.leading_ones()
+    }
+}
+
 /// # Safety
 /// This assumes that the `mask_chunks` contains a number of set/true items equal
 /// to `filter_count`
@@ -29,7 +38,7 @@ where
         .zip(mask_chunks.by_ref())
         .for_each(|(chunk, mask_chunk)| {
             let ones = mask_chunk.count_ones();
-            let leading_ones = mask_chunk.leading_ones();
+            let leading_ones = get_leading_ones(mask_chunk);
 
             if ones == leading_ones {
                 let size = leading_ones as usize;
@@ -91,7 +100,7 @@ where
         .zip(mask_chunks.by_ref())
         .for_each(|((chunk, validity_chunk), mask_chunk)| {
             let ones = mask_chunk.count_ones();
-            let leading_ones = mask_chunk.leading_ones();
+            let leading_ones = get_leading_ones(mask_chunk);
 
             if ones == leading_ones {
                 let size = leading_ones as usize;


Test patch:
diff --git a/tests/it/compute/filter.rs b/tests/it/compute/filter.rs
index cdec0b8297..98df9079d0 100644
--- a/tests/it/compute/filter.rs
+++ b/tests/it/compute/filter.rs
@@ -13,6 +13,26 @@ fn array_slice() {
     assert_eq!(expected, c.as_ref());
 }
 
+#[test]
+fn array_large_filter_chunks() {
+    let len = 65usize;
+    let a = Int32Array::from_iter((0..(len as i32)).map(Some));
+
+    let init = vec![true, true, true, false, false, true];
+    let remaining = len - init.len();
+    let iter = init
+        .into_iter()
+        .chain(std::iter::repeat(false).take(remaining))
+        .map(Some);
+    let b = BooleanArray::from_iter(iter);
+
+    let c = filter(&a, &b).unwrap();
+
+    let expected = Int32Array::from_slice([0, 1, 2, 5]);
+
+    assert_eq!(expected, c.as_ref());
+}
+
 #[test]
 fn array_low_density() {
     // this test exercises the all 0's branch of the filter algorithm
@@ -71,7 +91,7 @@ fn string_array_simple() {
 }
 
 #[test]
-fn primative_array_with_null() {
+fn primitive_array_with_null() {
     let a = Int32Array::from(&[Some(5), None]);
     let b = BooleanArray::from_slice(vec![false, true]);
     let c = filter(&a, &b).unwrap();