Neden sıralanmış bir dizi sıralanmamış bir dizi daha yavaş işliyor?

SORU

24 Aralık 2012, PAZARTESİ

Neden sıralanmış bir dizi sıralanmamış bir dizi daha yavaş işliyor?

Hangi basit bir gösteri yapıyorum rasgele oluşturulmuş Tuple<long,long,string> 500000 nesnelerin bir listesi var "" arama: arasında

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

Rastgele dizi ve bu benim çalışma oluşturmak için 100 arayışım rastgele x arar, birkaç saniye sonra tam değerleri oluşturulur. Bilerek great wonders that sorting does to searching ancak, karar için sıralama benim veri - ilk Item1 Item2 ve son olarak Item3 - önce benim çalışan 100 arar. Beklediğim sıralanmış sürüm gerçekleştirmek için biraz daha hızlı çünkü şube tahmini: benim düşünce oldu bu kez biz sadede nerede Item1 == x, diğer tüm kontroller t.Item1 <= x olacağını tahmin şube doğru olarak "hayır", hızlandırmak kuyruk bölümünü arayın. Olması beni çok şaşırttıaramalarda iki kat daha uzun sıralanmış bir dizi aldı!

Denedim anahtarlama etrafında sırayla hangi koştum deneylerde kullanılan farklı tohum için rastgele sayı üreteci, ama etkisi aynı: aramalarda bir sıralanmamış dizi koştu neredeyse iki kat daha hızlı olarak arama aynı dizi, ama sıralanmış!

Herkes bu garip etkisi iyi bir açıklama var mı? Benim testleri kaynak kodu şöyle; kullanıyorum .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)

CEVAP

24 Aralık 2012, PAZARTESİ

Sıralanmamış listeyi kullanırken tüm dizilerini erişilebilirbellek-sipariş. RAM arka arkaya tahsis edilmiştir. CPU gerektiğinde speculatively her zaman var olacak bir sonraki önbellek satırı talep edebilirler çünkü bellek sırayla erişim seviyorum.

Liste sıralama yaparken içine koymakrastgelesenin gibiler yüzünden tuşlara rastgele oluşturulur. Bu başlığın üyelerine bellek erişir tahmin edilemez anlamına gelir. Bir demet için ve hemen hemen her bellek erişemiyor hazırlık CPU önbellek bir bayan.

Bu özel avantajı için güzel bir örnektirBellek yönetimi GCbirlikte ayrılmış ve birlikte kullanılan veri yapıları çok güzel. gerçekleştirmek Harikareferans konum.

Önbellekten cezası özlüyorkaydedilmiş şube tahmini cezası daha ağır basarbu durumda.

struct-demet geçmeyi deneyin. Bu işaretçi çözümlemesi hayır zamanında gerçekleşmesi demet üyeleri erişim gerekiyor çünkü performans geri yükler.

Chris yorum bu notlar Sinclair"10,000 veya daha az etrafında sıralanmış sürümü daha hızlı gerçekleştirmek için TotalCount". Bu küçük bir liste çünkütamamen CPU önbellek içine sığar. Bellek erişim öngörülemeyen olabilir ama hedef her zaman önbelleğidir. Önbellekten bile bir yük bazı devir alır, çünkü hala küçük bir ceza olduğuna inanıyorum. Ama bu, çünkü bu bir sorun değil gibi görünüyorCPU birden çok bekleyen yükler aldatabilirböylece verimlilik artıyor. CPU bellek için bir bekleme vurur zaman hala talimat akışında önceden mümkün olduğunca çok sayıda bellek işlemleri sıraya hızlandıracaktır. Bu teknik, gecikme gizlemek için kullanılır.

Bu tür bir davranış modern CPU performansını tahmin etmek için nasıl gösterir. Olduğumuz gerçeğisadece 2x yavaşsıralı rastgele bellek erişim altında oluyor bana nasıl gidiyor, bellek gecikme gizlemek kapsar. Bellek erişim 50-200 devir için CPU yavaşlamayı. Bu sayı verilen program ^ olmak için bekleyebilir . Rastgele bellek erişimi tanıtırken 10x daha yavaş.

Bunu Paylaş: