问题：

if（A | B）总是比if（A | B）快吗？

乌靖

2023-03-14

我正在读费多尔·皮库斯的这本书，他有一些非常非常有趣的例子，对我来说是一个惊喜。
特别是这个基准抓住了我，唯一的区别是，在其中一个基准中，我们在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());
}

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

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

共有3个答案

蒙墨竹

2023-03-14

如果评估A是快的，B是慢的，并且当短路发生时（A返回true），那么If（A | | B）将避免If（A | B）不会出现的慢路径。

如果计算A几乎总是给出相同的结果，那么处理器的分支预测可能会给出If（A | | B）性能优于If（A | B），即使B速度很快。

正如其他人所提到的，在某些情况下，短路是强制性的：如果已知A评估为false，则只希望执行B：

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

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

詹甫

2023-03-14

按位or是对应于单个ALU指令的无分支算术运算符。逻辑or被定义为暗示快捷方式求值，它涉及（代价高昂的）条件分支。当操作数的求值有副作用时，这两种方法的效果可能不同。