But the overly specific constraint means this is not a general count_if algorithm.
For this to be useful I have to: - know there are only 255 true values - but have a large dataset so it’s worth optimizing - not want to stop early when some threshold is met
This is so specialized it’s not even worth having a generic predicate argument for.
Many programming languages/frameworks expose this operation as `reduce()`.
let arr = [ 1, 3, 4, 6,7, 0, 9, -4];
let n_evens = arr.iter().fold(0, |acc, i| acc + (i & 1 == 0) as usize);
assert_eq!(n_evens, 4);
fn count_if<T>(it: impl Iterator<Item=T>, pred: impl Fn(&T) -> bool) -> usize {
it.fold(0, |acc, t| acc + pred(&t) as usize)
}This is the same argument as why have count_if if I can write a for loop.
The wrapping version uses vpandn + vpaddb (i.e. `acc += 1 &~ elt`). On Intel since Haswell (2013) on ymm inputs that can manage 1.5 iterations per cycle, if unroll 2x to reduce the dependency chain.
Whereas vpsadbw would limit it to 1 iteration per cycle on Intel.
On AMD Zen≤2, vpsadbw is still worse, but Zen≥3 manages to have the two approaches be equal.
On AVX-512 the two approaches are equivalent everywhere as far as uops.info data goes.