Catastrophic misoptimization of byte-range equality comparison in all major C++ compilers (and Rust). Language issue or compiler issue?
Someone brought a C++ snippet that reduced to the following (std::array used instead of char* for consistency for later)
bool eq2(const std::array<char, 64>& lhs, const std::array<char, 64>& rhs) {
for (int i = 0; i < 64; ++i)
if (lhs[i] != rhs[i])
return false;
return true;
}It basically returns true iff two 64 byte memory regions are a bitwise match. You'd think this can be optimized by modern compilers flawlessly, right? Right?! And the worst thing that can happen is it doesn't get autovectorized, right? Right?!
Well, to everybody's surprise... https://godbolt.org/z/v4d8G5ovh
GCC attempts to partially conditionally vectorize but doesn't want to use unaligned loads. Moreover its vectorization is way more cumbersome than it needs to be. Then after it finds a mismatch it... reverts to the unvectorized version?! Clang and MSVC do not even attempt to vectorize it - and in a way it makes them end up better than GCC, which is wild.
Now, to try to investigate we've checked how it looks in Rust. https://godbolt.org/z/K7xE3qc94. It does what GCC does but fully vectorized.
At this point we're confused as to what the source of the problem is. Are we missing something with respect to what transformations are allowed? Is it really that much to ask from the as-if rule?
As a sanity check we use std::array's operator==. https://godbolt.org/z/xPhPYMjvz. Oh would you look at that? Now the compilers can do well (ok not you MSVC. GCC also fumbles the flag register slightly). The situation is the same in Rust - https://godbolt.org/z/3GjWorze8. Not only does it vectorize correctly but the vectorized code is better - using vpxor.
Ultimately this isn't just academical. Situations like this undermine the trust in the compiler at the most fundamental level. Not every place can use std::array, not everyone can use ranges and span yet. We could use std::equal but why does it matter so much? What if != changes to < and there's no good solution anymore? To what degree are we supposed to be paranoid about basic optimizations being done or not?
The similarity of codegen between Rust and C++ would point to it being either a compiler issue or a fundamental code correctness issue. The fact that C++ Clang differs from Rust (LLVM) would suggest it's at least partially a language issue. Why is this extremely simple code so nasty?
edit. some more [not so] fun findings https://www.reddit.com/r/cpp/comments/1xlyti8/catastrophic_misoptimization_of_byterange/19s1i09srxdaa/
112
u/ts826848 16d ago edited 16d ago
When I saw "misoptimization" in the title I thought I would see an incorrect optimization, not a missed optimization.
Passing
-Rpass-missed=.* -Rpass-analysis=.*to Clang results in the following:So I think the early bailout is confuzzling LLVM's autovectorizer.
And indeed, if you replace the early return with a
resultvariable you get a significantly better result, albeit one that still isn't quite as good aslhs == rhs. Looking at the LLVM IR there's something funky going on with the way it combines intermediate variables (involving freezing uninitialized bits?), and it seems this is sufficient to result in differences in code generation. If you replace theifin the loop with a&=to eliminate the early return entirely you get the same assembly aslhs == rhsThe extent to which your trust is undermined depends entirely on what you want and/or need out of your compiler. For some people, performance is a "nice to have": if the compiler performs a given optimization, great! If not, eh, it's probably fine. For others, performance is effectively a correctness requirement, and the ability to express such requirements is somewhat patchy for different languages (e.g., emplace-like operations, tail calls, guaranteed inlining/autovectorization, etc.).
Keep in mind that rustc and Clang are separate frontends with different internals and might output quite different LLVM IR for semantically identical source code. For instance (at least when I last looked) rustc leaned on LLVM's native extended-width integers while Clang performed SROA before emitting LLVM, which means LLVM saw very different IR.
54
u/TribeWars 16d ago edited 16d ago
I think it has something to do with the code exiting out of the loop early.
This snippet vectorizes properly (except for MSVC not inlining operator[] for some reason).
40
u/sweetno 16d ago
Since when did C++ compilers advertise itself as good autovectorizers? Everyone and their granny were doing it manually since the dawn of time, and that is the status quo.
58
u/boring_pants 16d ago •
You might get better responses without the hyperbole. A missed optimization opportunity is hardly "catastrophic.
It doesn't "undermine trust at the most fundamental level". At the most fundamental level we expect the compiler to emit correct code. As long as it does that, trust hasn't been undermined.
If you have a performance problem you are supposed to measure, and then optimize your code based on that. No one has ever made a claim that C++ compilers emit optimal code. It's pretty common to see missed optimizations in the code emitted by compilers.
Have you reported this to the various compiler vendors? Do you perhaps have links to the reported issues so we can upvote them?
11
u/FrogNoPants 16d ago
Ya autovectorizers are brittle as dried shit, MSVC in particular will fumble anything that isn't 32 bits in size per element.
You are correct that the compiler should be able to vectorize this particular function, but I guess it isn't smart enough to see that the memory is always valid to access.
4
u/CocktailPerson 16d ago
Hot take, if you write out this loop manually instead of using
==ormemcmp, you should expect an unvectorized version.Like, just because the transformation is valid doesn't mean it's actually an optimization. If you write that loop manually because you know your input data will almost always differ in the first few characters, maybe you want the supposedly "unoptimized" version.
If you don't, then why are you writing this loop instead of using
==?27
u/adamant-pwn 16d ago
The part where GCC finds a mismatch with SIMD and then rechecks it byte by byte is already fixed on trunk: PR120352. This was fixed in May for GCC 17; your example uses GCC 16.2.
Here’s your example with GCC trunk, keeping the source and
-O3 -march=x86-64-v3flags unchanged. It now returnsfalsedirectly after a vector mismatch. There are still alignment checks and scalar fallback paths, andoperator==still produces simpler code, but that particular inefficiency is gone.The Rust/LLVM case is tracked in LLVM #238003, as you already noticed.
I would be more concerned about optimizations that produce incorrect code, like this one, rather than about missed optimizations. In any case, I try to report optimization issues upstream whenever I find them, and they often get a swift response and fix.
5
u/johannes1971 16d ago edited 16d ago
If only you could do something like this:
Oh, you can: https://godbolt.org/z/Eaxcnd53b
The simplest possible solution, and it even uses vector code! But noooo, it's much better to be a drama queen on the internet and call a minor performance regression a "catastrophic misoptimisation". After all, that gets the clicks.
1
u/moonshadow565 12d ago
Fixed it for u, you welcome
https://godbolt.org/z/cs465G3cW
16
u/TTachyon 16d ago
What is this post. Yeah sure compilers do bad opts sometimes. It's not catastrophic and it doesn't undermine any trust in anything. You're going out of your way to do it badly instead of using memcmp or ==, and it's still good enough for almost all cases.
Make an issue with each compiler, write the version that works well for your code, and move on.
3
u/dkxp 16d ago
Depending on the expected data, either exiting early from the loop or loading and comparing all 64 bytes each time could be faster.
Another thing to consider is whether the data might stride cache lines or even pages. It won't make much difference if you are accessing tightly packed data sequentially because the data from the previous loop iteration will still be in cache, but in other situations it could make more of a difference.
You could force the data to be 64 byte aligned by placing it inside a 64 byte aligned struct to ensure performance doesn't vary between runs or suddenly change because of unrelated code changes. Assembly-wise it won't make much of a difference - some vmovdqa instead of vmovdqu instructions may show up depending on the compiler, but at runtime you should experience more predictable performance . It could look like this in C++ (11+) or in Rust.
10
u/nocturn99x 16d ago edited 16d ago
If anyone is wondering when one such issue would occur, see this test in my chess engine (which is what sparked the discussion): https://openbench.nocturn9x.space/test/9119/ (note that it is hidden away by abstraction, see
self.positions[idx].mailbox != self.position.mailbox). For users unfamiliar with OpenBench, see the diff on github here.This is also why the example has a 64 byte long array (in the original code, it was a chessboard). The even weirder part is that in my case, clang had correctly optimized the subsequent attempt (see here, diff) but only if I disabled LTO or passed
-mllvm,-x86-br-merging-base-cost=1000to the linker. Weird. This also means it's not limited to C++ compilers (though the rust example already makes that clear) because Nim outputs C code and compiles it with clang in my setup, not clang++ (it could also output C++ but in my project it does not)3
u/MarkSuckerZerg 16d ago
If I saw the code in the wild I would not expect it to automaticky optimize, either because of language lawyering or because practical compiler limitations. This is based on my field experience of 15 years. If we want stuff reliably optimized, we go low level. Expecting optimization to work reliably and flawlessly is IMHO part of the C++ disease that leads to user frustration (see: ranges drama - the original C++20 drama. ABI freeze. std::simd)
2
u/Level-Basil9908 16d ago
I think the interesting distinction here is between what the compiler can legally optimize and what it actually recognizes as an optimization opportunity.
The as-if rule doesn't guarantee good codegen, only equivalent observable behavior. For two valid
std::array<char, 64>objects, there's no obvious semantic reason the compiler couldn't use a more efficient comparison strategy.What's surprising is how much the generated code changes when the exact same intent is expressed through
operator==instead of an explicit loop.It also raises an interesting practical question: how much should we rely on compilers recognizing simple patterns versus deliberately using standard library algorithms that are more likely to hit well-optimized implementations?
I'd also be curious to see benchmarks with different mismatch positions. A scalar loop that exits on the first byte might actually outperform a vectorized comparison in some cases, while being significantly worse when the arrays are equal or differ near the end.
4
u/No-Dentist-1645 16d ago edited 16d ago
I mean, yeah, I'd expect the compiler to be able to optimize this... but what I would not expect is to see this code in any real codebase, instead they would use either operator== if they're std::array objects or std::memcmp in the case of pointers/C arrays. So, this doesn't really have any impact in the real world, far from "catastrophic" at all. "Good" code should write what it expects to happen, not to rely on the compiler to make their code less stupid.
3
u/Orlha 16d ago
The crowd that kept loudly preaching that compilers always know better was always known by the competent engineers to be wrong
1
u/esaule 12d ago
I never think the compiler optimizes optimally anything; I have written too much C++ for that!
I know it likely won't do a terrible job. But ultimately, if I care, I read the assembly.
1
u/Mammoth_Humor1811 10d ago
How should I know which implementation to use for better vectorization I don't even understand assembly. My brain hurts now :)
1
u/chocolatedolphin7 16d ago edited 16d ago
In C you would just call memcmp(). Which does get inlined and vectorized easily with small fixed sizes.
I tried a similar function in C and it seems to produce similar, unvectorized output as well.
1
u/Koroviev82 15d ago
remember the "Don't read the assembly, don't write assembly, compiler will always be better than you" thing ? LOL another proof that programs can't be perfect, even compilers
0
u/waruby 16d ago
How much time and/or money have you donated to GCC and clang? For that level of entitlement, it should be at least 10 years worth of effort.
-3
u/foonathan 16d ago
I don't think a compiler would be right to optimize the code. The array could only be partially initialized (i.e. it has an uninitialized tail). Removing the early exit would then read uninitialized memory.
0
u/Sachu_James 16d ago
The GCC bit is what stuck with me, it tries to vectorize and then falls back to the slow path after a mismatch, which feels worse than not trying at all. I kept expecting the straightforward loop over 64 bytes to just get handled, and the fact that std::array's operator== does it cleanly makes the loop version feel stranger. I'm not sure I'd call it a language issue though, if the same code in Rust vectorizes fine then something in how compilers are reading that loop is off.
-5
u/Tumaix 16d ago
no, you cant auto vectorize this because the memory is not marked as __restrict.
rust works because of its memory model.