Warum verbessert dies die Leistung?
Ich habe zwei for-Schleifen, die grundsätzlich in zwei verschiedenen Arrays (jede mit einer Größe von etwa 2-4k in der Spitze) nachschlagen und einen Wert in einem dritten Array basierend auf diesen Werten setzen. Aus irgendeinem seltsamen Grund gibt es einen Faktor zwei Unterschied zwischen der Leistung dieses Stückes des Codes abhängig davon, in welcher Reihenfolge ich die zwei for Schleifen setze.
Dies ist das erste Setup. Es läuft in ~ 150 Millisekunden auf meinem PC:
%Vor%Wenn ich jetzt nur die Reihenfolge der Schleifen ändere,
%Vor%Die Gesamtlaufzeit der Methode sinkt auf ca. 400 Millisekunden. Wie verbessert ein einfacher Austausch der Schleifenreihenfolge die Leistung um fast 300%? Ich nehme an, es ist eine Art Caching oder Pointer Performance-Ding?
6 Antworten
Es ist eine Sache der Datenanordnung. Stellen Sie sich Speicher als eindimensionales Array vor. So werden die Dinge tatsächlich auf dem Datenträger angeordnet (was den Computer betrifft). Wenn Sie also mehrdimensionale Arrays erstellen, ändern Sie bei der Änderung der Schleifenreihenfolge, wie das Array durchlaufen wird. Anstatt in der richtigen Reihenfolge zu lesen, springen Sie von Position zu Position.
Ein mehrdimensionales Array sieht für Sie so aus:
Und so zum Computer. Die optimale Art zu verfahren hat folgende Indizes:
Wenn Sie also Ihre Array-Schleifen ändern, wird das Array wie folgt durchlaufen:
Damit erhalten Sie mehr Cache-Misses und einen schlechteren Algorithmus.
Es hängt sehr wahrscheinlich mit den Cache-Treffern zusammen. Der Unterschied liegt im sequentiellen vs verstreuten Zugriff, der in der Größe über der Größe einer Cache-Zeile liegt.
Für einfache C ++ - Schleifen würde es auch hilfreich sein, die Schleifen rückwärts zu machen, um ein wenig Leistung in der Schleife zu erhalten. Nicht sicher, wie es für .NET passt.
Es ist eine Sache der Datenanordnung. Stellen Sie sich Speicher als eindimensionales Array vor. So werden die Dinge tatsächlich auf dem Datenträger angeordnet (was den Computer betrifft). Wenn Sie also mehrdimensionale Arrays erstellen, ändern Sie bei der Änderung der Schleifenreihenfolge, wie das Array durchlaufen wird. Anstatt in der richtigen Reihenfolge zu lesen, springen Sie von Position zu Position.
Ein mehrdimensionales Array sieht für Sie so aus:
Und so zum Computer. Die optimale Art zu verfahren hat folgende Indizes:
Wenn Sie also Ihre Array-Schleifen ändern, wird das Array wie folgt durchlaufen:
Damit erhalten Sie mehr Cache-Misses und einen schlechteren Algorithmus.
Ich habe zwei for-Schleifen, die grundsätzlich in zwei verschiedenen Arrays (jede mit einer Größe von etwa 2-4k in der Spitze) nachschlagen und einen Wert in einem dritten Array basierend auf diesen Werten setzen. Aus irgendeinem seltsamen Grund gibt es einen Faktor zwei Unterschied zwischen der Leistung dieses Stückes des Codes abhängig davon, in welcher Reihenfolge ich die zwei for Schleifen setze.
Dies ist das erste Setup. Es läuft in ~ 150 Millisekunden auf meinem PC:
%Vor%Wenn ich jetzt nur die Reihenfolge der Schleifen ändere,
%Vor%Die Gesamtlaufzeit der Methode sinkt auf ca. 400 Millisekunden. Wie verbessert ein einfacher Austausch der Schleifenreihenfolge die Leistung um fast 300%? Ich nehme an, es ist eine Art Caching oder Pointer Performance-Ding?
Ich würde auch denken, dass die relativen Größen der Arrays a und b einen Unterschied machen würden.
Wenn a.length groß und b.length klein ist, sollte die zweite Option schneller sein. Umgekehrt, wenn a.length klein und b.length groß ist, wäre die erste Option schneller. Das Problem besteht darin, die Setup / Teardown-Kosten der inneren Schleife zu vermeiden.
BTW, warum haben Sie
int aLen = a.Länge;
Aber ruf dann auch a.Length direkt an? Scheint so, als ob du das eine oder das andere wählen solltest.
Ihre Intuition ist richtig, es ist ein Caching-Problem. @Mike Daniels Beitrag zur Frage unten beschreibt im Wesentlichen genau das gleiche Problem. Das zweite Bit Code wird weit mehr Cache-Treffer bekommen.
Schnellste Möglichkeit, ein 2D-Array zu durchlaufen?
Aber, shhhh, wir sollten uns nicht um die Leistung kümmern, oder? :)
Ich erinnere mich daran, darüber in Code Complete gelesen zu haben. In den meisten Sprachen sind Arrays so eingerichtet, dass der letzte Index sequenziell eingerichtet ist. Sie greifen also beim Iterieren über den letzten Index direkt auf Bytes zu, anstatt beim Iterieren über den ersten Index zu springen.
Ort, Ort, Ort der Daten. Aus Wikipedia (was es besser sagt als ich):
Lineare Datenstrukturen: Lokalität tritt häufig auf, weil Code Schleifen enthält, die dazu neigen, Arrays oder andere Datenstrukturen durch Indizes zu referenzieren. Sequentielle Lokalität, ein spezieller Fall von räumlicher Lokalität, tritt auf, wenn relevante Datenelemente linear angeordnet und zugänglich sind. Zum Beispiel würde das einfache Durchlaufen von Elementen in einem eindimensionalen Array von der Basisadresse bis zum höchsten Element die sequentielle Lokalität des Arrays im Speicher ausnutzen. [2] Die allgemein äquidistante Lokalität tritt auf, wenn die lineare Traversierung über einem längeren Bereich benachbarter Datenstrukturen mit identischer Struktur und Größe liegt und zusätzlich dazu nicht die gesamten Strukturen zugänglich sind, sondern nur die einander entsprechenden gleichen Elemente der Strukturen. Dies ist der Fall, wenn eine Matrix als sequentielle Matrix von Zeilen dargestellt wird und die Anforderung besteht, auf eine einzelne Spalte der Matrix zuzugreifen.
Es hängt sehr wahrscheinlich mit den Cache-Treffern zusammen. Der Unterschied liegt im sequentiellen vs verstreuten Zugriff, der in der Größe über der Größe einer Cache-Zeile liegt.
Für einfache C ++ - Schleifen würde es auch hilfreich sein, die Schleifen rückwärts zu machen, um ein wenig Leistung in der Schleife zu erhalten. Nicht sicher, wie es für .NET passt.
Ihre Intuition ist richtig, es ist ein Caching-Problem. @Mike Daniels Beitrag zur Frage unten beschreibt im Wesentlichen genau das gleiche Problem. Das zweite Bit Code wird weit mehr Cache-Treffer bekommen.
Schnellste Möglichkeit, ein 2D-Array zu durchlaufen?
Aber, shhhh, wir sollten uns nicht um die Leistung kümmern, oder? :)
Ich würde auch denken, dass die relativen Größen der Arrays a und b einen Unterschied machen würden.
Wenn a.length groß und b.length klein ist, sollte die zweite Option schneller sein. Umgekehrt, wenn a.length klein und b.length groß ist, wäre die erste Option schneller. Das Problem besteht darin, die Setup / Teardown-Kosten der inneren Schleife zu vermeiden.
BTW, warum haben Sie
int aLen = a.Länge;
Aber ruf dann auch a.Length direkt an? Scheint so, als ob du das eine oder das andere wählen solltest.
Ich erinnere mich daran, darüber in Code Complete gelesen zu haben. In den meisten Sprachen sind Arrays so eingerichtet, dass der letzte Index sequenziell eingerichtet ist. Sie greifen also beim Iterieren über den letzten Index direkt auf Bytes zu, anstatt beim Iterieren über den ersten Index zu springen.
Tags und Links optimization arrays c#