wake-up-neo.net

Warum ist die Verarbeitung eines sortierten Arrays langsamer als die eines nicht sortierten Arrays?

Ich habe eine Liste von 500000 zufällig generierten Tuple<long,long,string> Objekte, für die ich eine einfache Suche "zwischen" durchführe:

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

Wenn ich mein zufälliges Array generiere und nach 100 zufällig generierten Werten von x suche, sind die Suchvorgänge in ungefähr vier Sekunden abgeschlossen. In Kenntnis der Wunder, die das Sortieren bei der Suche bewirkt entschied ich mich jedoch, meine Daten zu sortieren - zuerst nach Item1, dann von Item2 und schließlich von Item3 - bevor meine 100 Suchanfragen ausgeführt werden. Ich habe erwartet, dass die sortierte Version aufgrund der Verzweigungsvorhersage etwas schneller abläuft: Ich habe gedacht, dass wir, sobald wir den Punkt erreicht haben, an dem Item1 == x, alle weiteren Prüfungen von t.Item1 <= x würde den Zweig korrekt als "no take" vorhersagen und so den Endteil der Suche beschleunigen. Zu meiner großen Überraschung dauerte die Suche in einem sortierten Array doppelt so lange!

Ich habe versucht, die Reihenfolge umzuschalten, in der ich meine Experimente durchgeführt habe, und habe für den Zufallszahlengenerator einen anderen Startwert verwendet, aber der Effekt war der gleiche: Suchen in einem unsortierten Array wurden fast doppelt so schnell ausgeführt wie Suchen in demselben Array, aber sortiert!

Hat jemand eine gute Erklärung für diesen seltsamen Effekt? Der Quellcode meiner Tests folgt; Ich benutze .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)
230
dasblinkenlight

Wenn Sie die unsortierte Liste verwenden, wird auf alle Tupel in Speicherreihenfolge zugegriffen. Sie wurden nacheinander im RAM zugewiesen. CPUs greifen am liebsten sequentiell auf den Speicher zu, weil sie spekulativ die nächste Cache-Zeile anfordern können, damit sie bei Bedarf immer vorhanden ist.

Wenn Sie die Liste sortieren, geben Sie sie in zufällige Reihenfolge ein, da Ihre Sortierschlüssel zufällig generiert werden. Dies bedeutet, dass die Speicherzugriffe auf Tuple-Mitglieder nicht vorhersehbar sind. Die CPU kann keinen Speicher vorabholen und fast jeder Zugriff auf ein Tupel ist ein Cache-Fehler.

Dies ist ein gutes Beispiel für einen besonderen Vorteil von GC-Speicherverwaltung: Datenstrukturen, die zusammen zugewiesen wurden und zusammen verwendet werden, funktionieren sehr gut. Sie haben große Ort der Referenz.

Die Strafe für Cache-Fehler überwiegt die Strafe für die gespeicherte Verzweigungsvorhersage in diesem Fall.

Versuchen Sie, zu einem struct- Tupel zu wechseln. Dadurch wird die Leistung wiederhergestellt, da zur Laufzeit keine Zeiger-Dereferenzierung erfolgen muss, um auf Tuple-Mitglieder zuzugreifen.

Chris Sinclair merkt in den Kommentaren an, dass "für TotalCount um 10.000 oder weniger die sortierte Version schneller abschneidet ". Dies liegt daran, dass eine kleine Liste passt vollständig in den CPU-Cache. Die Speicherzugriffe sind möglicherweise unvorhersehbar, das Ziel befindet sich jedoch immer im Cache. Ich glaube, es gibt immer noch eine kleine Strafe, weil selbst das Laden aus dem Cache einige Zyklen dauert. Dies scheint jedoch kein Problem zu sein, da die CPU kann mehrere ausstehende Lasten bewältigen, wodurch der Durchsatz erhöht wird. Immer wenn die CPU auf Speicher wartet, beschleunigt sie den Befehlsstrom weiter, um so viele Speicheroperationen wie möglich in die Warteschlange zu stellen. Diese Technik wird verwendet, um die Latenz auszublenden.

Diese Art von Verhalten zeigt, wie schwierig es ist, die Leistung auf modernen CPUs vorherzusagen. Die Tatsache, dass wir nur 2x langsamer sind, wenn wir von sequentiellem zu wahllosem Speicherzugriff übergehen, sagt mir, wie viel unter der Decke passiert, um die Speicherlatenz zu verbergen. Ein Speicherzugriff kann die CPU für 50-200 Zyklen blockieren. Angesichts dieser Zahl könnte man erwarten, dass das Programm> 10x langsamer wird, wenn zufällige Speicherzugriffe eingeführt werden.

264
usr

LINQ weiß nicht, ob Ihre Liste sortiert ist oder nicht.

Da Count with predicate parameter eine Erweiterungsmethode für alle IEnumerables ist, weiß sie meines Erachtens nicht einmal, ob sie die Auflistung mit effizientem Direktzugriff durchläuft. Es überprüft also einfach jedes Element und Usr erklärt, warum die Leistung geringer wurde.

Um die Leistungsvorteile eines sortierten Arrays (z. B. der binären Suche) zu nutzen, müssen Sie etwas mehr Codierung durchführen.

3
Emperor Orionii