C++ code speed, which is faster?

Question

Yes this is a homework question i just need a push in the right direction

Which code block of C++ is faster and why? I Think it is the top one because the [i] array is being used in order, or am i wrong here?.

    double A[100][100];
    ...
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            A[i][j] = i * j;
        }
     }


    double A[100][100];
    ...
    for (int j = 0; j < 100; j++) {
    for (int i = 0; i < 100; i++) {
        A[i][j] = i * j;
    }
 }

Answer 1

如果不运行和分析代码,就无法知道哪条代码更快.

我们可以猜测局部性和缓存行为将如何影响该时间(并且您的猜测是好的),但猜测不能替代分析.(请参阅:如何分析在Linux中运行的C++代码？)

第一个版本可能更快的一个原因:

• 按照它们在内存中布局的顺序访问数组的元素可以允许缓存利用它.(请参阅:什么是"缓存友好"代码？)

为什么没有区别:

• 整个10000个元素可以适合缓存,从而使上述优化无法实现.

我想不出有什么理由为什么第二个会更快,但我以前一直很惊讶.

Answer 2

最一般的答案是:您需要分析两个块并根据经验查看结果.

但是,我可以为大多数具有分层缓存的现代x86,x64,PPC和ARM处理器提供答案.在这些平台上,由于更好的数据局部性,最上面的一个会更快:它按顺序访问内存地址,因此您将更频繁地访问数据缓存.智能x86和x64实现甚至会注意到您正在以这种方式顺序读取内存,并在需要之前预取下一个缓存行.底部模式在远程地址上不间断地访问内存,这意味着您可能会在每次读取时错过缓存.

Ulrich Drepper有一篇很好的论文.他在该论文中的一个例子展示了这两个代码块的确切区别.

作为这里的数学示例,假设您正在编写具有64字节高速缓存行大小的Intel Corei7和32kb L1数据高速缓存.这意味着每次获取地址时,处理器也将获取该64字节对齐块中的所有其他数据.在该平台上,double是8个字节,因此每个缓存行适合8个字节.因此,顶部示例平均会错过八次迭代中的一次:在每次未命中之后,接下来的56个字节也将被提取,因此接下来的七次双*读取将在高速缓存中.

底部示例可能同时将100行数据(每行一个i)放入缓存中:100*64 = 6400字节,完全在缓存大小内.但是你也可能会超过关联缓存,这意味着两条线将映射到L1中的相同SRAM,这意味着一条线将驱逐另一条线.