search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
27.97k stars 11.54k forks source link

C++ Range view filters prevent vectorization. #85700

Open SylvanBrocard opened 6 months ago

SylvanBrocard commented 6 months ago

As of now, C++ range adapters pipelines that invoke std::ranges::views::filter prevent vectorization, where the equivalent imperative algorithm vectorizes normally. This is true with both the libstdc++ and the libc++. Note that the same thing happens for GCC. The only discussion I've found about the problem was by Bryce Adelstein Lelbach in episode 124 of ADSP.

Here is a Godbolt link showcasing the issue. I've added a version using Tristan Brindle's Flux library, which does vectorize properly due to its iteration logic.

What I'm yet unclear about, is whether this is just an implementation detail that might get ironed out eventually, or if there is something in the standard specification of the C++ ranges that prevents this kind of optimization. Bryce Adelstein Lelbach asserts that this is due to the non-shape preserving nature of the filter adaptor, but couldn't a standard library implementation do the same kind of consumer analysis that Flux does, or would that go against some aspect of the standard?

philnik777 commented 6 months ago

The ADSP episode describes the problem pretty well IIRC. I'm sure this can be improved, but it will take a while, since implementations basically have to specialize the algorithms to just check the condition instead of looping until it is met. It is on my list of things to improve, but that list is very long and this problem is not very high on it. We currently don't vectorize most of the basic algorithms, let alone more complex cases.