17040114484

Committed 18 Aug 2025 12:07PM UTC coverage: 86.042% (-1.9%) from 87.913%

Build # 17040114484

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 4600ca5c4 into cb1a92920

Pull Request Pull Request #4215: Ji/vectors

Run Details

132 of 1817 new or added lines in 42 files covered. (7.26%)

125 existing lines in 26 files now uncovered.

56932 of 66168 relevant lines covered (86.04%)

611735.65 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/vortex-vector/src/bits/vector.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use std::fmt::{Debug, Formatter};
use std::ops::Not;
use std::sync::{Arc, LazyLock};

use bitvec::array::BitArray;
use bitvec::order::Lsb0;

use crate::PIPELINE_STEP_COUNT;
use crate::bits::{BitView, BitViewMut};

static EMPTY: LazyLock<BitVector> = LazyLock::new(|| BitVector {
    bits: Arc::new(BitArray::ZERO),
    true_count: 0,
});

static FULL: LazyLock<BitVector> = LazyLock::new(|| BitVector {
    bits: Arc::new(BitArray::ZERO.not()),
    true_count: PIPELINE_STEP_COUNT,
});

/// An owned fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
///
/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
/// it up for use within Vortex.
#[derive(Clone)]
pub struct BitVector {
    pub(super) bits: Arc<BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>>,
    pub(super) true_count: usize,
}

impl Debug for BitVector {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("BitVector")
            .field("true_count", &self.true_count)
            //.field("bits", &self.bits.as_raw_slice())
            .finish()
    }
}

impl PartialEq for BitVector {
    fn eq(&self, other: &Self) -> bool {
        Arc::ptr_eq(&self.bits, &other.bits)
            || (self.true_count == other.true_count && self.bits == other.bits)
    }
}

impl Eq for BitVector {}

impl BitVector {
    pub fn empty() -> &'static BitVector {
        &EMPTY
    }

    pub fn full() -> &'static BitVector {
        &FULL
    }

    pub fn true_until(n: usize) -> Self {
        assert!(
            n <= PIPELINE_STEP_COUNT,
            "Cannot create a BitVector with more than N bits"
        );

        let mut bits = Arc::new(BitArray::<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>::ZERO);
        let bits_mut = Arc::make_mut(&mut bits);

        let mut word = 0;
        let mut remaining = n;
        while remaining >= 64 {
            bits_mut.as_raw_mut_slice()[word] = u64::MAX;
            remaining -= 64;
            word += 1;
        }

        if remaining > 0 {
            // For LSB ordering, set the lower bits (0 to remaining-1)
            bits_mut.as_raw_mut_slice()[word] = (1u64 << remaining) - 1;
        }

        BitVector {
            bits,
            true_count: n,
        }
    }

    pub fn true_count(&self) -> usize {
        self.true_count
    }

    pub fn as_raw(&self) -> &[u64; PIPELINE_STEP_COUNT / 64] {
        // It's actually remarkably hard to get a reference to the underlying array!
        let raw = self.bits.as_raw_slice();
        unsafe { &*(raw.as_ptr() as *const [u64; PIPELINE_STEP_COUNT / 64]) }
    }

    pub fn as_raw_mut(&mut self) -> &mut [u64; PIPELINE_STEP_COUNT / 64] {
        // SAFETY: We assume that the bits are mutable and that the view is valid.
        let raw = Arc::make_mut(&mut self.bits).as_raw_mut_slice();
        unsafe { &mut *(raw.as_mut_ptr() as *mut [u64; PIPELINE_STEP_COUNT / 64]) }
    }

    pub fn fill_from<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = u64>,
    {
        let mut true_count = 0;
        for (dst, word) in self.as_raw_mut().iter_mut().zip(iter) {
            true_count += word.count_ones() as usize;
            *dst = word;
        }
        self.true_count = true_count;
    }

    pub fn as_view(&self) -> BitView<'_> {
        unsafe { BitView::new_unchecked(&self.bits, self.true_count) }
    }

    pub fn as_view_mut(&mut self) -> BitViewMut<'_> {
        unsafe { BitViewMut::new_unchecked(Arc::make_mut(&mut self.bits), self.true_count) }
    }
}

impl From<BitView<'_>> for BitVector {
    fn from(value: BitView<'_>) -> Self {
        let true_count = value.true_count();
        let bits = Arc::new(BitArray::<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>::from(
            *value.as_raw(),
        ));
        BitVector { bits, true_count }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fill_from() {
        let mut vec = BitVector::empty().clone();

        // Fill with a pattern
        let pattern = [0b1010101010101010u64, 0b1111000011110000u64, u64::MAX, 0];

        vec.fill_from(pattern.iter().copied());

        let raw = vec.as_raw();
        assert_eq!(raw[0], 0b1010101010101010u64);
        assert_eq!(raw[1], 0b1111000011110000u64);
        assert_eq!(raw[2], u64::MAX);
        assert_eq!(raw[3], 0);

        // Check true_count is updated correctly
        let expected_count = 0b1010101010101010u64.count_ones() as usize
            + 0b1111000011110000u64.count_ones() as usize
            + u64::MAX.count_ones() as usize;
        assert_eq!(vec.true_count(), expected_count);
    }

    #[test]
    fn test_as_view() {
        let vec = BitVector::true_until(100);
        let view = vec.as_view();

        assert_eq!(view.true_count(), 100);

        // Verify the view sees the same bits
        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));
        assert_eq!(ones, (0..100).collect::<Vec<_>>());
    }

    #[test]
    fn test_as_view_mut() {
        let mut vec = BitVector::true_until(64);
        {
            let view_mut = vec.as_view_mut();
            // BitViewMut would allow modifications
            // This test just verifies we can create a mutable view
            assert_eq!(view_mut.true_count(), 64);
        }
        assert_eq!(vec.true_count(), 64);
    }

    #[test]
    fn test_from_bitview() {
        // Create a BitView from raw data
        let mut raw = [0u64; PIPELINE_STEP_COUNT / 64];
        raw[0] = 0b11111111;
        raw[1] = 0b11110000;

        let view = BitView::new(&raw);
        let vec = BitVector::from(view);

        assert_eq!(vec.true_count(), view.true_count());
        assert_eq!(vec.as_raw()[0], 0b11111111);
        assert_eq!(vec.as_raw()[1], 0b11110000);
    }

    #[test]
    fn test_lsb_ordering_verification() {
        // Verify LSB ordering by setting specific bits
        let vec = BitVector::true_until(5);
        let view = vec.as_view();

        // Collect which bits are set
        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        // With LSB ordering, bits 0-4 should be set
        assert_eq!(ones, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_as_raw_mut() {
        let mut vec = BitVector::empty().clone();

        // Modify through as_raw_mut
        let raw_mut = vec.as_raw_mut();
        raw_mut[0] = 0b1111;
        raw_mut[2] = u64::MAX;

        // Note: true_count is NOT automatically updated when using as_raw_mut
        // This is a low-level API, so the user must manage true_count
        vec.true_count = 4 + 64; // Update manually

        assert_eq!(vec.as_raw()[0], 0b1111);
        assert_eq!(vec.as_raw()[2], u64::MAX);
        assert_eq!(vec.true_count(), 68);
    }

    #[test]
    fn test_boundary_conditions() {
        // Test various boundary values
        let boundaries = [
            1,
            31,
            32,
            33,
            63,
            64,
            65,
            127,
            128,
            129,
            PIPELINE_STEP_COUNT - 1,
            PIPELINE_STEP_COUNT,
        ];

        for &n in &boundaries {
            let vec = BitVector::true_until(n);
            assert_eq!(vec.true_count(), n);

            // Verify correct bits are set via view
            let view = vec.as_view();
            let mut ones = Vec::new();
            view.iter_ones(|idx| ones.push(idx));
            assert_eq!(ones.len(), n);
            if n > 0 {
                assert_eq!(ones[0], 0); // First bit should be 0 (LSB)
                assert_eq!(ones[n - 1], n - 1); // Last bit should be n-1
            }
        }
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	// SPDX-License-Identifier: Apache-2.0
5	// SPDX-FileCopyrightText: Copyright the Vortex contributors
6
7	use std::fmt::{Debug, Formatter};
8	use std::ops::Not;
9	use std::sync::{Arc, LazyLock};
10
11	use bitvec::array::BitArray;
12	use bitvec::order::Lsb0;
13
14	use crate::PIPELINE_STEP_COUNT;
15	use crate::bits::{BitView, BitViewMut};
16
17	static EMPTY: LazyLock<BitVector> = LazyLock::new(\|\| BitVector {
NEW 18	bits: Arc::new(BitArray::ZERO),	×
19	true_count: 0,
NEW 20	});	×
21
22	static FULL: LazyLock<BitVector> = LazyLock::new(\|\| BitVector {
NEW 23	bits: Arc::new(BitArray::ZERO.not()),	×
24	true_count: PIPELINE_STEP_COUNT,
NEW 25	});	×
26
27	/// An owned fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
28	///
29	/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
30	/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
31	/// it up for use within Vortex.
32	#[derive(Clone)]
33	pub struct BitVector {
34	pub(super) bits: Arc<BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>>,
35	pub(super) true_count: usize,
36	}
37
38	impl Debug for BitVector {
NEW 39	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {	×
NEW 40	f.debug_struct("BitVector")	×
NEW 41	.field("true_count", &self.true_count)	×
42	//.field("bits", &self.bits.as_raw_slice())
NEW 43	.finish()	×
NEW 44	}	×
45	}
46
47	impl PartialEq for BitVector {
NEW 48	fn eq(&self, other: &Self) -> bool {	×
NEW 49	Arc::ptr_eq(&self.bits, &other.bits)	×
NEW 50	\|\| (self.true_count == other.true_count && self.bits == other.bits)	×
NEW 51	}	×
52	}
53
54	impl Eq for BitVector {}
55
56	impl BitVector {
NEW 57	pub fn empty() -> &'static BitVector {	×
NEW 58	&EMPTY	×
NEW 59	}	×
60
NEW 61	pub fn full() -> &'static BitVector {	×
NEW 62	&FULL	×
NEW 63	}	×
64
NEW 65	pub fn true_until(n: usize) -> Self {	×
NEW 66	assert!(	×
NEW 67	n <= PIPELINE_STEP_COUNT,	×
NEW 68	"Cannot create a BitVector with more than N bits"	×
69	);
70
NEW 71	let mut bits = Arc::new(BitArray::<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>::ZERO);	×
NEW 72	let bits_mut = Arc::make_mut(&mut bits);	×
73
NEW 74	let mut word = 0;	×
NEW 75	let mut remaining = n;	×
NEW 76	while remaining >= 64 {	×
NEW 77	bits_mut.as_raw_mut_slice()[word] = u64::MAX;	×
NEW 78	remaining -= 64;	×
NEW 79	word += 1;	×
NEW 80	}	×
81
NEW 82	if remaining > 0 {	×
NEW 83	// For LSB ordering, set the lower bits (0 to remaining-1)	×
NEW 84	bits_mut.as_raw_mut_slice()[word] = (1u64 << remaining) - 1;	×
NEW 85	}	×
86
NEW 87	BitVector {	×
NEW 88	bits,	×
NEW 89	true_count: n,	×
NEW 90	}	×
NEW 91	}	×
92
NEW 93	pub fn true_count(&self) -> usize {	×
NEW 94	self.true_count	×
NEW 95	}	×
96
NEW 97	pub fn as_raw(&self) -> &[u64; PIPELINE_STEP_COUNT / 64] {	×
98	// It's actually remarkably hard to get a reference to the underlying array!
NEW 99	let raw = self.bits.as_raw_slice();	×
NEW 100	unsafe { &(raw.as_ptr() as const [u64; PIPELINE_STEP_COUNT / 64]) }	×
NEW 101	}	×
102
NEW 103	pub fn as_raw_mut(&mut self) -> &mut [u64; PIPELINE_STEP_COUNT / 64] {	×
104	// SAFETY: We assume that the bits are mutable and that the view is valid.
NEW 105	let raw = Arc::make_mut(&mut self.bits).as_raw_mut_slice();	×
NEW 106	unsafe { &mut (raw.as_mut_ptr() as mut [u64; PIPELINE_STEP_COUNT / 64]) }	×
NEW 107	}	×
108
NEW 109	pub fn fill_from<I>(&mut self, iter: I)	×
NEW 110	where	×
NEW 111	I: IntoIterator<Item = u64>,	×
112	{
NEW 113	let mut true_count = 0;	×
NEW 114	for (dst, word) in self.as_raw_mut().iter_mut().zip(iter) {	×
NEW 115	true_count += word.count_ones() as usize;	×
NEW 116	*dst = word;	×
NEW 117	}	×
NEW 118	self.true_count = true_count;	×
NEW 119	}	×
120
NEW 121	pub fn as_view(&self) -> BitView<'_> {	×
NEW 122	unsafe { BitView::new_unchecked(&self.bits, self.true_count) }	×
NEW 123	}	×
124
NEW 125	pub fn as_view_mut(&mut self) -> BitViewMut<'_> {	×
NEW 126	unsafe { BitViewMut::new_unchecked(Arc::make_mut(&mut self.bits), self.true_count) }	×
NEW 127	}	×
128	}
129
130	impl From<BitView<'_>> for BitVector {
NEW 131	fn from(value: BitView<'_>) -> Self {	×
NEW 132	let true_count = value.true_count();	×
NEW 133	let bits = Arc::new(BitArray::<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>::from(	×
NEW 134	*value.as_raw(),	×
135	));
NEW 136	BitVector { bits, true_count }	×
NEW 137	}	×
138	}
139
140	#[cfg(test)]
141	mod tests {
142	use super::*;
143
144	#[test]
145	fn test_fill_from() {
146	let mut vec = BitVector::empty().clone();
147
148	// Fill with a pattern
149	let pattern = [0b1010101010101010u64, 0b1111000011110000u64, u64::MAX, 0];
150
151	vec.fill_from(pattern.iter().copied());
152
153	let raw = vec.as_raw();
154	assert_eq!(raw[0], 0b1010101010101010u64);
155	assert_eq!(raw[1], 0b1111000011110000u64);
156	assert_eq!(raw[2], u64::MAX);
157	assert_eq!(raw[3], 0);
158
159	// Check true_count is updated correctly
160	let expected_count = 0b1010101010101010u64.count_ones() as usize
161	+ 0b1111000011110000u64.count_ones() as usize
162	+ u64::MAX.count_ones() as usize;
163	assert_eq!(vec.true_count(), expected_count);
164	}
165
166	#[test]
167	fn test_as_view() {
168	let vec = BitVector::true_until(100);
169	let view = vec.as_view();
170
171	assert_eq!(view.true_count(), 100);
172
173	// Verify the view sees the same bits
174	let mut ones = Vec::new();
175	view.iter_ones(\|idx\| ones.push(idx));
176	assert_eq!(ones, (0..100).collect::<Vec<_>>());
177	}
178
179	#[test]
180	fn test_as_view_mut() {
181	let mut vec = BitVector::true_until(64);
182	{
183	let view_mut = vec.as_view_mut();
184	// BitViewMut would allow modifications
185	// This test just verifies we can create a mutable view
186	assert_eq!(view_mut.true_count(), 64);
187	}
188	assert_eq!(vec.true_count(), 64);
189	}
190
191	#[test]
192	fn test_from_bitview() {
193	// Create a BitView from raw data
194	let mut raw = [0u64; PIPELINE_STEP_COUNT / 64];
195	raw[0] = 0b11111111;
196	raw[1] = 0b11110000;
197
198	let view = BitView::new(&raw);
199	let vec = BitVector::from(view);
200
201	assert_eq!(vec.true_count(), view.true_count());
202	assert_eq!(vec.as_raw()[0], 0b11111111);
203	assert_eq!(vec.as_raw()[1], 0b11110000);
204	}
205
206	#[test]
207	fn test_lsb_ordering_verification() {
208	// Verify LSB ordering by setting specific bits
209	let vec = BitVector::true_until(5);
210	let view = vec.as_view();
211
212	// Collect which bits are set
213	let mut ones = Vec::new();
214	view.iter_ones(\|idx\| ones.push(idx));
215
216	// With LSB ordering, bits 0-4 should be set
217	assert_eq!(ones, vec![0, 1, 2, 3, 4]);
218	}
219
220	#[test]
221	fn test_as_raw_mut() {
222	let mut vec = BitVector::empty().clone();
223
224	// Modify through as_raw_mut
225	let raw_mut = vec.as_raw_mut();
226	raw_mut[0] = 0b1111;
227	raw_mut[2] = u64::MAX;
228
229	// Note: true_count is NOT automatically updated when using as_raw_mut
230	// This is a low-level API, so the user must manage true_count
231	vec.true_count = 4 + 64; // Update manually
232
233	assert_eq!(vec.as_raw()[0], 0b1111);
234	assert_eq!(vec.as_raw()[2], u64::MAX);
235	assert_eq!(vec.true_count(), 68);
236	}
237
238	#[test]
239	fn test_boundary_conditions() {
240	// Test various boundary values
241	let boundaries = [
242	1,
243	31,
244	32,
245	33,
246	63,
247	64,
248	65,
249	127,
250	128,
251	129,
252	PIPELINE_STEP_COUNT - 1,
253	PIPELINE_STEP_COUNT,
254	];
255
256	for &n in &boundaries {
257	let vec = BitVector::true_until(n);
258	assert_eq!(vec.true_count(), n);
259
260	// Verify correct bits are set via view
261	let view = vec.as_view();
262	let mut ones = Vec::new();
263	view.iter_ones(\|idx\| ones.push(idx));
264	assert_eq!(ones.len(), n);
265	if n > 0 {
266	assert_eq!(ones[0], 0); // First bit should be 0 (LSB)
267	assert_eq!(ones[n - 1], n - 1); // Last bit should be n-1
268	}
269	}
270	}
271	}

vortex-data / vortex / 17040114484

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous