Repository: jorgecarleitao/arrow2
Pull request #327 (2021-08-24 07:34:09)

Fixed error in extending bitmaps
The extension on unaligned bitmap was incorrect.

codecov[bot]: # [Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) Report
> Merging [#327](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) (f6c5906) into [main](https://codecov.io/gh/jorgecarleitao/arrow2/commit/824ad7ec8d714449f321683d963c9b737ff736ba?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) (824ad7e) will **increase** coverage by `0.00%`.
> The diff coverage is `94.11%`.

[![Impacted file tree graph](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327/graphs/tree.svg?width=650&height=150&src=pr&token=AgyTF60R3D&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao)](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao)

```diff
@@           Coverage Diff           @@
##             main     #327   +/-   ##
=======================================
  Coverage   80.55%   80.56%           
=======================================
  Files         324      324           
  Lines       21399    21414   +15     
=======================================
+ Hits        17239    17252   +13     
- Misses       4160     4162    +2     
```


| [Impacted Files](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) | Coverage Δ | |
|---|---|---|
| [src/bitmap/mutable.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2JpdG1hcC9tdXRhYmxlLnJz) | `89.21% <90.00%> (-0.06%)` | :arrow_down: |
| [tests/it/bitmap/mutable.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-dGVzdHMvaXQvYml0bWFwL211dGFibGUucnM=) | `100.00% <100.00%> (ø)` | |
| [src/io/json\_integration/write.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2lvL2pzb25faW50ZWdyYXRpb24vd3JpdGUucnM=) | `0.00% <0.00%> (-6.25%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327?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/327?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao). Last update [824ad7e...f6c5906](https://codecov.io/gh/jorgecarleitao/arrow2/pull/327?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/Cargo.toml b/Cargo.toml
index e779422396..7175283b7c 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -18,7 +18,7 @@ bench = false
 num = "^0.4"
 chrono = "^0.4"
 # To efficiently cast numbers to strings
-lexical-core = "^0.7"
+lexical-core = { version = "0.7", optional = true }
 # We need to Hash values before sending them to an hasher. This
 # crate provides HashMap that assumes pre-hashed values.
 hash_hasher = "^2.0.3"
@@ -50,8 +50,6 @@ base64 = { version = "0.13.0", optional = true }
 
 packed_simd = { version = "0.3.4", optional = true, package = "packed_simd_2" }
 
-multiversion = "0.6.1"
-
 # to write to parquet as a stream
 futures = { version = "0.3", optional = true }
 
@@ -62,6 +60,7 @@ parquet2 = { version = "0.3", optional = true, default_features = false, feature
 
 # for division/remainder optimization at runtime
 strength_reduce = { version = "0.2", optional = true }
+multiversion = { version = "0.6.1", optional = true }
 
 [dev-dependencies]
 rand = "0.8"
@@ -87,7 +86,7 @@ default = [
     "compute",
 ]
 merge_sort = ["itertools"]
-io_csv = ["csv", "lazy_static", "regex"]
+io_csv = ["csv", "lazy_static", "regex", "lexical-core"]
 io_json = ["serde", "serde_json", "indexmap"]
 io_ipc = ["flatbuffers"]
 io_ipc_compression = ["lz4", "zstd"]
@@ -103,7 +102,7 @@ io_parquet_compression = [
 io_json_integration = ["io_json", "serde_derive", "hex"]
 io_print = ["comfy-table"]
 # the compute kernels. Disabling this significantly reduces compile time.
-compute = ["strength_reduce"]
+compute = ["strength_reduce", "multiversion", "lexical-core"]
 # base64 + io_ipc because arrow schemas are stored as base64-encoded ipc format.
 io_parquet = ["parquet2", "io_ipc", "base64", "futures"]
 benchmarks = ["rand"]
diff --git a/benches/comparison_kernels.rs b/benches/comparison_kernels.rs
index 2c41f8dbd6..be76eb0597 100644
--- a/benches/comparison_kernels.rs
+++ b/benches/comparison_kernels.rs
@@ -42,6 +42,16 @@ fn add_benchmark(c: &mut Criterion) {
         c.bench_function(&format!("bool scalar 2^{}", log2_size), |b| {
             b.iter(|| bench_op_scalar(&arr_a, &BooleanScalar::from(Some(true)), Operator::Eq))
         });
+
+        let arr_a = create_string_array::<i32>(size, 0.1, 42);
+        let arr_b = create_string_array::<i32>(size, 0.1, 43);
+        c.bench_function(&format!("utf8 2^{}", log2_size), |b| {
+            b.iter(|| bench_op(&arr_a, &arr_b, Operator::Eq))
+        });
+
+        c.bench_function(&format!("utf8 2^{}", log2_size), |b| {
+            b.iter(|| bench_op_scalar(&arr_a, &Utf8Scalar::<i32>::from(Some("abc")), Operator::Eq))
+        });
     })
 }
 
diff --git a/benches/filter_kernels.rs b/benches/filter_kernels.rs
index 4ff8b0428d..65aaad8675 100644
--- a/benches/filter_kernels.rs
+++ b/benches/filter_kernels.rs
@@ -113,7 +113,7 @@ fn add_benchmark(c: &mut Criterion) {
         b.iter(|| bench_built_filter(&sparse_filter, &data_array))
     });
 
-    let data_array = create_string_array::<i32>(size, 0.5);
+    let data_array = create_string_array::<i32>(size, 0.5, 42);
     c.bench_function("filter context string", |b| {
         b.iter(|| bench_built_filter(&filter, &data_array))
     });
diff --git a/benches/sort_kernel.rs b/benches/sort_kernel.rs
index e78e4462b0..780b361999 100644
--- a/benches/sort_kernel.rs
+++ b/benches/sort_kernel.rs
@@ -80,7 +80,7 @@ fn add_benchmark(c: &mut Criterion) {
             b.iter(|| bench_lexsort(&arr_a, &arr_b))
         });
 
-        let arr_a = create_string_array::<i32>(size, 0.1);
+        let arr_a = create_string_array::<i32>(size, 0.1, 42);
         c.bench_function(&format!("sort utf8 null 2^{}", log2_size), |b| {
             b.iter(|| bench_sort(&arr_a))
         });
diff --git a/benches/take_kernels.rs b/benches/take_kernels.rs
index 9303a719f3..a66ae30503 100644
--- a/benches/take_kernels.rs
+++ b/benches/take_kernels.rs
@@ -91,36 +91,36 @@ fn add_benchmark(c: &mut Criterion) {
         b.iter(|| bench_take(&values, &indices))
     });
 
-    let values = create_string_array::<i32>(512, 0.0);
+    let values = create_string_array::<i32>(512, 0.0, 42);
     let indices = create_random_index(512, 0.0);
     c.bench_function("take str 512", |b| b.iter(|| bench_take(&values, &indices)));
 
-    let values = create_string_array::<i32>(1024, 0.0);
+    let values = create_string_array::<i32>(1024, 0.0, 42);
     let indices = create_random_index(1024, 0.0);
     c.bench_function("take str 1024", |b| {
         b.iter(|| bench_take(&values, &indices))
     });
 
-    let values = create_string_array::<i32>(512, 0.0);
+    let values = create_string_array::<i32>(512, 0.0, 42);
     let indices = create_random_index(512, 0.5);
     c.bench_function("take str null indices 512", |b| {
         b.iter(|| bench_take(&values, &indices))
     });
 
-    let values = create_string_array::<i32>(1024, 0.0);
+    let values = create_string_array::<i32>(1024, 0.0, 42);
     let indices = create_random_index(1024, 0.5);
     c.bench_function("take str null indices 1024", |b| {
         b.iter(|| bench_take(&values, &indices))
     });
 
-    let values = create_string_array::<i32>(1024, 0.5);
+    let values = create_string_array::<i32>(1024, 0.5, 42);
 
     let indices = create_random_index(1024, 0.0);
     c.bench_function("take str null values 1024", |b| {
         b.iter(|| bench_take(&values, &indices))
     });
 
-    let values = create_string_array::<i32>(1024, 0.5);
+    let values = create_string_array::<i32>(1024, 0.5, 42);
     let indices = create_random_index(1024, 0.5);
     c.bench_function("take str null values null indices 1024", |b| {
         b.iter(|| bench_take(&values, &indices))
diff --git a/benches/write_ipc.rs b/benches/write_ipc.rs
index 23edc33b5f..a91b8e5da6 100644
--- a/benches/write_ipc.rs
+++ b/benches/write_ipc.rs
@@ -35,7 +35,7 @@ fn add_benchmark(c: &mut Criterion) {
     });
 
     (0..=10).step_by(2).for_each(|i| {
-        let array = &create_string_array::<i32>(1024 * 2usize.pow(i), 0.1);
+        let array = &create_string_array::<i32>(1024 * 2usize.pow(i), 0.1, 42);
         let a = format!("write utf8 2^{}", 10 + i);
         c.bench_function(&a, |b| b.iter(|| write(array).unwrap()));
     });
diff --git a/benches/write_parquet.rs b/benches/write_parquet.rs
index 7cff2c1305..d1a8ff37ae 100644
--- a/benches/write_parquet.rs
+++ b/benches/write_parquet.rs
@@ -55,13 +55,13 @@ fn add_benchmark(c: &mut Criterion) {
     });
 
     (0..=10).step_by(2).for_each(|i| {
-        let array = &create_string_array::<i32>(1024 * 2usize.pow(i), 0.1);
+        let array = &create_string_array::<i32>(1024 * 2usize.pow(i), 0.1, 42);
         let a = format!("write utf8 2^{}", 10 + i);
         c.bench_function(&a, |b| b.iter(|| write(array, Encoding::Plain).unwrap()));
     });
 
     (0..=10).step_by(2).for_each(|i| {
-        let array = &create_string_array::<i32>(1024 * 2usize.pow(i), 0.1);
+        let array = &create_string_array::<i32>(1024 * 2usize.pow(i), 0.1, 42);
         let a = format!("write utf8 delta 2^{}", 10 + i);
         c.bench_function(&a, |b| {
             b.iter(|| write(array, Encoding::DeltaLengthByteArray).unwrap())
diff --git a/src/bitmap/mutable.rs b/src/bitmap/mutable.rs
index f3ec798866..358d1786b2 100644
--- a/src/bitmap/mutable.rs
+++ b/src/bitmap/mutable.rs
@@ -15,6 +15,7 @@ use super::Bitmap;
 /// This container is backed by [`MutableBuffer<u8>`].
 pub struct MutableBitmap {
     buffer: MutableBuffer<u8>,
+    // invariant: length.saturating_add(7) / 8 == buffer.len();
     length: usize,
 }
 
@@ -466,12 +467,16 @@ impl MutableBitmap {
     }
 
     fn extend_unaligned(&mut self, slice: &[u8], offset: usize, length: usize) {
-        let own_offset = self.length % 8;
         // e.g.
         // [a, b, --101010]     <- to be extended
         // [00111111, 11010101] <- to extend
         // [a, b, 11101010, --001111] expected result
+
         let aligned_offset = offset / 8;
+        let own_offset = self.length % 8;
+        debug_assert_eq!(offset % 8, 0); // assumed invariant
+        debug_assert!(own_offset != 0); // assumed invariant
+
         let bytes_len = length.saturating_add(7) / 8;
         let items = &slice[aligned_offset..aligned_offset + bytes_len];
         // self has some offset => we need to shift all `items`, and merge the first
@@ -483,11 +488,19 @@ impl MutableBitmap {
         *last &= 0b11111111u8 >> (8 - own_offset); // unset before setting
         *last |= items[0] << own_offset;
 
+        if length + own_offset <= 8 {
+            // no new bytes needed
+            self.length += length;
+            return;
+        }
+        let additional = length - (8 - own_offset);
+
         let remaining = [items[items.len() - 1], 0];
         let bytes = items
             .windows(2)
             .chain(std::iter::once(remaining.as_ref()))
-            .map(|w| merge_reversed(w[0], w[1], 8 - own_offset));
+            .map(|w| merge_reversed(w[0], w[1], 8 - own_offset))
+            .take(additional.saturating_add(7) / 8);
         self.buffer.extend_from_trusted_len_iter(bytes);
 
         self.length += length;
@@ -520,6 +533,8 @@ impl MutableBitmap {
             // todo: further optimize the other branches.
             _ => self.extend_from_trusted_len_iter(BitmapIter::new(slice, offset, length)),
         }
+        // internal invariant:
+        debug_assert_eq!(self.length.saturating_add(7) / 8, self.buffer.len());
     }
 
     /// Extends the [`MutableBitmap`] from a [`Bitmap`].
diff --git a/src/compute/comparison/utf8.rs b/src/compute/comparison/utf8.rs
index 4f12f2059c..e36b89167e 100644
--- a/src/compute/comparison/utf8.rs
+++ b/src/compute/comparison/utf8.rs
@@ -37,12 +37,9 @@ where
     let validity = combine_validities(lhs.validity(), rhs.validity());
 
     let values = lhs
-        .iter()
-        .zip(rhs.iter())
-        .map(|(lhs, rhs)| match (lhs, rhs) {
-            (Some(lhs), Some(rhs)) => op(lhs, rhs),
-            _ => false,
-        });
+        .values_iter()
+        .zip(rhs.values_iter())
+        .map(|(lhs, rhs)| op(lhs, rhs));
     let values = Bitmap::from_trusted_len_iter(values);
 
     Ok(BooleanArray::from_data(values, validity))
@@ -57,10 +54,7 @@ where
 {
     let validity = lhs.validity().clone();
 
-    let values = lhs.iter().map(|lhs| match lhs {
-        None => false,
-        Some(lhs) => op(lhs, rhs),
-    });
+    let values = lhs.values_iter().map(|lhs| op(lhs, rhs));
     let values = Bitmap::from_trusted_len_iter(values);
 
     BooleanArray::from_data(values, validity)
diff --git a/src/util/bench_util.rs b/src/util/bench_util.rs
index 1216d0d4c0..14cd3bc11a 100644
--- a/src/util/bench_util.rs
+++ b/src/util/bench_util.rs
@@ -95,15 +95,15 @@ where
 }
 
 /// Creates an random (but fixed-seeded) array of a given size and null density
-pub fn create_string_array<O: Offset>(size: usize, null_density: f32) -> Utf8Array<O> {
-    let rng = &mut seedable_rng();
+pub fn create_string_array<O: Offset>(size: usize, null_density: f32, seed: u64) -> Utf8Array<O> {
+    let mut rng = StdRng::seed_from_u64(seed);
 
     (0..size)
         .map(|_| {
             if rng.gen::<f32>() < null_density {
                 None
             } else {
-                let value = rng
+                let value = (&mut rng)
                     .sample_iter(&Alphanumeric)
                     .take(4)
                     .map(char::from)
diff --git a/src/util/lexical.rs b/src/util/lexical.rs
new file mode 100644
index 0000000000..bbeeed6c15
--- /dev/null
+++ b/src/util/lexical.rs
@@ -0,0 +1,23 @@
+/// Converts numeric type to a `String`
+#[inline]
+pub fn lexical_to_bytes<N: lexical_core::ToLexical>(n: N) -> Vec<u8> {
+    let mut buf = Vec::<u8>::with_capacity(N::FORMATTED_SIZE_DECIMAL);
+    unsafe {
+        // JUSTIFICATION
+        //  Benefit
+        //      Allows using the faster serializer lexical core and convert to string
+        //  Soundness
+        //      Length of buf is set as written length afterwards. lexical_core
+        //      creates a valid string, so doesn't need to be checked.
+        let slice = std::slice::from_raw_parts_mut(buf.as_mut_ptr(), buf.capacity());
+        let len = lexical_core::write(n, slice).len();
+        buf.set_len(len);
+    }
+    buf
+}
+
+/// Converts numeric type to a `String`
+#[inline]
+pub fn lexical_to_string<N: lexical_core::ToLexical>(n: N) -> String {
+    unsafe { String::from_utf8_unchecked(lexical_to_bytes(n)) }
+}
diff --git a/src/util/mod.rs b/src/util/mod.rs
index 53b658b841..71e30dfea7 100644
--- a/src/util/mod.rs
+++ b/src/util/mod.rs
@@ -15,29 +15,10 @@
 // specific language governing permissions and limitations
 // under the License.
 
-/// Converts numeric type to a `String`
-#[inline]
-pub fn lexical_to_bytes<N: lexical_core::ToLexical>(n: N) -> Vec<u8> {
-    let mut buf = Vec::<u8>::with_capacity(N::FORMATTED_SIZE_DECIMAL);
-    unsafe {
-        // JUSTIFICATION
-        //  Benefit
-        //      Allows using the faster serializer lexical core and convert to string
-        //  Soundness
-        //      Length of buf is set as written length afterwards. lexical_core
-        //      creates a valid string, so doesn't need to be checked.
-        let slice = std::slice::from_raw_parts_mut(buf.as_mut_ptr(), buf.capacity());
-        let len = lexical_core::write(n, slice).len();
-        buf.set_len(len);
-    }
-    buf
-}
-
-/// Converts numeric type to a `String`
-#[inline]
-pub fn lexical_to_string<N: lexical_core::ToLexical>(n: N) -> String {
-    unsafe { String::from_utf8_unchecked(lexical_to_bytes(n)) }
-}
+#[cfg(any(feature = "compute", feature = "io_csv"))]
+mod lexical;
+#[cfg(any(feature = "compute", feature = "io_csv"))]
+pub use lexical::*;
 
 #[cfg(feature = "benchmarks")]
 pub mod bench_util;


Test patch:
diff --git a/tests/it/bitmap/mutable.rs b/tests/it/bitmap/mutable.rs
index 234365d67f..f5a973547b 100644
--- a/tests/it/bitmap/mutable.rs
+++ b/tests/it/bitmap/mutable.rs
@@ -312,3 +312,15 @@ fn extend_constant1() {
         }
     }
 }
+
+#[test]
+fn extend_bitmap_one() {
+    for offset in 0..7 {
+        let mut b = MutableBitmap::new();
+        for _ in 0..4 {
+            b.extend_from_slice(&[!0], offset, 1);
+            b.extend_from_slice(&[!0], offset, 1);
+        }
+        assert_eq!(b.as_slice(), &[0b11111111]);
+    }
+}