首页 文章

为什么处理排序数组比未排序数组慢?

提问于
浏览
226

我有一个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 值时,搜索将在大约四秒钟内完成 . 但是,知道了great wonders that sorting does to searching,我决定在运行100次搜索之前对我的数据进行排序 - 首先是 Item1 ,然后是 Item2 ,最后是 Item3 . 我期望排序版本由于分支预测而执行得更快一些:我的想法是,一旦我们到达 Item1 == xt.Item1 <= x 的所有进一步检查将正确预测分支为"no take",加快了搜索的尾部 . 令我惊讶的是, the searches took twice as long on a sorted array

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

有没有人对这种奇怪的效果有一个很好的解释?我的测试的源代码如下;我使用的是.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)

2 回答

  • 259

    LINQ不知道您的列表是否已排序 .

    由于具有谓词参数的Count是所有IEnumerables的扩展方法,我认为它不会通过高效的随机访问来运行集合 . 因此,它只是检查每个元素,Usr解释了性能降低的原因 .

    要利用排序数组的性能优势(例如二进制搜索),您将不得不进行更多编码 .

  • 3

    当您使用未排序的列表时,在 memory-order 中访问所有元组 . 它们已在RAM中连续分配 . CPU喜欢顺序访问内存,因为它们可以推测性地请求下一个缓存行,因此它将在需要时始终存在 .

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

    对于 GC memory management 的特定优势,这是一个很好的例子:已经分配在一起并且一起使用的数据结构执行得非常好 . 他们有很棒的 locality of reference .

    缓存中的惩罚在这种情况下未命中 outweighs the saved branch prediction penalty .

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

    Chris Sinclair在评论中指出,“对于TotalCount大约10,000或更少,排序版本确实执行得更快” . 这是因为一个小清单 fits entirely into the CPU cache . 内存访问可能是不可预测的,但目标始终在缓存中 . 我相信仍有一个小的惩罚,因为即使缓存加载需要一些周期 . 但这似乎不是一个问题,因为 CPU can juggle multiple outstanding loads ,从而提高了吞吐量 . 每当CPU命中等待内存时,它仍将在指令流中加速,以尽可能多地排队内存操作 . 此技术用于隐藏延迟 .

    这种行为表明在现代CPU上预测性能有多难 . 从顺序存储器访问到随机存储器访问时我们是 only 2x slower 的事实告诉我隐藏内存延迟的情况下有多少 . 内存访问可以使CPU停顿50-200个周期 . 鉴于第一个人可能期望在引入随机存储器访问时程序变得慢10倍 .

相关问题