c# - 为什么处理排序的数组比处理未排序的数组慢？

Question

我有一个随机生成的 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 值时, 搜索在大约四秒钟内完成。知道 great wonders that sorting does to searching , 但是，我决定对我的数据进行排序 - 首先是 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)

Answer 1

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

当您对列表进行排序时，您将其放入随机顺序，因为您的排序键是随机生成的。这意味着对元组成员的内存访问是不可预测的。 CPU 无法预取内存，几乎每次访问元组都是缓存未命中。

这是GC 内存管理 特定优势的一个很好的例子:一起分配并一起使用的数据结构表现得非常好。它们具有很好的引用位置。

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

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

Chris Sinclair 在评论中指出，“对于大约 10,000 或更少的 TotalCount，排序版本确实执行得更快”。这是因为一个小列表完全适合 CPU 缓存。内存访问可能无法预测，但目标始终在缓存中。我相信仍然有一个小的惩罚，因为即使从缓存加载也需要一些周期。但这似乎不是问题，因为 CPU 可以兼顾多个未完成的负载，从而提高吞吐量。每当 CPU 等待内存时，它仍会在指令流中加速前进，以排队尽可能多的内存操作。此技术用于隐藏延迟。

这种行为表明预测现代 CPU 的性能有多么困难。从顺序内存访问到随机内存访问时，我们只慢了 2 倍这一事实告诉我隐藏内存延迟的幕后工作有多少。内存访问可以使 CPU 停止 50-200 个周期。考虑到第一点，在引入随机内存访问时，程序会变慢 10 倍以上。