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

11–20 of 51 posts

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

#11

Post by aqrit »

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()`.

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

#12

Post by jasonthorsness »

jsheard wrote: post #7
jasonthorsness wrote: post #5

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/1898408922…

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.

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.

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

#13

Post by jsheard »

jasonthorsness wrote: post #12
jsheard wrote: post #7

Earlier quoted context omitted.

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.

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 sometime…

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.

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

#15

Post by neonsunset »

jsheard wrote: post #13
jasonthorsness wrote: post #12

Earlier quoted context omitted.

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 sometime…

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.

Indeed. .NET's SIMD primitives and platform intrinsics are more like the building blocks on top of which ISPC-like framework could've been built in .NET (more likely in F# since it's more flexible for libraries that want DSL-like customization).

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

#16

Post by dcsommer »

TheCoreh wrote: post #3

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 :?

If the goal is brevity, the rules could first replace 'std::' with nothing.

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

#18

Post by garaetjjte »

jsheard wrote: post #13
jasonthorsness wrote: post #12

Earlier quoted context omitted.

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 sometime…

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.

Larrabee influenced ispc but was dead by that time. https://pharr.org/matt/blog/2018/04/18/ispc-origins

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

#19

Post by nicula »

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

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."

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

#20

Post by nicula »

meisel wrote: post #10

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.

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.

Post reply on HN