我刚刚读过Rico Mariani的article，它考虑到在不同位置，体系结构，对齐方式和密度的情况下内存访问的性能。
作者构建了一个大小可变的数组，其中包含一个带有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
但是在32k项周围可以看到一些非常奇怪的东西:
因此，问题是:可能导致这种意外行为的原因是什么？
我已经考虑了一段时间，但找不到很好的解释。测试代码对我来说看起来不错。在这种情况下，我认为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，但这只是一个猜测，我没有证实。
谜团已揭开!从我的博客:
瑞安·蒙(Ryan Mon)，2014年9月29日上午9:35＃
等待-您是否得出结论，在非常大的情况下，完全随机访问的速度与顺序访问的速度相同？那将是非常令人惊讶的!
rand()的范围是多少？如果是32k，那意味着您只是改组前32k项，并且在大写情况下对大多数项进行基本上顺序的读取，因此每个项目的平均值将非常接近顺序的情况。这与您的数据非常匹配。
2014年9月29日，星期一10:57 AM＃
就是这样!
rand函数返回0到RAND_MAX(32767)范围内的伪随机整数。在调用rand之前，使用srand函数为伪随机数生成器设定种子。
我需要一个不同的随机数生成器!
我会重做!