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

Is if(A | B) always faster than if(A || B)?

我正在阅读 Fedor Pikus 的 this book,他有一些非常非常有趣的例子,这对我来说是一个惊喜。
特别是这个基准引起了我的注意,唯一的区别是在其中一个中我们使用 ||在 if 和 another 中我们使用 |.

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());
}

我不会详述书中解释的为什么后者更快的所有细节,但想法是硬件分支预测器在较慢的版本和 | (按位或)版本。请参阅下面的基准测试结果。

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

代码可读性,short-circuiting并且不能保证运行Ord 将始终优于|| ope运行d。 计算机系统比预期的要复杂,尽管它们 man-made.

曾经有一种情况,条件更复杂的 for 循环 运行 在 IBM 上更快。 CPU 不酷,因此指令执行得更快,这是一个可能的原因。我想说的是,关注其他领域来改进代码,而不是与 small-cases 作斗争,这将根据 CPU 和布尔评估(编译器优化)而有所不同。

Bitwise-or是对应单条ALU指令的无分支算术运算符。 Logical-or 被定义为暗示快捷评估,它涉及一个(昂贵的)条件分支。当操作数的计算有副作用时,两者的效果可能不同。

在两个布尔变量的情况下,智能编译器可能会将 logical-or 评估为 bitwise-or,或者使用条件移动,但谁知道呢...

Is if(A | B) always faster than if(A || B)?

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

考虑 A 为真且 B 表达式是非常昂贵的操作的情况。不做手术可以节省这笔费用。

So the question is why don't we always use | instead of || in branches?

除了逻辑或更高效的情况外,效率并不是唯一的问题。经常有操作有pre-conditions,也有左手操作的结果表示右手操作是否满足pre-condition的情况。在这种情况下,我们必须使用逻辑运算符。

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 如果我们总是可以使用按位或代替逻辑运算符,那么就不需要逻辑运算符,而且它们可能不会出现在语言中。但是这种替换并不总是可行的,这就是我们使用逻辑运算符的原因,也是优化器有时不能使用更快选项的原因。

如果判断A快,B慢,短路时(A returns true),那么 if (A || B) 将避开 if (A | B) 不会的慢速路径。

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

正如其他人所提到的,有些情况下短路是强制性的:如果已知 A 评估为假,您只想执行 B

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

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

添加到列表中:

假设 AB 是完全不可预测的,但通常 A||B 是正确的(即当 A 错误时,通常 B 为真,反之亦然)。 在这种情况下 A||B 可能会导致很多错误预测,但 A|B 是可预测的并且很可能更快。

So the question is why don't we always use | instead of || in branches?

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

此外,将AB作为合适类型的表达式(不一定是单一变量),关键的相关差异包括:

  • A || B 中,仅当 A 的计算结果为 0 时才计算 B,但在 A | B 中,B 总是评估。 有条件地避免评估 B 有时恰恰是使用前者的要点

  • A || BA的求值和B的求值之间有一个序列点,但A | B中没有. 即使您不关心 short-circuiting,您也可能关心排序,即使在相对简单的示例中也是如此。例如,给定一个整数 xx-- || x-- 具有 well-defined 行为,但 x-- | x-- 具有未定义的行为。

  • 当在条件上下文中使用时,A || B 的意图对其他人来说很清楚,但是替代 A | B 的原因就不那么明显了.代码清晰度非常重要。毕竟,如果编译器可以看到这样做是安全的(并且在大多数情况下,它比人类做出决定更可靠),那么它就可以自由地编译其中一个表达式,就好像它是另一个表达式一样.

  • 如果您不能确定 AB 都具有 built-in 类型 -- 例如在模板中 -- 您必须考虑 ||| 之一或两者已过载的可能性 。在那种情况下,假设 || 仍然会做一些对分支控制有意义的事情是合理的,但是假设 | 会做一些等效甚至合适的事情就不太安全了。

作为一个额外的小问题,| 的优先级与 || 的优先级不同。如果您依靠优先级而不是圆括号进行分组,这可能会给您带来麻烦,如果您正在考虑修改现有代码以将 || 表达式更改为 | 表达式,则需要注意这一点。例如,A && B || C && D 分组为 (A && B) || (C && D),但 A && B | C && D 分组为 (A && (B | C)) && D

即使 ab 是 automatic-duration 布尔标志,这并不意味着像 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) 以及许多因素来决定是否执行此类替换可能导致上述替换 运行 比原始代码更快或更慢。

表达式 A | B 在编译器可以优化为按位或两个向量的循环中可能更快。 | 可能稍微优化的另一种情况是编译器希望通过将两个操作数与位掩码组合来优化分支。如果右边的操作数可能是可见的 side-effects,编译器必须插入一个分支来保证正确的 short-circuiting.

在我能想到的其他情况下,A || B 会一样快或更快,包括几乎所有我能想到的比较一对操作数而不是向量的情况。然而,这些对性能几乎从来都不是关键。

So the question is why don't we always use | instead of || in branches?

在我的小脑子里有三个原因,但可能只有我一个人。

首先也是最重要的一点:所有代码的阅读次数往往比编写的次数多。因此,在示例中,您有一个值为零或 1 的整数数组。代码真正要做的是隐藏在 reader 中。原作者可能很清楚应该做什么,但多年后,在添加了很多很多代码行之后,可能任何人都在猜测。在我的世界中,使用显示预期比较的内容,它要么是位比较,要么是逻辑比较。两者都不应该。

其次:性能提升真的很重要吗?该示例基本上什么都不做,并且可以更有效地进行编码。不是?好吧,首先不要创建数组,代码现在所做的只是检查 rand 函数的质量。优化是一个示例,其中对问题进行更好的分析可能会带来更大的收益。

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

因此,如果出于某种原因,从代码中获得最后一点效率是值得的,我会将该选择标记为“hack”。我可能会包含一个带有类似“DO_PERFORMANCE_HACKS”的宏,并且有两个版本的代码,一个带有 |和一个||并评论意图是什么。通过更改宏,下一个 reader 将有可能查看黑客的内容和位置,并且将来可能会选择不编译它们。