是什么原因导致这种奇怪的性能下降**中*数量的项目？
maf*_*afu 9 memory performance
我刚刚阅读了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
作者解释说:
这是基线测量.你可以看到结构是一个很好的圆形12字节,它将在x86上很好地对齐.看看第一列,没有改组,正如预期的那样,随着阵列变得越来越大,情况变得越来越糟,直到最后缓存没有多大帮助,你得到的是你将要得到的最差,大约是2.55ns平均每件商品.
但是在32k项目周围可以看到一些非常奇怪的东西:
洗牌的结果并不完全符合我的预期.在小尺寸,它没有任何区别.我期待这一点,因为基本上整个表都在缓存中保持热,因此局部性无关紧要.然后随着表的增长,您会发现洗牌对大约32000个元素产生了很大的影响.这是384k的数据.可能是因为我们已经超过了256k的限制.
现在奇怪的是:在此之后,洗牌的成本实际上下降了,以至于后来几乎不重要.现在我可以理解,在某些时候,洗牌或不洗牌真的应该没有区别,因为数组是如此巨大,以至于运行时很大程度上由内存带宽决定,无论顺序如何.然而......在中间有一些点,非地方的成本实际上比在最后阶段的成本要差得多.
我期待看到的是,洗牌使我们更快地达到最大的不良并留在那里.实际发生的是,在中等规模的非地方似乎导致事情变得非常糟糕......我不知道为什么:)
所以问题是:可能导致这种意外行为的原因是什么？
我已经考虑了一段时间,但没有找到好的解释.测试代码对我来说很好.我不认为CPU分支预测是这个例子中的罪魁祸首,因为它应该比32k项目早得多,并显示出更小的峰值.
我已经在我的盒子上确认了这种行为,它看起来几乎完全相同.
我认为它可能是由CPU状态转发引起的,所以我改变了行和/或列生成的顺序 - 几乎没有输出差异.为了确保,我为更大的连续样本生成了数据.为了便于查看,我把它放到了excel:
我把我最好的理论放在这里: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#
等等 - 您是否认为完全随机访问与非常大的案例的顺序速度相同？这将是非常令人惊讶的!
兰德()的范围是多少？如果它是32k,这意味着你只需要洗掉前32k项目并对大型项目中的大多数项目进行基本顺序读取,并且每项目avg将变得非常接近顺序情况.这非常符合您的数据.
星期一,2014年9月29日上午10:57#
就是这样!
rand函数返回0到RAND_MAX(32767)范围内的伪随机整数.在调用rand之前,使用srand函数为伪随机数生成器播种.
我需要一个不同的随机数生成器!
我会重做它!
| 归档时间： |
|
| 查看次数： |
274 次 |
| 最近记录： |