Skip to main content

vortex_array/arrays/primitive/compute/
zip.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::mem::MaybeUninit;
5
6use vortex_buffer::Alignment;
7use vortex_buffer::BufferMut;
8use vortex_error::VortexExpect;
9use vortex_error::VortexResult;
10use vortex_error::vortex_bail;
11use vortex_mask::Mask;
12
13use crate::ArrayRef;
14use crate::ExecutionCtx;
15use crate::IntoArray;
16use crate::array::ArrayView;
17use crate::arrays::Primitive;
18use crate::arrays::PrimitiveArray;
19use crate::builtins::ArrayBuiltins;
20use crate::match_each_ptype_width;
21use crate::scalar_fn::fns::zip::ZipKernel;
22use crate::scalar_fn::fns::zip::zip_validity;
23
24/// A dedicated primitive zip kernel that selects values branchlessly per row.
25///
26/// The generic zip path copies runs of `if_true`/`if_false` between mask boundaries, which is fast
27/// for clustered masks but degrades to per-element work on fragmented masks. This kernel instead
28/// walks the mask as 64-bit chunks and blends both sides per row without a data-dependent branch,
29/// so the inner loop stays branch-free and auto-vectorizable regardless of mask shape.
30impl ZipKernel for Primitive {
31    fn zip(
32        if_true: ArrayView<'_, Primitive>,
33        if_false: &ArrayRef,
34        mask: &ArrayRef,
35        ctx: &mut ExecutionCtx,
36    ) -> VortexResult<Option<ArrayRef>> {
37        let Some(if_false) = if_false.as_opt::<Primitive>() else {
38            return Ok(None);
39        };
40
41        if if_true.ptype() != if_false.ptype() {
42            vortex_bail!(
43                "zip requires if_true and if_false to share a primitive type, got {} and {}",
44                if_true.ptype(),
45                if_false.ptype()
46            );
47        }
48
49        // Null mask entries select `if_false`, matching `Zip`'s SQL ELSE semantics.
50        let mask = mask.clone().fill_null(false)?.execute::<Mask>(ctx)?;
51        match &mask {
52            // Defer trivial masks to the generic zip, which just casts the surviving side.
53            Mask::AllTrue(_) | Mask::AllFalse(_) => return Ok(None),
54            Mask::Values(_) => {}
55        }
56
57        let validity = zip_validity(if_true.validity()?, if_false.validity()?, &mask)?;
58        let true_values = if_true
59            .buffer_handle()
60            .as_host_opt()
61            .vortex_expect("zip requires host values");
62        let false_values = if_false
63            .buffer_handle()
64            .as_host_opt()
65            .vortex_expect("zip requires host values");
66
67        // TODO(connor): inspect the mask's true_count (and validity) to special-case heavily-skewed
68        // masks. When one side dominates (true_count near 0 or near len), it is cheaper to bulk
69        // copy (or mutate in place, if the dominant side is uniquely owned) that side's values
70        // and validity, then conditionally pull in only the minority rows from the other side,
71        // rather than blending every row.
72        let values = match_each_ptype_width!(
73            if_true.ptype(),
74            |W| {
75                select_values(
76                    true_values.as_slice().as_chunks::<W>().0,
77                    false_values.as_slice().as_chunks::<W>().0,
78                    &mask,
79                )
80                .freeze()
81                .into_byte_buffer()
82                .aligned(Alignment::new(W))
83            },
84            _ => { unreachable!("primitive widths are specialized") },
85        );
86        let array =
87            PrimitiveArray::from_byte_buffer(values, if_true.ptype(), validity).into_array();
88
89        Ok(Some(array))
90    }
91}
92
93/// Branchlessly blend `if_true` and `if_false` per row into a fresh value buffer.
94fn select_values<T: Copy>(true_values: &[T], false_values: &[T], mask: &Mask) -> BufferMut<T> {
95    let len = true_values.len();
96    let mut out = BufferMut::<T>::with_capacity(len);
97    {
98        let out_slice = out.spare_capacity_mut();
99
100        let mask_bits = mask
101            .values()
102            .vortex_expect("mask is Mask::Values")
103            .bit_buffer();
104        // TODO(perf): `unaligned_chunks` is a faster single-buffer iterator than `chunks`; switch to
105        // it here, handling its lead/trailing padding.
106        let chunks = mask_bits.chunks();
107
108        let mut base = 0;
109        for word in chunks.iter() {
110            let end = base + 64;
111            select_block(
112                word,
113                &true_values[base..end],
114                &false_values[base..end],
115                &mut out_slice[base..end],
116            );
117            base = end;
118        }
119
120        let remainder = chunks.remainder_len();
121        if remainder > 0 {
122            let end = base + remainder;
123            select_block(
124                chunks.remainder_bits(),
125                &true_values[base..end],
126                &false_values[base..end],
127                &mut out_slice[base..end],
128            );
129        }
130    }
131
132    // SAFETY: `select_block` initialized every slot covered by the chunks plus remainder, i.e. `len`.
133    unsafe { out.set_len(len) };
134    out
135}
136
137/// Blend one 64-bit mask chunk's worth of rows: bit `j` (LSB-first) keeps `true_values[j]`, an unset
138/// bit keeps `false_values[j]`. Slices are trimmed to the output length up front so the compiler can
139/// elide bounds checks and lower the body to a vector blend / conditional move.
140#[inline]
141fn select_block<T: Copy>(
142    word: u64,
143    true_values: &[T],
144    false_values: &[T],
145    out: &mut [MaybeUninit<T>],
146) {
147    let n = out.len();
148    let true_values = &true_values[..n];
149    let false_values = &false_values[..n];
150    for j in 0..n {
151        let pick = (word >> j) & 1 == 1;
152        out[j].write(if pick {
153            true_values[j]
154        } else {
155            false_values[j]
156        });
157    }
158}
159
160#[cfg(test)]
161mod tests {
162    #![allow(
163        clippy::cast_possible_truncation,
164        reason = "test fixtures use small indices that fit the target widths"
165    )]
166
167    use std::sync::LazyLock;
168
169    use vortex_error::VortexResult;
170    use vortex_mask::Mask;
171    use vortex_session::VortexSession;
172
173    use crate::ArrayRef;
174    use crate::IntoArray;
175    use crate::VortexSessionExecute;
176    use crate::arrays::Primitive;
177    use crate::arrays::PrimitiveArray;
178    use crate::assert_arrays_eq;
179    use crate::builtins::ArrayBuiltins;
180
181    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
182
183    /// The branchless kernel must agree with the scalar reference across the chunk boundary (index
184    /// 63/64) and the trailing remainder, for non-nullable inputs.
185    #[test]
186    fn zip_nonnull_spans_mask_chunks() -> VortexResult<()> {
187        let len = 150usize;
188        let if_true = PrimitiveArray::from_iter(0..len as i64).into_array();
189        let if_false = PrimitiveArray::from_iter((0..len as i64).map(|i| 1_000 + i)).into_array();
190
191        let bits: Vec<bool> = (0..len).map(|i| i.is_multiple_of(3) || i == 64).collect();
192        let mask = Mask::from_iter(bits.iter().copied());
193
194        let mut ctx = SESSION.create_execution_ctx();
195        let result = mask
196            .into_array()
197            .zip(if_true, if_false)?
198            .execute::<ArrayRef>(&mut ctx)?;
199        assert!(result.is::<Primitive>());
200
201        let expected = PrimitiveArray::from_iter(
202            (0..len).map(|i| if bits[i] { i as i64 } else { 1_000 + i as i64 }),
203        )
204        .into_array();
205        assert_arrays_eq!(result, expected, &mut ctx);
206        Ok(())
207    }
208
209    /// With `Validity::Array` on both sides the kernel must select values and validity from the
210    /// chosen side across the chunk boundary.
211    #[test]
212    fn zip_nullable_selects_values_and_validity() -> VortexResult<()> {
213        let len = 130usize;
214        let if_true =
215            PrimitiveArray::from_option_iter((0..len as i64).map(|i| (i % 4 != 0).then_some(i)))
216                .into_array();
217        let if_false = PrimitiveArray::from_option_iter(
218            (0..len as i64).map(|i| (i % 5 != 0).then_some(1_000 + i)),
219        )
220        .into_array();
221
222        let bits: Vec<bool> = (0..len).map(|i| i.is_multiple_of(2)).collect();
223        let mask = Mask::from_iter(bits.iter().copied());
224
225        let mut ctx = SESSION.create_execution_ctx();
226        let result = mask
227            .into_array()
228            .zip(if_true, if_false)?
229            .execute::<ArrayRef>(&mut ctx)?;
230        assert!(result.is::<Primitive>());
231
232        let expected = PrimitiveArray::from_option_iter((0..len).map(|i| {
233            let v = i as i64;
234            if bits[i] {
235                (!i.is_multiple_of(4)).then_some(v)
236            } else {
237                (!i.is_multiple_of(5)).then_some(1_000 + v)
238            }
239        }))
240        .into_array();
241        assert_arrays_eq!(result, expected, &mut ctx);
242        Ok(())
243    }
244}