Diese Antwort ist keine Antwort, sondern eher eine Reihe von Notizen.
Erstens neigt die CPU dazu, auf Cache-Zeilen zu arbeiten, nicht auf einzelnen Bytes/Wörtern/Dwords. Das bedeutet, dass beim sequenziellen Lesen/Schreiben eines Arrays von Ganzzahlen der erste Zugriff auf eine Cache-Zeile einen Cache-Miss verursachen kann, nachfolgende Zugriffe auf verschiedene Ganzzahlen in derselben Cache-Zeile jedoch nicht. Für 64-Byte-Cache-Zeilen und 4-Byte-Ganzzahlen bedeutet dies, dass Sie nur einmal alle 16 Zugriffe einen Cache-Mißerfolg erhalten würden; was die Ergebnisse verwässern wird.
Zweitens hat die CPU einen "Hardware-Pre-Fetcher". Wenn erkannt wird, dass Cache-Zeilen sequentiell gelesen werden, ruft der Hardware-Pre-Fetcher automatisch Cache-Zeilen vorab ab, von denen er annimmt, dass sie als nächstes benötigt werden (in einem Versuch, sie in den Cache zu holen, bevor sie benötigt werden).
Drittens tut die CPU andere Dinge (wie "Out-of-Order-Execution"), um Abrufkosten zu verbergen. Die Zeitdifferenz (zwischen Cache-Hit und Cache-Mißerfolg), die Sie messen können, ist die Zeit, die die CPU nicht verbergen konnte, und nicht die Gesamtkosten des Abrufs.
Diese 3 Dinge zusammen bedeuten das; Für das sequentielle Lesen eines Arrays von Ganzzahlen ist es wahrscheinlich, dass die CPU die nächste Cache-Zeile vorab abruft, während Sie 16 Lesevorgänge aus der vorherigen Cache-Zeile durchführen. und etwaige Kosten für Cache-Fehlversuche sind nicht wahrnehmbar und können vollständig ausgeblendet werden. Um dies zu verhindern; Sie möchten auf jede Cache-Zeile einmal "zufällig" zugreifen, um den Leistungsunterschied zu maximieren, der zwischen "Arbeitssatz passt in Cache/s" und "Arbeitssatz passt nicht in Cache/s" gemessen wird.
Schließlich gibt es noch andere Faktoren, die Messungen beeinflussen können. Beispielsweise gibt es für ein Betriebssystem, das Paging verwendet (z. B. Linux und fast alle anderen modernen Betriebssysteme), darüber hinaus eine ganze Caching-Schicht (TLBs/Translation Look-aside Buffers), und TLB verfehlt, sobald der Arbeitssatz eine bestimmte Größe überschreitet; was als vierter "Schritt" in der Grafik sichtbar sein sollte. Es gibt auch Interferenzen vom Kernel (IRQs, Seitenfehler, Taskwechsel, mehrere CPUs usw.); die als zufällige Statik/Fehler im Diagramm sichtbar sein können (es sei denn, die Tests werden häufig wiederholt und Ausreißer verworfen). Es gibt auch Artefakte des Cache-Designs (Cache-Assoziativität), die die Effektivität des Caches auf eine Weise reduzieren können, die von der/den vom Kernel zugewiesenen physischen Adresse(n) abhängt; was als "Schritte" in der Grafik gesehen werden kann, die sich an verschiedene Stellen verschieben.
Stimmt etwas mit meiner Methode nicht?
Möglicherweise, aber ohne Ihren eigentlichen Code zu sehen, der nicht beantwortet werden kann.
-
Ihre Beschreibung dessen, was Ihr Code tut, sagt nicht, ob Sie das Array einmal oder viele Male lesen.
-
Das Array ist möglicherweise nicht groß genug ... abhängig von Ihrer Hardware. (Haben nicht einige moderne Chips einen 3rd-Level-Cache von einigen Megabyte?)
-
Gerade im Java-Fall muss man einiges richtig machen, um einen aussagekräftigen Micro-Benchmark zu implementieren.
Im C-Fall:
-
Sie könnten versuchen, die Optimierungsschalter des C-Compilers anzupassen.
-
Da Ihr Code seriell auf das Array zugreift, kann der Compiler möglicherweise die Anweisungen so anordnen, dass die CPU mithalten kann, oder die CPU kann optimistisch vorab abrufen oder breite Abrufe durchführen. Sie könnten versuchen, die Array-Elemente in einer weniger vorhersehbaren Reihenfolge zu lesen.
-
Es ist sogar möglich, dass der Compiler die Schleife komplett wegoptimiert hat, weil das Ergebnis der Schleifenberechnung für nichts verwendet wird.
(Laut dieser Frage und Antwort – Wie viel Zeit dauert es, ein Wort aus dem Speicher abzurufen?) beträgt ein Abruf aus dem L2-Cache ~ 7 Nanosekunden und ein Abruf aus dem Hauptspeicher ~ 100 Nanosekunden. Aber Sie erhalten ~ 2 Nanosekunden. Etwas Cleveres muss hier vorgehen, damit es so schnell läuft, wie Sie beobachten.)