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

const int n=100000;

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

这种循环是通过另一个外部for循环执行 10000 次。为了加快它,更改到的代码︰

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.0SSE2启用了 32 位英特尔酷睿 2双核处理器 (x64) 上,第一个示例采用 5.5 秒并双循环示例仅为 1.9 秒。我的问题是: (请参阅我在底部的 rephrased 的问题)

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︰完整代码http://pastebin.com/ivzkuTzGTBB Tick_Count 用于高分辨率计时,可以通过未定义 TBB_TIMING 宏被禁用。

(它显示垂直/s n的不同值.)

enter image description here

2011-12-17 20:40:52
问题评论:

可能这将减缓在搜索时的物理内存访问它,并且有一些像相同的 memblock 次访问时缓存每次操作系统。

正在编译优化?看起来像很多 asm 代码为 O2...

我要求看起来是不久前的一个类似的问题它也没有回答有感兴趣的信息。

只是为了能办到,下列两个代码段并不等效由于可能重叠指针。C99 都有这种情况下的restrict关键字。我不知道是否 MSVC 具有类似。当然,如果这是问题然后 SSE 代码不会正确。

这可能有一些与内存锯齿。使用一个循环, d1[j]可能与 aliase a1[j],因此编译器无法做某些内存 optimisations 可退。虽然不会发生如果您分隔两个环路中内存作品。

回答:

对此进一步分析,我认为这 (至少部分) 由四个指针的数据对齐方式。这将导致某种级别的缓存银行中的方法冲突。

如果我已经猜到正确上如何分配您的阵列,它们可能会对齐到页面行.

这意味着所有您访问包含在每个循环将落在同一缓存的方式。但是,英特尔处理器有一段有 8 路 L1 缓存关联。但事实上,性能并不完全统一。访问 4 方式是仍然低于说 2 种。

编辑︰ 它实际上看起来像单独分配的所有阵列。通常在这种大分配请求,分配器会从操作系统请求新页。因此,没有大的分配将出现在相同的偏移量,从页面边界高机会。

以下是测试代码︰

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;
}

基准检验结果︰

编辑︰ 结果实际酷睿 2 体系结构的计算机上︰

2 x @ 3.2 g h z 的英特尔至强 X5482 Harpertown:

#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

观察结果︰

  • 与一个循环和带有两个环路2.116 秒 6.206 秒这完全重现 OP 的结果。

  • 在前两个测试中,分别分配数组。您会注意到他们都有同一个相对于页面对齐方式。

  • 在两个测试中,数组一起打包,准备该对齐方式。这里,您会发现这两种循环的速度较快。此外,第二个 (双线) 循环是通常像预期的那样的速度较慢的一个。

作为 @Stephen Cannon 意见中指出,没有很可能,这种对齐方式会导致的假锯齿加载/存储单位或缓存中的可能性。我周围的 Googled 和发现英特尔实际上具有硬件计数器,对于部分地址别名停滞︰

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


5 区域的说明

地区 1:

这一个问题很简单。数据集是那么小,性能主要由如循环和分支的系统开销。

区域 2:

在这里,随着数据大小的增加,相对消耗的资源量下降和性能"会饱和"。这两个循环是慢,因为它具有两倍的循环和分支系统开销。

我不知道这里发生什么完全...对齐方式仍能播放效果,如 Agner 雾中提到了缓存银行冲突(链接有关 Sandy Bridge 但仍思路应该是适用于核心 2。

区域 3:

在这种情况下,数据不再适合在 L1 缓存中。L1 两端各带性能使 <>-L2 缓存带宽。

区域 4:

在单循环性能下降是我们观察。并提到,这是因为这 (很可能) 会导致假锯齿隔在处理器加载/存储单位的对齐方式。

但是,为了使假锯齿出现,必须有足够大的数据集之间步长。这就是为什么您看不到此区域 3 中。

地区 5:

在这种情况下,不适合在高速缓存中。因此所受的内存带宽。


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz

+ 1︰ 我认为这是答案。与所有其他答案说了什么,但并不是单一循环变量本身就拥有更多的缓存未命中数,它即将导致缓存未命中数组的特定的对齐方式。

这;假的锯齿隔栏是最有可能的解释。

@VictorT。我使用操作链接到代码。它生成的.css 文件的我可以在 Excel 中打开,请从该关系图。

@Nawaz 页通常是 4 KB。如果您看一下我打印出的十六进制地址,所有的单独分配的测试有 4096 模相同。(这是 4KB 边界开始从 32 个字节)也许是 GCC 没有这种现象。它能解释为什么不能查看的差异。

每个人都感兴趣,这里是好内存对齐方式的阅读这里有几个链接的方式在内存中缓存的数据

好了,正确答案肯定有做一些 CPU 高速缓存。但使用缓存参数可能会非常困难,尤其是没有数据。

有许多的答案,导致了大量的讨论,但让我们面对现实吧︰ 高速缓存问题可能会非常复杂,并不是一维。他们严重依赖的大小的数据,所以我的问题是 unfiar︰ 它被证明是缓存图中非常有趣的时刻。

@Mysticial 的答案相信很多人 (包括我),可能因为它依赖的事实,似乎只有一个,但它是真实的只有一个"数据点"。

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

下面的图表显示的大部分答案和特别是意见的问题和答案大部分可以被认为是 complelety 错误或根据具体的情况和使用参数,则返回 true。

请注意,我最初的问题是在n = 100.000此点 (偶然) 表现出特殊的行为︰

  1. 它拥有一个和两个 loop'ed 版本 (几乎三个因子) 之间的最大差异

  2. 它是唯一点,其中一个循环 (即具有连续分配) 节拍的两个循环版本。(这使 Mysticial 在所有应答可能,)。

结果使用初始化数据︰

Enter image description here

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

Enter image description here

这也是难解释一个︰ Initilized 的数据,进行一次分配和重用于不同向量大小的每个以下测试用例︰

Enter image description here

计划书

在堆栈溢出每个低级别性能相关的问题需要提供相关的数据的高速缓存大小的整个范围的 MFLOPS 信息 !它是时间的浪费每个人进行思考的答案和特别讨论这些与其他人没有这些信息。

+ 1 好分析。我没有打算离开事先未初始化的数据。它只被发生,分配器零它们仍。因此,初始化的数据是重要的内容。我刚编辑过的我的答案与实际酷睿 2 体系结构上的结果,它们是很接近所观察。另一件事是,我测试各种大小n ,它显示的相同的性能差距n = 80000, n = 100000, n = 200000,等等...

第二个循环涉及很少的缓存活动,以便更容易的处理器,以跟上内存需求。

你所说的第二个变量会导致更少的缓存未命中数?为什么?

@Oli︰ 在第一个款式,处理器需要访问四个内存线路在时间- a[i]b[i]c[i]d[i]中的第二个变量,它需要两个。这使得更加可行,同时添加重填这些行。

但只要阵列不在高速缓存中发生碰撞,每种款式要求完全相同数量的读取并写入从到主内存中。因此结论是 (我认为),这些两个数组碰巧冲突的所有时间。

@Oli︰ 但所有行都需要读取一次,在第一个 variant 类型的值。在第二个处理器可以延迟读取两个数组。

我不追随。每个指令 (即每个实例的x += y),有两次读取和一次写入。这适用于任一变体。高速缓存 <>-CPU 带宽需求因此是相同的。只要不有任何冲突,<>-缓存内存带宽要求也是相同。.

假设您正在使用一台计算机,其中n是只是右边的它只是为了能够在同一时间,在内存中保存您的阵列中的两个价值但总内存可用,通过磁盘缓存,仍不足以容纳所有四个。

假定有简单的后进先出缓存策略,这段代码︰

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

第一次将导致a1b1可以被加载到内存,然后要处理的完全在内存中。在第二循环开始, c1d1都将从磁盘加载到内存并对其进行操作。

其他循环

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

将两个数组和其他两个每次循环中的页的页。这显然是慢。

您可能不会看到磁盘缓存在测试中,但您可能会看到其他窗体缓存的副作用。


似乎有点混乱/误解此处以便将试图详细阐述一些使用的示例。

n = 2和我们使用的字节数。因此我的方案中有只是 4 个字节的高速缓存和戴尔内存的其余部分则要慢得多 (长说 100 次访问)。

假设相当笨字节是不在缓存中,并将其置于其中,得到下的一个字节太时我们是否在它的缓存策略将收到方案如下所示︰

  • 使用

    for(int j=0;j<n;j++){
     a1[j] += b1[j];
    }
    for(int j=0;j<n;j++){
     c1[j] += d1[j];
    }
    
  • 高速缓存a1[0]a1[1]然后b1[0]b1[1]并设置a1[0] = a1[0] + b1[0]在缓存-现在有四个字节在缓存中, a1[0], a1[1]b1[0], b1[1]成本 = 100 + 100。

  • 设置a1[1] = a1[1] + b1[1]高速缓存中。成本 = 1 + 1。
  • 重复这些步骤c1和 ' d1。
  • 总成本 = (100 + 100 + 1 + 1) * 2 = 404

  • 使用

    for(int j=0;j<n;j++){
     a1[j] += b1[j];
     c1[j] += d1[j];
    }
    
  • 高速缓存a1[0]a1[1]然后b1[0]b1[1]并设置a1[0] = a1[0] + b1[0]在缓存-现在有四个字节在缓存中, a1[0], a1[1]b1[0], b1[1]成本 = 100 + 100。

  • 弹出a1[0], a1[1], b1[0], b1[1]从缓存和缓存c1[0]c1[1]然后d1[0]d1[1]并设置c1[0] = c1[0] + d1[0]高速缓存中。成本 = 100 + 100。
  • 我怀疑您也开始,我将。
  • 总成本 = (100 + 100 + 100 + 100) * 2 = 800

这是一个经典的缓存的 thrash 方案。

这是不正确的。对数组的特定元素的引用不会导致整个阵列从磁盘 (或非缓存内存); 中分页相关页或缓存行被调进。

@Brooks Moses-如果您遍历整个数组,发生在这里,然后它将。

嗯,是的但它是怎样通过整个操作,不会出现每次周围循环。您已声明,第二个窗体"将页出两个数组和网页中的其他两个周围循环,该循环的每次",这就是我在 objecting 的到。无论整个数组的大小,此循环的中间存放在 RAM 中的页面的四个阵列,每个,并没有将获得调出直到循环结束与其后也。

在特定的情况下,其中n 是只是右边的它只是为了能将保留在内存中一次您的阵列中的两个价值然后访问在一个循环中的四个数组的所有元素肯定必须最终失效。

为什么您保持完整的a1b1的第一次赋值,该环 2 页面,而不是只是它们中的每个的第一页?(您假设 5 字节的页,因此页面是 RAM 的一半?已不只比例,完全不同于真实的处理器的。)

它是不是因为不同的代码,而是由于缓存︰ RAM 比 CPU 寄存器和高速缓存位于 CPU 以避免每次更改变量写入内存。但随着 ram 缓存不大,因此,映射只有它的一小部分。

第一个代码修改远内存地址交替它们在每个循环中,这样就需要不断地使缓存无效。

不替换第二个代码︰ 它只是流动在相邻的地址上两次。这样,要完成在缓存中,使它无效,只有在第二循环开始后的所有作业。

为什么这会导致缓存持续失效?

@OliCharlesworth︰ 到缓存视为一个连续的内存地址范围的硬拷贝。如果假装访问地址不是其中的一部分,则必须重新加载缓存。和如果高速缓存中的某些内容已被修改,它不得不写回在 RAM 中,或将会丢失。在示例代码中,4 000 100"整数 (400kBytes) 的矢量是最有可能超过 L1 缓存 (128 或 256 K) 的容量。

在这种情况下,缓存的大小没有任何影响。每个数组元素只能使用一次,和之后的不安,它被驱逐。缓存大小仅有要求,如果有临时所在地 (即您要在以后重复使用相同的元素)。

@OliCharlesworth︰ 如果我必须加载缓存中的新值和已有一个值在其中被 modifyed、 我第一次有把它写下来,和这样我等待写入发生。

但操作码的两个变种,在获取一次修改的每个值。这样做相同数量的每个变体中的写回。

请输入您的翻译

Why is one loop so much slower than two loops?

确认取消