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 次错误预测的机会。（按位或）版本。请参阅下面的基准测试结果。

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

Answer 1

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

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

考虑一种情况，其中A为 true 并且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

此外，有些类型可转换为 bool，因此是 的有效操作数||，但不是 的有效运算符|：

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

TL;DR 如果我们总是可以使用按位或来代替逻辑运算符，那么就不需要逻辑运算符，并且它们可能不会出现在该语言中。但这种替换并不总是可能的，这就是我们使用逻辑运算符的原因，也是优化器有时无法使用更快选项的原因。

Answer 2

如果评估A快，B则慢，并且当短路发生时（A返回true），则将避免不会的if (A || B)慢路径。if (A | B)

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

正如其他人提到的，在某些情况下，短路是强制性的：您只想执行BifA已知来评估 false：

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

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

Answer 3

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

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

Answer 4

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

• 分支预测仅与相当热门的代码片段相关，并且它取决于分支的可预测性是否足够重要。 在大多数地方，|与 相比几乎没有性能优势||。

此外，将A和B作为合适类型的表达式（不一定是单个变量），关键的相关差异包括：

• 在A || B,中，B仅当A计算结果为 0 时才计算，但在A | B, 中，B始终计算。 有条件地避免评估B有时正是使用前者的目的。

• 在 的求值和 的求值A || B之间有一个序列点，但在 中没有序列点。 即使您不关心短路，您也可能会关心排序，即使在相对简单的示例中也是如此。例如，给定一个整数，具有明确定义的行为，但具有未定义的行为。ABA | Bxx-- || 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。

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) 的选择来决定是否执行此类替换，并且许多因素可能会导致上述替换比原始代码运行得更快或更慢。