为什么GCC不能为两个int32s的结构体生成最优的operator==操作符？

Question

我的同事给我展示了一段代码，我认为这段代码不必要，但是实际上它非常重要。我预期大多数编译器会将下面三种尝试判断相等性的方式视为相等：

#include <cstdint>
#include <cstring>

struct Point {
    std::int32_t x, y;
};

[[nodiscard]]
bool naiveEqual(const Point &a, const Point &b) {
    return a.x == b.x && a.y == b.y;
}

[[nodiscard]]
bool optimizedEqual(const Point &a, const Point &b) {
    // Why can't the compiler produce the same assembly in naiveEqual as it does here?
    std::uint64_t ai, bi;
    static_assert(sizeof(Point) == sizeof(ai));
    std::memcpy(&ai, &a, sizeof(Point));
    std::memcpy(&bi, &b, sizeof(Point));
    return ai == bi;
}

[[nodiscard]]
bool optimizedEqual2(const Point &a, const Point &b) {
    return std::memcmp(&a, &b, sizeof(a)) == 0;
}


[[nodiscard]]
bool naiveEqual1(const Point &a, const Point &b) {
    // Let's try avoiding any jumps by using bitwise and:
    return (a.x == b.x) & (a.y == b.y);
}

但出乎意料的是，只有使用memcpy或memcmp的部分会被GCC转换为一个64位比较。为什么？(https://godbolt.org/z/aP1ocs)

难道对于优化器来说，如果我检查四个连续字节对的相等性，这就等同于在所有8个字节上进行比较？

试图避免将两个部分分别布尔运算的尝试编译效率稍微提高了一些（指令减少了一个且EDX没有错误依赖），但仍然需要两个32位操作。

bool bithackEqual(const Point &a, const Point &b) {
    // a^b == 0 only if they're equal
    return ((a.x ^ b.x) | (a.y ^ b.y)) == 0;
}

GCC和Clang在通过值传递结构体时都存在相同的未优化问题（因此a在RDI中，b在RSI中，因为这是x86-64 System V调用约定将结构体打包到寄存器中的方式）：https://godbolt.org/z/v88a6s。memcpy/memcmp版本都编译为cmp rdi, rsi/sete al，但其他版本则进行单独的32位操作。

令人惊讶的是，在参数位于寄存器中的按值情况下，struct alignas(uint64_t) Point仍然有助于优化GCC的两个naiveEqual版本，但不适用于bithack XOR/OR。（https://godbolt.org/z/ofGa1f）。这是否给我们提供了有关GCC内部的任何提示？Clang不受对齐的影响。

- Ben

---

请参考提供链接中的汇编输出。 - Drew Dormann

这句话的意思是如何使用 return std::memcmp(&a, &b, sizeof(a)) == 0; 来代替优化版本，因为它生成的汇编代码相同且更为表达清晰。 - Ayxan Haqverdili

@dyp：哇，是的，它无意义地扩展了比较结果到两个64位元素，使用vpmovsxdq / vmovmskpd，而不是只使用vmovmskps / cmp al, 0xf（高零值在pcmpeqd输入中将相等，因此总是会设置顶部2位）。甚至可以使用vpmovmskb; 我们只需要低8位。当然，在这里纯标量显然更好，但如果要查找类似a.x == b.x && a.y！=b.y的内容，您可以使用clang的SIMD策略，只需使用不同的比较值，例如低2位中的0x1而不是0x3。 - Peter Cordes

对于C++20，return std::bit_cast<std::int64_t>(a) == std::bit_cast<std::int64_t>(b);是memcpy / memcmp的类型安全版本，并且生成相同的优化汇编代码。 - bolov

那个推理非常错误。例如，x < 10 && x > 1 会优化成一个 sub / cmp / setbe (无符号下限或等于) 的范围检查 https://godbolt.org/z/G8h3eM 。GCC当然愿意考虑做C抽象机器不会做的工作，特别是如果能在不需要更多指令的情况下完成全部工作（包括从分支源代码到无分支汇编的if-conversion）。甚至有一个答案指出，如果你保证 Point 的对齐，GCC实际上会执行所需的优化。 - Peter Cordes

Answer 1

如果你“修复”对齐方式，所有代码将产生相同的汇编语言输出（使用GCC）：

Translated text:

如果您“修复”对齐方式，则所有内容都将产生相同的汇编语言输出（使用GCC）：

struct alignas(std::int64_t) Point {
    std::int32_t x, y;
};

演示

需要注意的是，一些正确合法的操作（如类型游戏）可以使用memcpy进行，因此在使用该函数时进行特定优化（或更加激进）似乎是合理的。

- Jarod42

---

但是memcpy函数并不假定对齐方式......因此，优化后的equal函数也不假定Point类型是过度对齐的。 - dyp

那么，为什么 memcpy 版本不需要对齐？编译器通过 memcpy 将非对齐结构体复制到寄存器中，这是一种缺失的编译器优化，对齐操作是否起到了某种推动作用？ - Ben

这是一个有趣的观察，但我觉得它并没有回答“为什么？”——为什么这些有效、琐碎、等效的函数会产生不同的汇编代码？ - Drew Dormann

为什么这里对齐很重要？为什么编译器不能像OP手动优化一样做优化？ - Ayxan Haqverdili

“guaranteed alignment” 的意思是优化更加有利：使用单个 64 位加载时不会出现缓存行分裂的情况。这可能会使优化器更加努力，或将一种启发式方法提高到某个盈利门槛之上。但由于不知道具体是哪一种情况，这个答案只是一个有用的观察结果和解决方法，而非真正的答案。 - Peter Cordes

Answer 2

如果将此代码实现为单个64位比较，则可能会面临性能崖问题：

你会破坏存储器到加载器的转发。

如果在结构体中的32位数字是通过单独的存储指令写入内存，然后使用64位加载指令快速加载回来（在存储命中L1缓存之前），则执行结果会陷入停顿，直到这些存储指令提交到全局可见的高速缓存一致性L1缓存。如果这些加载指令是匹配前面32位存储的32位加载指令，那么现代CPU将避免存储-加载停顿，通过将存储值转发到加载指令中，在存储达到缓存之前完成加载指令。这会违反顺序一致性（如果多个CPU访问内存，一个CPU看到自己的存储与其他CPU不同），但大多数现代CPU体系结构（甚至x86）都允许这种转发。转发还可以允许更多的代码被完全推测性地执行，因为如果必须回滚执行，没有其他CPU能够看到用于在该CPU上使用已加载值的代码的存储器以便推测性地执行。

如果你想要使用64位操作而又不想受到性能崖的影响，你可能需要确保该结构体也总是作为单个64位数字写入。

- EOF

---

为什么对齐方式会影响那个变量？ - dyp

我的意思是：如果已经给出了额外的对齐，为什么还要进行优化呢？这是否会改变你的论点？我的意思是，即使没有对齐，它也可能跨越缓存行，但它是否会影响存储->加载转发呢？ - dyp

你的执行将会停滞，直到存储提交到全局可见的缓存一致性L1$。但事实并非如此。有证据表明，在现代x86 CPU上，存储转发阻塞不必等待提交，只需对存储缓冲区进行更慢、更完整的扫描，可能还要与L1d中的数据合并。现代x86实现是否可以从多个先前的存储器进行存储转发？提供了更多关于这方面的细节。这也不是流水线停顿，乱序执行可能能够隐藏延迟。但是，是的，好的观点，通常应该避免。 - Peter Cordes

但是我记得，GCC的开发人员告诉我，GCC对存储转发停顿一无所知，并且不会积极尝试避免它们。（开发人员会这样做，因此并不排除调整一些启发式算法以获得更广泛的负载的成本效益。） - Peter Cordes

@Noah：请阅读我在Godbolt链接中的注释。2个依赖于负载的存储器都必须重新加载（而不是重新加载1个存储器+从L1d高速缓存合并数据），这会因为资源冲突而变慢：两个存储器都必须将数据写入存储器缓冲区。 - Peter Cordes

Answer 3

为什么编译器不能生成与memcpy版本相同的汇编代码？

从我的角度来看，编译器“可以”生成相同的汇编代码。

但是编译器实际上没有这样做。我不知道它为什么不这样做，因为这需要深入了解优化器的实现方式。但是，答案可能从“没有适用于此类转换的逻辑”到“规则未调整以假定一个输出比另一个更快”涉及所有目标CPU。

如果您使用的是Clang而不是GCC，则会注意到它为naiveEqual和naiveEqual1生成相同的输出，并且该汇编没有跳转。它与“优化”版本相同，只是使用两个32位指令代替一个64位指令。此外，像Jarod42的answer所示限制Point的对齐方式对优化器没有影响。

MSVC的行为类似于Clang，因为它不受对齐的影响，但在naiveEqual中不会消除跳转。

值得一提的是，编译器（我检查了GCC和Clang）为C++20默认比较生成的输出与naiveEqual基本相同。由于某种原因，GCC选择使用jne而不是je进行跳转。

这是否是缺少的编译器优化？

如果假设一个输出总是比另一个更快，那么这将是合理的结论。

- eerorika

---

使用-march=tigerlake选项的Clang编译器会使用SSE指令集。 - dyp

жңүи¶Јзҡ„жҳҜпјҡеҪ“жҲ‘з”Ёstd::tuple<std::int32_t, std::int32_t>жҲ–иҖ…std::pair<std::int32_t, std::int32_t>д»ЈжӣҝжҲ‘зҡ„Pointж—¶пјҢжҲ‘еҫ—еҲ°дәҶзӣёеҗҢзҡ„иЎҢдёәвҖҰвҖҰдҪҶжҳҜдҪҝз”Ёstd::array<std::int32_t, 2>еҸӘйңҖиҰҒдёҖж¬ЎжҜ”иҫғпјҢе°Ҫз®ЎиҝҷдёүиҖ…пјҲйҖҡеёёжғ…еҶөдёӢпјҢжҲ‘жңҹжңӣеҰӮжӯӨпјҒпјүеңЁеҶ…еӯҳдёӯеҚ жҚ®зӣёеҗҢзҡ„дҪҚ并且具жңүзӣёеҗҢзҡ„еҜ№йҪҗж–№ејҸгҖӮ - Ben

@Ben：gcc 进行数组优化，但是 clang 不会... - dyp

@supercat：就像我在那个帖子中评论的那样，那是不正确的。C结构体是全有或全无的，不像相对于指针的单独索引。访问a.x保证了a.y是可访问的。 - Peter Cordes

@supercat：我知道你对严格别名或有符号溢出等问题的立场/观点，但我不明白它如何适用于这里。你认为一个struct Point＆引用应该指向一个只有一半存在的对象，即扩展到未映射页面吗？（还是你还在谈论数据竞争？）那个未映射页面的参数对于struct Point *指针来说有些道理（尽管这不是C实际工作的方式），但调用者必须有一个指向部分存在的结构体的指针，并执行foo（*p），看起来像整个东西。 - Peter Cordes