2

我一直认为，经过测试，下面的函数foo2比 untile 更快。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

缓存：

L1d 缓存：32K

L1i 缓存：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

4

3 回答 3

3

在某些情况下，我希望 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到达an，都需要一定的代价。这是因为必须做一个分支。这么一想，很明显，当 foo3 的流程不短路时（遇到所有 4 个foo3sif时），每个函数的代价是相同的。（正如 KillianDS 所指出的，如果分支预测错误，对于 foo3 来说实际上会花费更长的时间，因为错误的分支必须被重绕并执行正确的分支。尽管总是选择正确的分支，但对您来说似乎是这样。）

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

if (short_runtime()) {}

和：

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

如果short_runtime返回 true，则第二个函数调用显然需要更长的时间。如果short_runtime()返回为假，则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 组的形式发生。

于 2013-08-15T09:43:55.200 回答
2

这是分支预测：

通过你的程序，我得到了这些速度（这里 foo3 有点慢，g++4.8）：

7.57
0.63
0.99

现在会发生什么？您不初始化会话的初始数组，因为其中的所有变量session都是 POD，它们不会被默认初始化，并且基本上包含垃圾。因此if，您的代码中的 ' 将很快收敛到始终预测未采用的分支。在这种情况下foo3并且foo2非常相似，foo2将无条件执行所有 if ，foo3因为它是预测的，所以会这样做。我真的不明白为什么foo3仍然有点慢，我将不得不查看反汇编代码。

现在看看如果我添加以下默认构造函数会发生什么：

session() : proto(1), sport(2), dport(3), sip(4), dip(5) {}

我当然还必须将foo's 中的会话变量更改为session s;现在我的时间变成：

9.7
1.5
0.75

一下子foo3就快了很多。仅仅因为现在分支将大部分（正确）预测为“采取”。在这种情况下，foo3意味着只执行第一个条件并且函数快速退出。foo2即使预测很好，仍然必须评估所有分支，这显然会使其变慢。

于 2013-08-15T10:08:53.070 回答
0
  • foo2 和 foo3 表现出相同的性能，因为您的输出中只有 0.02 ms 或 s 的差异。您可以使用不同的会话大小对 foo2 和 foo3 进行多次测试；大小为 10、19、20、21、50、80、99 等。这将为您提供更多输出，以确定它们的性能是否仍然相同。
  • 在这个问题中，您试图通过执行循环展开来利用编译器。if 和 else if 语句对编译器可能意义不大，因为它不是并行和优化的一部分，但它可能仍然有帮助。
于 2013-09-01T05:10:20.760 回答