Matrizenmultiplikation/ schneller Array-Zugriff

Java-Forum Allgemeine Themen
21

Faktor 20 nun, pff, aber steigt vielleicht mit der Größe,
kannst du mein Programm aus Posting #17 ausführen, welchen Unterschied da?
wenn auch dafür irgendwas über 10 (statt bei mir nur 3.4), dann hast du anscheinend einen entsprechenden Rechner/ JVM/ was immer das schneller macht

wenn das langsam ist, dein Programm aber ähnliches mit Faktor 20 Unterschied schafft,
dann poste doch bitte dein Programm, möglichst komplett in möglichst wenigen Code-Blöcken,
die parallel-Variante kannst du dabei weglassen, Seriell erstmal interessant,

und Zeitmessungscode auch nicht so wichtig, falls nicht leicht zu integrieren, aber besser doch um möglichst diese Ergebnisse zu sehen, selbst wenn sie vielleicht an der Messung liegen,
Testdaten kann ich mir auch selber generieren, aber wiederum gut falls doch dabei, falls es daran liegt

22

Ich habe mal deinen Code aus #17 ausgeführt:

5239993975677955 - 571
5239993975677955 - 4211
5239993975677955 - 506
5239993975677955 - 4141
5239993975677955 - 505
5239993975677955 - 4145

Nicht ganz 10, aber deutlich höher als 3.4. Vllt ist das echt rechnerspezifisch.

23

und mit 2000er Matrixen komme ich bei mir auf Faktor 5+ statt 3+, das erklärt vielleicht weitere Erhöhung auf 20 bei dir,
dann bin ich vorerst zufrieden,
naja, morgen, wenn du deinen Rechner mitgebracht hast zum Tausch

24

:smiley: Jaja. Xeon E3 1230v3 Preisleistungswunder. Wobei die Zeiten für den normal-seriellen Algorithmus ja ziemlich nah beeinander liegen. Das zeilenweise multiplizieren geht dann aus welchen Gründen auch immer wesentlich schneller.

Wenn ich die Matrizen wieder vergrößere auf 1024x1024, komme ich auch fast wieder auf identische Werte:
14072338906485700 - 1016
14072338906485700 - 11287
14072338906485700 - 1030
14072338906485700 - 11422
14072338906485700 - 1015
14072338906485700 - 11311

Schon erstaunlich, das das relativ simple transponieren solche Unterschiede in der späteren Multiplikation verursacht.

25

Nur kurz nebenbei: Die Größe spielt keine Rolle. Das behauptet zumindest meine Freundin immer gebetsmühlenartig. :o) Mal im Ernst: Sie spielt eine Rolle. Insbesondere die größe der Caches. (Ich glaube, der Xeon hat tendenziell größere Caches, aber das ist Halbwissen, genau wie alles, was ich über die tatsächlichen Einflüsse und Funktionsweisen der Caches sagen könnte - das ist durch die JVM ja SO weit weg vom Code, dass da (zu) viel Spekulation dabei wäre).

26

Die Geschwindigkeitssteigerung durch Parallelisierung lässt sich ggf. noch ein wenig erhöhen, wenn du mit einem Executor arbeitest und eine feste Anzahl an Threads vorgibst (1,5x Anzahl Kerne). Da sparst du einen Haufen Threads zu erstellen und es muss weniger zwischen Threads geswitched werden.

Dazu habe ich vor kurzem etwas hochinteressantes über den LMAX Disruptor gelesen (The LMAX Architecture und als Video LMAX - How to Do 100K TPS at Less than 1ms Latency). Dort wird von mechanical sympathy gesprochen und unter anderem auch auf die Bedeutung der verschiedenen Caches eingegangen. Java ist also offensichtlich nicht ganz so weit weg von der Hardware, dass man diese Einflüsse nicht ausnutzen könnte.

27

Also ich hab hier ein Test Programm geschrieben, bei dem der Arrayzugriff noch viel extremere Ausmaße annimmt.
Hier haben wir ein Verhältnis von 84 zu 5431 Millisekunden das Beispiel braucht aber auch 2GB Arbeitsspeicher (-Xmx2G)

Das Programm mach nichts anders als alle Werte eines Arrays zu summieren
nur einmal durchlauft es zuerst die Zeilen und dann die Spalten beim anderen genau umgekehrt

public class SumMatrixTest {
	
	
	public static void main(String[] args){
		
		for (int i=0;i<5;i++){
			int[][] test = fillintArray();
			long start = System.currentTimeMillis();
			long sum2 = sumArrayFast(test);
			long stop1 = System.currentTimeMillis();			
			long sum = sumArraySlow(test);
			long stop2 = System.currentTimeMillis();
			
			System.out.print(sum==sum2);
			System.out.print("  |  ");
			System.out.print(stop1-start);
			System.out.print("  |  ");
			System.out.println(stop2-stop1);
			
					
		}
	}
	
	private static long sumArrayFast(int[][] test) {
		long sum = 0;
		for (int i = 0;i<test.length;i++){
			for (int j= 0;j<test**.length;j++){
				sum+= test**[j];
			}
		}
		return sum;
	}

	private static long sumArraySlow(int[][] test) {
		long sum = 0;
		for (int i = 0;i<test.length;i++){
			for (int j= 0;j<test**.length;j++){
				sum+= test[j]**;
			}
		}
		return sum;
	}

	private static int[][] fillintArray() {
		int[][] array = new int[Short.MAX_VALUE/2][Short.MAX_VALUE/2];

		Random r = new Random();
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array**.length; j++) {
				array**[j] = r.nextInt(Byte.MAX_VALUE);

			}
		}
		return array;
	}
}
28

Letztendlich ist das ganze logisch.

Betrachtet man mal eine etwas Systemnähere Sprache dann wird das offensichtlich.

Dort hat man für ein Array von integern z.B. einen Befehl ähnlich diesem

address = malloc(sizeof(int)*arraysize);

Damit liegen die Integer schön in reih und glied hintereinander im Speicher.

Wenn man nun Objekte / structs hat und diese in einem Array ablegen möchte, dann sieht das eher so aus.

address = malloc(sizeof(pointer) * arraysize);

Jetzt liegen die Pointer zu den Objekten in Reih und Glied im Speicher. Die Daten auf die die Pointer verweisen können über das gesamte System verstreut sein.

Bei einem Mehrdimensionalen Array hat man ein Array von Arrays.

Im ersten Array, dürften nur Pointer liegen, zu den anderen Arrays. Diese wiederum könnten, sofern alles passt wieder schön aufgereiht im Speicher liegen, da ein Int eine feste größe von 32 Bit belegt.

Modeliert man ein 3 x 3 Matrix anders wird es offensichtlicher

r1 = {1,2,3};
r2 = {4,5,6};
r3 = {7,8,9};

matrix = {r1, r2, r3};

Möchte man nun den Vektor 1,2,3 haben so holt man sich aus der Matrix den “Pointer” zu r1 und liest von dort die Werte evtl. schon am Stück ein.

Möchte man den Vektor 3,6,9 haben. Dann muss man sich alle 3 “Pointer” holen, und damit dann jeweils zur letzten Adresse Springen um sich dann ein Array mit den Zahlen zusammenzusuchen.

Ich gehe davon aus, dass wenn auf einen Speicherbereich zugegriffen wird, dann evtl. auch mehr auf einmal gelesen werden kann und damit auch mehr gecacht wird.

29

Ich hab mal ein bisschen nachgelesen, ich vermute mal, dass caching da die entscheidende Rolle spielt

[JavaSpecialists 070] - Too many dimensions are bad for you (leider uralt)

Java: Multi-dimensional array vs. One-dimensional - Stack Overflow

Caching In: Understand, Measure and Use your CPU Cache more effectively

**
Multidimensional arrays (in Java) are arrays of arrays, so not necessarily close in physical memory. You can convert a multidimensional array to a linear array, e.g. using a calculated index like array[ROWS * col + row]. Make sure the inner loop is iterating over sequential elements, if you get this the wrong way round you’ll just get cache misses all the time (i.e. NOT array[COLS * row + col], but array[ROWS * col + row] where the inner loop is for (int row=0; row < ROWS; row++)
**

30

Das mit den Arrays und Cache werd ich mir im Laufe den Tages nochmal genauer durchlesen.

Hab grade nochmal diesen Tipp befolgt:

[QUOTE=cmrudolph]Die Geschwindigkeitssteigerung durch Parallelisierung lässt sich ggf. noch ein wenig erhöhen, wenn du mit einem Executor arbeitest und eine feste Anzahl an Threads vorgibst (1,5x Anzahl Kerne). Da sparst du einen Haufen Threads zu erstellen und es muss weniger zwischen Threads geswitched werden.
[/QUOTE]

Hatte nach meiner „trivialen“ Version erst mit einem CachedThreadPool gearbeitet. Der hat natürlich Threads ohne Ende rausgehauen.
Ich kam damit auf folgende Werte:
[spoiler]
Groesse der Matrix 64

Seriell: 2
Parallel: 18
Speedup 0.1111111111111111
Transponiert Parallel: 18
Transponiert Seriell: 6
Speedup 0.3333333333333333

Groesse der Matrix 128

Seriell: 4
Parallel: 32
Speedup 0.125
Transponiert Parallel: 26
Transponiert Seriell: 2
Speedup 0.07692307692307693

Groesse der Matrix 256

Seriell: 26
Parallel: 6
Speedup 4.333333333333333
Transponiert Parallel: 10
Transponiert Seriell: 14
Speedup 1.4

Groesse der Matrix 512

Seriell: 244
Parallel: 70
Speedup 3.4857142857142858
Transponiert Parallel: 24
Transponiert Seriell: 116
Speedup 4.833333333333333

Groesse der Matrix 1024

Seriell: 10832
Parallel: 3190
Speedup 3.3956112852664577
Transponiert Parallel: 158
Transponiert Seriell: 953
Speedup 6.031645569620253
[/spoiler]

Also schonmal etwas höher.

Bin dann auf den FixedThreadPool gewechselt.
[spoiler]
Groesse der Matrix 64

Seriell: 1
Parallel: 14
Speedup 0.07142857142857142
Transponiert Parallel: 13
Transponiert Seriell: 5
Speedup 0.38461538461538464

Groesse der Matrix 128

Seriell: 4
Parallel: 28
Speedup 0.14285714285714285
Transponiert Parallel: 16
Transponiert Seriell: 2
Speedup 0.125

Groesse der Matrix 256

Seriell: 38
Parallel: 8
Speedup 4.75
Transponiert Parallel: 4
Transponiert Seriell: 17
Speedup 4.25

Groesse der Matrix 512

Seriell: 253
Parallel: 110
Speedup 2.3
Transponiert Parallel: 19
Transponiert Seriell: 113
Speedup 5.947368421052632

Groesse der Matrix 1024

Seriell: 10888
Parallel: 3094
Speedup 3.5190691661279896
Transponiert Parallel: 149
Transponiert Seriell: 994
Speedup 6.671140939597316
[/spoiler]

Das ist das Ergnis wenn ich mit 12 Threads arbeite. Erziele mit ~12 Threads die besten Werte. Auffällig ist auch, dass der Speedup von normal-seriell zu normal-parallel bei einer Matrixgröße von 512x512 immer sehr stark abfällt.
War ja beim CachedThreadPool schon etwas zu sehen aber mit dem FixedThreadPool fällt es auch nach mehr als 20 Durchläufen auf, dass es wesentlich stärker droppt. Auch wenn ich die Anzahl der Threads ändere.

Naja wird warsch. auch irgendwie mit dem Cache zusammenhängen. Bin erstmal ganz zufrieden :slight_smile:

31

Und jetzt noch mal die ganzen Benchmarks mit einem ordentlichen MB-Framework wie dem JMH.

32

:wink: Werd ich später dann nochmal machen.

Falls es irgendeinen interessiert könnte ich auch die .jar bereitstellen.