在条件上更新变量的最快方法是什么？

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的观点一致:只需以简单的方式编写代码并将优化留在优化器手中.

虽然这一般是一个很好的建议,但有时候它会走得太远.如果您真的关心此代码的速度,则需要检查并查看编译器实际使用它的内容.检查它正在生成的目标代码,并确保它是合理的并且函数的代码是内联的.

这样的检查可能非常有启发性.例如,让我们考虑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;
}

这成功地说服锵的现代版本生成网点代码B,但在GCC和MSVC完整pessimization.如果您还没有检查生成的程序集,那么您就不会知道.如果要强制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

同样,这里我们有比简单分支更多的指令,但至少它们是相对低延迟的指令.现实数据的基准将告诉您是否值得权衡.如果您要实际签到这样的代码,请告诉您放置评论所需的理由.

一旦我走下了那个笨拙的兔子洞,我就能够迫使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指令,但两者在道德上是等价的.锵将其转换成我们看到它产生上述同样的条件移动).这可能是最好的代码然而,如果我们需要避免分支机构,考虑到它在所有测试的编译器生成健全的输出,同时保留在源代码中(一定程度上)的可读性.

Answer 2

这里最低悬的果实不是你想象的那样.正如在其他几个答案的讨论,reset_if_true将被编译成机器代码是一样快,您可以合理预期得到了它做什么.如果这还不够快,你需要开始考虑改变它的作用.我看到两个选项,一个很简单,一个不那么容易:

1. 更改调用约定:

   template <class T>
   inline T* reset_if_true(T* ptr, bool condition)
   {
       return condition ? nullptr : ptr;
   }
   

   然后更改调用者以读取类似的内容

   ptr_var = reset_if_true(ptr_var, expression);
   

   这样做会使得更有可能ptr_var在reset_if_true每秒调用数百万次的关键最内层循环期间生存在寄存器中,并且不会有任何与之关联的内存访问. ptr_var被迫离开内存是代码中最昂贵的东西,就像它现在一样; 甚至比潜在的错误预测分支更昂贵.(一个足够好的编译器可能会为你提供这种转换reset_if_true是无法实现的,但它并不总是可以这样做.)

2. 改变周围的算法,这样就reset_if_true不会再被调用数百万次.

   既然你没有告诉我们周围的算法是什么,我无法帮助你.但是,我可以告诉你,做一些涉及每秒数百万次检查条件的事情,可能表示一种具有二次时间复杂度或更差的算法,这总是意味着你至少应该考虑找到一个更好的算法.(可能没有成为一个更好的,唉.)

Answer 3

只要我们有sizeof(size_t) == sizeof(void*),nullptr用二进制表示为0,size_t用所有位(或者有std :: uintptr_t)表示,你可以这样做:

// typedef std::uintptr_t ptrint_t; // uncomment if you have it
typedef size_t ptrint_t; // comment out if you have std::uintptr_t

void reset_if_true(void*& ptr, bool cond)
{
    ((ptrint_t&)ptr) &= -ptrint_t( !cond );
}

但请注意,bool转换size_t为非常依赖于实现的时间,并且可能需要一个分支.

Answer 4

代码绝对简单.

通过内联函数(如果编译器没有单独内联它),你肯定会使事情变得更快.例如,内联可能意味着您设置为null的指针变量可能保留在寄存器中.

除此之外,这段代码非常简单,如果有任何技巧可以使它更快,编译器就会使用它们.