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

Ich habe eine Liste von 500000 zufällig generierten Tuple<long,long,string>Objekten, für die ich eine einfache "Zwischen" -Suche 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 suche x, sind die Suchvorgänge in etwa vier Sekunden abgeschlossen. Da ich die großen Wunder kannte, die das Sortieren mit der Suche bewirkt , entschied ich mich jedoch, meine Daten zu sortieren - zuerst nach Item1, dann nach Item2und schließlich nach Item3-, bevor ich meine 100 Suchvorgänge durchführte. Ich hatte erwartet, dass die sortierte Version aufgrund der Verzweigungsvorhersage etwas schneller funktioniert: Ich dachte, sobald wir den Punkt erreicht haben Item1 == x, an dem alle weiteren Überprüfungen t.Item1 <= xdie Verzweigung korrekt als "no take" vorhersagen würden, würde dies den hinteren Teil der Verzweigung beschleunigen Suche. Zu meiner großen Überraschung dauerte die Suche in einem sortierten Array doppelt so lange !

Ich habe versucht, die Reihenfolge zu ändern, in der ich meine Experimente ausgeführt habe, und habe einen anderen Startwert für den Zufallszahlengenerator verwendet, aber der Effekt war der gleiche: Die Suche in einem unsortierten Array lief fast doppelt so schnell wie die Suche in demselben Array, aber sortiert!

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

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

Wenn Sie die Liste sortieren, ordnen Sie sie in zufälliger Reihenfolge an, da Ihre Sortierschlüssel zufällig generiert werden. Dies bedeutet, dass die Speicherzugriffe auf Tupelmitglieder nicht vorhersehbar sind. Die CPU kann keinen Speicher vorab abrufen und fast jeder Zugriff auf ein Tupel ist ein Cache-Fehler.

Dies ist ein schönes Beispiel für einen besonderen Vorteil der GC-Speicherverwaltung : Datenstrukturen, die zusammen zugewiesen wurden und zusammen verwendet werden, arbeiten sehr gut. Sie haben eine große Referenzlokalität .

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

Versuchen Sie, zu einem structTupel zu wechseln . Dadurch wird die Leistung wiederhergestellt, da zur Laufzeit keine Zeiger-Dereferenzierung erforderlich ist, um auf Tupel-Mitglieder zuzugreifen.

Chris Sinclair merkt in den Kommentaren an, dass "für TotalCount um 10.000 oder weniger die sortierte Version schneller arbeitet ". Dies liegt daran, dass eine kleine Liste vollständig in den CPU-Cache passt . Die Speicherzugriffe sind möglicherweise nicht vorhersehbar, aber das Ziel befindet sich 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 mehrere ausstehende Lasten jonglieren und dadurch den Durchsatz erhöhen kann. Immer wenn die CPU auf den Speicher wartet, beschleunigt sie im Befehlsstrom, um so viele Speicheroperationen wie möglich in die Warteschlange zu stellen. Diese Technik wird verwendet, um die Latenz zu verbergen.

Diese Art von Verhalten zeigt, wie schwierig es ist, die Leistung moderner CPUs vorherzusagen. Die Tatsache, dass wir beim Übergang vom sequentiellen zum zufälligen Speicherzugriff nur zweimal langsamer sind, sagt mir, wie viel unter der Decke vor sich geht, 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.

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

Da Count with predicate parameter eine Erweiterungsmethode für alle IEnumerables ist, weiß es meiner Meinung nach nicht einmal, ob es mit effizientem Direktzugriff über die Sammlung läuft. Es überprüft also einfach jedes Element und Usr erklärte, warum die Leistung geringer wurde.

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