为什么memcpy（）的速度每4KB急剧下降？

我testing了memcpy()的速度，注意到速度在i * 4KB下急剧下降。 结果如下：Y轴是速度（MB /秒），X轴是memcpy()的缓冲区大小，从1KB增加到2MB。 图2和图3详细描述了1KB-150KB和1KB-32KB的部分。

环境：

CPU：Intel（R）Xeon（R）CPU E5620 @ 2.40GHz

OS：2.6.35-22-generic＃33-Ubuntu

GCC编译器标志：-O3 -msse4 -DINTEL_SSE4 -Wall -std = c99

我想它必须与高速caching相关，但是我无法从以下高速caching不友好的情况中find原因：

• 为什么我的程序在循环8192个元素时变慢？

• 为什么转置512×512的matrix要比转置513×513的matrix慢得多？

由于这两种情况的性能下降是由不友好的循环引起的，这些循环将零散的字节读入高速caching，浪费了高速caching行的剩余空间。

这是我的代码：

 void memcpy_speed(unsigned long buf_size, unsigned long iters){ struct timeval start, end; unsigned char * pbuff_1; unsigned char * pbuff_2; pbuff_1 = malloc(buf_size); pbuff_2 = malloc(buf_size); gettimeofday(&start, NULL); for(int i = 0; i < iters; ++i){ memcpy(pbuff_2, pbuff_1, buf_size); } gettimeofday(&end, NULL); printf("%5.3f\n", ((buf_size*iters)/(1.024*1.024))/((end.tv_sec - \ start.tv_sec)*1000*1000+(end.tv_usec - start.tv_usec))); free(pbuff_1); free(pbuff_2); } 

UPDATE

考虑到@usr，@ChrisW和@Leeor的build议，我更精确地重新进行了testing，下图显示了结果。 缓冲区大小从26KB到38KB，我testing了其他64B（26KB，26KB + 64B，26KB + 128B，……，38KB）。 每个testing在约0.15秒内循环100,000次。 有趣的是，下降不仅发生在4KB的边界上，而且还以4 * i + 2KB的方式出现，幅度下降的幅度要小得多。

PS

@Leeor提供了一种方法来填充下拉列表，在pbuff_1和pbuff_2之间添加一个2KB的虚拟缓冲区。 它有效，但我不确定Leeor的解释。

Answer 1

内存通常组织在4k页（虽然也支持更大的尺寸）。 你的程序看到的虚拟地址空间可能是连续的，但在物理内存中并不一定是这种情况。 维护虚拟地址到物理地址（在页面地图中）的映射的操作系统通常会尽量保持物理页面在一起，但这并不总是可能的，并且它们可能被破坏（特别是在长时间使用时偶尔会被交换）。

当你的内存stream超过4k页面边界时，CPU需要停止并获取一个新的翻译 – 如果它已经看到了页面，它可能被caching在TLB中，访问被优化为最快，但如果这是第一次访问（或者如果你有太多的页面供TLB使用），CPU将不得不停止内存访问并开始页面漫游页面映射条目 – 这是相当长的，因为每个级别都是事实一个内存自己读取（在虚拟机上它甚至更长，因为每个级别可能需要在主机上完整的分页）。

你的memcpy函数可能有另外一个问题 – 当第一次分配内存的时候，操作系统会把这些页面build立到页面映射中，但是由于内部的优化，将它们标记为未访问和未修改。 第一次访问不仅可以调用页面遍历，还可能是一个协助，告诉操作系统该页面将被使用（并存储到目标缓冲区页面中），这将花费一些昂贵的过渡到一些操作系统处理程序。

为了消除这种噪音，分配缓冲区一次，执行副本的几次重复，并计算摊销时间。 另一方面，这会给你“温暖”的performance（即caching变暖之后），所以你会看到caching大小反映在你的图表上。 如果你想在没有分页延迟的情况下得到一个“冷”效果，你可能需要在迭代之间刷新caching（只要确保你没有这个时间）

编辑

重读这个问题，你似乎正在做一个正确的测量。 我的解释中的问题是，在4k*i之后它应该会逐渐增加，因为在每次这样的下降之后，您都要再次支付罚款，但是在下一个4k之后应该享受免费的旅行。 这并不能解释为什么会出现这样的“尖峰”，之后速度恢复正常。

我认为你面临的问题与你的问题相关的关键步骤问题类似的问题 – 当你的缓冲区大小是一个不错的一轮4K，两个缓冲区将alignment到相同的caching集，并相互冲突。 你的L1是32k，所以它起初看起来不是什么问题，但是假设数据L1有8种方式，实际上是相同的4k环绕，并且你有2 * 4k块，具有完全相同的alignment（假设分配是连续完成的），所以它们在相同的集合上重叠。 LRU不能像你期望的那样工作就足够了，你将会一直存在冲突。

为了检查这一点，我试图malloc pbuff_1和pbuff_2之间的虚拟缓冲区，使它2K大，希望它打破了alignment。

EDIT2：

好的，因为这个工作，是时候详细一点。 假设您分配两个4karrays，范围为0x1000-0x1fff和0x2000-0x2fff 。 在L1中设置0将包含在0x1000和0x2000的行，设置1将包含0x1040和0x2040，依此类推。 在这些大小你没有任何颠簸的问题，但它们可以共存而不会溢出caching的关联性。 但是，每次你执行一个迭代，你有一个负载和一个商店访问相同的集合 – 我猜这可能会导致硬件冲突。 更糟糕的是，你需要多次迭代来复制一条线，这意味着你拥有8个负载+8个商店（如果你vector化，但仍然很多），所有针对相同的穷人集合，我很漂亮肯定会有一堆隐藏在那里的碰撞。

我还看到， 英特尔优化指南有特别的说法（见3.6.8.2）：

当代码访问两个不同的内存位置，并且在它们之间有一个4K字节的偏移时，就会发生4KB的内存别名。 4 KB的混叠情况可以在内存复制例程中体现，其中源缓冲区和目标缓冲区的地址保持恒定的偏移量，并且常量偏移量恰好是从一次迭代到下一次迭代的字节增量的倍数。

…

负载必须等到商店已经退休，然后才能继续。 例如，在偏移16处，下一次迭代的负载是4 KB别名当前迭代存储，因此循环必须等到存储操作完成后，才能使整个循环序列化。 等待所需的时间量随着偏移量的增大而减小，直到96的偏移量解决问题为止（因为在具有相同地址的加载时没有挂起的存储器）。

Answer 2

我期望这是因为：

• 当块大小为4KB倍数时， malloc从O / S分配新的页面。
• 当块大小不是4KB的倍数时， malloc从其已分配的堆中分配一个范围。
• 当从O / S分配页面时，它们是“冷的”：第一次触摸它们是非常昂贵的。

我的猜测是，如果你在第一个gettimeofday之前做了一个单一的memcpy ，那么这将会“暖化”分配的内存，你不会看到这个问题。 而不是做一个初始的memcpy，甚至在每个分配的4KB页面中写入一个字节可能足以预热该页面。

通常当我想要像你的性能testing我编码为：

 // Run in once to pre-warm the cache runTest(); // Repeat startTimer(); for (int i = count; i; --i) runTest(); stopTimer(); // use a larger count if the duration is less than a few seconds // repeat test 3 times to ensure that results are consistent 

Answer 3

既然你循环了很多次，我认为关于未被映射的页面的争论是无关紧要的。 在我看来，你所看到的是硬件预取器不愿意越过页面边界的效果，以免造成（潜在不必要的）页面错误。