Ich habe ein Problem bei meiner Prüfung für das Fach Principal of Programming Language. Ich dachte lange nach, aber ich verstand das Problem immer noch nicht.
Problem: Unten ist ein Programm C, das in MSVC ++ 6.0 Umgebung auf einem PC mit Konfiguration ~ CPU Intel 1,8 GHz, Ram 512 MB
ausgeführt wird %Vor%Erkläre, warum Part A nur in 1s ausgeführt wird, aber es hat B 8s zum Beenden gebraucht?
Reihen-Haupt-Reihenfolge gegen Spalten-Haupt-Reihenfolge.
Erinnern Sie sich zunächst daran, dass alle mehrdimensionalen Arrays im Speicher als zusammenhängender Speicherblock dargestellt werden. Somit könnte das mehrdimensionale Array A (m, n) im Speicher als
dargestellt werdena00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn
In der ersten Schleife durchlaufen Sie sequentiell diesen Speicherblock. Sie durchlaufen also das Array, indem Sie die Elemente in der folgenden Reihenfolge durchlaufen:
%Vor%In der zweiten Schleife springen Sie im Speicher umher und durchlaufen das Array durch die Elemente in der folgenden Reihenfolge:
%Vor%oder, vielleicht deutlicher,
%Vor%Alles, was Sie herumspringen, tut Ihnen wirklich weh, weil Sie beim Cachen keine Vorteile erzielen. Wenn Sie das Array sequenziell durchlaufen, werden benachbarte Elemente in den Cache geladen. Wenn Sie sich durch das Array bewegen, erhalten Sie diese Vorteile nicht und erhalten stattdessen Cache-Fehler, die die Leistung beeinträchtigen.
Das hat damit zu tun, wie der Speicher des Arrays ausgelegt ist und wie er in den Cache geladen und darauf zugegriffen wird: In Version A werden die Nachbarn beim Zugriff auf eine Zelle des Arrays in den Cache geladen, und der Code greift dann sofort auf diese Nachbarn zu. In Version B wird auf eine Zelle zugegriffen (und ihre Nachbarn in den Cache geladen), aber der nächste Zugriff ist in der nächsten Zeile weit entfernt, und so wurde die gesamte Cachezeile geladen, aber nur ein Wert verwendet, und eine andere Cachezeile muss für jeden Zugang gefüllt werden. Daher die Geschwindigkeitsdifferenz.
Aufgrund von Hardware-Architekturoptimierungen. Teil A führt Operationen mit sequentiellen Speicheradressen aus, wodurch die Hardware wesentlich beschleunigt, wie die Berechnungen gehandhabt werden. Teil B springt ständig im Speicher herum, was viele Hardwareoptimierungen zunichte macht.
Das Schlüsselkonzept für diesen speziellen Fall ist Prozessor-Cache .
Das Array, das Sie deklarieren, ist zeilenweise im Speicher angeordnet. Im Grunde genommen haben Sie einen großen Block von M × N ganzen Zahlen und C tut ein bisschen trickreich, um Sie glauben zu lassen, dass es rechteckig ist. Aber in Wirklichkeit ist es flach.
Wenn Sie also zeilenweise iterieren (mit M als äußere Schleifenvariable), gehen Sie wirklich linear durch den Speicher. Etwas, das der CPU-Cache sehr gut beherrscht.
Wenn Sie jedoch mit N in der äußeren Schleife iterieren, dann machen Sie immer mehr oder weniger zufällige Sprünge im Speicher (zumindest für die Hardware sieht es so aus). Sie greifen auf die erste Zelle zu, dann verschieben Sie M Integer weiter und machen dasselbe, usw. Da Ihre Seiten im Speicher in der Regel 4 KiB groß sind, bewirkt dies, dass für jede Iteration der Seite eine andere Seite aufgerufen wird innere Schleife. Auf diese Weise versagt fast jede Cache-Strategie und Sie sehen eine starke Verlangsamung.
Das Problem ist hier, wie Ihr Array im Speicher liegt.
Im Computerspeicher werden Arrays normalerweise so zugewiesen, dass zuerst alle Spalten der ersten Zeile, dann der zweiten Zeile usw. kommen.
Ihr Computerspeicher wird am besten als ein langer Streifen von Bytes betrachtet - es ist ein eindimensionales Array von Speicher - nicht zweidimensional, daher müssen mehrdimensionale Arrays in der beschriebenen Weise zugeordnet werden.
Jetzt kommt ein weiteres Problem: Moderne CPUs haben Caches. Sie haben mehrere Caches und sie haben sogenannte "Cache-Lines" für den Cache der ersten Ebene. Was bedeutet das. Der Zugriff auf den Speicher ist schnell, aber nicht schnell genug. Moderne CPUs sind viel schneller. So haben sie ihre On-Chip-Caches, die die Dinge beschleunigen. Sie greifen auch nicht mehr auf einzelne Speicherplätze zu, sondern füllen in einem Abruf eine komplette Cache-Zeile aus. Dies gilt auch für die Leistung. Aber dieses Verhalten gibt allen Operationen Vorteile, die Daten linear verarbeiten. Wenn Sie zuerst auf alle Spalten in einer Zeile, dann auf die nächste Zeile usw. zugreifen, arbeiten Sie tatsächlich linear. Wenn Sie zuerst alle ersten Spalten aller Zeilen verarbeiten, "springen" Sie in den Speicher. Dadurch erzwingen Sie immer, dass eine neue Cache-Zeile gefüllt wird, nur wenige Bytes können verarbeitet werden, dann wird die Cache-Zeile möglicherweise durch Ihren nächsten Sprung ungültig gemacht ....
Somit ist die Spalte-Großordnung für moderne Prozessoren schlecht, da sie nicht linear arbeitet.
Tags und Links c++ programming-languages