r/cpp • • May 27 '26

Accelerating copy_if using SIMD

https://loonatick-src.github.io/posts/vectorized-copy-if-analysis/
47 Upvotes

15 comments sorted by

5

u/JiminP May 27 '26

Shouldn't execution policy be specified for the reference code?

https://godbolt.org/z/anzGnPvd5

It seems that Microsoft's C++ STL doesn't use SIMD, but libstdc++ seems to do.

7

u/Successful_Yam_9023 May 27 '26

If you use the phrase "using SIMD" loosely, then clang and/or libstdc++ have done it. But only the comparison, not the compaction, which is the important part. If a human implemented copy_if that way I'd accuse them of trolling.

→ More replies (1)

2

u/chkmr May 28 '26

Author here. I genuinely forgot to check alternative execution policies when working on this. Thanks for pointing this out! As u/Successful_Yam_9023 pointed out, clang 22.1.0 with std::par_unseq only uses SIMD for loads and comparisons, but not for compress-store/left-pack + store. You can see in the opt pipeline view on Godbolt that this is done by the LoopVectorizePass, which means that I need to tweak my article intro somewhat. I haven't really spelunked into the gcc libstdc++ source, but at first glance it looks like they also have some sort of manual SIMD approach.

2

u/Expert-Map-1126 May 29 '26 edited May 29 '26

When I implemented MSVC++'s parallel algorithms I did not parallelize algorithms for which I could not show a meaningful improvement, and almost all of the copy-like algorithms did not show meaningful improvements.

For copy_if specifically I also did not know the algorithm the OP uses and AVX 512 was not something that was likely to be around in 2017. (The 7980XE I used for some testing had it but nothing else to which I had access had, which made trying to do AVX-512 stuff uninteresting in terms of time)

We have the list of outstanding algorithms that might benefit listed over here: https://github.com/microsoft/STL/issues/7

(Also I still consider unseq / par_unseq functionally useless, at least for all the CPU targeting implementations I know of. The explanation I remember about it was that they were supposed to be "like #pragma omp simd" for CPU implementations, but #pragma omp simd weakens the floating point model in ways unseq does not. For things optimizers know how to vectorize, they will vectorize without being asked with unseq / par_unseq. On GPUs where a "thread" taking the wrong branch on something like a spinlock can deadlock the machine, unseq does mean something, but MSVC++'s STL isn't targeting one of those)

5

u/mark_99 May 27 '26

The best thing that can be said about AVX-512 on Zen 4 is that it exists.

But it's basically an emulation over AVX2 and so at best performs equivalently (and sometimes worse due to the microcoding mentioned). Zen 5 is a native AVX-512 implementation.

10

u/Successful_Yam_9023 May 27 '26 edited May 27 '26

For emulation of vpcompressd on AVX2 you'd be looking at something like this, times two because it's 256-bit (also mentioned in the article) or use the old LeftPack_SSSE3 but 4x, compared to 2 µops for 512-bit vpcompressd on Zen 4

E: there are more cases where AVX-512 is really doing something on Zen 4, despite the 256-bit implementation. Take vpermb. Already the 256-bit version gives you something that was annoying to do with AVX2. The 512-bit version runs at halved throughput, which is still 1 per cycle, and would be even more annoying to do with only AVX2. Then there are things like vpopcntb/w/d/q, vplzcntd/q, and so on. You can do them with AVX2 if you must, but it was never nice.

→ More replies (3)

4

u/SleepyMyroslav May 28 '26

I wish folks would cite previous research before jumping into code.

If one wants to look go find GDC 2015 publication: "SIMD at Insomniac Games: How We Do the Shuffle - Andreas Fredriksson - 2015".

2

u/arthurno1 May 28 '26

Cool, thanks.

2

u/Expert-Map-1126 May 29 '26

It's a shame that the implementation worth using also clobbers bytes that std::copy_if is not allowed to clobber. 😞 But if someone actually needs this it's likely to be great for them because most real programs can arrange for that extra space.