performance - 为什么一个循环反而比两个循环慢呢?

  显示原文与译文双语对照的内容

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


const int n=100000

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

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


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

上编译 MS 视觉 C++ 10.0 进行全面优化和 SSE2 上为 32位 启用睿 2 Duo ( x64 ),第一个示例接受 5.5秒和double-loop示例仅需 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/缓存架构,通过提供一个类似 graph.

PPS: 完整代码 is位于 http://pastebin.com/ivzkuTzG 。 它使用 TBB Tick_Count来获得更高的分辨率,它可以通过不定义TBB_TIMING宏而被禁用。

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

enter image description here

时间:

在进一步分析之后,我相信这是由四个指针的数据对齐引起的。 这将导致某些级别的缓存银行/路径冲突。

如果我已经猜到你是如何分配你的阵列上正确,他们 很可能会被对齐到页线

这意味着每个循环中的所有访问都会在同一个缓存上。 然而,英特尔处理器有 8 -way L1缓存的关联性。 但实际上,性能并不是完全一致的。 访问 4 -ways仍比说 2 -ways慢。

收费:它实际上看起来像你在分配所有的数组。 通常,当请求这么大的分配时,分配器会请求来自操作系统的新页面。 因此,较大的分配会出现在与page-boundary相同的偏移量上。

下面是测试代码:


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 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 秒有两个循环。 这将重新生成操作的结果。

  • 前两个测试中的,数组分别分配。 你会注意到它们都有相同的对齐方式。

  • 在第二个测试中的,数组被打包在一起,以打破对齐。 在这里你会注意到两个循环都是快速的。 另外,第二个( 双线) 循环现在比通常预期的慢。

就像 @Stephen 大炮指出在评论中,很有可能可能会忘,该对齐方式会导致 虚假混叠 在加载/存储单位或者缓存中。 为此周围我google了一下,发现英特尔有一个叫做硬件计数器用于 分部地址别名 熄火:

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:

single-loop中的性能下降就是我们正在观察的。 在处理器负载/存储units,和如前所述,这是由于对位其中( 最有可能) 导致 虚假混叠 stalls.

但是,为了产生假别名,数据集之间必须有足够的步长。 这就是你在区域 3中看不到的原因。

区域 5:

现在,没有什么适合缓存。 所以你受到了内存带宽的限制。


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

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

有很多答案,这导致了很多讨论,但让我们面对: 缓存问题可能非常复杂并且不是一维的。 它们依赖于数据的大小,所以我的问题是 unfiar: 在缓存图中,它是一个非常有趣的点。

@Mysticial's 回答了很多人的( 包括我),可能是因为它是唯一一个依赖事实的人,但它只是事实的一个"数据点"。

这就是为什么我把他的测试( 使用连续 vs 独立分配) 和 @James'建议结合起来。

对确切的方案和参数 used,,下面的图表显示了出来,这里的大多数答案,尤其是广大的回应,问题和答案可以被视为complelety错误或者真 depending.

注意,我最初的问题是以英镑为单位的 = 100.000. 这一点( 意外) 显示特殊行为:

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

  2. 这是唯一的一点,one-loop ( 即连续分配) 打败了two-loop版本。 ( 这使得Mysticial的回答完全可行) 。

使用初始化数据的结果:

Enter image description here

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

Enter image description here

这是一个 hard-to-explain: Initilized数据,它被分配一次,并为不同向量大小的后续测试用例重用:

Enter image description here

提案

所有关于堆栈溢出的低级性能相关问题都需要提供MFLOPS信息,以便为缓存相关数据大小提供信息 ! 在没有这里信息的情况下,考虑答案,尤其是与其他人讨论答案是浪费时间。

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

假设你正在使用一个机器,其中 n 只是一个正确的值,它只允许在内存中同时保存两个数组,但通过磁盘缓存,总的内存仍然足以容纳所有四个。

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


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

首先将 a1b1 加载到RAM中,然后完全在RAM中工作。 当第二个循环启动时,c1d1 将从磁盘装载到RAM并运行。

另一个循环


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场景。

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

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

第二个代码不能替代: 它只在相邻地址上流动两次。 这使得所有作业都在缓存中完成,只有在第二个循环启动后才会失效。

因为CPU没有这么多缓存丢失的( 它必须等待阵列数据来自RAM芯片) 。 你可以调整大小的数组不断的是很有趣的,以便你在 1级别超过该尺寸的缓存 ( L1 ),然后 2级别的缓存 ( L2 ),你的中央处理器和 plot 所花费的时间你的代码来执行这里对象的大小的数组。 图形应该不是你期望的直线。

我无法复制这里讨论的结果。

我不知道如果代码基准测试仍然是对于过失或者是差,但这两种方式彼此 10%之内使用下面的代码在我的机器上,而另一个环通常只是速度稍快于两个- 是你可以猜测。

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

我使用各种方案,比如把 b[j] 赋值,d[j]InitToZero[j]的赋值,以及使用 += b[j] = 1+= d[j] = 1 我得到了相当一致的结果。

就像你预期的那样,使用 InitToZero[j] 在循环中初始化 bd 会使组合成为一个优势,因为它们在工作分配到 ac 之前,但仍然在 10% 。 转到图。

硬件是 Dell XPS 8500 带 3 内核仿真器 @ 3.4 GHz和 8 GB内存。 对于 2 ^16到 2 ^24,使用八个循环,累计时间为 44.987和 40.965. Visual C++ 2010,完全优化。

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


//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秒内,累计时间几乎相同。

第一个循环在每个变量中交替写入。 第二个和第三个只做元素大小的小跳跃。

尝试写两条平行的20条平行线,它们与一支笔和一个由 20厘米分隔的纸交叉。 尝试一次完成一个,然后再尝试另一行,通过在每行交替写一个十字来尝试另一个时间。

语言没有速度的概念,它允许你进行这样的比较。 一种编程语言规范的"时间单位"可能说"至少得花费最多//恰好n的时间单位来完成x 操作",但它不会下个定义。 这是一个由实现引入的属性。

在你的情况下,你的实现是微软 Visual C++ 10.0,但这与 GNU C++ 编译器几乎不相关。 可能一个循环执行与两个循环相同的任务在你的实现中较慢,但这不是其他实现的需求。 出于同样的原因,讨论速度与对齐和CPU缓存的速度是不合适的。 在同一machine,上每个人都有不同的处理器,并且假定你不是开发程序,它将只曾经运行。在此之前

部分 1.9程序执行,段落 1

在本国际标准的语义描述中,定义了一个参数化的,非确定的抽象机器。 这里国际标准不要求符合一致性实现的结构。 特别是,它们不需要复制或者模仿抽象机器的结构。 相反,需要一致性实现来模拟( 仅仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限仅限而已而已)的可见行为,如下面解释的。

部分 1.9程序执行,段落 8

对一致性实现的最低要求是:

—对volatile对象的访问严格按照抽象机器的规则进行评估。

在程序终止时,所有写入文件的数据都应与根据抽象语义执行程序的可能结果相同。

—交互设备的输入和输出动态应以这样一种方式进行,在程序等待输入前实际传递输出。 交互式设备的实际构成由实现定义。

这些统称为程序的可见行为。 [ 注意:抽象和实际语义之间更加严格的对应可能由每个实现定义。 —end便笺]

假设你使用了不同的编译器,它碰巧注意到它不需要为 a1b1c1 或者 d1 或者循环生成代码来改变这些对象的值,因为它们对程序的可见行为没有影响。 考虑在这种情况下可能发生什么,如果 t1-t0 == 1 。 一个智能编译器可能会优化 plain 到这个,只是为了让你:


double plain(int n,int m,int cont,int loops)
{
 return 2.0*double(n)*double(m)/0.0;
}

也许更重要的是问题: 我如何知道什么时候可能浪费时间来考虑过早的优化? 停止猜测。通过开发一个能解决实际的有用问题的工作程序来让你的雇主满意。 如果他/她说太慢了,那么就用剖析的结果并使用分析结果来确定最重要的优化。

在 multi-core PC ( 或者至少有一个带有 hyper-threading 支持的CPU ) 上执行这里操作时,这将是真的。 在创建两个独立的循环时,CPU可以轻松地将计算分割为多个 CPU 并并行执行它们,从而提高性能。

...