# Einfluss von Caching auf die Performance (große Arrays)



## Marco13 (18. Dez 2011)

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). 

```
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: 

```
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 ms
```
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.


----------



## ThreadPool (18. Dez 2011)

Marco13 hat gesagt.:


> 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?).
> 
> [...]



Die VM mag zwar abstrahieren aber an der zugrundeliegenden Hardware und deren Funktionsweise ändert die nichts. Wenn man große Matrizen in "column major" verarbeitet gibt es eben viele CPU/Hardwarecachemisses. Die Caches laufen IMHO zeilenweise nicht spaltenweise. Große Matrizen werden deshalb IMHO auch blockweise verarbeitet und zwar so das die Blöcke von der Größe her in den Cache passen. Mal von Matrizen abgesehen sollten Objekte die sehr oft in Operationen verwendet werden nicht zu groß sein sonst gibts nämlich auch wieder reichlich Cache-Misses . 

Und die Sache mit dem Integer, schiebt man Integer in ein Array sind das in Java immernoch Referenzen. In C++ hat man den Vorteil das solche "value"-Objekte schön hintereinander in den Speicher gedängelt werden wenn ein Feld verwendet wird, also nicht nur Referenzen sind die irgendwo in die Botanik zeigen.


----------



## Guest2 (18. Dez 2011)

Moin,

ja, die Ergebnisse sind bei mir vergleichbar:

[c]-Xms4096m -Xmx4096m -Xbatch -XX:CompileThreshold=1 -XX:ReservedCodeCacheSize=1024m -XX:+UseFastAccessorMethods[/c]

```
size 1000 run 2 row    major 499999500000 time 0.580481 ms
size 1000 run 2 column major 499999500000 time 4.421656 ms
size 1000 run 2 linear       499999500000 time 0.558299 ms
[..]
size 5000 run 2 row    major 312499987500000 time 19.852903 ms
size 5000 run 2 column major 312499987500000 time 192.908808 ms
size 5000 run 2 linear       312499987500000 time 21.595097 ms
[..]
size 10000 run 2 row    major 4999999950000000 time 76.993815 ms
size 10000 run 2 column major 4999999950000000 time 1054.143766 ms
size 10000 run 2 linear       4999999950000000 time 83.367828 ms
[..]
size 15000 run 2 row    major 25312499887500000 time 176.011321 ms
size 15000 run 2 column major 25312499887500000 time 2291.85601 ms
size 15000 run 2 linear       25312499887500000 time 182.308637 ms
[..]
size 20000 run 2 row    major 79999999800000000 time 324.402422 ms
size 20000 run 2 column major 79999999800000000 time 4281.870908 ms
size 20000 run 2 linear       79999999800000000 time 342.99323 ms
[..]
size 25000 run 2 row    major 195312499687500000 time 486.297603 ms
size 25000 run 2 column major 195312499687500000 time 6831.645841 ms
size 25000 run 2 linear       195312499687500000 time 501.624708 ms
```




Marco13 hat gesagt.:


> 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.



Dem würde ich mich uneingeschränkt anschließen. Es gibt zu dem Thema auch eine reihe von papers (Stichwörter dazu sind z.B.: "data / array prefetching" und "irregular array accesses"). Das Problem dabei ist, dass die meisten davon wohl schon älter sind und man eigentlich annehmen könnte in der VM gäb es dazu Neuerungen, aber die Zeiten da oben sind diesbezüglich nicht besonders vielversprechend.

Viele Grüße,
Fancy


----------



## bERt0r (18. Dez 2011)

Ich weis jetzt nicht in wie fern das relevant ist, aber wenn du eine Matrix hast, wieso machst du dann kein 2 Dimensionales Array? Ich hab das mal getestet, das is sogar schneller als deine rowMajor:

```
private static long run2D(int input[][], int n)
    {
    	long result=0;
    	for(int i=0; i<n;i++)
    	{
    		for(int j=0;j<n;j++)
    		{
    			result+=input[i][j];
    		}
    	}
    	return result;
    }
```


```
size 5000 run 0 row    major 312499987500000 time 97.869422 ms
size 5000 run 0 column major 312499987500000 time 261.391881 ms
size 5000 run 0 linear       312499987500000 time 58.895195 ms
size 5000 run 0 2 dimensional312499987500000 time 77.18048 ms
size 5000 run 1 row    major 312499987500000 time 98.881283 ms
size 5000 run 1 column major 312499987500000 time 262.97197 ms
size 5000 run 1 linear       312499987500000 time 58.669468 ms
size 5000 run 1 2 dimensional312499987500000 time 77.019565 ms
size 5000 run 2 row    major 312499987500000 time 98.514197 ms
size 5000 run 2 column major 312499987500000 time 261.15051 ms
size 5000 run 2 linear       312499987500000 time 58.756351 ms
size 5000 run 2 2 dimensional312499987500000 time 76.860328 ms
```


----------



## Guest2 (18. Dez 2011)

Das Problem ist dabei aber scheinbar ähnlich:


```
size 5000 run 2 row    major      312499987500000 time 19.443483 ms
size 5000 run 2 column major      312499987500000 time 192.526081 ms
size 5000 run 2 linear            312499987500000 time 20.195025 ms
size 5000 run 2 2 dimensional row 312499987500000 time 18.312597 ms
size 5000 run 2 2 dimensional col 312499987500000 time 265.788125 ms
```


```
private static long run2DRowMajor(final int input[][], final int n) {

        long result = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                result += input[i][j];

        return result;

    }


    private static long run2DColumnMajor(final int input[][], final int n) {

        long result = 0;
        for (int j = 0; j < n; j++)
            for (int i = 0; i < n; i++)
                result += input[i][j];

        return result;

    }
```

Viele Grüße,
Fancy


----------



## TIRI (18. Dez 2011)

Hallo,

ich bin kein Java-Spezialist, aber versucht doch ein Verfahren aus HPC – „Schleifenaufrollen“. In deinem Beispiel:
…
for( int r = 0; r < n; r+=2 )
…
size 5000 run 0 row    major 312499987500000 time 15.672532 ms
size 5000 run 0 column major 312499987500000 time 255.606985 ms // ohne
size 5000 run 0 column major 312499987500000 time 140.534693 ms // mit aufgerollter Schleife
size 5000 run 0 linear       312499987500000 time 15.902122 ms


----------



## Guest2 (18. Dez 2011)

Langsam wird’s wieder spanend 


```
size 5000 run 2 row  major             312499987500000 time 24.785487 ms
size 5000 run 2 column major           312499987500000 time 184.224526 ms
size 5000 run 2 column major unroll    312499987500000 time 58.749642 ms
size 5000 run 2 linear                 312499987500000 time 19.608152 ms
size 5000 run 2 2D row major           312499987500000 time 20.53978 ms
size 5000 run 2 2D column major        312499987500000 time 274.979576 ms
size 5000 run 2 2D column major unroll 312499987500000 time 84.499465 ms
```

(schön einen HPCler hier zu sehen! Willkommen!)

Viele Grüße,
Fancy


----------



## TIRI (18. Dez 2011)

Oooo, Sarkasmus,
es soll nur das Verhalten von Cache zeigen.


----------



## Marco13 (18. Dez 2011)

bERt0r hat gesagt.:


> wenn du eine Matrix hast, wieso machst du dann kein 2 Dimensionales Array?



Dass dort ein ähnlicher Effekt aufritt hat Fancy ja schon erwähnt (zugegeben: Getestet hatte ich es selbst noch nicht). Ich hatte für den konkreten Fall aus verschiedenen Gründen einen 1D-Array verwendet - hauptsächlich, weil die Matrix schnell und einfach nach jcuda.org - JCublas rübergeschickt werden sollte. Aber auch weil ich gehofft hatte, dass im 1D-Fall der Unterschied der _Speicherung_ der Matrix nicht so wichtig sein könnte - also nicht die Frage, ob man die Matrix row- oder column-Major _traversiert_, sondern wirklich wie man sie _speichert_. (Auf den ersten Blick sehen die Zahlen von Fancy (1D:192ms vs. 2D:265 ms) so aus, als wäre das der Fall, aber das müßte man noch genauer prüfen). 

Grundsätzlich weiß ich, dass solche unregelmäßigen Zugriffe nicht so gut sind, wie ein lineares Durchlaufen, und weiß, dass es dazu Forschung und Veröffentlichungen gibt. Im Nachhinein kann man sich da selbst ohne tiefgreifendes Wissen eine plausible Begründung zurechtlegen: "Joa, da ist irgendwo ein 128bit-Bus oder Cache-Eintrag, und im einen Fall liegen da dann die 4*32bit drin, die man braucht, und im anderen Fall schmeißt man 3*32 bit unbenutzt weg (oder so)". Aber störend ist es schon. "Ein" Unterschied wäre ja OK, mich hatte nur überrascht, dass der Unterschied da locker Faktor 20 ausmacht. Es ist in bezug auf die Programmierung wohl kaum praktikabel, sich darauf einzustellen  Wenn man irgendeine Operation durchführen muss, die auf row-major-matrizen "schnell" laufen würde, wäre es u.U. um ein _vielfaches_ schneller, eine column-major Matrix vorher in row-major und nachher wieder zurück zu konvertieren. Wenn man das im Code so (unkommentiert) sehen würde, würde das irgendwie krampfig wirken :autsch: ... Dinge wie loop-unrolling sind in solchen Fällen wohl noch weniger praktikabel, weil man dann mit unroll-leveln, blockgrößen und ähnlichem hantieren müßte...


----------



## Guest2 (18. Dez 2011)

@TIRI, von meiner Seite aus war dort kein Sarkasmus. In Java legt man den Schwerpunkt der Programmierung normalerweise auf sauberen Code und überlässt die Performanceoptimierungen weitgehend der VM bzw. dem JIT (just in time compiler). Der macht seine Sache für gewöhnlich auch sehr gut, sodass meistens (auch ohne Hacks) sehr akzeptable Ergebnisse erzeugt werden. So etwas wie Schleifen aufrollen ist deshalb in Java (außerhalb von HPC) auch praktisch nicht vorhanden, auch wenn es eigentlich eine Standarttechnik ist. Umso trauriger ist es imho eigentlich, das der JIT hier offensichtlich versagt.

@Marco, ich kann die Situation innerhalb von JCuda nicht einschätzen. Was ich mir aber z.B. vorstellen könnte, wäre eine Klasse, die das eigentliche Array kapselt und dabei sicherstellt das die Größe des internen Arrays immer einem Vielfachen von z.B. 4 (*) entspricht. Die öffentlichen Methoden könnten die reale Größe verstecken und sich so verhalten als seien die z.B. notwendigen 3 extra ints nicht vorhanden. Intern aber (z.B. in Methoden zur Matrixmultiplikation) könntest Du sicher die äußeren Schleifen auf 4 Elemente aufrollen, ohne zusätzliche Bedingungen einbauen zu müssen. Imho sollte das schneller und einfacher sein, als die Matrizen dauernd zu konvertieren oder doppelt zu bevorraten.

((*) 4 scheint ein willkürlicher Wert und ist es auch . In der Praxis sollte das Optimum der Anzahl der freien Register entsprechen. Innerhalb der JVM ist das natürlich schwierig abzuschätzen, aber 4 bis 8 würde ich erstmal als realistische Größe ansehen. Wenn viel gerechnet wird, dann ggf. auch mehr.)

Viele Grüße,
Fancy


----------



## Marco13 (18. Dez 2011)

Die Frage hat mit JCuda/JCublas eigentlich nichts zu tun, das war nur einer der Gründe für den 1D-Array - der ist leichter auf die Grafikkarte zu kopieren, aber mit 2D wären es auch nur ein paar Zeilen mehr. Ich wollte aber auch (während des Rumprobierens) die Darstellung für Java möglichst "elementar" haben, und dachte, dass man mit einem 1D Array mit plain Java das Maximum an Performance rausholen könnte. 

(BTW und halb OT: Eigentlich wäre loop-Unrolling hier geradezu die "Paradedisziplin" des JIT: DER könnte zur Laufzeit (im Gegensatz zu einem C-Compiler) einen passenden Wert für's unrollen suchen...)

Tatsächlich ist dieser (float) Array natürlich in einer Klasse "ColumnMajor1DArrayFloatMatrix2D implements FloatMatrix2D" versteckt, aber wenn jemand eine (nicht näher spezifizierte) FloatMatrix2D _verwenden_ will, und zufällig so drüberläuft, dass es nicht zur Matrix passt, ist's 20mal langsamer - Empfehlungen kann man auch nicht geben, weil man "im Idealfall" ja die Implementierung nicht kennt und es keinen Unterschied machen sollte, ob man eine _Column-_ oder _Row_Major1DArrayFloatMatrix2D hat :autsch: Offenbar wieder ein Beispiel dafür, dass Abstraktion und Performance schwer unter einen Hut zu bringen sind...


----------



## Marco13 (18. Dez 2011)

BTW: Hab's gerade noch mal auf einem 2.4Ghz QuadCore getestet: Hier ist der Unterschied bei weitem nicht so deutlich: Bei einer 10000x10000-Matrix ist es ""nur"" Faktor 5 - aber auf einem anderen Rechner (Core i7 meine ich ???:L ) war der Unterschied AFAIR größer - muss ich bei Gelegenheit nochmal testen...


----------



## bERt0r (19. Dez 2011)

Könntest du die Daten in deiner ColumnMajor dann nicht gleich in Column-Reihenfolge speichern?

```
public class CachingTest
{
    public static void main(String args[])
    {
        for (int n=1000; n<=5000; n+=1000)
        {
            int input[] = new int[n*n];
            int input2D[][]=new int[n][n];
            int input2DColumn[][]=new int[n][n];
            ColumnMajor2DArray classArray=new ColumnMajor2DArray(n,n);
            for (int i=0; i<input.length; i++)
            {
                input[i] = i;
                input2D[i/n][i%n]=i;
                input2DColumn[i%n][i/n]=i;
                classArray.set(i/n, i%n, 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");
                
                before = System.nanoTime();
                long result3 = run2DColumnMajor(input2DColumn, n);
                after = System.nanoTime();
                System.out.println("size "+n+" run "+i+"       2D column major "+result2+" time "+(after-before)/1e6+" ms");
                
                before = System.nanoTime();
                long result4 = runClass2DColumnMajor(classArray, n);
                after = System.nanoTime();
                System.out.println("size "+n+" run "+i+" Class 2D column major "+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;
    }
    
    private static long run2DColumnMajor(int input[][], int n)
    {
    	long result=0;
    	for(int column=0;column<n;column++)
    	{
    		for(int row=0;row<n;row++)
    		{
    			result+=input[column][row];
    		}
    	}
    	return result;
    }
    
    private static long runClass2DColumnMajor(ColumnMajor2DArray input, int n)
    {
    	long result=0;
    	for(int column=0;column<n;column++)
    	{
    		for(int row=0;row<n;row++)
    		{
    			result+=input.get(row, column);
    		}
    	}
    	return result;
    }
 
}

class ColumnMajor2DArray
{
	int[][] arr;
	ColumnMajor2DArray(int rows,int columns)
	{
		arr=new int[columns][rows];
	}
	
	public void set(int row, int column, int value)
	{
		arr[column][row]=value;
	}
	
	public int get(int row, int column)
	{
		return arr[column][row];
	}
}
```


```
size 5000 run 2        row    major   312499987500000 time 128.723622 ms
size 5000 run 2        column major   312499987500000 time 316.765469 ms
size 5000 run 2        linear         312499987500000 time 80.088321 ms
size 5000 run 2       2D column major 312499987500000 time 96.098317 ms
size 5000 run 2 Class 2D column major 312499987500000 time 114.772268 ms
```


----------



## Spacerat (19. Dez 2011)

Mal dumm gefragt... Gibt es ausser Performance noch andere Gründe warum man Daten cached? Soweit ich weis, nicht. Ein Cache sollte also stets den schnellstmöglichen Zugriff auf seine Daten gewährleisten im einfachsten Fall also über eine Map.
Die Zugriffszeiger einer Map sollten aber besser immutable sein, das trifft aber auf eine Matrix leider nicht zu.
Die Art, wie die einzelnen Werte in der Matrix gespeichert sind - rowMajor, coloumnMajor, 2D-Array, ist implementationsabhängig, im Speicher jedoch liegen alle Werte hintereinander. Daraus folgt, dass der lineare Zugriff stets die richtige Wahl sein muss.
Was das Aufsummieren der Werte aber noch um einiges performanter machen würde:
- Beim Instanzieren der Matrix die Summe aller Werte in einer Membervariable speichern
- Zugriff auf die einzelnen Elemente per Getter und Setter
- Bei SetElement schlicht den entsprechenden Wert (alt) von der Summe abziehen und den neuen hinzuzählen.
Wenn man die Summe nun noch als Wrapper-Objekt eines Primitivtypen anlegt, kann man darauf sogar synchronisieren. Der entscheidende Nachteil dieser Art wäre aber, dass Elemente nur einzeln geändert werden können.


----------



## ThreadPool (19. Dez 2011)

bERt0r hat gesagt.:


> Könntest du die Daten in deiner ColumnMajor dann nicht gleich in Column-Reihenfolge speichern?



Das sollte man wenn die Matrizen spaltenweise verarbeitet werden sollen. Im Prinzip solltest man es vermeiden z.B. auf row major angeordnete Daten eine column major basierte Verarbeitung zu starten vice versa. Du springst dann ständig hin und her und im ungünstigsten Fall lädst du ständig Daten aus dem RAM nach deshalb achtet man bei solchen Dingen auf die "Data Locality" und versucht konsitent zu bleiben was die Funktionen betrifft die auf die Daten angewendet werden. Aber das wurde ja hier schon festgestellt.


----------



## bERt0r (19. Dez 2011)

Ich hab mich dabei auf das hier bezogen, man kann den Zugriff ja kapseln wenn man sich eine eigene Datenhaltunggsklasse schreibt. Sogar ein Iterator oder eine Enumeration wäre denkbar.

```
class ColumnMajor2DArray
{
    int[][] arr;
    ColumnMajor2DArray(int rows,int columns)
    {
        arr=new int[columns][rows];
    }
    
    public void set(int row, int column, int value)
    {
        arr[column][row]=value;
    }
    
    public int get(int row, int column)
    {
        return arr[column][row];
    }
}
```


----------



## Marco13 (19. Dez 2011)

bERt0r hat gesagt.:


> Könntest du die Daten in deiner ColumnMajor dann nicht gleich in Column-Reihenfolge speichern?



Wie ThreadPool schon sagte: Man kann die Daten (in einem 1D-Array, bzw. je nach konkreter Implementierung der Matrix-Klasse) Column-Major ODER Row-Major _speichern_. Aber egal, wie sie gespeichert ist: Wenn man auf "die andere Art" drüberläuft, wird es langsam. Plakativ gesagt: Wenn jemand sowas schreibt wie

```
long computeA(FloatMatrix2D m)
{
    for (int r=0; r<m.getNumRows(); r++)
    {
        for (int c=0; c<m.getNumCols(); c++)
        {
            doSomething(m.get(r,c));
        }
    }
}

long computeB(FloatMatrix2D m)
{
    for (int c=0; c<m.getNumCols(); c++)
    {
        for (int r=0; r<m.getNumRows(); r++)
        {
            doSomething(m.get(r,c));
        }
    }
}
```
dann wird immer eine der beiden Methoden schrecklich langsam sein - viel langsamer, als sie sein müßte, wenn man eine Kleinigkeit ändern würde, die auf das, was die Methode _macht_, eigentlich keinen Einfluß hat - nämlich die Reihenfolge der for-Schleifen. Und ohne irgendwelche krampfigen Interfaces und Dinge wie

```
if (m implements PerfersRowMajorIteration) { ... }
else { ... }
```
wird man da (soweit ich sehe) kaum was dran ändern können...


@Spacerat: Es ging bei dem Cachen nicht im das "manuelle" Cachen der Matrix, sondern um das Hardware-Caching, das der Prozessor intern bei jedem Speicherzugriff macht. Das Aufsummieren der Werte war nur "irgendein" Beispiel, wo eben auf die Matrix zugegriffen werden muss. Das entscheidende ist ja, dass der Geschwindigkeitsunterschied (unabhängig davon, WAS genau man macht) aus den unterschiedlichen Zugriffsmustern herrührt...


----------



## Spacerat (19. Dez 2011)

Ob manuell oder nicht, die entgegen der Implementation gewählte Methode führt stets zu einer nicht linearen Abarbeitung der Daten. Das führt logischerweise zu häufigeren Cache-Misses. Was könnte denn schon anderes in so einem Prozessor-Daten-Cache liegen als eine Kopie des Speicherblocks auf den grad' zugegriffen wurde? Diese Kopie der Daten ist natürlich ebenso linear wie der Speicherblock in welchen die Matrixelemente lt. Implementation abgelegt wurden. Deswegen hast du ja bei linearem Zugriff stets mit die besten Ergebnisse.


----------



## Marco13 (19. Dez 2011)

Einerseits ja. Andererseits geben sich die Hardwareleute schon viel Mühe mit dem Caching und dem auspendeln der Antwort auf die Frage, wo das nächste mal daruf zugegriffen wird. Es ist ja auch (wie schon angedeutet, selbst bei der "naiven" Sichtweise auf Basis dessen, was man im ersten Semester in einer Vorlesung über "Caching" so hört) nicht verwunderlich, _dass_ es langsamer ist. Aber dass es in so einem Beispiel wirklich den Unterschied ausmachen kann, zwischen einer "kurzen Verzögerung" und einer Kaffeepause hätte ich nicht gedacht. Hab's nochmal auf dem Core i7 getestet: Dort sind es bei 10000x10000 auch etwa 50ms vs. 1000ms....


----------



## Guest2 (19. Dez 2011)

Ich würde vermuten, das in der Praxis die länge der CPU pipeline und die Geschwindigkeit des Hauptspeichers hauptsächlich das Laufzeitverhalten zwischen den beiden Varianten bestimmt. So dürfte der i7 (mit dem Verhältnis von 1:20) zwar eine schnellere Speicheranbindung besitzen (als z.B. mein Q9450) aber aufgrund seiner (imho) längeren pipeline müssten die kurzen for-Schleifen teurer sein (beim Q9450 ist das Verhältnis "nur" ~1:10 mit manuellem unroll(8) ~1:3).

Umso wichtiger wäre es eigentlich, das der JIT eingreift. Warum er das nicht macht, ist mir allerdings schleierhaft. Ich habe mir gestern mal die Assemblerausgaben des JIT und das hotspot.log angesehen, in der Hoffnung irgendwas zu entdecken, was den daran hindert zu optimieren, aber leider ohne Erfolg. Selbst wenn man in den for-Schleifen das n durch 10000 ersetzt, so das eigentlich schon zur Compilezeit klar wäre was passiert, lässt ihn das vollkommen kalt. Der baut die beiden schleifen fast 1:1 als native. Selbst der billigste C-Compiler im Halbkoma würde da optimierend eingreifen.

Viele Grüße,
Fancy


----------



## bERt0r (19. Dez 2011)

> dann wird immer eine der beiden Methoden schrecklich langsam sein - viel langsamer, als sie sein müßte, wenn man eine Kleinigkeit ändern würde, die auf das, was die Methode macht, eigentlich keinen Einfluß hat - nämlich die Reihenfolge der for-Schleifen. Und ohne irgendwelche krampfigen Interfaces und Dinge wie


Wenn du verhindern willst dass jemand, der deine Klasse benutzt, falsch darauf zugreift, bleibt dir eben nichts anderes über, als den Zugriff zu kapseln. Beispielsweise indem die Klasse wie eine Collection das Interface Iterable implementiert. Dann machst du eine RowMajor und eine ColumnMajor Klasse, und die können dann jeweils nur in der effizienten Reihenfolge verarbeitet werden.


----------



## Spacerat (19. Dez 2011)

Ich nehme mal ganz stark an, dass solche Cachingoptimierungen Prozessoroptimierungen sind und JIT Aufgrund seiner Platform- und Prozessorunabhängigkeit maw. keine Kenntnis über die Hardware gar nicht bzw. Standardrollbacks optimiert.
Klar, das Chaching wurde im Laufe der Jahre schon recht gut durchdacht (Blockweises Kopieren, Datenprefetch, Ringspeichernutzung), dient aber immer noch der performanten Anbindung langsamerer Speichermedien an schnellere Recheneinheiten. Möglichst linearer Speicherzugriff funktioniert deswegen immernoch stets am besten.
Für Performancetests verschiedener Prozessoren bedeutet das, dass dazu nicht nur allein die Prozessortakte und Cachezugriffszeiten herangezogen werden dürfen, sondern auch die Speicherzugriffszeiten mit eine Rolle spielen. Feststellen, ob ein Prozessor nun schneller oder langsamer ist, funktioniert deswegen nur bei gleichem Ram-Bustakt.


----------



## bERt0r (19. Dez 2011)

Ich bin kein experte wenn sichs ums Assembler/Hardwareinnenleben dreht. Aber ich schätze mal, wenn die JVM sieht, es wird auf ein Array zugeggriffen, wird das array mal in den Level2 Cache vom Prozessor geschoben. Wenn es dafür zu groß ist, eben nur ein Teil. Solange man linear drüberläuft, fährt man damit ganz gut. Springt man aber ständig hin und her im array, passt der Teil der gerade gecached wurde nie oder nur sehr viel seltener, wodurch sich der enorme Performanceverlust erklärt.


----------



## Marco13 (19. Dez 2011)

Guest2 hat gesagt.:


> Umso wichtiger wäre es eigentlich, das der JIT eingreift. Warum er das nicht macht, ist mir allerdings schleierhaft.



Das könnte zwar an dem liegen, was bERt0r und Spacerat angedeutet haben. Pragmatisch gesehen gibt es zwar nichts, was die JVM nicht über ihr Hostsystem herausfinden könnte, aber für jeden x-beliebigen Prozessor eine bestimmte unroll- oder sonstige Optimierungsstrategie implementieren wäre wohl nicht praktikabel. 80% Arbeit in die 20% der Fälle stecken, wo man durch sowas einen Tick mehr Performance rausholen könnte, lohnt sich wohl einfach nicht.



> Ich habe mir gestern mal die Assemblerausgaben des JIT und das hotspot.log angesehen



Geht das auch ohne Debug-JVM? Muss ich mir mal ansehen....




> Beispielsweise indem die Klasse wie eine Collection das Interface Iterable implementiert.



Hmja, auch das ist nur schwierig umsetzbar. Erstmal bräuchte man keinen Iterator<Float> sondern einen PrimitiveFloatIterator (ggf. auch mit settern), und selbst dann würde das nur für den Fall funktionieren, wo man einfach so über alle Elemente iteriert. Wenn man (konkret auf das Matrix-Beispiel bezogen) im einen Fall über eine Zeile und im anderen über eine Spalte iterieren muss, wird wieder einer der beiden Fälle langsam sein.


----------



## Gregorrr (19. Dez 2011)

Marco13 hat gesagt.:


> Geht das auch ohne Debug-JVM? Muss ich mir mal ansehen....



Damit du nicht suchen musst:
https://wikis.oracle.com/display/HotSpotInternals/PrintAssembly

Unter Windows einfach ins jdk\jre\bin\server und/oder \jdk\jre\bin\client schmeißen (precompiled): Lukas Stadler's Blog: hsdis-i386.dll

Dann noch -XX:+UnlockDiagnosticVMOptions und weiters -XX:+PrintAssembly fertig.


----------

