Sam*_*zer 69 c c++ optimization performance assembly
我一直试图通过计算一个使用以下代码对数组元素进行扩展和求和的例程来了解在L1缓存与内存中使用数组的影响(我知道我应该将结果缩放为' a'在最后;关键是在循环中同时进行乘法和加法 - 到目前为止,编译器还没有想出要将'a'分解出来):
double sum(double a,double* X,int size)
{
double total = 0.0;
for(int i = 0; i < size; ++i)
{
total += a*X[i];
}
return total;
}
#define KB 1024
int main()
{
//Approximately half the L1 cache size of my machine
int operand_size = (32*KB)/(sizeof(double)*2);
printf("Operand size: %d\n", operand_size);
double* X = new double[operand_size];
fill(X,operand_size);
double seconds = timer();
double result;
int n_iterations = 100000;
for(int i = 0; i < n_iterations; ++i)
{
result = sum(3.5,X,operand_size);
//result += rand();
}
seconds = timer() - seconds;
double mflops = 2e-6*double(n_iterations*operand_size)/seconds;
printf("Vector size %d: mflops=%.1f, result=%.1f\n",operand_size,mflops,result);
return 0;
}
请注意,为简洁起见,不包括timer()和fill()例程; 如果你想运行代码,可以在这里找到他们的完整源代码:
现在,这里有趣的地方.这是输出:
Operand size: 2048
Vector size 2048: mflops=588.8, result=-67.8
尽管X的所有元素都应该在循环迭代之间保存在缓存中,但这完全是未缓存的性能.查看生成的汇编代码:
g++ -O3 -S -fno-asynchronous-unwind-tables register_opt_example.cpp
我注意到sum函数循环中有一个奇怪之处:
L55:
movsd (%r12,%rax,8), %xmm0
mulsd %xmm1, %xmm0
addsd -72(%rbp), %xmm0
movsd %xmm0, -72(%rbp)
incq %rax
cmpq $2048, %rax
jne L55
说明:
addsd -72(%rbp), %xmm0
movsd %xmm0, -72(%rbp)
表示它正在堆栈中存储sum()中的"total"值,并在每次循环迭代时读取和写入它.我修改了程序集,以便将此操作数保存在寄存器中:
...
addsd %xmm0, %xmm3
...
这个小小的改变创造了巨大的性能提升:
Operand size: 2048
Vector size 2048: mflops=1958.9, result=-67.8
tl; dr 我的问题是:为什么用寄存器替换单个内存位置访问,加速代码这么多,因为单个位置应该存储在L1缓存中？哪些架构因素使这成为可能？重复写一个堆栈位置会完全破坏缓存的有效性似乎很奇怪.
附录
我的gcc版本是:
Target: i686-apple-darwin10
Configured with: /var/tmp/gcc/gcc-5646.1~2/src/configure --disable-checking --enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin10 --with-gxx-include-dir=/include/c++/4.2.1 --program-prefix=i686-apple-darwin10- --host=x86_64-apple-darwin10 --target=i686-apple-darwin10
Thread model: posix
gcc version 4.2.1 (Apple Inc. build 5646) (dot 1)
我的CPU是:
英特尔至强X5650
Mys*_*ial 58
它可能是一个较长的依赖链和Load Misprediction*的组合.
更长的依赖链:
首先,我们确定关键的依赖路径.然后我们查看以下提供的指令延迟:http://www.agner.org/optimize/instruction_tables.pdf(第117页)
在未优化的版本中,关键依赖路径是:
addsd -72(%rbp), %xmm0movsd %xmm0, -72(%rbp)在内部,它可能会分解为:
如果我们查看优化版本,它只是:
所以你有8个周期而不是3个周期.差不多是3倍.
我不确定Nehalem处理器系列对存储加载依赖关系的敏感程度以及它的转发效果.但有理由相信它不是零.
加载存储误预测:
现代处理器以您能想象的更多方式使用预测.其中最着名的可能是分支预测.其中一个鲜为人知的是负载预测.
当处理器看到负载时,它会在所有挂起的写入完成之前立即加载它.它将假定这些写入不会与加载的值冲突.
如果先前的写操作与加载冲突,则必须重新执行加载并将计算回滚到加载点.(与分支错误预测回滚的方式大致相同)
它的相关性如何:
毋庸置疑,现代处理器将能够同时执行此循环的多次迭代.因此处理器将尝试执行加载(addsd -72(%rbp), %xmm0)在它完成movsd %xmm0, -72(%rbp)上一次迭代的store()之前).
结果？之前的商店与负载冲突 - 因此错误预测和回滚.
*请注意,我不确定名称"负载预测".我只在英特尔文档中读过它,但它们似乎没有给它起个名字.
UpA*_*dam 16
我猜测问题不在于缓存/内存访问,而是在处理器中(执行代码).这里有几个明显的瓶颈.
这里的演出数字是基于我使用的箱子(沙桥或威斯特米尔)
标量数学的峰值性能是2.7Ghz x2 FLOPS/Clock x2,因为处理器可以同时进行加法和乘法运算.代码的理论效率为0.6 /(2.7*2)= 11%
所需带宽:每个(+)和(x)2个双倍 - > 4个字节/ 4个字节的翻转*5.4GFLOPS = 21.6GB/s
如果你知道它最近被读取它可能在L1(89GB/s),L2(42GB/s)或L3(24GB/s),所以我们可以排除缓存B/W
内存系统为18.9 GB/s,即使在主内存中,峰值性能也应接近18.9/21.6GB/s = 87.5%
即使使用推测执行,tot + = a*X [i]也会序列化添加,因为tot(n)需要在tot(n + 1)开始之前进行评估
第一次展开循环
移动8和8
{//your func
for( int i = 0; i < size; i += 8 ){
tot += a * X[i];
tot += a * X[i+1];
...
tot += a * X[i+7];
}
return tot
}
使用多个累加器
这将破坏依赖关系并允许我们避免在添加管道上停滞
{//your func//
int tot,tot2,tot3,tot4;
tot = tot2 = tot3 = tot4 = 0
for( int i = 0; i < size; i += 8 )
tot += a * X[i];
tot2 += a * X[i+1];
tot3 += a * X[i+2];
tot4 += a * X[i+3];
tot += a * X[i+4];
tot2 += a * X[i+5];
tot3 += a * X[i+6];
tot4 += a * X[i+7];
}
return tot + tot2 + tot3 + tot4;
}
更新在SandyBridge盒子上运行之后我可以访问:(2.7GHZ SandyBridge -O2 -march = native -mtune = native
原始代码:
Operand size: 2048
Vector size 2048: mflops=2206.2, result=61.8
2.206 / 5.4 = 40.8%
改进代码:
Operand size: 2048
Vector size 2048: mflops=5313.7, result=61.8
5.3137 / 5.4 = 98.4%
我实际上无法重现这一点,因为我的编译器(gcc 4.7.2)保存total在寄存器中.
我怀疑缓慢的主要原因与L1缓存没有关系,而是由于存储之间的数据依赖性
movsd %xmm0, -72(%rbp)
以及后续迭代的负载:
addsd -72(%rbp), %xmm0