c++ - 在条件下更新变量的最快方法是什么？

Question

我有一个指针，ptr和条件，cond .我需要最快的方法来重置 ptr如果 cond是 true ，或保留 ptr如果 cond 不变是 false .当前的实现很简单:

void reset_if_true(void*& ptr, bool cond)
{
    if (cond)
        ptr = nullptr;
}

我知道上面的代码性能很好，我不能指望优化它的主要性能提升。然而，这段代码每秒被调用数百万次，并且保存的每一小纳秒都是相关的。

我正在考虑摆脱分支的东西，例如:

void* p[] = { ptr, nullptr };
ptr = p[cond];

但我不确定这是最好的方法。

Answer 1

void reset_if_true(void*& ptr, bool cond)
{
    if (cond)
        ptr = nullptr;
}

在大多数情况下，朴素的解决方案无疑是最快的。尽管它有一个分支，在现代流水线处理器上可能会很慢，但只有在分支预测错误时才会变慢。由于现在分支预测器非常好，除非 cond 的值是极其不可预测的，很可能一个简单的条件分支是编写代码的最快方式。

如果不是，一个好的编译器应该知道这一点，并且能够将代码优化为更好的东西，考虑到目标架构。转到gnasher729's point : 只需以简单的方式编写代码，然后将优化交给优化器。

虽然这通常是一个很好的建议，但有时它太过分了。如果你真的关心这段代码的速度，你需要检查一下编译器实际上在做什么。检查它正在生成的目标代码，并确保它是合理的并且函数的代码正在被内联。

这样的检查可能会很有启发性。例如，让我们考虑 x86-64，在分支预测失败的情况下，分支可能会非常昂贵(这是一个有趣的问题，因此我们假设 cond 完全不可预测)。几乎所有的编译器都会为简单的实现生成以下内容:

reset_if_true(void*&, bool):
    test   sil, sil              ; test 'cond'
    je     CondIsFalse
    mov    QWORD PTR [rdi], 0    ; set 'ptr' to nullptr, and fall through
  CondIsFalse:
    ret

这与您想象的一样紧凑。但是如果你把分支预测器放在一个病态的情况下，它最终可能比使用条件移动要慢:

reset_if_true(void*&, bool):
    xor    eax, eax              ; pre-zero the register RAX
    test   sil, sil              ; test 'cond'
    cmove  rax, QWORD PTR [rdi]  ; if 'cond' is false, set the register RAX to 'ptr'
    mov    QWORD PTR [rdi], rax  ; set 'ptr' to the value in the register RAX
    ret                          ;  (which is either 'ptr' or 0)

条件移动具有相对较高的延迟，因此它们比良好预测的分支慢得多，但它们可能比完全不可预测的分支快。您希望编译器在面向 x86 体系结构时知道这一点，但它(至少在这个简单示例中)不了解 cond的可预测性。它假设简单的情况，分支预测会站在你这边，并生成代码 A 而不是代码 B。

如果您决定要鼓励编译器由于不可预测的情况而生成无分支代码，您可以尝试以下操作:

void reset_if_true_alt(void*& ptr, bool cond)
{
    ptr = (cond) ? nullptr : ptr;
}

这成功地说服现代版本的 Clang 生成无分支代码 B，但在 GCC 和 MSVC 中是完全悲观的。如果您没有检查生成的程序集，您就不会知道这一点。如果要强制 GCC 和 MSVC 生成无分支代码，则必须更加努力。例如，您可以使用问题中发布的变体:

void reset_if_true(void*& ptr, bool cond)
{
    void* p[] = { ptr, nullptr };
    ptr = p[cond];
}

当以 x86 为目标时，所有编译器都为此生成无分支代码，但它并不是特别漂亮的代码。事实上，它们都不会产生条件移动。相反，您可以多次访问内存以构建数组:

reset_if_true_alt(void*&, bool):
    mov     rax, QWORD PTR [rdi]
    movzx   esi, sil
    mov     QWORD PTR [rsp-16], 0
    mov     QWORD PTR [rsp-24], rax
    mov     rax, QWORD PTR [rsp-24+rsi*8]
    mov     QWORD PTR [rdi], rax
    ret

丑陋而且可能非常低效。我预测即使在分支预测错误的情况下，它也会为条件跳转版本提供资金。当然，您必须对其进行基准测试才能确定，但​​这可能不是一个好的选择。

如果您仍然不顾一切地消除 MSVC 或 GCC 上的分支，您将不得不做一些更丑陋的事情，包括重新解释指针位并处理它们。就像是:

void reset_if_true_alt(void*& ptr, bool cond)
{
    std::uintptr_t p = reinterpret_cast<std::uintptr_t&>(ptr);
    p &= -(!cond);
    ptr = reinterpret_cast<void*>(p);
}

这将为您提供以下信息:

reset_if_true_alt(void*&, bool):
    xor   eax, eax
    test  sil, sil
    sete  al
    neg   eax
    cdqe
    and   QWORD PTR [rdi], rax
    ret

同样，这里我们有比简单分支更多的指令，但至少它们是相对低延迟的指令。现实数据的基准将告诉您权衡是否值得。如果您要实际 checkin 这样的代码，请给出您需要添加注释的理由。

一旦我进入了令人费解的兔子洞，我就能够强制 MSVC 和 GCC 使用条件移动指令。显然他们没有做这个优化，因为我们正在处理一个指针:

void reset_if_true_alt(void*& ptr, bool cond)
{
    std::uintptr_t p = reinterpret_cast<std::uintptr_t&>(ptr);
    ptr = reinterpret_cast<void*>(cond ? 0 : p);
}

reset_if_true_alt(void*&, bool):
    mov    rax, QWORD PTR [rdi]
    xor    edx, edx
    test   sil, sil
    cmovne rax, rdx
    mov    QWORD PTR [rdi], rax
    ret

鉴于 CMOVNE 的延迟和相似数量的指令，我不确定这是否真的比以前的版本更快。您运行的基准测试会告诉您是否存在。

类似地，如果我们对条件进行位处理，我们可以节省一次内存访问:

void reset_if_true_alt(void*& ptr, bool cond)
{
   std::uintptr_t c = (cond ? 0 : -1);
   reinterpret_cast<std::uintptr_t&>(ptr) &= c;
}

reset_if_true_alt(void*&, bool):
     xor    esi, 1
     movzx  esi, sil
     neg    rsi
     and    QWORD PTR [rdi], rsi
     ret

(那是 GCC。MSVC 做了一些稍微不同的事情，更喜欢它的特征序列 neg 、 sbb 、 neg 和 dec 指令，但两者在道德上是等效的。Clang 将其转换为与我们相同的条件移动看到它在上面生成。)如果我们需要避免分支，这可能是最好的代码，考虑到它在所有经过测试的编译器上生成合理的输出，同时保留(某种程度的)源代码的可读性。