Hallo
Bisher bin ich davon ausgegangen, dass man in bezug auf so Hardwarenahe Dinge wie Caching bei Java in der alltäglichen Praxis kaum noch etwas falsch oder richtig machen kann: Das ganze ist so weit abstrahiert und von der VM versteckt, dass man sein Programm kaum noch darauf hin optimieren kann (oder sollte?).
Dass z.B. die geringere Performance von 'Integer' gegenüber 'int' nicht zuletzt am Caching liegt könnte zwar so ein Fall sein, aber da man ohnehin immer 'int' nimmt, außer wenn es eine übergeordnete Designentscheidung ist, 'Integer' zu nehmen, wäre das hierfür ein schlechtes Beispiel.
Jetzt ist mir aber mal ganz praktisch ein Fall untergekommen, wo eine scheinbare Kleinigkeit einen dramatischen Unterschied ausmacht: Eine bestimmte Operation dauerte unerklärbar lange. Eine ähnliche Operation ging erst schnell, und nach einer scheinbar unbedeutenden Änderung plötzlich wahnsinnig langsam.
Deswegen habe ich en Effekt mal isoliert: Das folgende Programm berechnet die Summe der Elemente einer n*n-Matrix, für n=1000 bis 5000. (Im Moment sitz' ich an einem alten 1.4GHz-PC - bei neueren PCs könnte man das 5000 zum Testen auch noch auf 10000 oder so erhöhen). (Start mit -Xmx500m für genug Speicher).
Die Matrix ist als 1D-Array der Größe [n*n] gespeichert. Der einzige Unterschied zwischen den run*-Methoden, in denen alle Elemente aufsummiert werden, ist:
- In der [c]runRowMajor[/c] läuft man über alle Zeilen, und in jeder Zeile von Links nach Rechts
- In der [c]runColumnMajor[/c] läuft man über alle Spalten, und in jeder Spalte von Oben nach Unten
- In der [c]runLinear[/c] läuft man linear über alle Einträge des Arrays (nur zum Vergleich)
Rein mathematisch und Algorithmisch wird in allen Methoden genau das gleiche gemacht.
Schon bei geringeren Matrix-Größen zeigt sich, dass die [c]runColumnMajor[/c] langsamer ist. Aber ab einem bestimmten Punkt bricht die Performance dieser Methode dramatisch ein. Ein Beispiel der Ausgabe bei mir:
Es ist tatsächlich so, dass - obwohl alle Methoden das gleiche machen! - die [c]runColumnMajor[/c] mehr als 20 mal langsamer ist als die "gleichwertigen" anderen Methoden.
Wenn man mit großen Matrizen rumhantiert, kann man sich bei vielen Dingen leider nicht aussuchen, ob man über die Zeilen oder die Spalten laufen will. Und ob eine Matrix row-major oder column-major gespeichert ist, kann man schlecht nachträglich (oder für jede anstehende Operation aufs neue) umstellen.
Aber vielleicht so viel: FALLS man in einer Situation ist, wo man sich aussuchen kann, ob man bei einer zeitrkitischen Operation wild in einem Array hin- und her springt, oder alles von vorne nach hinten abarbeitet, sollte man sich eher für letzteres entscheiden.
Bisher bin ich davon ausgegangen, dass man in bezug auf so Hardwarenahe Dinge wie Caching bei Java in der alltäglichen Praxis kaum noch etwas falsch oder richtig machen kann: Das ganze ist so weit abstrahiert und von der VM versteckt, dass man sein Programm kaum noch darauf hin optimieren kann (oder sollte?).
Dass z.B. die geringere Performance von 'Integer' gegenüber 'int' nicht zuletzt am Caching liegt könnte zwar so ein Fall sein, aber da man ohnehin immer 'int' nimmt, außer wenn es eine übergeordnete Designentscheidung ist, 'Integer' zu nehmen, wäre das hierfür ein schlechtes Beispiel.
Jetzt ist mir aber mal ganz praktisch ein Fall untergekommen, wo eine scheinbare Kleinigkeit einen dramatischen Unterschied ausmacht: Eine bestimmte Operation dauerte unerklärbar lange. Eine ähnliche Operation ging erst schnell, und nach einer scheinbar unbedeutenden Änderung plötzlich wahnsinnig langsam.
Deswegen habe ich en Effekt mal isoliert: Das folgende Programm berechnet die Summe der Elemente einer n*n-Matrix, für n=1000 bis 5000. (Im Moment sitz' ich an einem alten 1.4GHz-PC - bei neueren PCs könnte man das 5000 zum Testen auch noch auf 10000 oder so erhöhen). (Start mit -Xmx500m für genug Speicher).
Java:
public class CachingTest
{
public static void main(String args[])
{
for (int n=1000; n<=5000; n+=1000)
{
int input[] = new int[n*n];
for (int i=0; i<input.length; i++)
{
input[i] = i;
}
long before = 0;
long after = 0;
int runs = 3;
for (int i=0; i<runs; i++)
{
before = System.nanoTime();
long result0 = runRowMajor(input, n);
after = System.nanoTime();
System.out.println("size "+n+" run "+i+" row major "+result0+" time "+(after-before)/1e6+" ms");
before = System.nanoTime();
long result1 = runColumnMajor(input, n);
after = System.nanoTime();
System.out.println("size "+n+" run "+i+" column major "+result1+" time "+(after-before)/1e6+" ms");
before = System.nanoTime();
long result2 = runLinear(input, n);
after = System.nanoTime();
System.out.println("size "+n+" run "+i+" linear "+result2+" time "+(after-before)/1e6+" ms");
}
}
}
private static long runRowMajor(int input[], int n)
{
long result = 0;
for (int c=0; c<n; c++)
{
for (int r=0; r<n; r++)
{
result += input[r+c*n];
}
}
return result;
}
private static long runColumnMajor(int input[], int n)
{
long result = 0;
for (int r=0; r<n; r++)
{
for (int c=0; c<n; c++)
{
result += input[r+c*n];
}
}
return result;
}
private static long runLinear(int input[], int n)
{
long result = 0;
for (int r=0; r<n*n; r++)
{
result += input[r];
}
return result;
}
}Die Matrix ist als 1D-Array der Größe [n*n] gespeichert. Der einzige Unterschied zwischen den run*-Methoden, in denen alle Elemente aufsummiert werden, ist:
- In der [c]runRowMajor[/c] läuft man über alle Zeilen, und in jeder Zeile von Links nach Rechts
- In der [c]runColumnMajor[/c] läuft man über alle Spalten, und in jeder Spalte von Oben nach Unten
- In der [c]runLinear[/c] läuft man linear über alle Einträge des Arrays (nur zum Vergleich)
Rein mathematisch und Algorithmisch wird in allen Methoden genau das gleiche gemacht.
Schon bei geringeren Matrix-Größen zeigt sich, dass die [c]runColumnMajor[/c] langsamer ist. Aber ab einem bestimmten Punkt bricht die Performance dieser Methode dramatisch ein. Ein Beispiel der Ausgabe bei mir:
Code:
size 5000 run 2 row major 312499987500000 time 271.124961 ms
size 5000 run 2 column major 312499987500000 time 6517.788434 ms
size 5000 run 2 linear 312499987500000 time 295.930908 msWenn man mit großen Matrizen rumhantiert, kann man sich bei vielen Dingen leider nicht aussuchen, ob man über die Zeilen oder die Spalten laufen will. Und ob eine Matrix row-major oder column-major gespeichert ist, kann man schlecht nachträglich (oder für jede anstehende Operation aufs neue) umstellen.
Aber vielleicht so viel: FALLS man in einer Situation ist, wo man sich aussuchen kann, ob man bei einer zeitrkitischen Operation wild in einem Array hin- und her springt, oder alles von vorne nach hinten abarbeitet, sollte man sich eher für letzteres entscheiden.
Zuletzt bearbeitet von einem Moderator:
. 
