Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Improving on std:count_if()'s auto-vectorization

nicula.xyz

Post reply on HN
Print view View original

41–50 of 51 posts

Re: Improving on std:count_if()'s auto-vectorization

#41

Post by grandempire »

Sharlin wrote: post #36
grandempire wrote: post #24

Earlier quoted context omitted.

Reduce does not accept a predicate.

It has no need for that. count_if is a fold/reduce operation where the accumulator is simply incremented by `(int)some_condition(x)` for all x. In Rust: 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); Or more generally, fn count_if (it: impl Iterator , pred: impl Fn(&T) -> bool) -> usize { it.fold(0, |acc, t| acc + pred(&t) as usize)…

I know that. But that’s still a different interface. If you have a predicate you now have to wrap that in a different closure that conforms it to a new pattern.

This is the same argument as why have count_if if I can write a for loop.

Re: Improving on std:count_if()'s auto-vectorization

#42

Post by dzaima »

aqrit wrote: post #11
grandempire wrote: post #2

It’s a good example to illustrate how to get more simd from the compiler 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.

A optimized version would use 64-bit accumulators (`psadbw` on SSE2, or some sort of horizontal adds on NEON). The `255` max constraint is pointless. Many programming languages/frameworks expose this operation as `reduce()`.

It's not that trivial:

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.

Re: Improving on std:count_if()'s auto-vectorization

#43

Post by gblargg »

tomn wrote: post #4

another solution is to just cast the result to an uint8_t; with this, clang 19.1.0 gives the same assembly: https://gcc.godbolt.org/z/E5oTW5eKe

I was hoping you could just provide an iterator_traits with a uint8_t difference type, but this is tied to the iterator type rather than specified separately, so you'd need some kind of iterator wrapper to do this.

Re: Improving on std:count_if()'s auto-vectorization

#44

Post by Sharlin »

grandempire wrote: post #41
Sharlin wrote: post #36

Earlier quoted context omitted.

It has no need for that. count_if is a fold/reduce operation where the accumulator is simply incremented by `(int)some_condition(x)` for all x. In Rust: 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); Or more generally, fn count_if (it: impl Iterator , pred: impl Fn(&T) -> bool) -> usize { it.fold(0, |acc, t| acc + pred(&t) as usize)…

I know that. But that’s still a different interface. If you have a predicate you now have to wrap that in a different closure that conforms it to a new pattern. This is the same argument as why have count_if if I can write a for loop.

Sure. But at least I interpreted the GP as just saying that the "count-if" operation can be implemented in terms of `reduce` if the latter is available.

Re: Improving on std:count_if()'s auto-vectorization

#45

Post by dzaima »

fc417fc802 wrote: post #39
nicula wrote: post #23

Earlier quoted context omitted.

> I'm not sure how "it can go the other way around too" -- in that case (assigning to a uint8_t local variable), it seems like that particular optimisation is just not being applied. So the case that you described has 2 layers. The internal std::count_if() layer, which has a 64-bit counter, and the 'return' layer of the count_even_values_v1() function, which has an 8-bit type. In this case, Clang propagates the 8-bit…

Wouldn't that violate the as-if rule? If you assign to a u8 in layer 2 then the compiler must truncate regardless of the widening of the value upon return. It can't just ignore the narrowing assignment.

At the very end there's a "movzx eax, dl", i.e. zero-extend the low 8 bits of the accumulated value.

Re: Improving on std:count_if()'s auto-vectorization

#47

Post by listeria »

zombot wrote: post #46

> it++ Should be ++it. Post-increment is generally more expensive, especially when you don't know the exact type you're applying it to.

I'd normally agree with you, but in this case this function is meant to be used for vectorizable input so it doesn't really matter since it's using a random-access iterator, otherwise you should go with the usual std::count_if().

Then again, it doesn't hurt to be pedantic.

Re: Improving on std:count_if()'s auto-vectorization

#48

Post by tomn »

tomn wrote: post #22
nicula wrote: post #19

Earlier quoted context omitted.

Like @wffurr mentioned, this is indeed discussed in a footnote. I just added another remark to the same footnote: "It's also debatable whether or not Clang's 'optimization' results in better codegen in most cases that you care about. The same optimization pass can backfire pretty easily, because it can go the other way around too. For example, if you assigned the `std::count_if()` result to a local `uint8_t` value, b…

I'm not sure how "it can go the other way around too" -- in that case (assigning to a uint8_t local variable), it seems like that particular optimisation is just not being applied. Interestingly, if the local variable is "volatile uint8_t", the optimisation is applied. Perhaps with an uint8_t local variable and size_t return value, an earlier optimisation removes the cast to uint8_t, because it only has an effect whe…

Just to correct my own comment:

> with an uint8_t local variable and size_t return value, an earlier optimisation removes the cast to uint8_t, because it only has an effect when undefined behaviour has been triggered

In this case, there is no undefined behaviour, because a narrowing cast to an unsigned type is well-defined. So, this could never have been a good explanation.

Re: Improving on std:count_if()'s auto-vectorization

#49

Post by tomn »

gblargg wrote: post #43
tomn wrote: post #4

another solution is to just cast the result to an uint8_t; with this, clang 19.1.0 gives the same assembly: https://gcc.godbolt.org/z/E5oTW5eKe

I was hoping you could just provide an iterator_traits with a uint8_t difference type, but this is tied to the iterator type rather than specified separately, so you'd need some kind of iterator wrapper to do this.

Yeah, I thought about that too, but if you want to process more than 255 values this might not be valid, depending on the implementation of count_if.

Re: Improving on std:count_if()'s auto-vectorization

#50

Post by zombot »

listeria wrote: post #47
zombot wrote: post #46

> it++ Should be ++it. Post-increment is generally more expensive, especially when you don't know the exact type you're applying it to.

I'd normally agree with you, but in this case this function is meant to be used for vectorizable input so it doesn't really matter since it's using a random-access iterator, otherwise you should go with the usual std::count_if(). Then again, it doesn't hurt to be pedantic.

It's not about being pedantic, it's about building the right habits. Building a habit of using x++ instead of ++x is suboptimal.
Post reply on HN