为什么处理排序后的数组要比未排序的数组慢？

我有一个500000个随机生成的Tuple<long,long,string>对象的列表，我正在其上执行一个简单的“between”搜索：

var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);

当我生成我的随机数组并运行我的搜索以获得100个随机生成的x值时，搜索将在大约4秒内完成。 但是，我知道排序对搜索有很大的好处，因此我决定先排序我的数据 - 首先按Item1 ，然后按Item2排序，最后按Item3排序 - 然后再运行100次搜索。 由于分支预测，我预计分类后的版本会执行得更快一些：我的想法是，一旦我们到达了Item1 == x ，对t.Item1 <= x所有进一步检查都可以正确预测分支为“no采取“，加快搜索的尾部。 令我惊讶的是， 搜索在排序后的阵列上花了两倍的时间 ！

我尝试切换执行我的实验的顺序，并使用不同的种子作为随机数生成器，但效果相同：未排序数组中的搜索运行速度几乎是同一数组中搜索的两倍，但排序！

有没有人有这个奇怪的影响很好的解释？ 我的测试源代码如下; 我正在使用.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)

---

当你使用未排序列表时，所有的元组都以内存顺序访问。 它们已经在RAM中连续分配。 CPU喜欢顺序访问内存，因为它们可以推测性地请求下一个缓存行，以便在需要时始终存在。

在对列表进行排序时，由于您的排序键是随机生成的，因此将它放入随机顺序中 。 这意味着访问元组成员的内存是不可预知的。 CPU不能预取内存，几乎每个对元组的访问都是缓存未命中。

这对于GC内存管理的特定优势来说是一个很好的例子：已经分配在一起并且一起使用的数据结构表现得非常好。 他们有很好的参考地点 。

在这种情况下，来自缓存未命中的处罚超过了保存的分支预测处罚 。

尝试切换到struct -tuple。 这将恢复性能，因为在运行时不需要使用指针取消引用来访问元组成员。

克里斯辛克莱在评论中指出，“对于大约10,000或更少的TotalCount，排序后的版本确实执行得更快”。 这是因为一个小列表完全适合CPU缓存 。 内存访问可能是不可预测的，但目标总是在缓存中。 我相信还是有一点小小的损失，因为即使是来自缓存的负载也需要一些周期。 但这似乎不成问题，因为CPU可以处理多个未完成的负载 ，从而提高吞吐量。 无论CPU何时等待内存，它都会在指令流中加速前进，以尽可能地排队尽可能多的内存操作。 该技术用于隐藏延迟。

这种行为表明预测现代CPU性能有多难。 事实上，从顺序访问到随机内存访问速度只有两倍 ，这告诉我隐藏内存延迟的时间有多少。 内存访问可能会使CPU停止50-200个周期。 在引入随机存储器访问的情况下，预计该程序的速度会降低10倍以上。

---

LINQ不知道你的列表是否被排序。

由于使用predicate参数的Count是所有IEnumerables的扩展方法，我认为它甚至不知道它是否以高效的随机访问在集合上运行。 所以，它只是检查每个元素，Usr解释了为什么性能降低。

为了利用排序数组的性能优势（比如二进制搜索），你必须做更多的编码。

链接地址: http://www.djcxy.com/p/827.html

上一篇: Why is processing a sorted array slower than an unsorted array?

下一篇: Is < faster than <=?