Gruß zur späten Stunde.
Aufgrund aktuellen Anlasses im Studium wollte ich mal ein kleines Snippet los werden, welches die Cache orientierte Programmierung nahe bringt.
Grundmodell ist das Transponieren einer Matrix.
Die native Lösung wäre folgende:
transposedMatrix[y][x] = Matrix[x][y];
Wir können die Matrix tatsächlich auf keinem anderen Weg rotieren, so oder so müssen wir sie in dieser Art und Weise zuordnen. Allerdings können wir dabei effektiv den Cache nutzen.
Hier erstmal das Snippet (in Java):
JavaCode
CacheTest.java
public class CacheTest {
public static void main(String[] args) {
matrixTester test = new matrixTester();
System.out.println("No Cache: " + (test.rotateMatrix() * 1e-6));
System.out.println("Cache: " + (test.rotateMatrixCache() * 1e-6));
System.out.println("No Cache Check: " + test.checkMatrixRightRotatedNoCache());
System.out.println("Cache Check: " + test.checkMatrixRightRotatedCache());
}
}matrixTester.java
public class matrixTester {
private int[][] Matrix;
private int[][] rotMatrix;
private int[][] rotMatrixCache;
matrixTester(){
this.Matrix = new int[4096][4096];
this.rotMatrix = new int[4096][4096];
this.rotMatrixCache = new int[4096][4096];
for(int x = 0; x < this.Matrix.length; x++){
for(int y = 0; y < this.Matrix.length; y++){
this.Matrix[x][y] = x + y;
}
}
}
public long rotateMatrix(){
long startTime = System.nanoTime();
for(int x = 0; x < this.Matrix.length; x++){
for(int y = 0; y < this.Matrix[0].length; y++){
this.rotMatrix[y][x] = this.Matrix[x][y];
}
}
long endTime = System.nanoTime();
return (endTime - startTime);
}
public long rotateMatrixCache(){
int stepWidth = 16;
long startTime = System.nanoTime();
for(int x = 0; x < this.Matrix.length; x += stepWidth){
for(int y = 0; y < this.Matrix[0].length; y++){
for(int xNew = x; xNew < x + stepWidth; xNew++){
this.rotMatrixCache[y][xNew] = this.Matrix[xNew][y];
}
}
}
long endTime = System.nanoTime();
return (endTime - startTime);
}
public boolean checkMatrixRightRotatedNoCache(){
for(int x = 0; x < this.Matrix.length; x++){
for(int y = 0; y < this.Matrix[0].length; y++){
if(this.Matrix[x][y] != this.rotMatrix[y][x]){return false;}
}
}
return true;
}
public boolean checkMatrixRightRotatedCache(){
for(int x = 0; x < this.Matrix.length; x++){
for(int y = 0; y < this.Matrix[0].length; y++){
if(this.Matrix[x][y] != this.rotMatrixCache[y][x]){return false;}
}
}
return true;
}
}Nun - Ich nutze meinen Cache selbstverständlich nicht optimal. Ohne die Specs meines Prozessors anzuschauen habe ich einfach mal die Annahme getroffen, dass eine Cache-Line 16 * 32 Bit lang ist (== 64 Byte). Um das genau heraus zu bekommen hätte ich ein Script gebraucht, welches mir mit verschiedenen Messungen sagen kann, wie groß eine Line meines L1 Caches tatsächlich ist.
Eventuell schreibe ich noch Eines zum Messen und stelle das ebenfalls hier rein.
Ferner nutze ich in dem Snippet auch nicht die Blockgröße aus. Zwar nutze ich die 64 Byte pro Cache-Line, allerdings beziehe ich mich überhaupt nicht auf die Anzahl der Cache Lines (in dem Falle die Anzahl der Zeilen, also y), das würde zusätzlich noch ein Speedup herbei bringen.
Nun aber zum eigentlichen Inhalt des Ganzen: Es geht dabei darum, zu zeigen, dass man effektiver Speicher(zugriffe) macht, und somit in seinen Programmen die Laufzeit verkürzt. Primär ist eine Matrix Rotation das perfekte Anwendungsbeispiel, da wir nach und nach jeden Wert in den Speicher laden, ihn zuweisen, und ihn dann nicht mehr anrühren.
Allerdings ist die native Implementierung nicht gerade zeitgünstig. Wir befüllen den Cache immer wieder mit neuen Werten, sodass wir keinerlei Zeitgewinn gegenüber dem Zugriff auf den RAM haben. Es wird etwas in den Cache geladen, einmal angerührt, und schon wird das nächste nachgeladen.
Dabei hat unser Cache eine weit schnellere Zugriffszeit als unser Arbeitsspeicher (für die Details empfehle ich Wikipedia - Cache). Deshalb ist es sinnvoll, wenn wir im Cache nur genau die Werte betrachten, die bereits darin stehen.
Beim laden einer Zeile der Matrix wird genau so viel der Zeile in den Cache geladen, wie ab index i hinein passt (in dem Falle: 16 mal ein 32 Bit Integer, was äquivalent zu 64 Byte Speicher ist (n Bit / 8 = x Byte). Wenn wir nun allerdings permanent die Zeilen durchrödeln, statt bei der x-ten Stelle weiter zu springen, wird der Cache nicht fortlaufend belegt, sondern "irgendwie". Wie genau das funktioniert, das weiß nur der Hersteller (oder jemand, der davon tatsächlich Ahnung hat), Fakt ist allerdings, dass er nicht mehr nur die Cache Lines belegen wird.
Es ist also ratsam, dass man in solchen Fällen den Cache nur bis dahin nutzt, wo er voll geschrieben ist. Das schafft im Endeffekt einen enormen Geschwindigkeitsvorteil.
Wie enorm ist denn der Vorteil?
Nun - In dem Beispiel von mir komme ich mit meinem i5-2500 auf folgende Ausgaben, ausgegeben in Millisekunden:
No Cache: 525.551611
Cache: 78.892377
No Cache Check: true
Cache Check: trueNo Cache: 291.565317
Cache: 65.253137
No Cache Check: true
Cache Check: trueNo Cache: 297.67008699999997
Cache: 68.514985
No Cache Check: true
Cache Check: true
No Cache Check & Cache Check beziehen sich lediglich darauf, ob die Matrix richtig rotiert wurde. Wenn dies nicht der Fall ist, dann hätten wir ja nix gewonnen.
Warum der erste Wert so hoch ist weiß ich jetzt nicht, im Allgemeinen ist aber ein Geschwindigkeitsvorteil um den Faktor ~4.5 zu erkennen. Bei genügend großen Daten macht das durchaus schon mal was aus.
Anbei noch die Bemerkung, warum der Code in Java ist: Ich versuchte in AutoIt ähnliches umzusetzen, ziemlich genau 1:1 den Code, jedoch mit weitaus kleineren Array Größen (AutoIt tut sich bei 4096*4096 im Minutenbereich weh). Allerdings erzielte ich in der Cache Lösung sogar eine langsamere Zeit, als in der NoCache Lösung, was sich mir absolut nicht erschloss. Vielleicht habe ich irgendwas falsch geschrieben, jemand Anderes kann gerne versuchen das in AutoIt umzusetzen und dann mitzuteilen. Vorab wäre mein Schluss für AutoIt daraus, dass der Interpreter "Sowieso macht, was er will", aber die Alteingesessenen wissen bestimmt, woran es liegt.
Damit Allen ein schönes Wochenende!
