c++ - 为什么在单独的循环中元素添加比在组合循环中快得多?





performance compiler-optimization vectorization (9)


想象一下,你正在使用一台机器,其中n只是正确的值,它只能在内存中同时保存两个阵列,但是通过磁盘缓存可用的总内存仍足以容纳所有四个。

假设一个简单的LIFO缓存策略,这段代码:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

首先会导致ab被加载到RAM中,然后完全在RAM中工作。 当第二个循环开始时, cd将从磁盘加载到RAM中并进行操作。

另一个循环

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

每次循环时 ,它会在其他两个数组中分页出两个数组和页面。 这显然会慢得多。

您可能没有在测试中看到磁盘缓存,但您可能会看到其他形式的缓存的副作用。

这里似乎有一点混乱/误解,所以我将尝试用一个例子来详细说明。

n = 2 ,我们正在使用字节。 因此,在我的场景中,我们只有4个字节的RAM ,其余的内存明显变慢(比如说访问时间长100倍)。

假设一个相当愚蠢的缓存策略, 如果该字节不在缓存中,把它放在那里并获得以下字节,当我们在它时你会得到这样的场景:

  • for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
  • 缓存a[0]a[1]然后b[0]b[1]并在缓存中设置a[0] = a[0] + b[0] - 缓存中现在有4个字节, a[0], a[1]b[0], b[1] 。 成本= 100 + 100。

  • 在缓存中设置a[1] = a[1] + b[1] 。 成本= 1 + 1。
  • 重复cd
  • 总费用= (100 + 100 + 1 + 1) * 2 = 404

  • for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
  • 缓存a[0]a[1]然后b[0]b[1]并在缓存中设置a[0] = a[0] + b[0] - 缓存中现在有4个字节, a[0], a[1]b[0], b[1] 。 成本= 100 + 100。

  • 从缓存和缓存c[0]c[1]弹出a[0], a[1], b[0], b[1] c[1]然后d[0]d[1]并设置c[0] = c[0] + d[0]缓存中的c[0] = c[0] + d[0] 。 成本= 100 + 100。
  • 我怀疑你开始明白我要去哪里了。
  • 总费用= (100 + 100 + 100 + 100) * 2 = 800

这是一个经典的缓存捶打场景。

假设a1b1c1d1指向堆内存,我的数字代码具有以下核心循环。

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

该循环通过另一个外部for循环执行10,000次。 为了加快速度,我将代码更改为:

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

在MS Visual C ++ 10.0上进行了全面优化编译,在Intel Core 2 Duo(x64)上为32位启用了SSE2 ,第一个示例需要5.5秒,双循环示例仅需1.9秒。 我的问题是:(请参考我在底部的改写问题)

PS:我不确定,如果这有帮助:

第一个循环的反汇编基本上看起来像这样(这个块在整个程序中重复大约五次):

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

双循环示例的每个循环都会生成此代码(以下块重复约三次):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

事实证明这个问题没有关系,因为行为严重依赖于数组(n)和CPU缓存的大小。 因此,如果有进一步的兴趣,我重新提出这个问题:

您能否提供一些有关导致不同缓存行为的详细信息,如下图中的五个区域所示?

通过为这些CPU提供类似的图表,指出CPU /缓存架构之间的差异也可能是有趣的。

PPS:这是完整的代码。 它使用TBB Tick_Count来实现更高分辨率的时序,可以通过不定义TBB_TIMING宏来禁用它:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(它显示不同n值的FLOP / s。)




这是因为CPU没有那么多缓存未命中(必须等待阵列数据来自RAM芯片)。 您可以有意识地连续调整阵列的大小,以便超过CPU的1级缓存 (L1)和2级缓存 (L2)的大小,并绘制代码所需的时间。执行数组的大小。 图表不应该像您期望的那样是直线。




这不是因为代码不同,而是因为缓存:RAM比CPU寄存器慢,CPU内部有缓存,以避免每次变量更改时写入RAM。 但是缓存并不像RAM那么大,因此,它只映射了一小部分。

第一个代码修改在每个循环中交替它们的远程存储器地址,因此需要连续地使高速缓存无效。

第二个代码不会交替:它只是在相邻地址上流动两次。 这使得所有作业都在缓存中完成,仅在第二个循环开始后使其无效。




好的,正确的答案肯定要对CPU缓存做一些事情。 但是使用缓存参数可能非常困难,尤其是没有数据。

有许多答案,导致了很多讨论,但让我们面对现实:缓存问题可能非常复杂,并不是一维的。 它们在很大程度上取决于数据的大小,所以我的问题是不公平的:事实证明它在缓存图中非常有趣。

@Mysticial的回答让很多人(包括我)相信,可能是因为它是唯一一个似乎依赖于事实的人,但它只是事实的一个“数据点”。

这就是为什么我结合他的测试(使用连续分配和单独分配)和@James答案的建议。

下图显示,根据所使用的确切方案和参数,大多数答案,特别是对问题和答案的大多数评论可以被认为是完全错误或真实的。

请注意,我的初始问题是在n = 100.000 。 这一点(偶然)表现出特殊的行为:

  1. 它在一个和两个循环版本之间存在最大的差异(几乎是三分之一)

  2. 这是唯一的一点,其中一个循环(即连续分配)胜过双循环版本。 (这使得Mysticial的答案成为可能。)

使用初始化数据的结果:

使用未初始化数据的结果(这是Mysticial测试的):

这是一个难以解释的问题:初始化数据,分配一次并重复用于以下每个不同矢量大小的测试用例:

提案

应该要求上的每个低级性能相关问题为整个缓存相关数据大小提供MFLOPS信息! 浪费每个人的时间来思考答案,特别是在没有这些信息的情况下与他人讨论答案。




我不能复制这里讨论的结果。

我不知道糟糕的基准代码是否应该受到责备,或者是什么,但是这两种方法在我的机器上使用下面的代码在10%之内,并且一个循环通常只比两个快一点 - 就像你一样期望。

阵列大小范围从2 ^ 16到2 ^ 24,使用八个循环。 我小心地初始化了源数组,所以+=赋值并没有要求FPU添加被解释为double的内存垃圾。

我玩了各种方案,例如将b[j]d[j]InitToZero[j]放在循环内的InitToZero[j] ,并使用+= b[j] = 1+= d[j] = 1 ,我得到了相当一致的结果。

正如您所料,使用InitToZero[j]在循环内初始化bd使得组合方法具有优势,因为它们在分配给ac之前背靠背地完成,但仍然在10%之内。 去搞清楚。

硬件是戴尔XPS 8500,具有第3代Core i7 @ 3.4 GHz和8 GB内存。 对于2 ^ 16到2 ^ 24,使用八个循环,累积时间分别为44.987和40.965。 Visual C ++ 2010,完全优化。

PS:我改变了循环以倒数到零,并且组合方法稍微快一点。 抓我的头。 请注意新的数组大小和循环计数。

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

我不确定为什么MFLOPS是一个相关指标。 我的想法是关注内存访问,所以我试着最小化浮点计算时间。 我离开了+= ,但我不确定为什么。

没有计算的直接分配将是对存储器访问时间的更清晰的测试,并且无论循环计数如何都将创建均匀的测试。 也许我在谈话中遗漏了一些东西,但值得三思。 如果加号未被分配,则累计时间几乎相同,每次31秒。




在进一步分析这一点后,我相信这是(至少部分地)由四个指针的数据对齐引起的。 这将导致某种程度的缓存库/方式冲突。

如果我已经正确猜出了如何分配数组,它们很可能与页面行对齐

这意味着每个循环中的所有访问都将采用相同的缓存方式。 但是,英特尔处理器暂时具有8路L1缓存关联性。 但实际上,表现并不完全一致。 访问4种方式仍然比说2种方式慢。

编辑:它实际上看起来像你分别分配所有数组。 通常,当请求这样大的分配时,分配器将从OS请求新的页面。 因此,大量分配很可能出现在与页边界相同的偏移处。

这是测试代码:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

基准结果:

编辑: 实际 Core 2架构机器上的结果:

2 x Intel Xeon X5482 Harpertown @ 3.2 GHz:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

观察:

  • 一个循环6.206秒 ,两个循环2.116秒 。 这完全再现了OP的结果。

  • 在前两个测试中,阵列是分开分配的。 您会注意到它们都具有相对于页面的相同对齐方式。

  • 在后两个测试中,阵列被打包在一起以打破对齐。 在这里你会发现两个循环都更快。 此外,第二个(双)循环现在是您通常所期望的较慢的循环。

正如@Stephen Cannon在评论中指出的那样,这种对齐很可能会导致加载/存储单元或缓存中的错误混叠 。 我用Google搜索,发现英特尔实际上有一个硬件计数器用于部分地址别名停顿:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

5个地区 - 解释

1区:

这个很容易。 数据集非常小,以至于性能受到诸如循环和分支之类的开销的支配。

2区:

这里,随着数据大小的增加,相对开销量下降,性能“饱和”。 这里有两个循环较慢,因为它有两倍的循环和分支开销。

我不确定究竟发生了什么......当Agner Fog提到缓存库冲突时, Alignment仍然会起作用。 (那个链接是关于Sandy Bridge的,但这个想法仍应适用于Core 2.)

3区:

此时,数据不再适合L1缓存。 因此性能受到L1 < - > L2缓存带宽的限制。

4区:

单循环中的性能下降是我们所观察到的。 并且如上所述,这是由于对齐(最有可能)导致处理器加载/存储单元中的错误混叠停顿。

但是,为了发生错误混叠,数据集之间必须有足够大的步幅。 这就是为什么你在3区没有看到这个。

5区:

此时,没有任何东西适合缓存。 所以你受内存带宽的限制。




原始问题

为什么一个循环比两个循环慢得多?

结论:

案例1是一个经典的插值问题,恰好是一个低效的问题。 我还认为这是为什么许多机器架构和开发人员最终构建和设计具有多线程应用程序以及并行编程能力的多核系统的主要原因之一。

从这种方法看它,而不涉及硬件,操作系统和编译器如何协同工作以进行涉及使用RAM,缓存,页面文件等的堆分配; 作为这些算法基础的数学证明了这两者中的哪一个是更好的解决方案。 我们可以使用一个类比,其中一个BossSummation代表一个必须在工人AB之间旅行的For Loop ,我们可以很容易地看到案例2至少是1/2 ,如果不是比案例1多一点,由于旅行所需距离的差异和工人之间的时间差异。 这个数学几乎完全符合Bench Mark Times以及装配说明中的差异。

我现在开始解释下面的所有这些是如何工作的。

评估问题

OP的代码:

const int n=100000;

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}

for(int j=0;j<n;j++){
    a1[j] += b1[j];
}
for(int j=0;j<n;j++){
    c1[j] += d1[j];
}

考虑

考虑OP关于for循环的两个变体的原始问题以及他对缓存行为的修正问题以及许多其他优秀答案和有用的评论; 我想通过对这种情况和问题采取不同的方法来尝试做一些与众不同的事情。

该方法

考虑到两个循环以及关于缓存和页面归档的所有讨论,我想采用另一种方法来从不同的角度来看待这个问题。 一个不涉及缓存和页面文件,也不涉及分配内存的执行,实际上这种方法甚至根本不涉及实际的硬件或软件。

透视

在查看代码一段时间之后,很明显问题是什么以及产生什么。 让我们将其分解为一个算法问题,并从使用数学符号的角度来看待它,然后对数学问题和算法进行类比。

我们所知道的

我们知道他的循环将运行100,000次。 我们也知道a1b1c1d1是64位架构的指针。 在32位机器上的C ++中,所有指针都是4个字节,而在64位机器上,它们的大小是8个字节,因为指针具有固定长度。 我们知道在两种情况下我们都有32个字节可供分配。 唯一的区别是我们在每次迭代时分配32个字节或2个2-8字节集合,在第二种情况下,我们为每个独立循环的每次迭代分配16个字节。因此,两个循环在总分配中仍然等于32个字节。有了这些信息,我们继续展示它的一般数学,算法和类比。我们知道在两种情况下必须执行相同集合或操作组的次数。我们知道在两种情况下都需要分配的内存量。我们可以评估两种情况之间分配的总体工作量大致相同。

我们不知道的

我们不知道每个案件需要多长时间,除非我们设置一个柜台并进行基准测试。然而,基准分数已经包含在原始问题和一些答案和评论中,我们可以看到两者之间存在显着差异,这就是这个问题对这个问题的整体推理以及对它的回答。首先。

我们来调查吧

很明显,许多人已经通过查看堆分配,基准测试,查看RAM,缓存和页面文件来完成此操作。还包括了特定的数据点和特定的迭代索引,关于这个特定问题的各种对话让很多人开始质疑其他相关的事情。那么我们如何通过使用数学算法并对其进行类比来开始研究这个问题呢?我们首先做几个断言!然后我们从那里构建我们的算法。

我们的断言:

  • 我们将让循环及其迭代成为一个从1开始并以100000结束而不是从循环开始的Summation,因为我们不需要担心内存寻址的0索引方案,因为我们只对它感兴趣算法本身。
  • 在这两种情况下,我们有4个函数可以使用,2个函数调用,每个函数调用都有2个操作。因此,我们将设置这些函数和函数调用是F1()F2()f(a)f(b)f(c)f(d)

算法:

第一种情况: - 只有一次求和,但有两次独立的函数调用。

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

第二种情况: - 两个总结但每个都有自己的函数调用。

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

如果您注意到F2()只存在于Sum两者Sum1Sum2仅包含的位置F1()。当我们开始断定第二种算法发生了某种优化时,这也将在后面明显。

通过第一个案例Sum调用的迭代f(a)将添加到它自己,f(b)然后它调用f(c)将执行相同但f(d)为每个调用添加自身100000 iterations。在第二种情况下,我们有Sum1Sum2并且两者的行为相同,就好像它们是连续两次调用的相同函数一样。在这种情况下,我们可以把Sum1Sum2作为只是普通的老Sum地方Sum在这种情况下是这样的:Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }现在这看起来像一个优化,我们可以只考虑它是相同的功能。

类比摘要

根据我们在第二种情况下看到的情况,它几乎看起来好像存在优化,因为两个for循环具有相同的精确签名,但这不是真正的问题。这个问题是不是正在做的工作f(a)f(b)f(c)f(d)在这两种情况下,以及两者之间的比较是在求和在这两种情况下,让你在执行时间的不同行驶的距离差。

的认为For Loops作为是Summations,做迭代作为一个Boss被发号施令两个人AB与他们的工作是肉CD分别拿起从他们一些包并返回它。在这里类比,for循环或求和迭代和条件检查本身实际上并不代表Boss。什么实际上代表了Boss这里是无法直接从实际的数学算法,但是从实际的概念ScopeCode Block的例程或子例程,方法,功能,翻译单元等内的第一算法具有1个范围,其中第二算法具有2连续范围。

在每个调用单上的第一种情况下,Boss转到A并给出订单然后A去获取B's包然后Boss转到C并给出命令以执行相同的操作并从D每次迭代接收包。

在第二种情况下,Boss直接A用于去获取B's包,直到收到所有包。然后Boss工作与C获取所有D's包相同。

由于我们正在使用8字节指针并处理堆分配,所以我们在这里考虑这个问题。让我们说Boss距离AA是100英尺,距离是500英尺C。由于执行的顺序,我们不需要担心Boss最初的距离C。在这两种情况下,Boss最初从A第一次到第二次旅行B。这个类比并不是说这个距离是准确的;它只是一个使用测试用例场景来显示算法的工作原理。在许多情况下,在进行堆分配并使用缓存和页面文件时,地址位置之间的这些距离在差异上可能不会有太大变化,或者它们可能非常显着地取决于数据类型的性质和数组大小。

测试用例:

第一种情况:在第一次迭代时,Boss必须首先走100英尺才能让订单滑到AA离开并完成他的工作,但随后Boss必须行驶500英尺C才能给他订单。然后在下一次迭代和每次其他迭代之后,Boss必须在两者之间来回500英尺。

第二种情况: The Boss在第一次迭代时必须行进100英尺A,但在此之后他已经在那里并等待A回到所有滑倒。然后Boss必须在第一次迭代时行进500英尺C因为C距离500英尺,A因为这Boss( Summation, For Loop )是在工作之后立即调用A,然后就像他一样等待A直到所有C's订单单完成。

旅行距离的差异

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

任意价值观的比较

我们可以很容易地看到600远远低于1000万。现在这不完全正确,因为我们不知道RAM的地址与每个迭代的每个调用的Cache或Page File之间的距离的实际差异是由于许多其他看不见的变量,但这只是评估从最坏情况下要注意并试图查看的情况。

因此,通过这些数字,几乎看起来算法一应该比算法二慢99%; 然而,这只是The Boss's部分或算法的责任,它不占实际工作者ABC,和D他们必须在每回路的每个迭代做什么。所以老板的工作只占工作总量的15-40%。因此,通过工人完成的大部分工作对将速度差异的比率保持在约50-70%有轻微的影响

观察: - 两种算法之间的差异

在这种情况下,它是正在完成工作的过程的结构,它确实表明案例2从具有类似函数声明和定义的部分优化两者中更有效,其中它只是名称不同的变量。我们还看到案例1中的总行进距离比案例2中的距离远得多,我们可以认为这个距离在两个算法之间传递了我们的时间因子案例1案例2做了大量工作。这也是在证据中看到的ASM两个案例之间都显示出来。即使已经说了这些情况是什么,它也不会考虑的事实,案例1的老板将不得不等待两个AC找回之前,他可以回到A对下一次迭代一次也没有按不能说明如果A或者B是否需要很长时间,那么Boss其他工人和其他工人也在闲置等待。在案例2中,唯一一个闲置的是Boss工人回来之前。所以即使这对算法也有影响。

OPs修订问题

编辑:问题证明是无关紧要的,因为行为严重依赖于数组(n)和CPU缓存的大小。因此,如果有进一步的兴趣,我重新提出这个问题:

您能否提供一些有关导致不同缓存行为的详细信息,如下图中的五个区域所示?

通过为这些CPU提供类似的图表,指出CPU /缓存架构之间的差异也可能是有趣的。

关于这些问题

正如我毫无疑问地证明的那样,即使在涉及硬件和软件之前也存在潜在的问题。现在关于内存和缓存以及页面文件等的管理,它们在以下各项系统之间协同工作:The Architecture{硬件,固件,一些嵌入式驱动程序,内核和ASM指令集},The OS{文件和内存管理系统,驱动程序和注册表},The Compiler{源代码的翻译单元和优化},甚至Source Code自身及其独特的算法集;我们已经可以看到,有是第一种算法中发生的事情之前,我们甚至可以与任意适用于任何机器的瓶颈ArchitectureOSProgrammable Language与第二种算法相比。因此在涉及现代计算机的内在函数之前就已存在问题。

结局结果

然而;并不是说这些新问题不重要,因为它们本身就是,而且它们确实起了作用。它们确实会对程序和整体绩效产生影响,这一点可以从许多给出答案和/或评论的图表和评估中看出来。如果你留意的类比Boss和两名工人AB谁过的去,并从中检索包CD分别与考虑问题的两种算法的数学符号,你可以看到,如果没有计算机,甚至参与Case 2大约为60%比...快Case 1 当您将这些算法应用于源代码后查看图形和图表,通过操作系统进行编译和优化并执行以在给定硬件上执行操作时,您甚至会看到这些算法之间的差异稍微降低。

现在,如果“数据”组是相当小的,它可能看起来不差的都坏在第一,但因为Case 1是约60 - 70%慢于Case 2我们可以看看这个函数的增长是在执行时间的不同条件是:

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

这个近似值是这两个循环在算法和机器操作之间的平均差异,涉及软件优化和机器指令。因此,当数据集线性增长时,两者之间的时间差也是如此。算法1比算法2个取时,这是显而易见Boss不得不来回之间的最大距离AC对于第一次迭代后,每一次迭代,而算法2 Boss辗转去A一次,然后正在做用后A,他不得不前往从A去往的最大距离只有一次C

所以试着把Boss注意力集中在同时做两件相似的事情并且来回摆弄他们而不是专注于类似的连续任务,这将使他在一天结束时非常生气,因为他必须旅行和工作两倍。因此,让老板陷入内插瓶颈,因为老板的配偶和孩子不会欣赏它,因此不会失去这种情况的范围。




第二个循环涉及更少的缓存活动,因此处理器更容易满足内存需求。




On a rather unrelated note: more performance hacks!

  • [the first «conjecture» has been finally debunked by @ShreevatsaR; removed]

  • When traversing the sequence, we can only get 3 possible cases in the 2-neighborhood of the current element N (shown first):

    1. [even] [odd]
    2. [odd] [even]
    3. [even] [even]

    To leap past these 2 elements means to compute (N >> 1) + N + 1 , ((N << 1) + N + 1) >> 1 and N >> 2 , respectively.

    Let`s prove that for both cases (1) and (2) it is possible to use the first formula, (N >> 1) + N + 1 .

    Case (1) is obvious. Case (2) implies (N & 1) == 1 , so if we assume (without loss of generality) that N is 2-bit long and its bits are ba from most- to least-significant, then a = 1 , and the following holds:

    (N << 1) + N + 1:     (N >> 1) + N + 1:
    
            b10                    b1
             b1                     b
           +  1                   + 1
           ----                   ---
           bBb0                   bBb
    

    where B = !b . Right-shifting the first result gives us exactly what we want.

    QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1 .

    As proven, we can traverse the sequence 2 elements at a time, using a single ternary operation. Another 2× time reduction.

The resulting algorithm looks like this:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

Here we compare n > 2 because the process may stop at 2 instead of 1 if the total length of the sequence is odd.

[EDIT:]

Let`s translate this into assembly!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

Use these commands to compile:

nasm -f elf64 file.asm
ld -o file file.o

See the C and an improved/bugfixed version of the asm by Peter Cordes on Godbolt . (editor's note: Sorry for putting my stuff in your answer, but my answer hit the 30k char limit from Godbolt links + text!)





c++ c performance compiler-optimization vectorization