wlh*_*wai 5 c++ comparison performance micro-optimization branch-prediction
struct Obj {
int x;
int y;
int z;
};
int Compare(Obj* a, Obj* b) {
if (a->x > b->x) return 1;
else if (a->x < b->x) return -1;
if (a->y > b->y) return 1;
else if (a->y < b->y) return -1;
if (a->z > b->z) return 1;
else if (a->z < b->z) return -1;
return 0;
}
如上面的代码所示，最多有3个条件分支来获取比较结果。比较函数将由某种函数调用。如何优化代码来杀死条件分支，从而提高比较函数的性能？
--- 更新 --- 由于调用者 func 是快速排序的改进版本，它需要更大、更少和相等的结果。所以比较函数应该用-1、1、0来区分三个结果。
C++ 不是汇编语言，如果编译器愿意，它可以将当前函数编译为无分支 asm 。（取消引用结构体指针来加载一个成员意味着整个结构体对象都存在，因此即使 C++ 抽象机不会触及 y 或 z 成员，也可以推测性地读取而不会出现错误。）您最关心什么架构？
您是否尝试过使用配置文件引导优化进行编译，以便编译器可以看到分支是不可预测的？这可能会导致它执行 if-convert 为if()无分支cmov或其他任何操作，具体取决于目标 ISA。（用rand() & 0x7或 生成随机数据，因此对象具有相等的 x 和相等的 y 并且实际上达到这种情况并不罕见z。）
可以使用 SIMD 查找第一个不匹配的元素，然后返回该元素的差异。例如，x86 SIMD 有一个movemask操作可以将向量比较结果转换为整数位掩码，我们可以将其与位扫描指令一起使用来查找第一个或最后一个设置位。
（这取决于是否能够安全地从 12 字节结构中读取 16 个字节，假设是 x86。只要您的数组不以页面末尾的最后一个元素结尾（下一页），就会出现这种情况未映射。 在 x86 和 x64 上读取同一页内缓冲区末尾是否安全？通常是的，并且广泛用于 strlen 和类似函数的高效实现。）
（ARM NEON 没有方便的 movemask，因此对于 ARM / AArch64，如果 SIMD 完全获胜，您可能最好在 SIMD 向量内对数据进行洗牌以得出结果。它可能与 ARM 的谓词比较不同指令，或者使用 AArch64 更有限的无分支条件指令，但仍然优于 x86 CMOV。）
SIMD 可以为我们提供良好的吞吐量，但与评论中 @Scheff 的无分支算术版本相比，延迟可能很差，特别是在像现代 x86 这样的宽管道上，它可以并行执行大量独立工作（例如将单独的比较结果转换为布尔整数）。在 QSort 中，高延迟可能并不理想，因为您预计分支错误预测并不罕见；重叠独立比较与无序执行仅在正确预测分支时才有效。
要从两个int值获得 + / 0 / - 结果，可以转换为 int64_t 并减去。这避免了有符号溢出的可能性，并且在 64 位 ISA 上非常高效。（或者，如果它可以内联，理想情况下可以编译为 32 位有符号比较，而不是实际的减法。32 位减法可能有符号溢出，即 UB，并且会在包装时丢失结果）。如果您不需要标准化为 +1 / 0 / -1，请这样做。
我在带有数组的联合中使用了匿名结构来扩展@Scheff 方便的基准测试框架（带有错误修复），而无需更改从a->x到 的所有内容a->vals.x。
#include <stdint.h>
#include <immintrin.h>
union Obj {
struct { // extension: anonymous struct
int x;
int y;
int z;
};
int elems[3];
};
// a better check would be on value ranges; sizeof can include padding
static_assert( sizeof(int64_t) > sizeof(int), "we need int smaller than int64_t");
int64_t compare_x86(const Obj *a, const Obj *b)
{
__m128i va = _mm_loadu_si128((const __m128i*)a); // assume over-read is safe, last array object isn't at the end of a page.
__m128i vb = _mm_loadu_si128((const __m128i*)b);
__m128i veq = _mm_cmpeq_epi32(va,vb);
unsigned eqmsk = _mm_movemask_ps(_mm_castsi128_ps(veq));
eqmsk |= 1<<2; // set elems[2]'s bit so we'll return that (non)diff if they're all equal
unsigned firstdiff = __builtin_ctz(eqmsk); // GNU C extension: count trailing zeros
// sign-extend to 64-bit first so overflow is impossible, giving a +, 0, or - result
return a->elems[firstdiff] - (int64_t)b->elems[firstdiff];
}
在适用于 x86-64 的GCC9.3 的Godbolt 上-O3 -march=skylake -fno-tree-vectorize，对于非内联情况，它编译为以下 asm：
compare_x86(Obj const*rdi, Obj const*rsi):
vmovdqu xmm1, XMMWORD PTR [rsi]
vpcmpeqd xmm0, xmm1, XMMWORD PTR [rdi]
vmovmskps edx, xmm0 # edx = bitmask of the vector compare result
or edx, 4
tzcnt edx, edx # rdx = index of lowest set bit
mov edx, edx # stupid compiler, already zero-extended to 64-bit
movsx rax, DWORD PTR [rdi+rdx*4] # 32->64 sign extending load
movsx rdx, DWORD PTR [rsi+rdx*4]
sub rax, rdx # return value in RAX
ret
延迟关键路径经过 SIMD 加载 + 比较，通过 movemask 返回整数or（1 个周期）、tzcnt/bsf（Intel 上的 3 个周期），然后是负载的另一个 L1d 加载使用延迟movsx（5 个周期）。（数字来自https://agner.org/optimize/ https://uops.info/。另请参阅https://stackoverflow.com/tags/x86/info）。标量加载地址直到 tzcnt 之后才知道，因此这里的 ILP 很少。现代 x86 每个时钟可以执行 2 次加载，因此我们正在利用这一点。不过，它可以在独立比较中很好地重叠，并且总 uop 计数较低，因此前端带宽的瓶颈并不算太糟糕。
未对齐的 SIMD 负载不会对 Intel CPU 产生任何影响，除非它们跨越高速缓存行边界。那么延迟会额外增加 10 个周期左右。或者更糟糕的是，如果它们跨越 4k 边界，尤其是在 Skylake 使页面分割变得更便宜之前的英特尔上。对于随机 4 字节对齐的对象地址，16 个起始位置中有 3 个会导致缓存行拆分加载（对于 64B 缓存行）。这进一步增加了从输入地址准备好到比较结果准备好的平均延迟，并且不能与任何工作重叠。
如果没有-march=skylakeGCC，则使用单独的movdqu未对齐加载，rep bsf这与tzcnt. 没有 BMI1 的 CPU 会将其解码为 plain bsf。（它们仅在输入为零时有所不同；我们确保这种情况不会发生。 bsf在 AMD 上速度很慢，与tzcnt在 Intel 上的速度相同。）
在 Godbolt 上使用 @Scheff 的基准（计算结果），当您禁用自动矢量化时，这比普通标量“算术”版本要快一些。（GCC 可以自动计算算术版本。）运行之间的计时结果不一致，因为测试用例太小，并且运行编译器资源管理器的 AWS 服务器可能具有不同的 CPU 频率，尽管它们都是 Skylake-avx512。但在一次运行中，在这个和算术之间交替，这样的结果是典型的：
compare_x86() 5. try: 28 mus (<: 3843, >: 3775)
compareArithm() 5. try: 59 mus (<: 4992, >: 5007)
compare_x86() 6. try: 39 mus (<: 3843, >: 3775)
compareArithm() 6. try: 64 mus (<: 4992, >: 5007)
compare_x86() 7. try: 27 mus (<: 3843, >: 3775)
compareArithm() 7. try: 64 mus (<: 4992, >: 5007)
但请记住，这只是将和返回值相加，因此是吞吐量限制，而不是延迟限制<0。>0新的比较可以开始，而对先前的比较结果没有任何数据依赖性或控制依赖性。
嗯，我可以用来pmovmskb获取每个字节的高位，而不是每个双字的ps版本，但是 C 使得在int数组中使用字节偏移量而不是元素偏移量变得不方便。在 asm 中，您需要 tzcnt 或 BSF，然后movsx rax, [rdi + rdx]. pcmpeqd这可能会节省 SIMD-integer和 SIMD-FP之间的旁路延迟中的一个延迟周期movmskps。但要从编译器中获取该值，您可能必须先将char*指针转换为 to ，然后再返回到int*.
我一开始想使用_mm_cmpgt_epi32(va,vb)0 / -1 的向量比较有符号大于的结果，但后来我意识到索引原始结构就像将正确的元素或其中的位映射到 -1 一样简单/+1 整数。
如果您想对全相等的情况进行特殊处理，您可以设置位#3 ( |= 1<<3)，然后在这种罕见的情况下进行分支，但仍然无分支地执行其余操作。
eqmsk |= 1<<3; // set the 4th bit so there's a non-zero bit to find
unsigned firstdiff = __builtin_ctz(eqmsk);
if (firstdiff >= 3) // handle this rare(?) case with a branch
return 0;
... something with (a < b) * 2 - 1
如果 s 很少x相等，也许可以考虑
if (a->x != b->x)
return a->x - (int_fast64_t)b->x;
else {
8-byte branchless SIMD?
or maybe just 2 element branchless scalar
}
我不知道是否值得为另外 2 个元素执行 SIMD。可能不会。
或者也许考虑对 x 和 y 进行无分支，并在y组件上进行分支等于跳过标量z？如果您的对象在 的大部分范围内都是随机的int，那么您很少会发现两个仅在最后一个分量上有所不同的对象。
我认为好的排序算法通过避免冗余比较来减少比较的方式可能会在结果模式中产生更多的熵，并且可能还会增加与最终排序顺序中彼此“接近”的元素进行的比较量。因此，如果有许多元素具有相等的 x，QSort 可能会进行更多的比较，这些比较确实需要检查 y 元素。
这是三向比较的通用模拟：
#include <tuple>
namespace util {
template <typename T>
int compare(const T& lhs, const T& rhs)
{
if (lhs == rhs) {
return 0;
} else if (lhs < rhs) {
return -1;
} else {
return 1;
}
}
namespace detail {
template <typename Tuple>
int compare_tuples(const Tuple&, const Tuple&, std::index_sequence<>)
{
return 0;
}
template <typename Tuple, std::size_t I, std::size_t... Is>
int compare_tuples(const Tuple& lhs, const Tuple& rhs, std::index_sequence<I, Is...>)
{
if (auto cmp = compare(std::get<I>(lhs), std::get<I>(rhs))) {
return cmp;
} else {
return compare_tuples(lhs, rhs, std::index_sequence<Is...>{});
}
}
}
template <typename Tuple>
int compare_tuples(const Tuple& lhs, const Tuple& rhs)
{
return detail::compare_tuples(
lhs, rhs, std::make_index_sequence<std::tuple_size_v<Tuple>>{}
);
}
}
std::tie然后您可以通过使用来形成成员元组来使用它：
struct Object {
int x, y, z;
};
int compare(const Object& lhs, const Object& rhs)
{
return util::compare_tuples(
std::tie(lhs.x, lhs.y, lhs.z),
std::tie(rhs.x, rhs.y, rhs.z)
);
}
（现场演示）
该compare函数最终由 GCC 对此进行了优化：
compare(Object const&, Object const&):
mov eax, DWORD PTR [rsi]
cmp DWORD PTR [rdi], eax
je .L11
.L2:
setge al
movzx eax, al
lea eax, [rax-1+rax]
ret
.L11:
mov eax, DWORD PTR [rsi+4]
cmp DWORD PTR [rdi+4], eax
jne .L2
mov edx, DWORD PTR [rsi+8]
xor eax, eax
cmp DWORD PTR [rdi+8], edx
jne .L2
ret
和叮当：
compare(Object const&, Object const&): # @compare(Object const&, Object const&)
mov ecx, dword ptr [rdi]
xor eax, eax
cmp ecx, dword ptr [rsi]
setge cl
jne .LBB0_1
mov ecx, dword ptr [rdi + 4]
xor eax, eax
cmp ecx, dword ptr [rsi + 4]
setge cl
jne .LBB0_1
mov eax, dword ptr [rdi + 8]
xor ecx, ecx
xor edx, edx
cmp eax, dword ptr [rsi + 8]
setge dl
lea eax, [rdx + rdx - 1]
cmove eax, ecx
ret
从C++20开始，这个问题可以通过默认的spaceship操作符轻松解决：
#include <compare>
struct Obj {
int x;
int y;
int z;
constexpr auto operator<=>(const Obj&) const = default;
};
int to_int(std::partial_ordering cmp) noexcept
{
if (cmp == 0) {
return 0;
} else if (cmp < 0) {
return -1;
} else {
return 1;
}
}
int Compare(Obj* a, Obj* b)
{
return to_int(*a <=> *b);
}