为什么元素级的添加在单独的循环中比在组合循环中要快得多？

Question

为什么元素级的添加在单独的循环中比在组合循环中要快得多？

假设a1, b1, c1，和d1指向堆内存，我的数字代码有下面的核心循环。

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上编译Visual C+10.0完全优化SSE 2上的32位启用。英特尔核心2Duo(X64)，第一个示例耗时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/缓存体系结构之间的差异也可能很有趣。

Answer 1

好的，正确的答案一定要对CPU缓存做些什么。但是使用缓存参数是相当困难的，特别是没有数据。有许多答案，这导致了很多讨论，但让我们面对它：缓存问题可能是非常复杂的，不是一维的。它们在很大程度上取决于数据的大小，所以我的问题是不公平的：结果是缓存图中的一个非常有趣的点。@神秘的答案说服了很多人(包括我)，可能是因为它是唯一一个似乎依赖事实的答案，但它只是真理的一个“数据点”。这就是为什么我结合了他的测试(使用连续的和单独的分配)和@James的答案的建议。下面的图表显示，大多数答案，特别是对问题和答案的大多数评论，都可以被认为是完全错误或正确的，这取决于所使用的确切场景和参数。请注意，我最初的问题是n=100.000..这一点(偶然)表现出特殊的行为：它有一个和两个循环版本之间最大的差异(几乎是三倍)。这是唯一的一点，其中单循环(即连续分配)超过了两个循环版本。(这使得神秘的答案成为可能。)使用初始化数据的结果：使用未初始化数据的结果(这是神秘测试的结果)：这是一个很难解释问题：初始化数据，只分配一次，并被用于每一个向量大小不同的测试用例：提案每个与堆栈溢出有关的低级别性能问题都应该被要求为整个缓存的相关数据大小提供MFLOPS信息！这是浪费每个人的时间去思考答案，特别是在没有这些信息的情况下与其他人讨论这些问题。

Answer 2

想象一下你在一台机器上工作n是正确的值，因为它只能一次在内存中容纳两个数组，但是通过磁盘缓存可用的总内存仍然足以容纳所有四个数组。假设有一个简单的LIFO缓存策略，以下代码：for(int&nbsp;j=0;j<n;j++){ &nbsp;&nbsp;&nbsp;&nbsp;a[j]&nbsp;+=&nbsp;b[j];}for(int&nbsp;j=0;j<n;j++){ &nbsp;&nbsp;&nbsp;&nbsp;c[j]&nbsp;+=&nbsp;d[j];}会首先引起a和b加载到RAM中，然后完全在RAM中工作。当第二个循环开始时，c和d然后从磁盘加载到RAM中并对其进行操作。另一个循环for(int&nbsp;j=0;j<n;j++){ &nbsp;&nbsp;&nbsp;&nbsp;a[j]&nbsp;+=&nbsp;b[j]; &nbsp;&nbsp;&nbsp;&nbsp;c[j]&nbsp;+=&nbsp;d[j];}将分出两个数组，并在另外两个数组中分页。每次绕圈..这显然是多慢点。您可能没有在测试中看到磁盘缓存，但是您可能看到了其他形式的缓存的副作用。这里似乎有点混乱/误解，所以我会尝试用一个例子来解释一下。说n = 2我们用的是字节。在我的场景中，我们有内存只有4字节我们剩下的内存要慢得多(比如100倍的访问时间)。假设一个相当愚蠢的缓存策略如果字节不在缓存中，则将其放在缓存中，并在缓存中获取以下字节您将得到这样的场景：带着for(int&nbsp;j=0;j<n;j++){ &nbsp;a[j]&nbsp;+=&nbsp;b[j];}for(int&nbsp;j=0;j<n;j++){ &nbsp;c[j]&nbsp;+=&nbsp;d[j];}高速缓存a[0]和a[1]然后b[0]和b[1]并设定a[0] = a[0] + b[0]在缓存中-缓存中现在有四个字节，a[0], a[1]和b[0], b[1]..费用=100+100。集a[1] = a[1] + b[1]在缓存中。费用=1+1。重复c和d.总费用=(100 + 100 + 1 + 1) * 2 = 404带着for(int&nbsp;j=0;j<n;j++){ &nbsp;a[j]&nbsp;+=&nbsp;b[j]; &nbsp;c[j]&nbsp;+=&nbsp;d[j];}高速缓存a[0]和a[1]然后b[0]和b[1]并设定a[0] = a[0] + b[0]在缓存中-缓存中现在有四个字节，a[0], a[1]和b[0], b[1]..费用=100+100。弹出a[0], a[1], b[0], b[1]从缓存和缓存c[0]和c[1]然后d[0]和d[1]并设定c[0] = c[0] + d[0]在缓存中。费用=100+100。我怀疑你开始看到我要去哪里了。总费用=(100 + 100 + 100 + 100) * 2 = 800这是一个经典的缓存处理场景。