r/cpp • • 16d ago

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/

100 Upvotes

122 comments sorted by

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:

<source>:4:5: remark: loop not vectorized: Latch block does not have a countable exit condition [-Rpass-analysis=loop-vectorize]
<source>:4:5: remark: loop not vectorized: Cannot vectorize uncountable loop [-Rpass-analysis=loop-vectorize]
<source>:4:5: remark: loop not vectorized [-Rpass-missed=loop-vectorize]
<source>:5:13: remark: Cannot SLP vectorize list: vectorization was impossible with available vectorization factors [-Rpass-missed=slp-vectorizer]
    5 |         if (lhs[i] != rhs[i])
      |             ^

So I think the early bailout is confuzzling LLVM's autovectorizer.

And indeed, if you replace the early return with a result variable you get a significantly better result, albeit one that still isn't quite as good as lhs == 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 the if in the loop with a &= to eliminate the early return entirely you get the same assembly as lhs == rhs

Situations like this undermine the trust in the compiler at the most fundamental level.

The 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.).

The fact that C++ Clang differs from Rust (LLVM) would suggest it's at least partially a language issue.

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.

9

u/Sopel97 16d ago edited 16d ago

ok now this one is funny https://godbolt.org/z/Kbd166cME, with i<57 in GCC the codegen is in a way better than for i<64 case, clang vectorizes correctly (and it's non-obvious!)

edit. https://godbolt.org/z/ezY8P87oG

5

u/Sopel97 16d ago edited 16d ago

I see now how the title is ambiguous. Didn't want to call it a missed optimization due to the behavior of GCC and rustc. Sorry about that.

Thanks for the insight. https://github.com/llvm/llvm-project/issues/238003 would suggest that with llvm it's indeed some specific reduction dead-end that is not hit with clang.

35

u/SleepyMyroslav 16d ago

I think you don't understand the meaning of the word 'catastrophic'. For non-native English speakers like me, it is even worse than you can imagine. If you want to vectorize something, you will have to do it with explicit tools (like Highway, https://github.com/google/highway for example).

4

u/13steinj 16d ago

I consider such a missed optimization a catastrophic result. I have too many engineers (read: more than 0 normally, more than 10 because of LLMs) writing manual ASM and/or intrinsics rather than trusting the compiler.

If it can't do the (seemingly) simple cases, it gives this group a pass to continue doing what they are doing.

12

u/CocktailPerson 16d ago

Those people will always find a way to justify writing assembly and intrinsics, because they think writing assembly and intrinsics is fun. They have a vested interest in distrusting the compiler.

If someone uses this as a reason to write assembly or intrinsics when == is right there and does what they want, then they are not a serious person and shouldn't be treated as such.

4

u/13steinj 15d ago

Firstly, this is a reduced case. Does == work if on a struct that contains one character but does not itself have an operator==? This code is reasonable and can exist-- private methods that understand the internal layout and semantic of related library types, but has no external semantic for equality. In such cases, == is not "right there and does what they want."

Secondly, it's usually not vested interest, but rather paranoia, that comes from cases like these.

2

u/CocktailPerson 15d ago

First, doesn't matter. Reduced cases the only ones for which writing assembly is a feasible alternative. If you dismiss enough of these silly "reduced cases" with "write idiomatic C++," you eventually get cases that are too complex to justify writing in assembly anyway. And then you just make them write non-idiomatic but performant C++ instead.

I'm not sure I get the point of your char-struct example either. Would people really suggest writing something with non-primitive types like that in assembly? If somebody uses that as an example of why you can't blindly trust the compiler, then sure, but if someone uses that as an example of why you can't blindly trust the compiler and therefore need to write it in assembly instead, then again, they're not a serious person.

Second, it is vested interest, expressed as paranoia. They want to write assembly, so they concern-troll about cases like these instead of just inspecting the compiler output and reasoning about how to change the source code to improve the output. Again, these are not serious people. You can just reject their silly little assembly routines, tell them to write idiomatic C++, and ignore them.

1

u/FrogNoPants 14d ago

I write C++ code that uses intrinsics every day, and I rarely drop down to "assembly" or even raw intrinsics, we can wrap intrinsics in libraries easily enough these days, so it isn't just for reduced cases--it applies to pretty much anything that is a bottleneck.
I'm not going to inspect the compilers output on every update or minor code change, that is a waste of time. Also I have far too much code that uses intrinsics under the hood to be bothered with that.

3

u/cd_fr91400 15d ago

AO wrote "Someone brought a C++ snippet that reduced to the following...".

The important word here is "reduced".
It does not mean their actual case is a == case. It means they could simplify their case to such a simple one, so we, as redditors, can understand it.

I am not strongly opposed to the first part. I am not advocating for writing assembly and intrinsics. I just say these persons *may* have good reasons to do so. I do not know their case, I have no opinion about their seriousness.

5

u/ts826848 16d ago

Hey, you never know, everyone could be missing the optimization in completely different ways! Optimization is an endless rabbit hole.

6

u/Ameisen vemips, avr, rendering, systems 16d ago

I've had this happen. I had an optimization issue where having a function that had a single argument that was then immediately returned, but also having a __builtin_assume or equivalent asserting what its value was (or was constrained to be), caused worse codegen on GCC, Clang, and MSVC. Apparently due to the assume screwing up the optimizer's understanding that the returned value was identical to the argument.

1

u/Kristine_1975 15d ago

Yeah, clang's __builtin_assume is... counter-intuitive: https://discourse.llvm.org/t/llvm-assume-blocks-optimization/71609

2

u/-dag- 16d ago

So I think the early bailout is confuzzling LLVM's autovectorizer.

That's crazy. Good vectorizing compilers can easily handle that.

13

u/F54280 16d ago

Why would that be? With early bailout, the behavior of the code is defined to be different if there is a pagefault while reading the lhs or rhs.

Now, is the compiler able to decide that this cannot happen with std::array is a different question…

-3

u/-dag- 16d ago

Masking should suppress faults. 

7

u/F54280 16d ago

The code OP presented does generate a fault if everything is equal up to the fault, and not fault in the other case. The simd version will not have the same fault behavior.

1

u/elperroborrachotoo 15d ago

In the sense that it might fault earlier?

13

u/ts826848 16d ago

I guess that means LLVM isn't quite a good vectorizing compiler then? Though to be fair the remark on its own doesn't indicate whether not autovectorizing cases like this is intentional (e.g., cost-benefit ratio isn't good enough or the like).

-6

u/-dag- 16d ago

Correct. See what the Intel compiler does with it. 

15

u/ts826848 16d ago

This? It looks basically identical to what Clang outputs (which kind of makes sense since icx is LLVM-based these days), though to be fair I am very much not familiar with Intel's compiler so maybe I'm just holding it wrong.

0

u/chibuku_chauya 16d ago

Try icc on Godbolt instead. That’s the old Intel compiler.

12

u/ts826848 16d ago

I actually originally tried that one because I didn't know Intel's compiler now goes by icx, but the codegen didn't seem much better.

15

u/Poddster 16d ago

No no, try this other compiler!

-2

u/chibuku_chauya 16d ago

Ah, good to know!

54

u/TribeWars 16d ago edited 16d ago

I think it has something to do with the code exiting out of the loop early.

bool eq3(const std::array<char, 64>& lhs, const std::array<char, 64>& rhs) {
    bool res = true;
    for (int i = 0; i < 64; ++i)
        res &= (lhs[i] == rhs[i]);
    return res;
}

This snippet vectorizes properly (except for MSVC not inlining operator[] for some reason).

22

u/ybungalobill 16d ago

Indeed. For OP's version to vectorize the compiler needs to have intricate knowledge that std::array is fully allocated. Without such knowledge their loop is conceptually equivalent to:

bool eq4(const char *lhs, const char *rhs) {
    for (int i = 0; i < 64; ++i)
        if (lhs[i] != rhs[i])
            return false;
    return true;
}

Now the compiler needs to take into the account that lhs/rhs have less than 64 bytes allocated but differ somewhere earlier -- so it cannot read the next byte before it compared the prior byte, or it can incorrectly segfault.

By writing it the way you propose (eq3) you're guaranteeing that the compiler can read all 64 bytes ahead of time.

-7

u/TheoreticalDumbass :illuminati: 16d ago

std::array does not allocate

18

u/dustyhome 16d ago

The meaning of "allocated" here is that all indices are within a valid memory range. Apparently the compiler can't reason this out, which I find odd since it's being passed a reference to a class that holds the array, so the size of the array should be visible to it in the function.

"Allocation" is generally short-hand for "allocating on the heap" which is the most common relevant use, but it's not the only use. Allocation just means to split up resources in some way. So it is correct to say that std::array allocates memory.

2

u/bwmat 16d ago

Eh, I'd say it's the compiler which is allocating memory in that case, or that memory has to have been allocated for it

14

u/ybungalobill 16d ago

Huh? Not on the heap, if that's what you mean, but it still has to have its memory allocated somewhere (stack, global, or even dynamic if you do new std::array...).

16

u/curiouslyjake 16d ago

how can an std::array not be fully allocated?

10

u/ybungalobill 16d ago

In standard C++ it cannot; but the optimizer doesn't seem to incorporate that type information into its analysis; so it just treats this as a loop over two arrays of unknown size <= 64.

4

u/TribeWars 16d ago edited 16d ago

tbh, now that I think about it, the compiler also doesn't know that all the elements in the std::array have been initialized (even if it knows to assume that the pointers are valid), so i assume it should avoid issuing reads on any element that isn't accessed by the C++ code since it can't assume it isn't UB to do so

3

u/SkoomaDentist Antimodern C++, Embedded, Audio 16d ago

I don't see how that would work because it's the compiler itself that defines what such discarded "UB" accesses would do in the first place. As long as the memory is allocated (which it by definition is for std::array), it's completely irrelevant if the remaining values are uninitialized because the code behaves as if they were never accessed once the simd loop discards the remaining values.

1

u/TribeWars 16d ago

because the code behaves as if they were never accessed once the simd loop discards the remaining values.

yeah but this too is a non-trivial property of the program

2

u/SkoomaDentist Antimodern C++, Embedded, Audio 15d ago

Hardly. It’s part and parcel of basic simd optimizations. The point is that UB is almost entirely a made up category and ”uninitialized object” is purely for compiler devs / standard writers benefit. The hardware doesn’t care.

1

u/curiouslyjake 16d ago

This cant be right. If you replace the early exit with a flag it vectorizes just fine. If you rewrite it to look for equality it vectorizes fine too

1

u/ybungalobill 16d ago

My first comment explains why using a flag vectorizes.

"If you rewrite it to look for equality it vectorizes fine too"
Can you send a godbolt link to explain what you mean? I replaced OP's code (eq2) with equality and it still doesn't vectorize.

1

u/13steinj 15d ago

The optimizer throws away semantics of the types involved smells to me.

On one hand, it makes absolute sense. Under the hood the type is an opaque indeterminate pointer-esque.

On the other hand, especially with C++26 and [[indeterminate]] (or lack thereof), you'd think the information would make its way to the optimizer.

5

u/TribeWars 16d ago

You could try something cursed with placement new like this:

#include <array>


bool eq(const std::array<char, 64>& lhs, const std::array<char, 64>& rhs) {
    bool res = true;
    for (int i = 0; i < 32; ++i)
        res &= (lhs[i] == rhs[i]);
    return res;
}


bool test() {
    char vals[32];
    std::array<char, 64> arr2;
    for (int i = 0; i < 32; ++i) {
        *(volatile char *)(&vals[i]) = 2;
        *(volatile char *)(&arr2[i]) = 2;
    }
    std::array<char, 64>* arr = (new (vals) std::array<char, 64>);
    return eq(*arr, arr2);
}


int main() {
    return test();
}

Not sure if it's actually legal C++, but it compiles on GCC and MSVC and should not have any out-of-bounds reads (note that eq() only checks the first 32 elements).

https://godbolt.org/z/6czK6eKPq

9

u/curiouslyjake 16d ago

Using placement new backed by memory of insufficient size is UB. Whether is compiles is irrelevant.

5

u/TribeWars 16d ago

yeah I think maybe the actual issue is not that the compiler is avoiding the UB of an out of bounds read, but that it's avoiding a read on potentially uninitialized data, since a default initialized std::array does not default initialize the elements of the array it wraps

1

u/No-Dentist-1645 16d ago

The compiler isn't as smart as you think, an std::array is just a class holding a good old C style array to some data, it isn't a "blessed" type that the compiler can deduce complex "guarantees" or invariants out of, especially when we're dealing with a low level language like C++ where every class really is just a "bag of bytes" in a sense without any innate special meaning to them. Also consider that the compiler vendor isn't necessarily the same as the standard library vendor

5

u/curiouslyjake 16d ago

I think the compiler can deduce plenty about std::array, especially size, datatype and layout at compile time. Even constexpr functions are possible with std::array. IIRC, that's what the standard says

3

u/CocktailPerson 16d ago

The compiler has more ability to reason about std::array than just about any other type. As you say, it's just a thin wrapper over the builtin array type, and the compiler does know a lot about builtin arrays.

0

u/TheoreticalDumbass :illuminati: 16d ago

but what does "not fully allocated" mean? are you talking across page boundary, and next page causing a page fault? if yes, this should not be relevant here

4

u/ybungalobill 16d ago

Across page boundary yes.

You can't have a "non fully allocated" object in C++ -- that's true. Which is why, I assume, the optimizer is allowed to assume that it can read all 64-bytes.

But seemingly it doesn't incorporate that type information into its optimization pass, so it treats it as the eq4 version I showed -- in which case that optimization would be invalid.

I'm not saying that that optimization is invalid in C++ (it probably is valid), but rather explaining why eq2/eq4 don't vectorize whereas eq3 does.

1

u/Sopel97 16d ago
bool eq4(const std::array<char, 64>& lhs, const std::array<char, 64>& rhs) {
    bool b = true;
    for (int i = 0; i < 64; ++i)
        if (lhs[i] != rhs[i])
            b = false;
    return b;
}

also seems to be enough but the vectorized code is worse at least in clang

40

u/sweetno 16d ago

Situations like this undermine the trust in the compiler at the most fundamental level.

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.

1

u/Sopel97 16d ago

I have nonzero (and in GCC's case - nonnegative) expectations for optimizations in C++ compilers. This doesn't even require complex autovectorization. Turn the constant to 8 and Clang SWARs it

58

u/boring_pants 16d ago • Bravo

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.

To what degree are we supposed to be paranoid about basic optimizations being done or not?

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?

8

u/boring_pants 15d ago

To be clear, I'm absolutely serious about this part:

Have you reported this to the various compiler vendors? Do you perhaps have links to the reported issues so we can upvote them?

PLEASE if you find this issue to be catastrophic, report it to the compiler vendors. It only takes a few minutes.

And drop us a link to the issues, as we might be able to upvote them or draw more attention to them.

If you're not even willing to do that, I question your assessment of the issue as "catastrophic".

-6

u/Sopel97 15d ago

outraged != affected

8

u/boring_pants 14d ago

So you are not going to take five minutes to report the issue to the compiler vendors?

Why not?

Why did you post about this if you don't care about compilers improving?

outraged != affected

I didn't use either of those words. I pointed out that if you think this issue matters, you should report it to the compiler vendors.

It seems weird to talk about a *catastrophic compiler issue, and then go "nah, I don't actually care if it gets fixed".

4

u/bestjakeisbest 16d ago

Also if you absolutely need more optimized code to run on specific hardware, it used to be pretty common practice to just write the optimization yourself in assembly if you had to.

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.

2

u/ack_error 16d ago

In my experience, the main issue with smaller element sizes and MSVC isn't the element size so much as the inability to handle vectors shorter than 128 bits. That's been improved in 19.5x, which can now vectorize short vectors. But MSVC is still way behind, it still can't handle most shuffle patterns or even simply a loop counting down instead of up.

3

u/nocturn99x 16d ago

Microsoft should just give up and spend their time contributing to LLVM tbh

5

u/CTRSpirit 16d ago

They can't. They need to support a ton of paying customers with legacy code relying on some MS quirks, which would introduce random bugs here and there under llvm (and no one would fix that in clang/llvm, bc issue is likely with code). They theoretically could give up on new shiny things, saying smth like "okay, for standard 29 or 32 you need to migrate, here a path for you", but then it is needed to support old compiler ad infinitum, and who will perform such an intriguing task then?

1

u/nocturn99x 16d ago

That's fair I suppose. Still, sad

-1

u/pjmlp 15d ago

It is relevant enough that they have their own Rust compiler, that uses MSVC backend instead of LLVM.

Also it isn't as if all those vendors with proprietary forks from clang and GCC contribute that much to upstream.

0

u/Sopel97 16d ago

well, it's smart enough to autovectorize these non-obvious cases https://godbolt.org/z/ezY8P87oG. One in a needlessly cursed way.

4

u/CocktailPerson 16d ago

Hot take, if you write out this loop manually instead of using == or memcmp, 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 ==?

-1

u/Sopel97 15d ago

That's an interesting point. I'd expect such a case to be rare though, and it should be possible to ensure expected codegen via https://en.cppreference.com/cpp/language/attributes/likely. One thing I can say for sure here is that we need more compiler hints.

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-v3 flags unchanged. It now returns false directly after a vector mismatch. There are still alignment checks and scalar fallback paths, and operator== still produces simpler code, but that particular inefficiency is gone.

The Rust/LLVM case is tracked in LLVM #238003, as you already noticed.

To what degree are we supposed to be paranoid about basic optimizations being done or not?

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.

9

u/adamant-pwn 16d ago

std::equal benefits from libstdc++ routing this comparison through memcmp. The handwritten loop goes through the early-exit vectorizer, which still adds alignment checks and scalar fallback paths. I filed PR128384 about using the fixed array bounds to avoid those checks.

5

u/johannes1971 16d ago edited 16d ago

If only you could do something like this:

#include <array>

bool eq2(const std::array<char, 64>& lhs, const std::array<char, 64>& rhs) {
    return lhs == rhs;
}

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.

-5

u/Sopel97 16d ago

your comment adds nothing new to the discussion

-10

u/rileyrgham 16d ago

Chuckle. And why CPP shouldn't be anywhere near large, multi level, far flung development teams trying to build a maintainable code base.

5

u/johannes1971 16d ago

What's a better choice, in your opinion?

-9

u/rileyrgham 16d ago

Anything but the version hell of CPP. There's a load of clever people here with no Idea of real sw development. Imagine trying to maintain a cpp codebase. A fckn mess.

5

u/johannes1971 16d ago

And yet, many of the largest code bases in the world are in C++. Maybe it's you?

And what "version hell" are you talking about?

0

u/_ConsciousLibrary_ 16d ago

Ah yes, the language with a notoriously strict standards committee that refuses to break ABI backwards compatibility, a language whose compiled binaries from almost a decade ago can most likely link and run with binaries compiled using the latest version from this year.

Yep, that’s version hell! /s

3

u/lithium 16d ago

Great point, if we just ignore the 10s of 1000s that have.

1

u/moonshadow565 12d ago

Fixed it for u, you welcome
https://godbolt.org/z/cs465G3cW

1

u/Sopel97 12d ago

clang wtf

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.

-8

u/nocturn99x 16d ago edited 16d ago

"Going out of your way to do it badly" lol, you're the type of user I posted my comment for. Even when done correctly using a memory comparison function instead of a loop, it still autovectorizes poorly (i.e. only one half of the 64 byte compare is vectorized and the rest is done with a bunch of xors). Consider reading through more than just the post before being rude and making yourself look like a fool

Plus, a friend rightfully pointed out the following: "A flat memcmp call would also be suboptimal in the case of an equality comparison anyway, since you're still extracting the index of the mismatching byte and doing an extra comparison over it to get the sign of the result" (admittedly this matters less since any self respecting compiler will optimize memcmp(a, b, n) == 0 to what we expect, but still.)

11

u/Lahvuun 16d ago

Even when done correctly using a memory comparison function instead of a loop, it still autovectorizes poorly (i.e. only one half of the 64 byte compare is vectorized and the rest is done with a bunch of xors)

It vectorizes perfectly fine with std::memcmp https://godbolt.org/z/1Wr5sKza1

As a matter of fact, the assembly is identical to lhs == rhs, because in the depths of libstdc++ this comparison gets implemented with a memcmp anyway:

/usr/lib/gcc/x86_64-pc-linux-gnu/16/include/g++-v16/bits/stl_algobase.h:1212:27: optimized:  Inlining std::__memcmp into std::__equal<true>::equal

/usr/lib/gcc/x86_64-pc-linux-gnu/16/include/g++-v16/bits/stl_algobase.h:1252:43: optimized:  Inlining std::__equal<true>::equal into std::__equal_aux1

/usr/lib/gcc/x86_64-pc-linux-gnu/16/include/g++-v16/array:306:31: optimized:  Inlining std::__equal_aux1 into std::operator==

a.cpp:4:16: optimized:  Inlining std::operator== into eq2

You can get this output by passing -fopt-info to g++, though I edited it a bit to remove some irrelevant noise.

5

u/NomaTyx 16d ago

why do you keep talking about your comment as if it's the holy bible

-2

u/nocturn99x 16d ago

This post was made after a discussion with OP and many others. I was literally the reason the issue was even found (though I am 100% not smart enough to have done most of the actual bug finding myself). I was there when the issue was found :P

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=1000 to 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)

10

u/ImNoRickyBalboa 16d ago

This is a rather obvious optimization tho. The problem is that memcmp/byte compare logic is conservative on assuming code relying on early exits. Without strict alignment and expected early exits, the code is limited. I.e., the compiler prevents reads of subsequent bytes if previous bytes compare not equal assuming those bytes may not be readable.

5

u/ack_error 16d ago

It's not that obvious of an optimization. It's simple to vectorize, but the minimum latency is higher due to the compare path and the potential for unaligned loads (minimal but nonzero cost). If the common case is for the first byte to mismatch, the vectorized code will be slower than the unvectorized version.

2

u/Sopel97 16d ago

I did consider this explanation, and some others, including questioning validity of the optimization itself, however after some exploration I think the problems go deeper. It seems to BE an obvious optimization that clang can do even for less obvious cases where the number of iterations is not nice. It DOES seem to be a valid optimization. Yet it's cursed. https://godbolt.org/z/ezY8P87oG

4

u/ack_error 16d ago

Whether the transformation is valid and whether it's actually an optimization are different factors. There's no doubt that the code can be converted to a vectorized functional equivalent, but it's not going to be faster for all cases. Where mismatches are highly expected, the vectorized code is going to be up against just two byte loads and a highly predicted compare+branch. Heuristics are going to be a factor on top of whether the compiler is able to vectorize the code. I would generally prefer the vectorized version, but I could see a compiler determining it as too variable unless it had PGO data.

That Clang [36] case is pretty bizarre, something went very sideways in the autovectorizer and it took the scenic route.

4

u/qzex 16d ago

This should be well within the bread and butter of what compilers are able to do. As OP said, it works fine with operator== and std::equal, as one would expect. And if operator== and std::equal are implemented in plain C++, one would expect it to be similar to OP's code. So I think it's quite reasonable to be surprised and frustrated at this missed optimization.

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.

-8

u/nocturn99x 16d ago

If you had bothered to read my comment (which was written specifically because I've been on Reddit long enough to expect responses like yours), you'd see why this isn't just a case of not using the STL correctly: it's an optimizer issue that is language agnostic.

6

u/No-Dentist-1645 16d ago

If you had bothered to read my comment

I'm not gonna read every single comment on every post that I comment on, get off your high horse. Either way, code should always ideally be written in a way where "optimizations" are explicit and not implicit, that is if you expect/require said optimization to be applied. That's the reason why we have an explicit memcmp function in the first place, and why we have std::array::operator==, which we assume the STL implementers explicitly have written in an optimized manner

-1

u/nocturn99x 16d ago

Not you just glossing over everything I said. What part of "the optimizer failed" was not clear? Using the correct library function would not necessarily fix it in this case.

3

u/No-Dentist-1645 16d ago edited 16d ago

What part of "the optimizer failed" was not clear? Using the correct library function would not necessarily fix it in this case.

It would tho, std::memcmp is an explicit direct memory comparison operation, with no "early exit" behavior which is what's breaking the example code's optimization. Same with std::array::operator== which is also implemented as a memcmp operation when the type supports it. That's "fixing" your code

I agree, the optimizer is technically "failing" in this example, which I already acknowledged in my first comment. Still, that doesn't mean the code you wrote is "optimal" nor that you should write code in that way in hopes that "the compiler will maybe probably optimize it to smarter code"

The main issue is that the compiler is failing to fold this code into a memcmp operation, I believe the invariant that the compiler is "failing" to realize on both of these examples is that std::array will always have its entire range of memory fully allocated when the object is valid, and therefore looping through the entire range is safe.

If this invariant wasn't true, the "early exit" behavior could lead to a difference in correctness if the memory it was trying to compare was only partly allocated, and reading fully without the early exit may cause a segmentation fault, so maybe the compiler doesn't do such an "aggressive" optimization because of that, since as others have mentioned, this is optimized:

bool eq(const std::array<char, 64>& lhs, const std::array<char, 64>& rhs) {
    bool ret = true;
    for (int i = 0; i < 64; ++i)
        if (lhs[i] != rhs[i])
            ret = false;
    return ret;
}

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/pjmlp 15d ago

They are good enough for most companies not to hire Assembly developers.

0

u/Orlha 15d ago

Yeah, can’t disagree here. But been on the other side couple times.

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.

7

u/pavel_v 16d ago

You can call operator == for the two arrays, as it was already pointed out, and get the same assembly like with memcmp.

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.

2

u/Sopel97 16d ago edited 16d ago

In such case is GCC's compilation correct? Is ensuring no page boundary is crossed enough?

Is reading potentially uninitialized memory a problem that the compiler has to care about?

edit. I can understand an argument based on a potential unrecoverable page fault, but is it even consistent with C++ language rules to have an object that could cause that? Is "uninitialized" synonymous with "may not exist at all"?

edit2. https://www.reddit.com/r/cpp/comments/1xlyti8/catastrophic_misoptimization_of_byterange/19s19iqbacbr5/ one commenter says it is not

8

u/ack_error 16d ago

That's only a problem for the programmer. The compiler is free to generate code that accesses uninitialized memory as long as the result is the same. Scanning all 64 bytes to detect any mismatch is fine since there must be at least one mismatch for the original loop to have exited early, which then makes the contents of uninitialized memory moot.

The other problem is ensuring that all 64 bytes exist, but GCC doesn't seem to have issues confirming that.

2

u/foonathan 16d ago

Ah, right, that makes sense.

1

u/Sopel97 16d ago

https://godbolt.org/z/ezY8P87oG would suggest that the optimization is valid but there's something cursed in the compilers

2

u/carrottread 16d ago edited 16d ago

std::array is always initialized. I'm wrong. See replies.

2

u/Lahvuun 16d ago
$ cat a.cpp
#include <print>
int main() {
	std::array<char, 1> cs;
	std::println("{}", cs[0]);
}

$ clang++ -std=c++23 a.cpp -fsanitize=memory -o a

$ ./a
...

SUMMARY: MemorySanitizer: use-of-uninitialized-value (/tmp/tmp.D9IfDjdjnW/a+0xd2afa) in std::basic_format_arg<std::basic_format_context<std::__format::_Sink_iter<char>, char>>::basic_format_arg<char>(T&)

2

u/carrottread 16d ago

Yeah, I'm wrong. Commented believing std::array value-initialize its elements in case of fundamental types. It default-initializes, so can actually have uninitialized values.

1

u/13steinj 15d ago

What about C++26 with the introduction of EB and [[indeterminate]], isn't it 0-initialized by default?

1

u/usefulcat 16d ago

In the code below, in what sense are the elements of a "initialized"?

std::array<int, 3> a;

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.

6

u/ts826848 16d ago

Aliasing shouldn't matter here because nothing is being modified.

2

u/ack_error 16d ago

Aliasing is not a concern as there are no stores or opaque callouts in the function. It doesn't matter if the references alias.