我正在读书阿格纳·雾 https://en.wikipedia.org/wiki/Agner_Fog's 优化手册 https://en.wikipedia.org/wiki/Agner_Fog#Optimization,我遇到了这个例子:
double data[LEN];
void compute()
{
const double A = 1.1, B = 2.2, C = 3.3;
int i;
for(i=0; i<LEN; i++) {
data[i] = A*i*i + B*i + C;
}
}
Agner 指出,有一种方法可以优化此代码 - 通过认识到循环可以避免使用昂贵的乘法,而是使用每次迭代应用的“增量”。
我用一张纸来证实这个理论,首先......
...当然,他是对的 - 在每次循环迭代中,我们可以通过添加“增量”,基于旧结果计算新结果。该增量从值“A+B”开始,然后每一步增加“2*A”。
所以我们将代码更新为如下所示:
void compute()
{
const double A = 1.1, B = 2.2, C = 3.3;
const double A2 = A+A;
double Z = A+B;
double Y = C;
int i;
for(i=0; i<LEN; i++) {
data[i] = Y;
Y += Z;
Z += A2;
}
}
就操作复杂性而言,这两个版本的功能之间的差异确实是惊人的。与加法相比,我们的 CPU 中的乘法运算速度要慢得多。我们用 2 个加法替换了 3 个乘法和 2 个加法……
所以我继续添加一个循环来执行compute
很多次 - 然后保留执行所需的最短时间:
unsigned long long ts2ns(const struct timespec *ts)
{
return ts->tv_sec * 1e9 + ts->tv_nsec;
}
int main(int argc, char *argv[])
{
unsigned long long mini = 1e9;
for (int i=0; i<1000; i++) {
struct timespec t1, t2;
clock_gettime(CLOCK_MONOTONIC_RAW, &t1);
compute();
clock_gettime(CLOCK_MONOTONIC_RAW, &t2);
unsigned long long diff = ts2ns(&t2) - ts2ns(&t1);
if (mini > diff) mini = diff;
}
printf("[-] Took: %lld ns.\n", mini);
}
我编译了两个版本,运行它们......然后看到这个:
gcc -O3 -o 1 ./code1.c
gcc -O3 -o 2 ./code2.c
./1
[-] Took: 405858 ns.
./2
[-] Took: 791652 ns.
嗯,这是出乎意料的。由于我们报告了最短执行时间,因此我们丢弃了操作系统各个部分引起的“噪音”。我们还小心翼翼地在一台完全不执行任何操作的机器上运行。结果或多或少是可重复的 - 重新运行两个二进制文件表明这是一致的结果:
for i in {1..10} ; do ./1 ; done
[-] Took: 406886 ns.
[-] Took: 413798 ns.
[-] Took: 405856 ns.
[-] Took: 405848 ns.
[-] Took: 406839 ns.
[-] Took: 405841 ns.
[-] Took: 405853 ns.
[-] Took: 405844 ns.
[-] Took: 405837 ns.
[-] Took: 406854 ns.
for i in {1..10} ; do ./2 ; done
[-] Took: 791797 ns.
[-] Took: 791643 ns.
[-] Took: 791640 ns.
[-] Took: 791636 ns.
[-] Took: 791631 ns.
[-] Took: 791642 ns.
[-] Took: 791642 ns.
[-] Took: 791640 ns.
[-] Took: 791647 ns.
[-] Took: 791639 ns.
接下来要做的唯一一件事是查看编译器为两个版本中的每一个创建了什么样的代码。
objdump -d -S
表明第一个版本compute
- “愚蠢”但不知何故快速的代码 - 有一个如下所示的循环:
那么第二个优化版本呢?它只添加了两个内容?
现在我不了解你的情况,但就我自己而言,我……很困惑。第二个版本的指令大约减少了 4 倍,其中两个主要指令只是SSE https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions基于添加(addsd
)。第一个版本不仅有 4 倍多的指令...它还包含完整的(如预期的)乘法(mulpd
).
我承认我没想到这个结果。不是因为我是阿格纳的粉丝(我是,但这无关紧要)。
知道我缺少什么吗?我在这里犯了任何错误吗?这可以解释速度的差异吗?请注意,我已经完成了测试至强 W5580 https://en.wikipedia.org/wiki/List_of_Intel_Xeon_processors_(Nehalem-based)#%22Gainestown%22_(45_nm) and a 至强E5-1620 https://en.wikipedia.org/wiki/List_of_Intel_Xeon_processors_(Sandy_Bridge-based)#Xeon_E5-1620- 在这两个版本中,第一个(哑)版本比第二个版本快得多。
为了轻松重现结果,两个版本的代码有两个要点:愚蠢但不知何故更快 https://gist.github.com/ttsiodras/7b4f4d6948886500cd8fa32fc90dab41 and 优化,但速度较慢 https://gist.github.com/ttsiodras/178ddc5dd696948a1b34bea09500d96a.
附:请不要评论浮点精度问题;这不是这个问题的重点。