我刚刚阅读了一篇 article由 Rico Mariani 撰写，关注给定不同位置、架构、对齐和密度的内存访问性能。

作者构建了一个不同大小的数组，其中包含一个带有 int 载荷的双向链表，该载荷被洗牌到一定百分比。他对这个列表进行了试验，并在他的机器上发现了一些一致的结果。

引用结果表之一:

Pointer implementation with no changes
sizeof(int*)=4   sizeof(T)=12
  shuffle   0%  1%  10% 25% 50% 100%
    1000    1.99    1.99    1.99    1.99    1.99    1.99
    2000    1.99    1.85    1.99    1.99    1.99    1.99
    4000    1.99    2.28    2.77    2.92    3.06    3.34
    8000    1.96    2.03    2.49    3.27    4.05    4.59
   16000    1.97    2.04    2.67    3.57    4.57    5.16
   32000    1.97    2.18    3.74    5.93    8.76    10.64
   64000    1.99    2.24    3.99    5.99    6.78    7.35
  128000    2.01    2.13    3.64    4.44    4.72    4.80
  256000    1.98    2.27    3.14    3.35    3.30    3.31
  512000    2.06    2.21    2.93    2.74    2.90    2.99
 1024000    2.27    3.02    2.92    2.97    2.95    3.02
 2048000    2.45    2.91    3.00    3.10    3.09    3.10
 4096000    2.56    2.84    2.83    2.83    2.84    2.85
 8192000    2.54    2.68    2.69    2.69    2.69    2.68
16384000    2.55    2.62    2.63    2.61    2.62    2.62
32768000    2.54    2.58    2.58    2.58    2.59    2.60
65536000    2.55    2.56    2.58    2.57    2.56    2.56

作者解释:

This is the baseline measurement. You can see the structure is a nice round 12 bytes and it will align well on x86. Looking at the first column, with no shuffling, as expected things get worse and worse as the array gets bigger until finally the cache isn't helping much and you have about the worst you're going to get, which is about 2.55ns on average per item.

但是在 32k 项左右可以看到一些非常奇怪的东西:

The results for shuffling are not exactly what I expected. At small sizes, it makes no difference. I expected this because basically the entire table is staying hot in the cache and so locality isn't mattering. Then as the table grows you see that shuffling has a big impact at about 32000 elements. That's 384k of data. Likely because we've blown past a 256k limit.

Now the bizarre thing is this: after this the cost of shuffling actually goes down, to the point that later on it hardly matters at all. Now I can understand that at some point shuffled or not shuffled really should make no difference because the array is so huge that runtime is largely gated by memory bandwidth regardless of order. However... there are points in the middle where the cost of non-locality is actually much worse than it will be at the endgame.

What I expected to see was that shuffling caused us to reach maximum badness sooner and stay there. What actually happens is that at middle sizes non-locality seems to cause things to go very very bad... And I do not know why :)

所以问题是:是什么导致了这种意外行为？

我已经考虑了一段时间，但没有找到好的解释。测试代码对我来说看起来不错。我不认为 CPU 分支预测是这种情况下的罪魁祸首，因为它应该早于 32k 项就可以观察到，并且显示出更轻微的峰值。

我已经在我的盒子上确认了这种行为，它看起来几乎完全一样。

我认为这可能是由 CPU 状态的转发引起的，所以我更改了行和/或列生成的顺序 - 输出几乎没有差异。为了确保，我为更大的连续样本生成了数据。为了方便查看，我把它放到了excel中:

And another independent run for good measure, negligible difference

最佳答案

我把我最好的理论放在这里:http://blogs.msdn.com/b/ricom/archive/2014/09/28/performance-quiz-14-memory-locality-alignment-and-density-suggestions.aspx#10561107但这只是一个猜测，我还没有证实。

谜团解开了!来 self 的博客:

2014 年 9 月 29 日，周一上午 9:35 #

等等 - 您是否得出结论，对于非常大的情况，完全随机访问与顺序访问的速度相同？那将是非常令人惊讶的!

rand() 的范围是多少？如果它是 32k，则意味着您只是对前 32k 个项目进行洗牌，并对大型案例中的大多数项目进行基本顺序读取，并且每个项目的平均值将变得非常接近顺序案例。这与您的数据非常匹配。

2014 年 9 月 29 日星期一上午 10:57 #

就是这样!

rand 函数返回 0 到 RAND_MAX (32767) 范围内的伪随机整数。在调用 rand 之前，使用 srand 函数播种伪随机数生成器。

我需要一个不同的随机数生成器!

我会重做的!

关于performance - 是什么导致*中等*数量的项目的性能出现这种奇怪的下降？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26098129/