C++ 优化 if/else 语句

Question

我编写了以下代码来模拟和简化我的应用程序中发生的事情。

在这个简化中，我有 if 和 else 分支，它们执行相同的代码，但写入内存的不同部分。所以我想使用一个包含两个条目的数组，并根据语句条件更新第一个或第二个条目。
该解决方案带来了预期的速度提升。

但是当我们在执行期间对每次迭代进行随机访问时，改进几乎消失了。为了展示这种奇怪的行为，我使用模板来激活或停用 if 语句和随机访问的使用，即..
useif:使用if语句时为true，使用内存访问时为false。
rand_access:当我们对每次迭代进行随机访问时为真，否则为假。

#include <chrono>
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#define N 1000000000
using namespace std;
using namespace std::chrono;

template <bool useif, bool rand_access>
void exec(vector<int>& V, vector<bool>& B) {
    auto start = high_resolution_clock::now();
    int sum[2], sum1 = 0, sum2 = 0;
    sum[0] = 0; sum[1] = 0;
    for ( int i = 0; i < N; i++ ) {
        const int index = (rand_access) ? V[i] : i;
        if ( useif ){
            if ( B[index] ) sum2 += V[i];
            else sum1 += V[i];
        } else
            sum[B[index]] += V[i];
    }
    auto t = std::chrono::duration_cast<milliseconds>(high_resolution_clock::now() - start);
    std::cout << "Time useif="<<useif<<", rand_access="<<rand_access<<" : " << t.count() << " ms" << std::endl;
    std::cout << (sum1+sum2+sum[0]+sum[1]) << std::endl;
}

int main() {
    vector<int> V(N);
    vector<bool> B(N, false);
    iota( V.begin(), V.end(), 0 );
    random_shuffle( V.begin(), V.end() );
    fill( B.begin(), B.begin() + B.size()/2, true);
    random_shuffle( B.begin(), B.end() );
    exec<false, false>(V, B);
    exec<false, true>(V, B);
    exec<true, false>(V, B);
    exec<true, true>(V, B); 
    return 0;
}

在我的机器上，使用 g++ --std=c++11 -O3 -march=native -mtune=native 编译，我得到以下结果:
时间 useif=0, rand_access=0 : 1518 毫秒
时间 useif=0, rand_access=1 : 10791 毫秒
时间 useif=1, rand_access=0 : 4384 毫秒
时间 useif=1, rand_access=1 : 12214 ms

因此，当NOT涉及随机访问时，用内存访问替换 if 语句的速度提高了 2.8，否则性能真的很差关闭(1.1 加速)。

我不明白为什么会发生这种情况以及我该如何处理它，即我如何优化 if 语句知道 if 和 else 分支正在执行相同的代码？

Answer 1

您使用数组优化 if/else 是正确的。它总能给您带来改进，但改进的意义还取决于其他因素。

您的实验显示了分支消除和缓存访问优化的相对影响。

当代码按顺序访问内存时，由于引用的局部性，它会利用 CPU 缓存优化，仅“支付”其内存访问的一小部分。对于 64 字节缓存行，对于存储在连续位置的 4 字节整数，它就像一个令人难以置信的“买一送十五”政策。它可以让您的 CPU 继续添加，而无需等待来自内存的数据。

当代码没有分支时，它会利用 CPU 指令流水线。使用难以预测的条件触发 if 会使流水线停止，因此同时“运行”的指令更少。

从带分支的随机访问到带分支的顺序访问可为您节省 7.8 秒；除此之外，消除分支还能为您节省 2.8 秒。

相比之下，在没有顺序访问的情况下消除分支只会给您带来 1.5 秒的改进，因为当 CPU 无论如何都在等待内存时，消除流水线停顿变得不那么重要了。