对于在学校的任务,我正在对一大堆数字进行密集操作 . 在对整个阵列上运行的单线程版本进行基准测试并将我的结果与我的同学进行比较时,我发现了一些奇怪的行为 .
功能如下:
int compute (char a[], int start, int end) {
int sum = 0;
int min = a[start];
int max = a[start];
for (int i = start; i < end; i++) {
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
int cube = a[i] * a[i] * a[i];
sum += cube;
}
return sum;
}
但我的同学的计划一直运行得更快,通常更快 . 他的代码是相同的,除了循环体中指令的顺序:
for (int i = start; i < end; i++) {
int cube = a[i] * a[i] * a[i];
sum += cube;
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
}
这是将每个版本的运行时与大小为1,000,000,000的输入数组(使用随机带符号字节初始化)进行比较的输出:
Min/max first:
sum = 5445493143089, min = -128, max = 127
Completed in 1.050268 sec
Product-sum first:
sum = 5445493143089, min = -128, max = 127
Completed in 1.010639 sec
我们检查了两个版本的生成组件,并注意到存在相同的指令,只是以不同的方式排序 . 据我所知,这不应该像它那样有效,但我可能是错的 . (我们也注意到使用的寄存器差异很大,但我特别怀疑这应该有效 . )
在编译C( -std=c11
)和C( -std=c++11
)时遇到此行为 .
Why is the order of those lines heavily affecting the behavior of the sequential program? 我们还对操作的并行版本进行了基准测试,相比之下,它的行为几乎没有变化 . 我将内存重新排序视为可能的罪魁祸首,但是在分区中并没有重叠 . )
Intensive back-to-back tests 展示了这种行为 . 产品总和总是快于最小/最大,即使在交替和允许缓存 .
2 回答
如果我们将明确的跳转放入代码中,您可以看到最后一个带有条件的跳转可以避免大部分时间跳转 . 这类似于编译器实际生成的代码 .
第一种形式,最小/最大第一:
第二种形式,最小/最后一次:
可能就像处理器跳转预测在循环底部的条件跳转更好地工作一样简单......