if(A | B) 总是比 if(A || B) 更快吗？

Question

我正在阅读Fedor Pikus的这本书，他有一些非常非常有趣的例子，对我来说是一个惊喜。
特别是这个基准测试，其中唯一的区别在于，在其中一个中我们在if中使用||，而在另一个中我们使用|。

void BM_misspredict(benchmark::State& state)
{

    std::srand(1);
    const unsigned int N = 10000;;
    std::vector<unsigned long> v1(N), v2(N);
    std::vector<int> c1(N), c2(N);

    for (int i = 0; i < N; ++i) 
    {
        v1[i] = rand();
        v2[i] = rand();
        c1[i] = rand() & 0x1;
        c2[i] = !c1[i];
    }

    unsigned long* p1 = v1.data();
    unsigned long* p2 = v2.data();
    int* b1 = c1.data();
    int* b2 = c2.data();

    for (auto _ : state)
    {
        unsigned long a1 = 0, a2 = 0;
        for (size_t i = 0; i < N; ++i) 
        {
            if (b1[i] || b2[i])  // Only difference
            {
                a1 += p1[i];
            }
            else 
            {
                a2 *= p2[i];
            }
        }
        benchmark::DoNotOptimize(a1);
        benchmark::DoNotOptimize(a2);
        benchmark::ClobberMemory();

    }
    state.SetItemsProcessed(state.iterations());
}

void BM_predict(benchmark::State& state)
{

    std::srand(1);
    const unsigned int N = 10000;;
    std::vector<unsigned long> v1(N), v2(N);
    std::vector<int> c1(N), c2(N);

    for (int i = 0; i < N; ++i)
    {
        v1[i] = rand();
        v2[i] = rand();
        c1[i] = rand() & 0x1;
        c2[i] = !c1[i];
    }

    unsigned long* p1 = v1.data();
    unsigned long* p2 = v2.data();
    int* b1 = c1.data();
    int* b2 = c2.data();

    for (auto _ : state)
    {
        unsigned long a1 = 0, a2 = 0;
        for (size_t i = 0; i < N; ++i)
        {
            if (b1[i] | b2[i]) // Only difference
            {
                a1 += p1[i];
            }
            else
            {
                a2 *= p2[i];
            }
        }
        benchmark::DoNotOptimize(a1);
        benchmark::DoNotOptimize(a2);
        benchmark::ClobberMemory();

    }
    state.SetItemsProcessed(state.iterations());
}

我不会详细解释书中为什么后者更快，但是基本思路是硬件分支预测器在较慢的版本和 |（按位或）版本中有2次错判的机会。请参见下面的基准测试结果。

那么问题来了，为什么我们不总是在分支中使用 | 而不是 ||？

- Eduard Rostomyan

---

那么问题是为什么我们不总是在分支语句中使用 | 而是使用 || 呢？-- 可读性和维护。如果在期望使用 || 的地方使用了 |，那么它看起来就像一个 bug。现在你必须花费时间说服同事（甚至是你自己），使用 | 的“技巧”是有效的。 - PaulMcKenzie

C++ 遵循"as-if"规则。简单来说，如果编译器可以证明它不会改变可观察行为，那么它可以对你的代码进行任何转换。这导致一个更重要的认识：代码是行为的描述，而不是指令清单。编译器将接受你的代码，解释所描述的行为，并生成一组最优的指令（在你要求的优化程度和编译器的限制范围内）。 - user4581301

将 1 | DropTheBomb() 与 true || DropTheBomb() 进行比较... - user1196549

不只是“看起来像一个 bug”；如果右侧引用了不该有的指针，那么它就 是 一个 bug。这就是为什么编译器不能将 b1[i] || b2[i] 在这种情况下优化成一个 or 指令。虽然 int* b2 = c2.data() 已经在此函数内部的初始化部分中被引用过了，但证明这一点需要很多工作。(并且在其他情况下，可能会出现缓存未命中的情况。) - Peter Cordes

@HristoIliev提到的关于序列点的评论是指声称|和||是等效的（除了短路）；但这是不正确的，因为（例如）printA_then_returnZero() || printB_then_returnZero()必须总是打印AB，但是printA_then_returnZero() | printB_then_returnZero()可以打印AB或BA。 - psmears

Answer 1

if(A | B) 总是比 if(A || B) 快吗？

不，if(A | B) 并不总是比 if(A || B) 快。

想象一种情况，当 A 为真而且 B 表达式是一个非常昂贵的操作时。不执行这个操作可以节省开销。

那么问题就是为什么我们不总是在条件分支中使用 | 而不是 ||？

除了逻辑或更高效的情况外，效率并不是唯一的关注点。通常会有具备前提条件的操作，而左边操作的结果可能会影响到右边操作是否满足前提条件。在这种情况下，我们必须使用逻辑运算符。

if (b1[i])  // maybe this exists somewhere in the program
    b2 = nullptr;

if(b1[i] || b2[i]) // OK
if(b1[i]  | b2[i]) // NOT OK; indirection through null pointer

当优化器无法用位运算符替换逻辑运算符时，通常是由于存在这种可能性。在if(b1[i] || b2[i])这个例子中，只有当优化器可以证明b2在b1[i] != 0时有效才能进行这种替换。在您的示例中可能不存在这样的条件，但这并不意味着优化器能够轻松证明不存在这样的条件，有时甚至不可能。

---

此外，操作的顺序可能会产生依赖关系，例如如果一个操作数修改了另一个操作读取的值：

if(a || (a = b)) // OK
if(a  | (a = b)) // NOT OK; undefined behaviour

---

此外，有些类型可以转换为布尔型并因此成为||的有效操作数，但它们不是|的有效操作数：

if(ptr1 || ptr2) // OK
if(ptr1  | ptr2) // NOT OK; no bitwise or for pointers

---

简而言之，如果我们总是可以使用按位或操作符而不是逻辑运算符，则不需要使用逻辑运算符，并且它们可能不会存在于语言中。但这种替换并非总是可行，这就是为什么我们使用逻辑运算符的原因，也是优化器有时无法使用更快选项的原因。

- eerorika

---

一个稍微更好的例子可能是if(!ptr || *ptr)，因为它很适合原始问题，尤其是第二行if(ptr & *ptr)很难想到一个有意义的场景，而if(!ptr | *ptr)则可以立即理解。 - Mike Vine

if(!ptr | *ptr) 的意思是“如果指针为空或者它所指的值不为零，那么进入这个代码块。这是一个非常合理的条件。if(ptr & *ptr) 的意思是“如果指针值与它所指的值进行按位与操作后结果不为零，那么进入这个代码块。”这个条件非常奇怪，几乎没有意义。” - Mike Vine

@MikeVine 哦，我明白你的意思了。我已经修复了这个例子。 - eerorika

& 不能良好替代 &&；即使是非空指针，if((ptr != nullptr) & *ptr) 只检查 *ptr 的低位是否为非零。而逻辑运算符 OR 则不存在这个问题。 - Peter Cordes

是的，绝对没错；clang没有将问题中的代码优化为按位“或”指令的原因几乎肯定是C++抽象机器在b1[i]非零时不访问b2[i]。这可能越界了。它应该能够假设int *b2是非NULL的，因为它是从先前在此函数中编写的std::vector的.data()设置的，但这需要编译器通过大量复杂的分支和重新分配来跟踪内容。*ptr1 || *ptr2将完全作为相关示例。 - Peter Cordes

Answer 2

如果评估 A 很快，B 很慢，当短路发生时（A 返回 true），那么 if (A || B) 将避免慢路径，而 if (A | B) 不会。

如果评估 A 几乎总是给出相同的结果，则处理器的分支预测可能会使得 if (A || B) 的性能优于 if (A | B)，即使 B 很快。

正如其他人提到的，有些情况下短路是必须的：只有在已知 A 为假时才想要执行 B：

if (p == NULL || test(*p)) { ... }  // null pointer would crash on *p

if (should_skip() || try_update()) { ... }  // active use of side effects

- comingstorm

---

根据我的个人主观经验，在现实世界的场景中，条件大多是可预测的，而不是在每次迭代中随机50/50。这就是为什么分支预测是一个重要的事情。 - Falco

Answer 3

按位或是一种无分支算术运算符，对应于单个ALU指令。逻辑或被定义为暗示着快捷评估，这涉及到一个（昂贵的）条件分支。当操作数的评估具有副作用时，两者的效果可能会有所不同。

在两个布尔变量的情况下，聪明的编译器可能会将逻辑或评估为按位或，或使用条件移动，但谁知道呢...

- user1196549

---

对于“int”类型的变量，编译器也可以将“a || b”优化为“a | b”。但前提是它们直接可用，如已在寄存器中，而非从指针解除引用。GCC和clang会这样做（https://godbolt.org/z/nxeKT1roP），即使这意味着从可能会缓存未命中的全局变量中加载，但这总是安全的。（如果另一个线程正在写入全局变量，那么只有当LHS为0时其值才重要；这可能会引入对变量的不同步访问，但在实际CPU的汇编中安全，只要您不关心值。但在ISO C ++源中不是这样：这是未定义行为）。 - Peter Cordes

只要您不关心值，那在真正的CPU上使用汇编是安全的。（但说真的，在读敏感的内存映射寄存器时，这就是为什么ISO C/C++不特别适合裸机开发的原因之一。volatile可以帮助解决问题。有时候。） - TLW

Answer 4

所以问题是为什么我们不总是在分支中使用 | 而是使用 || 呢？

分支预测只与热点代码相关，并且取决于分支足够可预测才有意义。在大多数情况下，| 与 || 相比几乎没有性能优势。此外，将 A 和 B 视为合适类型的表达式（不一定是单个变量），关键的差异包括：

在 A || B 中，当 A 评估为0时才评估 B，但在 A | B 中，始终评估 B。有时条件避免评估 B 正是使用前者的原因。

在 A || B 中，在评估 A 和评估 B 之间存在一个序列点，但在 A | B 中不存在。即使您不关心短路，您可能也会关心顺序，甚至在相对简单的示例中也是如此。例如，给定整数 x，x-- || x-- 具有明确定义的行为，但 x-- | x-- 具有未定义的行为。

当在条件语境中使用时，A || B 的意图对其他人来说很清晰，但用 A | B 替换的原因则不太明确。代码清晰度非常重要。总之，如果编译器能够确定这样做是安全的（而在大多数情况下，它比人类更可靠地进行判断），那么它可以自由地将其中一个表达式编译为另一个表达式。

如果不能确定 A 和 B 都具有内置类型——例如在模板中——那么就必须考虑 | 和 || 中的一个或两个已被重载的可能性。在这种情况下，可以合理地假设 || 仍然会执行对于分支控制有意义的操作，但假设 | 会执行等效或适合的操作则不太安全。

作为额外的小事情，| 的优先级不同于 ||。如果你依赖于优先级而不是用括号进行分组，这可能会影响到你。如果你考虑修改现有代码将 || 表达式更改为 | 表达式，那么你需要注意这一点。例如，A && B || C && D 分组为 (A && B) || (C && D)，但是 A && B | C && D 分组为 (A && (B | C)) && D。

- John Bollinger

Answer 5

即使 a 和 b 是自动持续时间的布尔标记，也并不意味着诸如 a||b 的表达式将通过检查一个标记的状态，然后如果必要的话再检查另一个标记的状态来进行评估。如果一段代码执行：

x = y+z;
flag1 = (x==0);
... code that uses flag1

编译器可以将其替换为：

x = y+z;
if (processor's Z flag was set)
{
... copy of that uses flag1, but where flag is replaced with constant 1
}
else
{
... copy of that uses flag1, but where flag is replaced with constant 0
}

尽管没有必要这样做，但编译器可能会根据程序员选择写(flag1 || flag2)还是(flag1 | flag2)来决定是否执行这种替换，许多因素可能导致上述替换比原始代码运行得更快或更慢。

- supercat

Answer 6

代码可读性、短路运算以及不能保证Ord始终优于||操作符。

计算机系统比预期的要复杂，即使它们是人造的。

有一次，在IBM上，一个更复杂条件的for循环跑得更快。这是因为CPU没有冷却，因此指令执行得更快，这可能是一个原因。我的意思是，应该注重改进代码的其他方面，而不是去解决小问题，这些问题取决于CPU和布尔值评估（编译器优化）。

- Tony Tannous

Answer 7

表达式A | B在循环中可能比编译器优化为两个向量的按位或更快。另一种情况是当编译器想通过使用位掩码来结合两个操作数来优化掉分支时，|可能会略微更加优化。如果右侧操作数可能具有可见的副作用，则编译器必须插入一个分支以保证正确的短路。

在我能想到的其他情况下，A || B将与更快或者一样快，包括几乎所有我能想到的只比较单个操作数对而不是向量的情况。然而，这些几乎从不关键于性能。

- Davislor

---

它不能使用||表达式来完成这个操作。一般情况下并非如此。如果编译器可以证明行为不变，那么它可以自由地执行优化。相关的“as-if规则”已经在注释中提到。 - Max Barraclough

@MaxBarraclough 是的，同意：有时静态编译器可以静态地判断 || 表达式的 RHS 没有副作用，有时则不能。如果这句话让人困惑，我会重新措辞。 - Davislor

Answer 8

在列表中添加：

考虑到 A 和 B 是完全不可预测的情况，但通常情况下 A||B 为真（即当 A 错误时，B 通常为真，反之亦然）。 在这种情况下，A||B 可能会导致大量错误预测，但 A|B 是可预测的，并且很可能更快。

- tommsch

---

这就是问题所在。问题在于询问是否总是如此，如果不是，为什么不能像编译A|B一样编译A||B。 - Peter Cordes

Answer 9

所以问题是为什么我们不总是在分支中使用 | 而不是 ||？

在我看来，有三个原因，但这可能只是我的想法。

首先也是最重要的：所有代码都倾向于被阅读的次数比编写的次数多。因此，在这个例子中，你有一个由值为零或1的int数组。代码真正意图做什么对读者来说是隐藏的。原始作者可能清楚地知道应该做什么，但是多年后，在添加了大量代码行之后，任何人都可能猜测。在我的世界里，使用显示预期比较的内容，它可以是位比较或逻辑比较。它不应该同时存在。

其次：性能提升真的很重要吗？这个例子基本上什么也没做，可以编写得更有效率。不是吗？那就不要首先创建数组，现在代码所做的只是检查rand函数的质量。优化是一个例子，更好地分析问题可能会带来更大的收益。

第三点：不同的编译器或处理器可能会改变相对速度。现在，你所做的是应用你对当前编译器和处理器内部的知识。下一个版本的编译器和处理器可能会完全颠倒这个问题。你真的无法知道。我们都知道，唯一知道优化是否真正更快的方法是通过测试，而这个非常具体的例子已经做到了。

因此，如果由于某种原因，从代码中获取最后一点效率非常重要，我会将选择标记为“hack”。我可能会包含一个带有类似“DO_PERFORMANCE_HACKS”的宏，并且有两个版本的代码，一个带有|，另一个带有||，并注释意图。通过更改宏，下一个读者可以看到hack是什么以及在哪里，未来可能会选择不编译它们。

- ghellquist