循环的执行时间

Question

我正在分析和测量,并通过我的分析和测量获得不同的结果.代码是两个循环,数据缓存大小为512字节,块大小为32字节:

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], int size)
{
  int i, j, 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)

Answer 1

我可以提供一个与您的代码密切相关的反例。

\n\n

代码

\n\n

#include "timer.h"\n#include <stdio.h>\n\nenum { M = 128 };\n\nextern int SumByColRow (int matrix[M][M], int size);\nextern int SumByRowCol (int matrix[M][M], int size);\n\nint SumByColRow (int matrix[M][M], int size)\n{\n    int Sum = 0;\n\n    for (int j = 0; j < size; j ++)\n    {\n        for (int i = 0; i < size; i ++)\n            Sum += matrix[i][j];\n    }\n    return Sum;\n}\n\nint SumByRowCol (int matrix[M][M], int size)\n{\n    int Sum = 0;\n\n    for (int i = 0; i < size; i ++)\n    {\n        for (int j = 0; j < size; j ++)\n            Sum += matrix[i][j];\n    }\n    return Sum;\n}\n\nstatic inline int max(int i, int j) { return (i > j) ? i : j; }\n\nint main(void)\n{\n    int matrix[M][M];\n    for (int i = 0; i < M; i++)\n        for (int j = 0; j < M; j++)\n            matrix[i][j] = 1000*i + j;\n\n    Clock clk;\n    unsigned long long x[M];\n    char buffer[32];\n    unsigned long long sum;\n\n    clk_init(&clk);\n\n    clk_start(&clk);\n    for (int i = 0; i < M; i++)\n        x[i] = SumByColRow(matrix, max(M - i, 10));\n    clk_stop(&clk);\n    sum = 0;\n    for (int i = 0; i < M; i++)\n        sum += x[i];\n    printf("SumByColRow: value = %llu, time = %s\\n", sum, clk_elapsed_us(&clk, buffer, sizeof(buffer)));\n\n    clk_start(&clk);\n    for (int i = 0; i < M; i++)\n        x[i] = SumByRowCol(matrix, max(M - i, 10));\n    clk_stop(&clk);\n    sum = 0;\n    for (int i = 0; i < M; i++)\n        sum += x[i];\n    printf("SumByRowCol: value = %llu, time = %s\\n", sum, clk_elapsed_us(&clk, buffer, sizeof(buffer)));\n\n    return 0;\n}\n

\n\n

这两个SumBy函数基本上没有变化（细微的符号调整，但仅此而已）。计时工具在结构中存储开始时间和停止时间Clock，并且该clk_elapsed_us()函数将经过的时间（以微秒为单位）格式化为传递给它的字符串。

\n\n

搞乱等等x[i]是为了（尝试并）确保编译器不会优化所有内容。

\n\n

输出

\n\n

机器：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）。

\n\n

SumByColRow: value = 33764046316, time = 0.002411\nSumByRowCol: value = 33764046316, time = 0.000677\n

\n\n

这显示了预期结果 \xe2\x80\x94，即逐行计算速度较慢，因为矩阵足够大，可以跨越页面 (64 KiB)。从问题中尚不清楚大小M是什么，也不清楚size传递给SumBy函数的内容是什么，但通过“足够大”的数组和不同的大小，您可以获得预期的性能模式。

\n\n

这些时间对于舒适来说不够大\xe2\x80\x94 我宁愿较低的时间是一两秒的数量级。for (int j = 0; j < 1600; j++)在主程序中的每个定时循环前面添加一个循环会产生：

\n\n

SumByColRow: value = 33764046316, time = 2.529205\nSumByRowCol: value = 33764046316, time = 1.022970\n

\n\n

该比率较小（3.56 比 2.47），但仍然明显倾向于SumByRowCol()。

\n\n

初始化矩阵“预热缓存”到可以预热的程度。反转计算顺序（SumByRowCol 在 SumByColRow 之前）不会对计时产生显着影响。多次运行的结果非常一致。

\n\n

汇编器输出

\n\n

编译gcc -O3 -std=c99 -S：

\n\n

    .section        __TEXT,__text,regular,pure_instructions\n    .globl  _SumByColRow\n    .align  4, 0x90\n_SumByColRow:\nLeh_func_begin1:\n    pushq   %rbp\nLtmp0:\n    movq    %rsp, %rbp\nLtmp1:\n    testl   %esi, %esi\n    jg      LBB1_5\n    xorl    %eax, %eax\nLBB1_2:\n    popq    %rbp\n    ret\nLBB1_5:\n    movl    %esi, %ecx\n    xorl    %eax, %eax\n    movq    %rcx, %rdx\n    jmp     LBB1_6\n    .align  4, 0x90\nLBB1_3:\n    addl    (%r8), %eax\n    addq    $512, %r8\n    decq    %rsi\n    jne     LBB1_3\n    addq    $4, %rdi\n    decq    %rdx\n    je      LBB1_2\nLBB1_6:\n    movq    %rcx, %rsi\n    movq    %rdi, %r8\n    jmp     LBB1_3\nLeh_func_end1:\n\n    .globl  _SumByRowCol\n    .align  4, 0x90\n_SumByRowCol:\nLeh_func_begin2:\n    pushq   %rbp\nLtmp2:\n    movq    %rsp, %rbp\nLtmp3:\n    testl   %esi, %esi\n    jg      LBB2_5\n    xorl    %eax, %eax\nLBB2_2:\n    popq    %rbp\n    ret\nLBB2_5:\n    movl    %esi, %ecx\n    xorl    %eax, %eax\n    movq    %rcx, %rdx\n    jmp     LBB2_6\n    .align  4, 0x90\nLBB2_3:\n    addl    (%r8), %eax\n    addq    $4, %r8\n    decq    %rsi\n    jne     LBB2_3\n    addq    $512, %rdi\n    decq    %rdx\n    je      LBB2_2\nLBB2_6:\n    movq    %rcx, %rsi\n    movq    %rdi, %r8\n    jmp     LBB2_3\nLeh_func_end2:\n

\n