das*_*ght 231 .net c# language-agnostic performance
我有一个500000随机生成的Tuple<long,long,string>对象列表,我在其上执行一个简单的"之间"搜索:
var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
当我生成随机数组并运行我的搜索100个随机生成的值时x,搜索在大约四秒内完成.知道了的伟大奇迹的整理确实给搜索,但是,我决定把我的排序数据-首先Item1,然后Item2,最后由Item3运行我的100次的搜索之前- .我期望排序版本由于分支预测而执行得更快一些:我的想法是,一旦我们达到这一点Item1 == x,所有进一步检查t.Item1 <= x将正确地预测分支为"不接受",加快了尾部的速度.搜索.令我惊讶的是,搜索在排序的阵列上花了两倍的时间!
我尝试切换运行实验的顺序,并为随机数生成器使用不同的种子,但效果是一样的:在未排序的数组中搜索的速度几乎是同一数组中搜索的两倍,但是排序!
有没有人对这种奇怪的效果有一个很好的解释？我的测试的源代码如下; 我使用的是.NET 4.0.
private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
var data = new byte[8];
r.NextBytes(data);
return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
var res = x.Item1.CompareTo(y.Item1);
if (res != 0) return res;
res = x.Item2.CompareTo(y.Item2);
return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
}
}
static void Test(bool doSort) {
var data = new List<Tuple<long,long,string>>(TotalCount);
var random = new Random(1000000007);
var sw = new Stopwatch();
sw.Start();
for (var i = 0 ; i != TotalCount ; i++) {
var a = NextLong(random);
var b = NextLong(random);
if (a > b) {
var tmp = a;
a = b;
b = tmp;
}
var s = string.Format("{0}-{1}", a, b);
data.Add(Tuple.Create(a, b, s));
}
sw.Stop();
if (doSort) {
data.Sort(new TupleComparer());
}
Console.WriteLine("Populated in {0}", sw.Elapsed);
sw.Reset();
var total = 0L;
sw.Start();
for (var i = 0 ; i != TotalQueries ; i++) {
var x = NextLong(random);
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
total += cnt;
}
sw.Stop();
Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
Test(false);
Test(true);
Test(false);
Test(true);
}
Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)
usr*_*usr 267
当您使用未排序列表时,将按内存顺序访问所有元组.它们已在RAM中连续分配.CPU喜欢顺序访问内存,因为它们可以推测性地请求下一个缓存行,以便在需要时始终存在.
当您对列表进行排序时,您将其按随机顺序排列,因为您的排序键是随机生成的.这意味着对元组成员的内存访问是不可预测的.CPU无法预取内存,几乎每次访问元组都是缓存未命中.
这是GC内存管理特定优势的一个很好的例子:已经分配在一起并一起使用的数据结构表现得非常好.他们有很好的参考地点.
在这种情况下,缓存未命中的惩罚超过了保存的分支预测惩罚.
尝试切换到struct-tuple.这将恢复性能,因为在运行时不需要指针取消引用来访问元组成员.
Chris Sinclair在评论中指出,"对于TotalCount大约10,000或更少,排序版本确实执行得更快 ".这是因为一个小列表完全适合CPU缓存.内存访问可能是不可预测的,但目标始终在缓存中.我相信仍有一个小的惩罚,因为即使缓存加载需要一些周期.但这似乎不是一个问题,因为CPU可以处理多个未完成的负载,从而提高吞吐量.每当CPU命中等待内存时,它仍将在指令流中加速,以尽可能多地排队内存操作.此技术用于隐藏延迟.
这种行为表明在现代CPU上预测性能有多难.从顺序存储器访问到随机存储器访问时,我们的速度只有2倍,这一事实告诉我隐藏内存延迟的情况有多少.内存访问可以使CPU停顿50-200个周期.鉴于第一号可以预期程序在引入随机存储器访问时会变慢> 10倍.