C程序执行速度 [英] Speed of C program execution

问题描述

我在编程语言校长的考试中遇到了一个问题.想了很久还是没看懂问题

I got one problem at my exam for subject Principal of Programming Language. I thought for long time but i still did not understand the problem

问题:下面是一个程序C，在配置~CPU Intel 1.8GHz，Ram 512MB的PC机上运行MSVC++ 6.0环境

Problem: Below is a program C, that is executed in MSVC++ 6.0 environment on a PC with configuration ~ CPU Intel 1.8GHz, Ram 512MB

#define M 10000
#define N 5000
int a[M][N];

void main() {
    int i, j;
    time_t start, stop;

    // Part A
    start = time(0);
    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            a[i][j] = 0;
    stop = time(0);
    printf("%d\n", stop - start);

    // Part B
    start = time(0);
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            a[i][j] = 0;
    stop = time(0);
    printf("%d\n", stop - start);
}

解释为什么 A 部分只在 1s 内执行，而 B 部分需要 8s 完成?

Explain why does part A only execute in 1s, but it took part B 8s to finish?

推荐答案

行优先与列优先.

首先回想一下，所有多维数组在内存中都表示为一个连续的内存块.因此多维数组 A(m,n) 在内存中可能表示为

Recall first that all multi-dimensional arrays are represented in memory as a continguous block of memory. Thus the multidimensional array A(m,n) might be represented in memory as

a00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn

a00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn

在第一个循环中，您按顺序运行此内存块.因此，您按以下顺序遍历遍历元素的数组

In the first loop, you run through this block of memory sequentially. Thus, you run through the array traversing the elements in the following order

a00  a01  a02  ...  a0n  a10  a11  a12  ...  a1n  a20 ... amn

1    2    3         n    n+1  n+2  n+3 ...   2n   2n+1    mn

在第二个循环中，您在内存中跳过并按以下顺序遍历遍历元素的数组

In the second loop, you skip around in memory and run through the array traversing the elements in the following order

a00  a10  a20  ...  am0  a01  a11  a21  ...  am1  a02  ...  amn

或者，也许更清楚，

a00  a01  a02  ...  a10  a11  a12  ...  a20 ... amn
1    m+1  2m+1      2    m+2  2m+2      3       mn

所有这些跳过真的会伤害你，因为你没有从缓存中获得好处.当您按顺序运行数组时，相邻元素会加载到缓存中.当您跳过数组时，您不会获得这些好处，反而会不断出现缓存未命中而损害性能.

All that skipping around really hurts you because you don't gain advantages from caching. When you run through the array sequentially, neighboring elements are loaded into the cache. When you skip around through the array, you don't get these benefits and instead keep getting cache misses harming performance.

这篇关于C程序执行速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！