Question: count_set_bits() and count_unset_bits() PR

[eadf]

I've been playing around trying to create a faster .iter_unset_bits(..).count() method (like we discussed before)
This is what i came up with, i have not actually benchmarked it but since it is processing entire words instead of bit-by-bit, it should be substantially faster.

Is this something you want a PR for?

    /// Counts the number of set bits.
    /// Generates the same result as Vob::iterate_set_bits().count() only much faster.
    /// # Examples
    /// 
    /// use vob::Vob;
    /// let mut v = Vob::new();
    /// v.push(false);
    /// v.push(true);
    /// assert_eq!(v.iter_set_bits(..).count(), v.count_set_bits(..));
    /// 
    pub fn count_set_bits<R>(&self, range: R) -> usize
    where
        R: RangeBounds<usize>,
    {
        self._count_set_bits(self.process_range(range))
    }

    /// Counts the number of unset bits.
    /// Generates the same result as Vob::iterate_unset_bits().count() only much faster.
    /// # Examples
    ///  
    /// use vob::Vob;
    /// let mut v = Vob::new();
    /// v.push(false);
    /// v.push(true);
    /// assert_eq!(v.iter_unset_bits(..).count(), v.count_unset_bits(..));
    /// 
    pub fn count_unset_bits<R>(&self, range: R) -> usize
    where
        R: RangeBounds<usize>,
    {
        let range = self.process_range(range);
        (range.end - range.start) - self._count_set_bits(range)
    }

    /// Counts the number of set bits.
    /// This method assumes the range is processed with process_range()
    fn _count_set_bits(&self, range: Range<usize>) -> usize {
        // Early return for empty ranges
        if range.start >= range.end {
            return 0;
        }
        let start_word = block_offset::<T>(range.start);
        if start_word >= self.len {
            return 0;
        }
        // this -1 is safe since we already tested for range.start & range.end equality
        let end_word = blocks_required::<T>(range.end) - 1;

        if start_word == end_word {
            // Range entirely within one word
            let word = self.vec[start_word];
            let start_bit = range.start % bits_per_block::<T>();
            let end_bit = range.end % bits_per_block::<T>();

            // Remove bits before start_bit and bits after end_bit
            return count_ones_usize(if end_bit == 0 {
                // end_bit = 0 means we want everything from start_bit to end of word
                // After the right shift above, we already have what we want
                word >> start_bit
            } else {
                // We want bits from start_bit to end_bit
                // After right shift, we need to remove the high bits
                (word >> start_bit) << (start_bit + bits_per_block::<T>() - end_bit)
            });
        }

        // First word: shift out bits before start_bit
        let start_bit = range.start % bits_per_block::<T>();
        let mut count = count_ones_usize(self.vec[start_word] >> start_bit);

        // Middle words (unchanged)
        for word_idx in (start_word + 1)..end_word {
            count += count_ones_usize(self.vec[word_idx]);
        }

        // Last word: shift out bits after end_bit
        let end_bit = range.end % bits_per_block::<T>();
        count
            + if end_bit == 0 {
                count_ones_usize(self.vec[end_word])
            } else {
                count_ones_usize(self.vec[end_word] << (bits_per_block::<T>() - end_bit))
            }
    }

...
/// Convenience function that calls T::count_ones() and converts the result to usize
/// (The conversion is always safe even if T is u128 and usize is u16)
#[inline(always)]
fn count_ones_usize<T: PrimInt>(value: T) -> usize {
    use std::convert::TryFrom;
    usize::try_from(value.count_ones()).unwrap()
}

Issues:

• I created a count_ones_usize() function only used in _count_set_bits(). Maybe a local function?
• count_ones_usize() could safely use unwrap_unchecked()
• n % bits_per_block::<T>() is frequently used, maybe it should be a function like block_offset() maybe bit_offset()?

[ltratt]

Without benchmarks, it's difficult to say: I've more than once did a seemingly clever optimisation that slowed things down! But, assuming it is faster, I think we'd need to find a good API for it. I think we can just override the count method and then, providing we're very careful (and test all the dangerous edge cases), the "natural" Rust thing will also be the fast thing!

[eadf]

I added some benchmarks that just copies the existing iter_set_bits* , but i need to check if the lack of blackbox is tricking me:

`
iter_set_bits time: [178.65 µs 178.77 µs 178.89 µs]

count_set_bits time: [196.90 ns 199.38 ns 202.91 ns]

iter_set_bits_u8 time: [240.79 µs 241.07 µs 241.42 µs]

count_set_bits_u8 time: [805.60 ns 806.23 ns 806.85 ns]

iter_all_set_bits time: [63.144 µs 63.979 µs 65.060 µs]

count_all_set_bits time: [194.74 ns 195.22 ns 195.76 ns]

iter_all_unset_bits time: [852.33 ns 856.12 ns 861.49 ns]

count_all_unset_bits time: [195.62 ns 196.04 ns 196.42 ns]
`

178.77 µs vs 199.38 ns for comparable work is sus.
But i can see that the count_* variant does not vary much over bit set/unset, only with word sizes (u8).

Overriding the .count() method can't improve the speed much. It's all about O(number of bits) vs O(number of words), still a constant but the constant is as large as 64 (or even 128).
Or do you mean a count() override should shortcut the iterator, and go back to the vob and call _count_set_bits() or similar?

Edit: nope, same dramatic results with or without std::hint::black_box

[eadf]

I just read up on the count() method, and how it frequently 'sidesteps' the iterator in std if it can count 'smarter'.
e.g Vec.iter().count() simply returns.len()

That sounds like a great idea to do here as well.

[ltratt]

Or do you mean a count() override should shortcut the iterator, and go back to the vob and call _count_set_bits() or similar?

Yes. Well, there'd be no point having an exposed count_set_bits method: it can just be contained in the overridden count.

[eadf]

_count_set_bits() is not public, and it's used for both set and unset mode. But i'll see what i can come up with

Edit: I've removed the count_set_bits() and count_unset_bits() methods and now only rely on iter*.count().
We need to use Vob::iter_set_bits(..).filter(|_|true).count() to trigger the old behavior, and i'm using that in the tests.
II tried with .skip(0) but rust std is too clever to fall for that. Maybe .take(usize::MAX) could work.

[ltratt]

Thanks!

[eadf]

move to #87