int SumByColRow (int matrix[M][M],int size)
{
int i,j,Sum = 0;
for (j = 0; j < size; j ++) {
for (i = 0; i < size; i ++) {
Sum += matrix[i][j];
}
}
return Sum;
}
int SumByRowCol (int matrix[M][M],Sum = 0;
for (i = 0; i < size; i ++) {
for (j = 0; j < size; j ++) {
Sum += matrix[i][j];
}
}
return Sum;
}
我认为不应该在内循环中切换行应该更快,因为C按行存储矩阵,因此SumByRowCol应该更快,但在测量中它是另一种方式.我认为由于空间局部性原理的缓存会使内部循环更快,因为值来自连续元素会更快吗？实际上测量的执行时间是什么原因是为什么SumByColRow实际上更快？
SumByColRow: Result: 31744 6415.29 us(641529 ticks) SumByRowCol: Result: 31744 7336.47 us(733647 ticks)
更新
我再次运行该程序,确保我实际上正在使用数据缓存,这次结果与预期一致,因此上述结果可能是巧合而且以下更像是：
SumByColRow: Result: 31744 5961.13 us(596113 ticks) SumByRowCol: Result: 31744 2328.89 us(232889 ticks)
解决方法
码
#include "timer.h" #include <stdio.h> enum { M = 128 }; extern int SumByColRow (int matrix[M][M],int size); extern int SumByRowCol (int matrix[M][M],int size); int SumByColRow (int matrix[M][M],int size) { int Sum = 0; for (int j = 0; j < size; j ++) { for (int i = 0; i < size; i ++) Sum += matrix[i][j]; } return Sum; } int SumByRowCol (int matrix[M][M],int size) { int Sum = 0; for (int i = 0; i < size; i ++) { for (int j = 0; j < size; j ++) Sum += matrix[i][j]; } return Sum; } static inline int max(int i,int j) { return (i > j) ? i : j; } int main(void) { int matrix[M][M]; for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) matrix[i][j] = 1000*i + j; Clock clk; unsigned long long x[M]; char buffer[32]; unsigned long long sum; clk_init(&clk); clk_start(&clk); for (int i = 0; i < M; i++) x[i] = SumByColRow(matrix,max(M - i,10)); clk_stop(&clk); sum = 0; for (int i = 0; i < M; i++) sum += x[i]; printf("SumByColRow: value = %llu,time = %s\n",sum,clk_elapsed_us(&clk,buffer,sizeof(buffer))); clk_start(&clk); for (int i = 0; i < M; i++) x[i] = SumByRowCol(matrix,10)); clk_stop(&clk); sum = 0; for (int i = 0; i < M; i++) sum += x[i]; printf("SumByRowCol: value = %llu,sizeof(buffer))); return 0; }
两个SumBy函数基本没有变化(次要的符号调整,但仅此而已).时序线束在Clock结构中存储开始时间和停止时间,clk_elapsed_us()函数将经过的时间(以微秒为单位)格式化为传递的字符串.
搞乱x [i]等等是为了(尝试并确保)编译器不会优化所有内容.
产量
机器：Mac OS X 10.8.5,GCC(i686-apple-darwin11-llvm-gcc-4.2(GCC)4.2.1(基于Apple Inc. build 5658)(LLVM build 2336.11.00)),Intel Core 2 Duo在2 GHz,4 GB 1067 MHz DDR3 RAM(‘2009年初’Mac Mini).
SumByColRow: value = 33764046316,time = 0.002411 SumByRowCol: value = 33764046316,time = 0.000677
这显示了预期的结果 – 逐行计算的速度较慢,因为矩阵足够大以跨越页面(64 KiB).目前还不清楚M的大小是多少,也没有传递给SumBy函数的大小,但是通过“足够大”的数组和不同的大小,您可以获得预期的性能模式.
那些时间不够舒适 – 我宁愿较低的时间是一两秒的量级.在主程序中的每个定时循环前面添加for(int j = 0; j< 1600; j)循环,得到：
SumByColRow: value = 33764046316,time = 2.529205 SumByRowCol: value = 33764046316,time = 1.022970
该比率较小(3.56对2.47),但仍然倾向于倾向于SumByRowCol().
初始化矩阵’将缓存加热到可以加热的程度.反转计算顺序(SumByColRow之前的SumByRowCol)不会对计时产生显着影响.多次运行的结果非常一致.
汇编程序输出
用gcc -O3 -std = c99 -S编译：
.section __TEXT,__text,regular,pure_instructions
.globl _SumByColRow
.align 4,0x90
_SumByColRow:
Leh_func_begin1:
pushq %rbp
Ltmp0:
movq %rsp,%rbp
Ltmp1:
testl %esi,%esi
jg LBB1_5
xorl %eax,%eax
LBB1_2:
popq %rbp
ret
LBB1_5:
movl %esi,%ecx
xorl %eax,%eax
movq %rcx,%rdx
jmp LBB1_6
.align 4,0x90
LBB1_3:
addl (%r8),%eax
addq $512,%r8
decq %rsi
jne LBB1_3
addq $4,%rdi
decq %rdx
je LBB1_2
LBB1_6:
movq %rcx,%rsi
movq %rdi,%r8
jmp LBB1_3
Leh_func_end1:
.globl _SumByRowCol
.align 4,0x90
_SumByRowCol:
Leh_func_begin2:
pushq %rbp
Ltmp2:
movq %rsp,%rbp
Ltmp3:
testl %esi,%esi
jg LBB2_5
xorl %eax,%eax
LBB2_2:
popq %rbp
ret
LBB2_5:
movl %esi,%rdx
jmp LBB2_6
.align 4,0x90
LBB2_3:
addl (%r8),%eax
addq $4,%r8
decq %rsi
jne LBB2_3
addq $512,%rdi
decq %rdx
je LBB2_2
LBB2_6:
movq %rcx,%r8
jmp LBB2_3
Leh_func_end2:
