为什么处理sorting数组比sorting数组慢？
我有一个500000个随机生成的Tuple<long,long,string>对象的列表，我正在执行一个简单的“between”search：
var data = new List<Tuple<long,long,string>>(500000); ... var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
当我生成我的随机数组并运行search100个随机生成的x值时，search将在大约四秒钟内完成。 知道sortingsearch的好处 ，然而，我决定先sorting我的数据 – 首先是Item1 ，然后是Item2 ，最后是Item3 – 在运行我的100次search之前。 由于分支预测，我预计分类后的版本会执行得更快一些：我的想法是，一旦我们到达了Item1 == x ，对t.Item1 <= x所有进一步检查都会正确地预测分支为“no采取“，加快了search的尾部。 令我惊讶的是， search花了两倍的时间在一个有序的数组上 ！
我尝试转换我运行实验的顺序，并为随机数生成器使用了不同的种子，但效果相同：在未sorting数组中的search运行速度几乎是同一数组中search的两倍，但sorting！
有没有人有这个奇怪的效果很好的解释？ 我的testing源代码如下; 我正在使用.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)
当你使用未sorting列表时，所有的元组都按照内存顺序被访问。 它们已经在RAM中连续分配了。 CPU喜欢顺序访问内存，因为它们可以推测性地请求下一个caching行，所以在需要时它总是存在。
当你对列表进行sorting时，由于你的sorting键是随机生成的，因此将它放入随机顺序 。 这意味着访问元组成员的内存是不可预知的。 CPU不能预取内存，几乎每个对元组的访问都是caching未命中。
对于GC内存pipe理的一个特殊优势，这是一个很好的例子：一起分配和一起使用的数据结构performance得非常好。 他们有很好的参考地点 。
在这种情况下，来自caching未命中的处罚超过了保存的分支预测处罚 。
尝试切换到一个struct -tuple。 这将恢复性能，因为在运行时不需要指针取消引用来访问元组成员。
Chris Sinclair在评论中指出： “对于大约10,000或更less的TotalCount，sorting的版本确实执行得更快 ”。 这是因为一个小列表完全适合CPUcaching 。 内存访问可能是不可预知的，但目标总是在caching中。 我相信还有一点小小的损失，因为即使是来自caching的负载也需要一些周期。 但这似乎不成问题，因为CPU可以处理多个未完成的负载 ，从而提高吞吐量。 每当CPU等待内存时，它仍然会在指令stream中向前排队，尽可能地排队尽可能多的内存操作。 这种技术被用来隐藏延迟。
这种行为表明预测现代CPU性能的难度。 事实上，从顺序访问到随机访问内存的速度只有两倍 ，这说明我们在底层隐藏了多less内存来隐藏内存延迟。 内存访问可能会使CPU停止50-200个周期。 考虑到第一个人可能期望程序在引入随机存储器访问时变慢了10倍以上。
LINQ不知道你的列表是否sorting。
由于带谓词参数的Count是所有IEnumerables的扩展方法，我想它甚至不知道它是否以高效的随机访问在集合上运行。 所以，它只是简单地检查每一个元素，而Usr解释了为什么性能降低。
为了利用sorting数组的性能优势（比如二进制search），你将不得不做更多的编码。
