c++ - 在 "loop unrolling"中，所有展开的表达式都执行了吗？

Question

我一直认为 foo2 下面的函数比 foo3 快，直到经过测试。

所有代码如下:

#include <iostream>
#include <boost/timer.hpp>
#include <boost/lexical_cast.hpp>
#include <stdint.h>

struct session {
    bool operator==(const session& r) const;

    uint8_t proto;
    uint16_t sport;
    uint16_t dport;
    uint32_t sip;
    uint32_t dip;
};

bool session::operator==(const session& r) const {
    return proto == r.proto && sport == r.sport && dport == r.dport 
        && sip == r.sip && dip == r.dip;
}

// my L1,L2,L3 total cache size is 16MB, so set it 32MB to overflow all 16MB caches.
static const int SIZE = 32 * 1024 * 1024 / sizeof(session);
int sum;

void foo1(session* p) {
    session s = {1, 2, 3, 4, 5};
    for (int i = 0; i < SIZE; i++)
        if (p[i] == s)
            sum++;
}

void foo2(session* p) {
    session s = {1, 2, 3, 4, 5};
    int n = SIZE - SIZE % 4;
    int i;

    for (i = 0; i < n; i += 4) {
        if (p[i + 0] == s)
            sum++;
        if (p[i + 1] == s)
            sum++;
        if (p[i + 2] == s)
            sum++;
        if (p[i + 3] == s)
            sum++;
    }
    /*
    for (; i < SIZE; i++)
            if (p[i] == s)
               sum++;
    */
}

void foo3(session* p) {
    session s = {1, 2, 3, 4, 5};
    int n = SIZE - SIZE % 4;
    int i;

    for (i = 0; i < n; i += 4) {
        if (p[i + 0] == s)
            sum++;
        else if (p[i + 1] == s)
            sum++;
        else if (p[i + 2] == s)
            sum++;
        else if (p[i + 3] == s)
            sum++;
    }
    /*
    for (; i < SIZE; i++)
            if (p[i] == s)
               sum++;
    */
}

int main(int argc, char* argv[]) {
    if (argc < 2)
        return -1;

    int n = boost::lexical_cast<int>(argv[1]);
    session* p = new session[SIZE];

    boost::timer t;
    for (int i = 0; i < n; i++)
        foo1(p);
    std::cout << t.elapsed() << std::endl;

    t.restart();
    for (int i = 0; i < n; i++)
        foo2(p);
    std::cout << t.elapsed() << std::endl;

    t.restart();
    for (int i = 0; i < n; i++)
        foo3(p);
    std::cout << t.elapsed() << std::endl;

    delete [] p;
    return 0;
}

测试1000次，./a.out 1000

输出:

4.36
3.98
3.96

我的机器:

CPU:Intel(R) Xeon(R) CPU E5-2420 0 @ 1.90GHz

缓存:

一级缓存:32K

一级缓存:32K

二级缓存:256K

三级缓存:15360K

在测试中，foo2和foo3性能相当。由于 foo2 可能大小写CPU 并行执行所有展开的表达式，所以 foo3 是相同的。是吗？如果是，则 else if 语法违反了 C/C++ 基本 else if 语义。

有人解释一下吗？非常感谢。

更新

我的编译器是 gcc 4.4.6 ins RedHat

g++ -Wall -O2 a.cpp

Answer 1

在某些情况下，我希望 foo3 更快，因为它可以短路(会出现一些小于或等于 4 的分支，而在 foo2 中，总是出现 4 个分支)。在 s 不等于 4 个数组元素中的任何一个的情况下(在这种情况下极有可能)，foo2 和 foo3 基本上是相同的代码。在这种情况下，两个函数都会发生 4 个分支。

考虑一下 foo3 的真实情况(就分支而言):

if (p[i + 0] == s)
    sum++;
else
    if (p[i + 1] == s)
        sum++;
    else 
        if (p[i + 2] == s)
            sum++;
        else 
            if (p[i + 3] == s)
                sum++;

这应该表明，只要 if 一直为假，子分支就会发生。这意味着在所有 if 都不为真的情况下，它将执行与 foo2 相同数量的操作(尽管功能不同)。

一种粗略的思考方式是好像每个 if 都有一个成本(不是 if 的主体，实际的 if)。也就是说，执行流程中每走到一个if，都需要付出一定的代价。这是因为必须完成一个分支。这样想，很明显，当 foo3 的流程没有短路时(当 foo3 的所有 4 个 if 都短路时，每个函数的成本是相同的遭遇)。 (正如 KillianDS 指出的那样，如果分支预测是错误的，那么 foo3 实际上会花费更长的时间，因为错误的分支将不得不倒回并执行正确的分支。尽管总是选择正确的分支，但对您来说似乎是这样。)

这有点像下面的代码片段如何具有相同的性能:

if (short_runtime()) {}

和:

if (short_runtime() && long_runtime()) {}

如果 short_runtime 返回 true，那么调用第二个函数的函数显然会花费更长的时间。如果 short_runtime() 返回为 false，则 long_runtime() 调用将永远不会发生，因此运行时间将相同(或者至少非常 类似)。

---

为了检验这个理论，您可以使 p[i + 0] == s 为真。只需值初始化数组 (session* p = new session[SIZE]();)，并使用 session s = {1, 2, 3, 4, 5}; 本地。

---

循环展开的目的/结果似乎有点困惑。这样做是为了减少必须发生的跳跃。如果必须完成 n 次操作，而不是 n 次迭代(跳跃)，每次迭代执行 1 个操作，您可以进行 n/k 次迭代(跳跃)反而发生了。当一切都适合缓存时，这可以提供速度提升(如果它不能适合缓存，它实际上会降低性能!)。

这些指令不是同时发生的(如果是，sum 将需要一个围绕它的互斥量，这将非常昂贵)。它们只是以 4 组而不是 1 组的形式出现。