Mengapa memproses array yang diurutkan lebih lambat dari pada array yang tidak disortir?

Saya memiliki daftar 500.000 Tuple<long,long,string>objek yang dibuat secara acak di mana saya melakukan pencarian "antara" sederhana:

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

Ketika saya menghasilkan array acak saya dan menjalankan pencarian saya untuk 100 nilai yang dihasilkan secara acak x, pencarian selesai dalam waktu sekitar empat detik. Mengetahui keajaiban besar yang dilakukan sorting terhadap pencarian , saya memutuskan untuk menyortir data saya - pertama Item1, kemudian Item2, dan akhirnya Item3- sebelum menjalankan 100 pencarian saya. Saya mengharapkan versi yang disortir untuk melakukan sedikit lebih cepat karena prediksi cabang: pemikiran saya adalah bahwa begitu kita sampai pada titik di mana Item1 == x, semua pemeriksaan lebih lanjut t.Item1 <= xakan memprediksi cabang dengan benar sebagai "tidak mengambil", mempercepat bagian ekor dari Cari. Yang mengejutkan saya, pencarian memakan waktu dua kali lebih lama pada array yang diurutkan !

Saya mencoba beralih di sekitar urutan saya menjalankan eksperimen, dan menggunakan seed berbeda untuk generator angka acak, tetapi efeknya sama: pencarian dalam array yang tidak disortir berjalan hampir dua kali lebih cepat daripada pencarian dalam array yang sama, tetapi disortir!

Adakah yang punya penjelasan bagus tentang efek aneh ini? Kode sumber pengujian saya mengikuti; Saya menggunakan .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)

Saat Anda menggunakan daftar yang tidak disortir, semua tuple diakses dalam urutan memori . Mereka telah dialokasikan secara berurutan dalam RAM. CPU suka mengakses memori secara berurutan karena mereka secara spekulatif dapat meminta baris cache berikutnya sehingga selalu ada saat diperlukan.

Ketika Anda menyortir daftar, Anda memasukkannya ke dalam urutan acak karena kunci sortir Anda dibuat secara acak. Ini berarti bahwa akses memori ke anggota tuple tidak dapat diprediksi. CPU tidak dapat mengambil memori lebih dulu dan hampir setiap akses ke tuple adalah cache miss.

Ini adalah contoh yang bagus untuk keuntungan spesifik dari manajemen memori GC : struktur data yang telah dialokasikan bersama dan digunakan bersama berfungsi dengan sangat baik. Mereka memiliki lokalitas referensi yang bagus .

Penalti dari cache gagal melebihi hukuman prediksi cabang yang disimpan dalam kasus ini.

Coba beralih ke struct-tuple. Ini akan mengembalikan kinerja karena tidak perlu pointer-dereference terjadi saat runtime untuk mengakses anggota tuple.

Chris Sinclair mencatat dalam komentar bahwa "untuk TotalCount sekitar 10.000 atau kurang, versi yang disortir berkinerja lebih cepat ". Ini karena daftar kecil sepenuhnya cocok dengan cache CPU . Akses memori mungkin tidak dapat diprediksi tetapi target selalu dalam cache. Saya percaya masih ada penalti kecil karena bahkan memuat dari cache memerlukan beberapa siklus. Tapi itu tampaknya tidak menjadi masalah karena CPU dapat menyulap beberapa beban yang luar biasa , sehingga meningkatkan throughput. Setiap kali CPU menunggu memori, CPU masih akan mempercepat dalam aliran instruksi untuk mengantri sebanyak mungkin operasi memori. Teknik ini digunakan untuk menyembunyikan latensi.

Perilaku semacam ini menunjukkan betapa sulitnya untuk memprediksi kinerja pada CPU modern. Fakta bahwa kita hanya 2x lebih lambat ketika beralih dari akses memori berurutan ke acak, katakan padaku berapa banyak yang terjadi di bawah selimut untuk menyembunyikan latensi memori. Akses memori dapat menghentikan CPU selama 50-200 siklus. Mengingat bahwa nomor satu dapat mengharapkan program menjadi> 10x lebih lambat ketika memperkenalkan akses memori acak.

LINQ tidak tahu apakah daftar Anda diurutkan atau tidak.

Karena Hitung dengan parameter predikat adalah metode ekstensi untuk semua IEnumerables, saya pikir itu bahkan tidak tahu apakah itu berjalan koleksi dengan akses acak yang efisien. Jadi, itu hanya memeriksa setiap elemen dan Usr menjelaskan mengapa kinerja semakin rendah.

Untuk memanfaatkan manfaat kinerja array yang diurutkan (seperti pencarian biner), Anda harus melakukan sedikit lebih banyak pengkodean.