12 ms·

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

134 points by nicula 2y ago

grandempire 2y ago
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.
- aqrit 2y ago
  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()`.
  - grandempire 2y ago
    Reduce does not accept a predicate.
    - Sharlin 2y ago
      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<T>(it: impl Iterator<Item=T>, pred: impl Fn(&T) -> bool) -> usize { it.fold(0, |acc, t| acc + pred(&t) as usize) }
      - grandempire 2y ago
        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.
        Sharlin 2y ago
        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.
  - dzaima 2y ago
    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.
TheCoreh 2y ago
Meta-question: Given how common :: is in programming languages, and how rare of a typo it is, is it really worth it for HN's title filtering logic to include a rule for automatically replacing it with a single :?
- dcsommer 2y ago
  If the goal is brevity, the rules could first replace 'std::' with nothing.
  - tialaramex 2y ago
    This only makes sense for C++ where they weirdly namespaced their standard library after popularising the language. But as your parent points out, other languages use this naming style.
    - dcsommer 2y ago
      For what languages would removing 'std::' realistically cause ambiguity for practicioners?
      - tialaramex 2y ago
        It's not exactly ambiguity, but I know I find it frustrating to read examples for language X and see oh, everybody (often even in presentations, blog pages, documentation) says foo.bar + baz.quux but you can't actually write that, what they meant was std::thing::foo.bar + (std::baz.::std::other::quux) And if you're stupid enough to just write foo.bar + baz.quux well that's nonsense and the compiler diagnostics won't have any suggestions for how to fix it, what a buffoon you are. I really don't enjoy this, like the trend for "narrative" cookery recipe style documentation where we're shown how to Quux a Baz [often with fragments that don't compile] in the library but given no indication whether we can Quux a Doodad or even whether that's a feature of the library's Baz or Quux or really what's going on, but hey, the author got to tell us about their trip to Tuscany so that's nice. Javadoc isn't perfect, but it's so much better than this.
tomn 2y ago
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 https://gcc.godbolt.org/z/E5oTW5eKe
- wffurr 2y ago
  Which is discussed in the post and doesn’t work in GCC.
  - tomn 2y ago
    Oh right, I didn't see it in a couple of passes (and searching for cast); for anyone else looking it's in the 3rd footnote. Thanks.
- nicula 2y ago
  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, but then returned that value as a `uint64_t` from the function, then Clang will assume that you wanted a `uint64_t` accumulator all along, and thus generates the poor vectorization, not the efficient one."
  - tomn 2y ago
    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 when undefined behaviour has been triggered? It would certainly be interesting to investigate further. In general I agree that being more explicit is better if you really care about performance. It would be great if languages provided more ways to specify this kind of thing. I tried using __builtin_expect to trigger this optimisation too, but no dice. Anyway, thanks for the interesting article.
jasonthorsness 2y ago
Soon I am wondering if rather than rely on finicky auto-vectorization we’ll just have LLMs help “hand-optimize” more routines. Just like how memcmp and memcpy are optimized by hand today maybe like 20% of the program could just be LLM-assisted assembly. @ffmpeg on X thinks maybe they are starting to get it [1] and I had some success having an LLM generate working WebAssembly [2] https://x.com/ffmpeg/status/1898408922769223994?s=46 https://x.com/ffmpeg/status/1898408922769223994?s=46 https://www.jasonthorsness.com/24 https://www.jasonthorsness.com/24
- jsheard 2y ago
  Instead of replacing one finicky and temperamental approach (auto-vectorizers) with another (LLM codegen) I'd much rather see more exploration of explicit SIMD abstractions like Intel's ISPC language. Shader languages for GPUs had this figured out forever ago, there is a sensible middle-ground to be had between brittle compiler magic and no compiler at all.
  - jasonthorsness 2y ago
    It does seem odd that languages or standard libraries haven’t embraced some of the most common SIMD instructions more than they have, after so many decades of the instructions being available in most processors. I’ve used dotnet’s Vector libraries a bit that tries to auto-adapt to register length and falls back to software on chips that don’t support hardware instructions; it can still be pretty unwieldy and sometimes you have to use the fixed-size ones anyway. Will take a look at ISPC.
    - jsheard 2y ago
      ISPC is a step above the .NET Vector stuff, it's more or less a GPU shader language except it compiles down to SSE/AVX/NEON code instead. In fact I think it was originally envisioned to be a shader language for Intel's ill-fated Larrabee GPU, since that was just meant to be an extremely wide x86 chip.
      - 2y ago
fsafdsaewr 2y ago
[flagged]
meisel 2y ago
Seems like you can do this sort of speed up even without the 256 constraint. Just run this sped up version, but after each set of 256 iterations, dump all the 8-bit counters to the 64-bit final result.
- nicula 2y ago
  Some people already mentioned this in the r/cpp discussion. Small correction: 256 is not the correct number of iterations, since if all elements in that slice are even, then your 8-bit counter will wrap-around to zero, which can lead to a wrong answer. What you want is 255 iterations. I've looked at the generated assembly for such a solution and it doesn't look great. I'm expecting a significant speed penalty, but I haven't had the time to test it today. Will probably do so tomorrow.
  - ack_complete 2y ago
    255 is not ideal either because it results in a partial vector at the end of either 15 or 31 elements. 256-V where V is the vector size is better, so 240 for SSE2/NEON or 224 for AVX2. This is still lower than optimal because the compiler will reduce to a uint8. Both SSE2 and NEON support reducing to a wider value by _mm_sad_epu8 and vpadal_u8, respectively. This allows for 255 iterations in the inner loop instead of 15 or 7.
    - nicula 2y ago
      Great observations, thanks! I wrote the code that you suggested (LMK if I understood your points): https://godbolt.org/z/jW4o3cnh3 https://godbolt.org/z/jW4o3cnh3 And here's the benchmark output, on my machine: https://0x0.st/8SsG.txt https://0x0.st/8SsG.txt (v1 is std::count_if(), v2 is the optimization from my blog post, and v3 is what you suggested). v2 is faster, but v3 is still quite fast.
      - ack_complete 2y ago
        Yeah, the difference you're seeing is likely due to the inner loop doing so few iterations, in addition to not being unrolled. A hand-rolled version doing 63 iterations of an x4 unrolled loop should be able to saturate the execution core (it'll be bottlenecked by load throughput). But it'll be tough to get the compiler to generate that without intrinsics.
eurekabot123 2y ago
[dead]
newgre 2y ago
Why did the compiler even chose to fetch DWORDs only in the first place? It's unclear to me why the accumulator (apparently) determines the vectorization width?
- deleted 2y ago
  [deleted]
- TinkersW 2y ago
  The accumulator is a vector type, with 64 bit sum you can only fit 4 into a 256 bit register. After the loop it will do a horizontal add across the vector register to produce the final scalar result.
  - deleted 2y ago
    [deleted]
tdhz77 2y ago
Wow what a title.
zombot 2y ago
> it++ Should be ++it. Post-increment is generally more expensive, especially when you don't know the exact type you're applying it to.
- listeria 2y ago
  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.
  - zombot 2y ago
    It's not about being pedantic, it's about building the right habits. Building a habit of using x++ instead of ++x is suboptimal.

134 points by nicula 2y ago

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.

aqrit 2y ago
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()`.
- grandempire 2y ago
  Reduce does not accept a predicate.
  - Sharlin 2y ago
    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<T>(it: impl Iterator<Item=T>, pred: impl Fn(&T) -> bool) -> usize { it.fold(0, |acc, t| acc + pred(&t) as usize) }
    - grandempire 2y ago
      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.
      - Sharlin 2y ago
        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.
- dzaima 2y ago
  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.

TheCoreh 2y ago

Meta-question: Given how common :: is in programming languages, and how rare of a typo it is, is it really worth it for HN's title filtering logic to include a rule for automatically replacing it with a single :?

dcsommer 2y ago
If the goal is brevity, the rules could first replace 'std::' with nothing.
- tialaramex 2y ago
  This only makes sense for C++ where they weirdly namespaced their standard library after popularising the language. But as your parent points out, other languages use this naming style.
  - dcsommer 2y ago
    For what languages would removing 'std::' realistically cause ambiguity for practicioners?
    - tialaramex 2y ago
      It's not exactly ambiguity, but I know I find it frustrating to read examples for language X and see oh, everybody (often even in presentations, blog pages, documentation) says foo.bar + baz.quux but you can't actually write that, what they meant was std::thing::foo.bar + (std::baz.::std::other::quux) And if you're stupid enough to just write foo.bar + baz.quux well that's nonsense and the compiler diagnostics won't have any suggestions for how to fix it, what a buffoon you are. I really don't enjoy this, like the trend for "narrative" cookery recipe style documentation where we're shown how to Quux a Baz [often with fragments that don't compile] in the library but given no indication whether we can Quux a Doodad or even whether that's a feature of the library's Baz or Quux or really what's going on, but hey, the author got to tell us about their trip to Tuscany so that's nice. Javadoc isn't perfect, but it's so much better than this.

tomn 2y ago

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 https://gcc.godbolt.org/z/E5oTW5eKe

wffurr 2y ago
Which is discussed in the post and doesn’t work in GCC.
- tomn 2y ago
  Oh right, I didn't see it in a couple of passes (and searching for cast); for anyone else looking it's in the 3rd footnote. Thanks.
nicula 2y ago
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, but then returned that value as a `uint64_t` from the function, then Clang will assume that you wanted a `uint64_t` accumulator all along, and thus generates the poor vectorization, not the efficient one."
- tomn 2y ago
  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 when undefined behaviour has been triggered? It would certainly be interesting to investigate further. In general I agree that being more explicit is better if you really care about performance. It would be great if languages provided more ways to specify this kind of thing. I tried using __builtin_expect to trigger this optimisation too, but no dice. Anyway, thanks for the interesting article.

jasonthorsness 2y ago

Soon I am wondering if rather than rely on finicky auto-vectorization we’ll just have LLMs help “hand-optimize” more routines. Just like how memcmp and memcpy are optimized by hand today maybe like 20% of the program could just be LLM-assisted assembly. @ffmpeg on X thinks maybe they are starting to get it [1] and I had some success having an LLM generate working WebAssembly [2] https://x.com/ffmpeg/status/1898408922769223994?s=46 https://x.com/ffmpeg/status/1898408922769223994?s=46 https://www.jasonthorsness.com/24 https://www.jasonthorsness.com/24

jsheard 2y ago
Instead of replacing one finicky and temperamental approach (auto-vectorizers) with another (LLM codegen) I'd much rather see more exploration of explicit SIMD abstractions like Intel's ISPC language. Shader languages for GPUs had this figured out forever ago, there is a sensible middle-ground to be had between brittle compiler magic and no compiler at all.
- jasonthorsness 2y ago
  It does seem odd that languages or standard libraries haven’t embraced some of the most common SIMD instructions more than they have, after so many decades of the instructions being available in most processors. I’ve used dotnet’s Vector libraries a bit that tries to auto-adapt to register length and falls back to software on chips that don’t support hardware instructions; it can still be pretty unwieldy and sometimes you have to use the fixed-size ones anyway. Will take a look at ISPC.
  - jsheard 2y ago
    ISPC is a step above the .NET Vector stuff, it's more or less a GPU shader language except it compiles down to SSE/AVX/NEON code instead. In fact I think it was originally envisioned to be a shader language for Intel's ill-fated Larrabee GPU, since that was just meant to be an extremely wide x86 chip.
    - 2y ago

fsafdsaewr 2y ago

[flagged]

meisel 2y ago

Seems like you can do this sort of speed up even without the 256 constraint. Just run this sped up version, but after each set of 256 iterations, dump all the 8-bit counters to the 64-bit final result.

nicula 2y ago
Some people already mentioned this in the r/cpp discussion. Small correction: 256 is not the correct number of iterations, since if all elements in that slice are even, then your 8-bit counter will wrap-around to zero, which can lead to a wrong answer. What you want is 255 iterations. I've looked at the generated assembly for such a solution and it doesn't look great. I'm expecting a significant speed penalty, but I haven't had the time to test it today. Will probably do so tomorrow.
- ack_complete 2y ago
  255 is not ideal either because it results in a partial vector at the end of either 15 or 31 elements. 256-V where V is the vector size is better, so 240 for SSE2/NEON or 224 for AVX2. This is still lower than optimal because the compiler will reduce to a uint8. Both SSE2 and NEON support reducing to a wider value by _mm_sad_epu8 and vpadal_u8, respectively. This allows for 255 iterations in the inner loop instead of 15 or 7.
  - nicula 2y ago
    Great observations, thanks! I wrote the code that you suggested (LMK if I understood your points): https://godbolt.org/z/jW4o3cnh3 https://godbolt.org/z/jW4o3cnh3 And here's the benchmark output, on my machine: https://0x0.st/8SsG.txt https://0x0.st/8SsG.txt (v1 is std::count_if(), v2 is the optimization from my blog post, and v3 is what you suggested). v2 is faster, but v3 is still quite fast.
    - ack_complete 2y ago
      Yeah, the difference you're seeing is likely due to the inner loop doing so few iterations, in addition to not being unrolled. A hand-rolled version doing 63 iterations of an x4 unrolled loop should be able to saturate the execution core (it'll be bottlenecked by load throughput). But it'll be tough to get the compiler to generate that without intrinsics.

eurekabot123 2y ago

[dead]

newgre 2y ago

Why did the compiler even chose to fetch DWORDs only in the first place? It's unclear to me why the accumulator (apparently) determines the vectorization width?

deleted 2y ago
[deleted]
TinkersW 2y ago
The accumulator is a vector type, with 64 bit sum you can only fit 4 into a 256 bit register. After the loop it will do a horizontal add across the vector register to produce the final scalar result.
- deleted 2y ago
  [deleted]

tdhz77 2y ago

Wow what a title.

zombot 2y ago

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

listeria 2y ago
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.
- zombot 2y ago
  It's not about being pedantic, it's about building the right habits. Building a habit of using x++ instead of ++x is suboptimal.