7

我正在分析和测量，并从我的分析和测量中得到不同的结果。代码是两个循环，数据缓存大小为 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)
4

1 回答 1

4

我可以根据您的代码提供一个反例。

代码

#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, max(M - i, 10));
    clk_stop(&clk);
    sum = 0;
    for (int i = 0; i < M; i++)
        sum += x[i];
    printf("SumByRowCol: value = %llu, time = %s\n", sum, clk_elapsed_us(&clk, buffer, 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是多少，也不清楚size传递给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().

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

汇编器输出

编译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, %ecx
    xorl    %eax, %eax
    movq    %rcx, %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, %rsi
    movq    %rdi, %r8
    jmp     LBB2_3
Leh_func_end2:
于 2013-10-08T09:22:45.853 回答