在特定大小的阵列上运行时计算时间达到峰值
我创建了一个程序,它分配了两个C++双精度数组.首先包含从0到pi/4的x的sin(x)值.对于第二个,我写了sin(x)的二阶导数,使用三点公式计算:
(vals[i-1]-2*vals[i]+vals[i+1])/(dx*dx)
我对不同大小的数组执行这些计算,重复几次,并输出平均计算时间.这样我得到了很好的图表,显示了计算特定大小数组的衍生物所需的时间.
这一切听起来都相当容易,但我遇到了一个奇怪的问题.看一下图表:
当数组很小时,没有什么奇怪的事情发生.但是,当它们大于10000个元素(有两个数组意味着大约16kB 160kB的内存)时,我得到了周期性的峰值,每个峰值大约在前面的512个元素之后.这种情况发生在多个CPU(AMD Sempron 3850,Intel Q9400和Intel Xeon 5310)上,并不会发生在其他CPU(Intel i5 5200U,Intel Nehalem-C)上.
如果这还不够,当阵列达到约65,000个元素时,Windows 7上的AMD 3850会突然增加.这不会发生在Debian上.
我认为它可能与CPU缓存,给定'神奇'数量的元素以及操作系统的调度有关,但我想不出任何具体的解释和方法来确认它(除了分析CPU缓存命中率) .
码:
int main(int, char**)
{
double maxerr=0.0;
double avgerr=0.0;
for(unsigned SIZE=5000u; SIZE<100000u; SIZE+=1u)
{
const unsigned REPEATS=10000000/SIZE+1;
const double STEP=1.0/(SIZE-1.0)*atan(1.0)*4.0;
double *vals;
double *derivs;
// Alokacja
vals= new double[SIZE];
derivs=new double[SIZE];
// Inicjalizacja
for(unsigned i=0u; i<SIZE; ++i)
{
vals[i]=sin(i*STEP);
derivs[i]=0.0;
}
// Obliczenia normalne
const double TIME_FPU_START=msclock();
for(unsigned r=0u; r<REPEATS; ++r)
{
const double STEP2RCP=1.0/(STEP*STEP);
for(unsigned i=1u; i<SIZE-1u; ++i)
{
derivs[i]=(vals[i-1]-2.0*vals[i]+vals[i+1u])*STEP2RCP;
}
}
const double TIME_FPU_END=msclock();
const double TIME_FPU=(TIME_FPU_END-TIME_FPU_START)/REPEATS;
maxerr=0.0;
avgerr=0.0;
for(unsigned i=1u; i<SIZE-1; ++i)
{
double err=fabs((derivs[i]+sin(i*STEP))/(-sin(i*STEP)));
avgerr+=err/(SIZE-2);
if(err>maxerr)
{
//printf("%f > %f\n", derivs[i], -sin(i*step));
maxerr=err;
}
}
const double MAX_REL_ERR_FPU=maxerr;
const double AVG_REL_ERR_FPU=avgerr;
// Podsumowanie
fprintf(stdout, "%u %.8f %.8f\n", SIZE, TIME_FPU, AVG_REL_ERR_FPU);
fprintf(stderr, "%u %.8f %.8f\n", SIZE, TIME_FPU, AVG_REL_ERR_FPU);
// Kasowanie
delete [] vals;
delete [] derivs;
}
return 0;
}
"msclock"函数是linux上的普通旧时钟()/ CLOCKS_PER_SEC,Windows上的QueryPerformanceTimer(clock()及其在Windows上的所有变体似乎都具有大约16ms的分辨率.
数据文件:https://pastebin.com/4iDn5Y9k 第一列表示数组大小,第二列表示平均时间,最后一列是导数的平均误差.
附加信息:我已经检查了我得到的阵列的地址.第一个(vals)似乎总是保持相同的值,而第二个(vals)不断增加.这可能意味着第二个数组的开头与第一个数组的结尾位于同一个块中.页面大小为4kiB时,增加512个元素可能需要使用另一个页面.
附加信息:关于Debian峰值与数组的地址密切相关(第4列和第5列):
50670 0.00021090 0.00000016 0x55efa5e04c30 0x55efa5e67bb0
50680 0.00021244 0.00000017 0x55efa5e04c30 0x55efa5e67c00
50690 0.00170968 0.00000023 0x7f1617d0b010 0x7f1617ca7010 @
50700 0.00021141 0.00000024 0x55efa5e04c30 0x55efa5e67ca0 @
50710 0.00021873 0.00000027 0x55efa5e04c30 0x55efa5e67cf0
50720 0.00021126 0.00000002 0x55efa5e04c30 0x55efa5e67d40
附加信息:对于小于10'000个元素的数组,两个数组始终位于相同的地址.对于更大的,第二阵列继续移动.这可能是我没有获得小尺寸峰值的原因.
我也玩过"perf stat",正如@geza建议的那样.运行时的第一个输出,大小从5000到12930:
Performance counter stats for './a.out':
70733.635707 task-clock (msec) # 0.999 CPUs utilized
6,008 context-switches # 0.085 K/sec
3 cpu-migrations # 0.000 K/sec
3,866 page-faults # 0.055 K/sec
90,800,323,159 cycles # 1.284 GHz (50.00%)
0 stalled-cycles-frontend (50.01%)
0 stalled-cycles-backend # 0.00% backend cycles idle (50.01%)
160,806,960,842 instructions # 1.77 insn per cycle (50.00%)
16,118,385,897 branches # 227.874 M/sec (50.00%)
5,818,878 branch-misses # 0.04% of all branches (49.99%)
70.839631335 seconds time elapsed
......尺寸从12940到30000:
Performance counter stats for './a.out':
157468.056544 task-clock (msec) # 0.999 CPUs utilized
13,420 context-switches # 0.085 K/sec
10 cpu-migrations # 0.000 K/sec
32,271 page-faults # 0.205 K/sec
201,597,569,555 cycles # 1.280 GHz (50.00%)
0 stalled-cycles-frontend (50.00%)
0 stalled-cycles-backend # 0.00% backend cycles idle (50.00%)
351,405,781,351 instructions # 1.74 insn per cycle (50.00%)
35,289,858,166 branches # 224.108 M/sec (50.00%)
10,494,566 branch-misses # 0.03% of all branches (50.00%)
157.692170504 seconds time elapsed
程序运行时间是两倍,因此更多两倍的上下文切换并不令人惊讶.但是,在这个范围内,我遇到了更多的页面错误.
另一个有趣的事情,当我重新启动第二次运行程序时,第二个数组没有在内存中移动那么多.当程序运行一段时间后,它似乎开始这样做.
我测试的东西越久,我知道的越少; _;