一位同事向我展示了一些我认为没有必要的代码,但果然是这样。我希望大多数编译器会将所有这三种相等测试尝试视为等效:
#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)
对于优化器来说,如果我检查连续的四个字节对的相等性,这与比较所有八个字节相同,这不是很明显吗?
尝试避免分别对两个部分进行布尔化,编译效率会更高一些(减少一条指令,并且不会错误地依赖 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 在通过 value 传递结构时都有相同的缺失优化(因此
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 没有帮助。
2024 年 10 月更新,使用 C++23:
operator==
与 = default
至少与幼稚的实现一样糟糕!我认为 operator==
对于内置类型的密集小型结构肯定会被优化为 memcmp
,但不是! https://godbolt.org/z/948n8vnWj
如果“修复”对齐方式,所有的都会给出相同的汇编语言输出(使用 GCC):
struct alignas(std::int64_t) Point {
std::int32_t x, y;
};
请注意,做某些事情(如类型双关)的一些正确/合法的方法是使用
memcpy
,因此在使用该函数时进行特定的优化(或更激进)似乎是合乎逻辑的。
将其实现为单个 64 位比较时,您可能会遇到性能悬崖:
您中断存储以加载转发。
如果结构中的 32 位数字通过单独的存储指令写入内存,然后使用 64 位加载指令快速从内存加载回(在存储命中 L1$ 之前),则执行将停止,直到存储提交到全局可见缓存一致 L1$。如果加载是与之前的 32 位存储相匹配的 32 位加载,现代 CPU 将通过在存储到达缓存之前将存储的值转发到加载指令来避免存储加载停顿。如果多个 CPU 访问内存(一个 CPU 以与其他 CPU 不同的顺序查看自己的存储),这会违反顺序一致性,但大多数现代 CPU 架构(甚至 x86)都允许这样做。转发还允许完全推测性地执行更多代码,因为如果必须回滚执行,则其他 CPU 无法看到使用该 CPU 上的加载值进行推测性执行的代码的存储。
如果您希望它使用 64 位操作并且您不希望出现这种性能悬崖,您可能需要确保该结构也始终以单个 64 位数字的形式写入。
为什么编译器无法生成[与memcpy版本相同的程序集]?
编译器“可以”是指它被允许这样做。
编译器根本不这样做。为什么它不超出我的知识范围,因为这需要深入了解优化器的实现方式。但是,答案可能范围从“没有逻辑涵盖这种转换”到“规则未调整为假设所有目标 CPU 上的一个输出比另一个输出更快”。
如果您使用 Clang 而不是 GCC,您会注意到它为
naiveEqual
和 naiveEqual1
生成相同的输出,并且该程序集没有跳转。除了使用两条 32 位指令代替一条 64 位指令之外,它与“优化”版本相同。此外,如 Jarod42 的 answer中所示限制
Point
的对齐对优化器没有影响。
MSVC 的行为类似于 Clang,因为它不受对齐的影响,但不同之处在于它不会消除
naiveEqual
中的跳转。
就其价值而言,编译器(我检查了 GCC 和 Clang)为 C++20 默认比较生成的输出与
naiveEqual
的输出基本相同。无论出于何种原因,GCC 选择使用 jne
而不是 je
进行跳转。
这是缺少编译器优化吗
假设在目标 CPU 上一个总是比另一个更快,这是公平的结论。