You are not logged in.

dluebke

Trainee

  • "dluebke" is male
  • "dluebke" started this thread

Posts: 37

Date of registration: Aug 26th 2004

1

Monday, August 7th 2006, 3:00pm

Spass & Java II

So, ich fand die Idee mit ein paar Denkaufgaben eigentlich ganz nett...
Hier also mal ein kleines Problem, was verdeutlichen soll, dass man nicht optimieren sollte, bevor man nicht ein lauffähiges Programm hat (also immer Methoden bitte erst klein machen und sauber hinschreiben!). Hier hat das aber nicht so viel mit Aufrufen zu tun, sondern ist ein ganz triviales Problem: Es soll eine Einheitsmatrix erzeugt werden (also alles 0, bis auf die Diagonale 1).

Verschiedene Vorschläge:

Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ForXyInitializer implements IMatrixInitializer {

	public void initialize(int[][] matrix) {
		for(int x = 0; x < matrix.length; x++) {
			for(int y = 0; y < matrix[x].length; y++) {
				if(x == y) {
					matrix[x][y] = 1;
				} else {
					matrix[x][y] = 0;
				}
			}
		}
	}
}


Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ForYxInitializer implements IMatrixInitializer {

	public void initialize(int[][] matrix) {
		for(int y = 0; y < matrix[0].length; y++) {
			for(int x = 0; x < matrix.length; x++) {
				if(x == y) {
					matrix[x][y] = 1;
				} else {
					matrix[x][y] = 0;
				}
			}
		}
	}
}


Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class SimpleInitializer implements IMatrixInitializer {

	public void initialize(int[][] matrix) {
		for(int x = 0; x < matrix.length; x++) {
			for(int y = 0; y < matrix[x].length; y++) {
				matrix[x][y] = 0;
			}
		}
		
		for(int x = 0; x < matrix.length; x++) {
			matrix[x][x] = 1;
		}
	}

}


Source code

1
2
3
4
5
6
7
8
9
10
11
public class MultiplyXyInitializer implements IMatrixInitializer {

	public void initialize(int[][] matrix) {
		for(int x = 0; x < matrix.length; x++) {
			for(int y = 0; y < matrix[x].length; y++) {
				matrix[x][y] = ((x + 1)/(y + 1)) * ((y + 1)/(x + 1));
			}
		}
	}

}


Source code

1
2
3
4
5
6
7
8
9
10
11
public class MultiplyYxInitializer implements IMatrixInitializer {

	public void initialize(int[][] matrix) {
		for (int y = 0; y < matrix[0].length; y++) {
			for (int x = 0; x < matrix.length; x++) {
				matrix[x][y] = ((x + 1) / (y + 1)) * ((y + 1) / (x + 1));
			}
		}
	}

}


Alle Vorschläge sollten das richtige Ergebnis liefern (auch wenn ich das jetzt nicht überprüft habe...), wobei die beiden letzten sicherlich etwas kurios sind. Habe auch ein Benchmark dazu (daher auch die Interfaces, war zu faul, die rauszunehmen).

Mal ohne das Ganze auszuführen: Welcher Variante ist die schnellste? Und viel interessanter: Warum?

Daniel

This post has been edited 1 times, last edit by "dluebke" (Aug 7th 2006, 3:04pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Monday, August 7th 2006, 3:19pm

RE: Spass & Java II

Quoted

Original von dluebke
Mal ohne das Ganze auszuführen: Welcher Variante ist die schnellste? Und viel interessanter: Warum?
Hmm, gute Frage. :)

Ich tippe mal auf Variante 3, da dort in den Schleifendurchläufen keine Fallunterscheidungen geprüft werden müssen (da die Bedingung von x und y abhängt, wird der Compiler hierbei in den anderen Varianten wohl nicht viel optimieren können). Das doppelte Initialisieren der Diagonalen dürfte hingegen bei großen Matrizen nichts ins Gewicht fallen.

EDIT: Dann nehme ich den (neu hinzu gekommenen) SimpleInitializer2, da dort auch die von x abhängigen Längenprüfungen entfallen; das sollte sich von Compiler und VM besser optimieren lassen. Ein Nachteil könnte hier allerdings die veränderte Iterationsreihenfolge sein; ich hoffe hier aber auf den Compiler und die VM, da die Ausführungsreihenfolge hier keine Rolle spielt und dies auch einfach automatisch erkannt werden könnte, also die "beste" Iterationsreihenfolge vom Compiler oder der VM gewählt werden könnte.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 4 times, last edit by "Joachim" (Aug 7th 2006, 3:35pm)


dluebke

Trainee

  • "dluebke" is male
  • "dluebke" started this thread

Posts: 37

Date of registration: Aug 26th 2004

3

Monday, August 7th 2006, 3:22pm

RE: Spass & Java II

Sorry, fehlte noch einer :-)

Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class SimpleInitializer2 implements IMatrixInitializer {

	public void initialize(int[][] matrix) {
		for(int y = 0; y < matrix[0].length; y++) {
			for(int x = 0; x < matrix.length; x++) {
				matrix[x][y] = 0;
			}
		}
		
		for(int x = 0; x < matrix.length; x++) {
			matrix[x][x] = 1;
		}
	}

}

dfex

Junior Schreiberling

  • "dfex" is male

Posts: 248

Date of registration: Dec 11th 2001

4

Monday, August 7th 2006, 3:44pm

RE: Spass & Java II

Quoted

Original von Joachim
... da dort in den Schleifendurchläufen keine Fallunterscheidungen geprüft werden müssen (da die Bedingung von x und y abhängt, wird der Compiler hierbei in den anderen Varianten wohl nicht viel optimieren können). Das doppelte Initialisieren der Diagonalen dürfte hingegen bei großen Matrizen nichts ins Gewicht fallen.


Ich würde Joachim auch recht geben und nochmal etwas zu den Compares anmerken. In der zusätzlichen for Schleife des SimpleInitializer2 wird natürlich auch in jedem Schritt ein Compare durchgeführt (x < matrix.length). Allerdings liegt die Anzahl der Vergleiche hier deutlich (quadratisch) unter denen vom ForXYInitializer. Sollten die Vergleiche also wirklich das Aufwändige sein, sollte SimpleInitializer2 schneller sein.


P.S.: Der direkte Zugriff auf die Arraylängen ist höchstwahrscheinlich durch den Compiler besser optimierbar. Aber Frage an Joachim: Warum sollte bzw. könnte es in diesem Fall einen Unterschied machen, wenn die Iterationsreihenfolge vertauscht ist und vom Compiler nicht optimiert werden kann?

denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

5

Monday, August 7th 2006, 3:44pm

Also entweder initialize static oder matrix als Objektvariable.

Unter der Annahme, daß wir von quadratischen Matrizen ausgehen (ansonsten wäre matrix[x][x]=1 auch fraglich), möchte ich noch folgendes vorschlagen:

Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class SimpleInitializer3 implements IMatrixInitializer {

        public void initialize(int[][] matrix) {
                int n = matrix.length;
                for(int y = n; y-- > 0;) {
                        int [] zeile=matrix[y];
                        for(int x = n; x-- > 0;) {
                                zeile[x] = 0;
                        }
                        zeile[y] = 1;
                }
        }

}


Grundsätzlich würde ich aber Matrizen als int[] statt als int[][] machen, da ein Objekt pro Zeile bzw. Spalte nicht wirklich performant ist. Dann könnte auch ein Arrays.fill(matrix,0) etwas bringen, wenn SUN das endlich mal native implementieren würde (System.arraycopy ist ja schon native).

Werde die Ansätze mal benchmarken.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

6

Monday, August 7th 2006, 3:53pm

RE: Spass & Java II

Quoted

Original von dfex
Aber Frage an Joachim: Warum sollte bzw. könnte es in diesem Fall einen Unterschied machen, wenn die Iterationsreihenfolge vertauscht ist und vom Compiler nicht optimiert werden kann?
int[][] ist soweit ich weiß ein Array von Arrays. Eventuell macht es einen Geschwindigkeitsunterschied, ob ich zunächst die "innersten" Arrays jeweils komplett abarbeite (das erscheint mir intuitiv schneller, das kann aber täuschen) oder zwischen ihnen hin- und herspringe. Um das beurteilen zu können, müßte ich jedoch wissen, wie Java intern mit derartigen Speicherzugriffen umgeht. Vielleicht fällt das (wenn überhaupt) auch erst bei sehr großen Matrizen ins Gewicht, die nicht vollständig im Arbeitsspeicher gehalten werden können.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Aug 7th 2006, 3:54pm)


DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

7

Monday, August 7th 2006, 5:27pm

Quoted

Original von dluebke
Mal ohne das Ganze auszuführen: Welcher Variante ist die schnellste? Und viel interessanter: Warum?

Auf welcher Maschine?, Additionen und Vergleiche kosten das hundertfache von Multiplikationen, richtig? ;)
Ich würde mich fragen: Macht es für eine Interpretersprache überhaupt Sinn, etwas derartig optimieren zu wollen?

Trotzdem tippe ich jetzt auch mal auf SimpleInitializer 2 oder 3.

This post has been edited 1 times, last edit by "DrChaotica" (Aug 7th 2006, 5:29pm)


denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

8

Monday, August 7th 2006, 5:47pm

Benchmark-Ergebnisse:

Alles unter x86 Linux auf einer relativ alten Kiste.
S=SUN javac bzw. java JVM 1.5.0_06-b05
E=Eclipse ecj 0.671, 3.2.0 release
G=GNU gcj 4.1.1
I=GNU gij 4.1.1

Zeiten in Millisekunden für 5000 Durchläufe bei einer 100x100 Matrix

Source code

1
2
3
4
5
6
7
8
9
Compiler/JVM          S/S   E/S   G/S   S/I   E/I   G/I   S/G   E/G   G/G
---------------------------------------------------------------------------
MultiplyXyInitializer 12918 12918 12912 66969 66200 66972 11673 11675 11614
MultiplyYxInitializer 10943 10948 10939 66066 66263 65997 11302 11511 11135
ForXyInitializer      2503  2052  2488  34519 34252 34520 718   715   720
ForYxInitializer      2395  2123  2339  32103 32324 32073 6902  6900  6901
SimpleInitializer     2243  1949  2261  25158 24235 25153 745   744   745
SimpleInitializer2    1936  1977  2134  22823 23091 22821 6553  6555  6543
SimpleInitializer3    1290  1137  1287  18262 16033 17612 701   700   700


Zum Vergleich 5000000 Durchläufe mit einer 3x3 Matrix S/S:

Source code

1
2
3
4
5
6
7
MultiplyXyInitializer 12842
MultiplyYxInitializer 11369
ForXyInitializer      3396
ForYxInitializer      2997
SimpleInitializer     3360
SimpleInitializer2    3019
SimpleInitializer3    2535


Fazit:
1. der Compiler ist relativ egal
2. gij ist enttäuschend
3. bei gcj sind Arrayzugriffe lahm, wenn er sie nicht wegoptimieren kann
4. I am the winner! :D

Phill

Trainee

  • "Phill" is male

Posts: 78

Date of registration: May 30th 2006

Location: Atlanta, GA, USA

Occupation: Exotic Dancer

9

Monday, August 7th 2006, 9:37pm

Müss eine Matrix eingegeben werden, um diese Matrix zu erzeugen? Wenn nicht, würde ich empfehlen:

Source code

1
2
3
4
5
6
7
public static int[][] makeIdentityMatrix(int n){
    int[][] matrix = new int[n][n];
    for(int i=0; i<n; i++){
        matrix[i][i] = 1;
    }
    return matrix;
}

da ein int immer als 0 initialisiert wird.

EDIT:
Eigentlich kann eine Matrix auch eingegeben werden, die man benutzen kann, die neue Matrix zu definieren.

This post has been edited 4 times, last edit by "Phill" (Aug 8th 2006, 6:23am)


denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

10

Tuesday, August 8th 2006, 12:02am

Nur so zur Info,

Source code

1
2
3
int array[100][100];
for(int i=5000;i--;)
  memset(array,0,sizeof(array));
braucht mit -O3 gebaut 685ms auf dem Rechner.
Java ist also schon sehr nah an der Grenze.

cowhen

Muuuh!

  • "cowhen" is male

Posts: 1,374

Date of registration: Dec 13th 2001

11

Tuesday, August 8th 2006, 12:20am

Quoted

Original von Dr.Chaotica
Macht es für eine Interpretersprache überhaupt Sinn, etwas derartig optimieren zu wollen?

Quoted

Original von denial
Nur so zur Info,

Source code

1
2
3
int array[100][100];
for(int i=5000;i--;)
  memset(array,0,sizeof(array));
braucht mit -O3 gebaut 685ms auf dem Rechner.
Java ist also schon sehr nah an der Grenze.


Das finde ich sehr interessant. Vielfach hat sich ja die Meinung festgesetzt: "Java -> interpretiert -> langsam".


Quoted

Original von Dr.Chaotica
Additionen und Vergleiche kosten das hundertfache von Multiplikationen, richtig? ;)

Multiplikation sollte nur dann schnell sein, wenn man sie durch eine Verschiebung realisieren kann (Multiplikation mit der Basis), oder?
plenty of time to relax when you are dead

denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

12

Tuesday, August 8th 2006, 3:21am

Sobald man die Matrix in den (in diesem Fall 16KB) L1 Cache passen läßt, sieht das Ergebnis etwas anders aus...

50x50 Matrix mit 20000 Durchläufen

Source code

1
2
3
4
5
6
7
8
9
                      S/S   G/G
---------------------------------
MultiplyXyInitializer 12971 11058
MultiplyYxInitializer 11004 11344
ForXyInitializer      2527  823
ForYxInitializer      2065  694
SimpleInitializer     2258  369
SimpleInitializer2    1638  673
SimpleInitializer3    1312  506


ForYxInitializer ist in SUNs JVM also schneller als SimpleInitializer und gcj mag meine rückwärtszählenden Schleifen nicht.

Die C memset Schleife setzt bei dieser Matrizengröße die Meßlatte auf 112ms.

maffe

Unregistered

13

Tuesday, August 8th 2006, 4:35am

Quoted

Original von cowhen
Das finde ich sehr interessant. Vielfach hat sich ja die Meinung festgesetzt: "Java -> interpretiert -> langsam".

Ist ja auch so, wenn in Firefox ein Java-Applet eingebunden ist, rödelt die Festplatte erstmal (gefühlte) 12 Minuten, bis die VM geladen ist.

Phill

Trainee

  • "Phill" is male

Posts: 78

Date of registration: May 30th 2006

Location: Atlanta, GA, USA

Occupation: Exotic Dancer

14

Tuesday, August 8th 2006, 6:31am

Quoted

Original von maffe

Quoted

Original von cowhen
Das finde ich sehr interessant. Vielfach hat sich ja die Meinung festgesetzt: "Java -> interpretiert -> langsam".

Ist ja auch so, wenn in Firefox ein Java-Applet eingebunden ist, rödelt die Festplatte erstmal (gefühlte) 12 Minuten, bis die VM geladen ist.


Windows und Linux brauchen auch Zeit zu laden. Das heißt aber nicht, dass die Programmen, die compiliert sind auch langsam sind. Genauer gesagt: die Ladezeit des Betriebssystems hat fast nichts mit der Laufzeit eines Programms zu tun. Die interpretation von Java ist nicht so langsam, die Ladezeit des erforderlichen "Betriebssystem" ist.

Ich sage nicht, das Java so schnell wie compilierte C ist, aber die Interpretation von Bytecode ist ziemlich schnell (mit JIT).

This post has been edited 3 times, last edit by "Phill" (Aug 8th 2006, 9:07am)


Phill

Trainee

  • "Phill" is male

Posts: 78

Date of registration: May 30th 2006

Location: Atlanta, GA, USA

Occupation: Exotic Dancer

15

Tuesday, August 8th 2006, 6:34am

.

This post has been edited 1 times, last edit by "Phill" (Aug 8th 2006, 6:35am)


DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

16

Tuesday, August 8th 2006, 9:45am

Quoted

Original von cowhen

Quoted

Original von Dr.Chaotica
Macht es für eine Interpretersprache überhaupt Sinn, etwas derartig optimieren zu wollen?

Quoted

Original von denial
Nur so zur Info,

Source code

1
2
3
int array[100][100];
for(int i=5000;i--;)
  memset(array,0,sizeof(array));
braucht mit -O3 gebaut 685ms auf dem Rechner.
Java ist also schon sehr nah an der Grenze.


Das finde ich sehr interessant. Vielfach hat sich ja die Meinung festgesetzt: "Java -> interpretiert -> langsam".


Was ist -O3? Ist das jetzt immer noch Java gewesen? Wenn ja: Es gibt eine memset - Implementierung, aber kein array.fills(..)? Aha, das wäre seltsam...

Quoted

Original von denial
Sobald man die Matrix in den (in diesem Fall 16KB) L1 Cache passen läßt, sieht das Ergebnis etwas anders aus...

50x50 Matrix mit 20000 Durchläufen

Source code

1
2
3
4
5
6
7
8
9
                      S/S   G/G
---------------------------------
MultiplyXyInitializer 12971 11058
MultiplyYxInitializer 11004 11344
ForXyInitializer      2527  823
ForYxInitializer      2065  694
SimpleInitializer     2258  369
SimpleInitializer2    1638  673
SimpleInitializer3    1312  506


ForYxInitializer ist in SUNs JVM also schneller als SimpleInitializer und gcj mag meine rückwärtszählenden Schleifen nicht.

Die C memset Schleife setzt bei dieser Matrizengröße die Meßlatte auf 112ms.


Anscheinend ist C ja doch selbst bei so primitiven Initialisierungen fast fünf Mal so schnell.
Das mit dem L1-Cache ist ja cool, leider kommts aber wohl nie vor dass man immer wieder die selbe kleine Matrix (in dem gleichen Speicherplatz) initialisieren wird, ausser man ist wirklich sehr vergesslich :)

Quoted


Quoted

Original von Dr.Chaotica
Additionen und Vergleiche kosten das hundertfache von Multiplikationen, richtig? ;)

Multiplikation sollte nur dann schnell sein, wenn man sie durch eine Verschiebung realisieren kann (Multiplikation mit der Basis), oder?

Hey, Du hast eiskalt das Smilie übersehen :). Allgemein ist die Multiplikation langsam, aber das braucht ja theorethisch gar nicht so zu sein, dann müsste man sich eben den Prozessor vorher anschauen. Ist so ähnlich wie mit diesen Scherzfragen auf den KVA-Übungszetteln, wo sie dich fragen, ob für n=1000 ein O(n)- oder ein O(n²)-Algorithmus schneller sein wird, man weiss es nicht...
Ab wann ist man denn mit Shiftoperationen und Additionen mit einem Durchschnittsprozessor schneller als mit einer Multiplikation? Ist für Integer statt 3*i schon i+(i<<1) besser? (hoffe, ich habe die < - Zeichen gerade richtig herum gesetzt...)

EDIT: gcj kann ja wirklich nativen Code erzeugen, das wußte ich gar nicht. Kann man denn mit einem so kompilierten Javaprogramm immer noch alles machen, was man auch mit einem interpretierten Programm tun könnte? Irgendwo gibt es doch dann garantiert Einschränkungen, wie sieht es mit Reflections etc. aus? Dann wäre aber irgendwie Java!=Java, ziemlich unschön finde ich...

This post has been edited 1 times, last edit by "DrChaotica" (Aug 8th 2006, 12:21pm)


dluebke

Trainee

  • "dluebke" is male
  • "dluebke" started this thread

Posts: 37

Date of registration: Aug 26th 2004

17

Tuesday, August 8th 2006, 11:20am

Ich habe auch noch mal ein paar Zahlen (habe den SimpleInitializer3 noch nicht drin, dafür mal eine Variante, wo ich das if( == ) zu einem if( != ) gemacht habe...

Dann sieht das auf Windows XP (Bürorechner...) SP2, JRE 1.5.0_06, 1300x1300 Matrix mit je 1000 Durchläufen folgendermaßen aus:

Source code

1
2
3
4
5
6
7
Initializer de.unihannover.se.matrixtest.ForXyInitializer [6750ms]
Initializer de.unihannover.se.matrixtest.ForYxInitializer [29047ms]
Initializer de.unihannover.se.matrixtest.SimpleInitializer [5921ms]
Initializer de.unihannover.se.matrixtest.SimpleInitializer2 [28469ms]
Initializer de.unihannover.se.matrixtest.MultiplyXyInitializer [64766ms]
Initializer de.unihannover.se.matrixtest.MultiplyYxInitializer [64547ms]
Initializer de.unihannover.se.matrixtest.ForXyInitializer2 [6765ms]


Jetzt, wo wir die Zahlen haben, stellt sich immer noch die Frage nach den Effekten, die das bewirken... Die meisten kamen ja schon auf: Vergleiche, arithmetische Operationen und Cacheeffekte. Das lustige ist halt, dass der Prozessorcache eine entscheidende Rolle bei den Speicherzugriffen spielt. Daher ist die intuitive Variante eine xy-Schleife zu machen deutlich besser. Die "inneren" Arrays (also die zweite []) liegen sequentiell im Speicher, so dass die Cache-Hit-Raten i.d.R. sehr gut sind. Dagegen hat man immer direkte Speicherzugriffe (am Cache vorbei), wenn man im Speicher rumspringt. (s. ForYxIntializer, da sage noch einer mal, RAM sei schnell...). Nachdem schonmal geklärt ist, in welcher Reihenfolge man durch das Array schwirrt, stellt sich die Frage, was mit den Sachen dadrin passiert. Regel ist, man sollte möglichst wenig in Schleifen machen... (vor allem, wenn es eine quadratische Schleife wie hier ist). Multiplikationen sind selbst auf typischer, moderner Hardware tötlich, daher sind die Multiply-Varianten zwar verschachtelungsarm (McCabe) und relativ kompakt, aber von der Laufzeit richtig schlecht. Die ifs sind Sachen, die Zeit kosten. Was mich gewundert hat, ist, dass es zu Turbo Pascal Zeiten hieß, der if-Zweig würde auf i386 um 1 Takt schneller ausgeführt als der else-Zweig. Dies scheint wohl nicht mehr der Fall zu sein, da der For2-Initializer langsamer ist.
Die Frage, die sich dann stellt, ist, ob es schneller ist, die ifs zu machen oder ein zweites Mal über das Array zu iterieren, um die 1en zu setzen. Da die 1en aber nur n Speicherzugriffe mit n Inkrementen und n Vergleichen darstellen (verglichen mit n² Vergleichen) ist dies bei "großen" Matrizen sicherlich schneller.

All dies relativiert sich natürlich sehr schnell, wenn man mit Matrizen arbeitet, die komplett gecached werden können.
Insgesamt kann man daraus lernen, dass jede der beiden Variante, die einem normalerweise eingefallen wäre (also forXy und Simple) schnell genug für eine normale Anwendung. Denkt man nun daran zu optimieren, bevor man das weiß (die Multiply-Lösung kommt daher, ist also nicht "ersponnen" sondern ein echtes Beispiel... - man spart ja n² teure Vergleiche...) macht man erstmal mehr kaputt.

Mich würde ja mal interessieren, ob jemand mal einen Benchmark machen würde, wo eine Methode in drei private Methoden zerteilt wird, die nur lokale Variablen haben vs. eine, die in drei private Methoden zerteilt wird, die auf Instanzvariablen zugreifen vs. halt die Methode in einem Stück (s. Threaddiskussion woanders zu Java und Lesbarkeit vs. Performance von langen Methoden). Ich würde wetten, dass der Unterschied richtig zu vernachlässigen ist :-)

Vor allem, weil - wie auch schon irgendwo mal bemerkt - man immer nur auf eine Plattform hinoptimieren kann. Deswegen ist es auch schonmal interessant zu sehen, wie der gcj (hat jemand eine IBM VM oder noch was anderes installiert?) mit dem Benchmark umgeht... Und wenn man dann zu früh optimiert... Könnt Ihr Euch ja selber ausrechnen :-)

Anbei noch der Benchmark:

Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Main {

	private static final int MATRIX_DIMENSION = 1300;

	private static final int TEST_RUNS = 1000;

	private static final IMatrixInitializer[] INITIALIZERS = {
			new ForXyInitializer(), new ForYxInitializer(),
			new SimpleInitializer(), new SimpleInitializer2(),
			new MultiplyXyInitializer(), new MultiplyYxInitializer(),
			new ForXyInitializer2() };

	public static void main(String[] args) {

		int[][] matrix = new int[MATRIX_DIMENSION][MATRIX_DIMENSION];

		for (IMatrixInitializer initializer : INITIALIZERS) {
			System.out.print("Initializer " + initializer.getClass().getName());

			long start = System.currentTimeMillis();
			for (int i = 0; i < TEST_RUNS; i++) {
				initializer.initialize(matrix);
			}
			long finish = System.currentTimeMillis();

			System.out.printf(" [%dms]\n", finish - start);
		}
	}
}


P.S. Hat sonst jemand noch interessante Java-Fragestellungen?
P.P.S. Ja, ich wußte auch, dass Java int-Arrays mit 0 initialisiert... Aber das sollte hier ja nicht gezeigt werden... :-)

This post has been edited 1 times, last edit by "dluebke" (Aug 8th 2006, 12:47pm)


denial

Erfahrener Schreiberling

  • "denial" is male

Posts: 394

Date of registration: Feb 18th 2003

Location: Göttingen

Occupation: Linux Coder (ex Mathe SR Inf Student)

18

Tuesday, August 8th 2006, 1:00pm

Quoted

Original von DrChaotica
Was ist -O3? Ist das jetzt immer noch Java gewesen? Wenn ja: Es gibt eine memset - Implementierung, aber kein array.fills(..)? Aha, das wäre seltsam...
Ich dachte es wäre offensichtlich, daß das kein gültiges Java ist. In Java kann man Arrays (leider) nicht so deklarieren und Integer wie i-- casten nicht nach boolean.

Quoted

Original von dluebke
Dann sieht das auf Windows XP (Bürorechner...)

Bürorechner die 1GB/s in den Hauptspeicher blasen können... Geldverschwendung.

Quoted

Multiplikationen sind selbst auf typischer, moderner Hardware tötlich, daher sind die Multiply-Varianten zwar verschachtelungsarm (McCabe) und relativ kompakt, aber von der Laufzeit richtig schlecht.

Die Multiplikationen sind nicht das Problem. Die dauern auf heutigen Rechnern höchstens so lange wie 4 Additionen. Das tödliche sind die Divisionen.

Quoted

Die ifs sind Sachen, die Zeit kosten. Was mich gewundert hat, ist, dass es zu Turbo Pascal Zeiten hieß, der if-Zweig würde auf i386 um 1 Takt schneller ausgeführt als der else-Zweig.

Heute gibt es branch prediction. Damals mußte der 486 seine Pipeline neu füllen. Und je größer du die Matrix machst, desto unwahrscheinlicher wird der Fall mit den einsen.

Quoted

Insgesamt kann man daraus lernen, dass jede der beiden Variante, die einem normalerweise eingefallen wäre (also forXy und Simple) schnell genug für eine normale Anwendung.
Wenn man beim Programmieren Matrizen benutzt, möchte man meist sehr viel rechnen. Und in einem solchen Fall gibt es kein "schnell genug". Stell dir vor bei Doom 3 hätte sich der Programmierer der Matrizenmultiplikation gesagt "brauch ich nicht optimieren, ist schnell genug".

maffe

Unregistered

19

Tuesday, August 8th 2006, 1:59pm

Quoted

Original von Phill

Quoted

Original von maffe

Quoted

Original von cowhen
Das finde ich sehr interessant. Vielfach hat sich ja die Meinung festgesetzt: "Java -> interpretiert -> langsam".

Ist ja auch so, wenn in Firefox ein Java-Applet eingebunden ist, rödelt die Festplatte erstmal (gefühlte) 12 Minuten, bis die VM geladen ist.


Windows und Linux brauchen auch Zeit zu laden. Das heißt aber nicht, dass die Programmen, die compiliert sind auch langsam sind. Genauer gesagt: die Ladezeit des Betriebssystems hat fast nichts mit der Laufzeit eines Programms zu tun. Die interpretation von Java ist nicht so langsam, die Ladezeit des erforderlichen "Betriebssystem" ist.

Ich sage nicht, das Java so schnell wie compilierte C ist, aber die Interpretation von Bytecode ist ziemlich schnell (mit JIT).

Hast ja recht, aber mein OS läuft halt, solange der Computer an ist (abzüglich Bootzeit natürlich), und die VM eben nicht. Und das OS muss ich sowieso booten, eine Java-VM brauche ich hingegen nicht unbedingt.

dluebke

Trainee

  • "dluebke" is male
  • "dluebke" started this thread

Posts: 37

Date of registration: Aug 26th 2004

20

Tuesday, August 8th 2006, 2:12pm

Quoted

Original von denial

Quoted

Original von dluebke
Dann sieht das auf Windows XP (Bürorechner...)

Bürorechner die 1GB/s in den Hauptspeicher blasen können... Geldverschwendung.


Du weißt, was wir hier machen, oder? Ich mache nicht nur Textverarbeitung etc. hier... Aber gut. Aber davon mal ab, kann heutzutage jeder dumme Bürorechner das. Deswegen muss man halt auch nicht so viel optimieren. Und ja, das ist technisch nicht so "sauber" für Geeks, aber es ist halt wirtschaftlicher.

Quoted


Quoted

Die ifs sind Sachen, die Zeit kosten. Was mich gewundert hat, ist, dass es zu Turbo Pascal Zeiten hieß, der if-Zweig würde auf i386 um 1 Takt schneller ausgeführt als der else-Zweig.

Heute gibt es branch prediction. Damals mußte der 486 seine Pipeline neu füllen. Und je größer du die Matrix machst, desto unwahrscheinlicher wird der Fall mit den einsen.


Ich weiß schon, dass es Branch Prediction gibt. Und ich weiß auch warum die Dinger früher langsamer waren. Aber warum läuft es jetzt dann andersrum langsamer!!!??? Das ist das, was mich gewundert hat. Die Branchprediction sollte ja diesen Nachteil ausgleichen, nicht ihn in das Gegenteil verkehren, oder?

Quoted


Quoted

Insgesamt kann man daraus lernen, dass jede der beiden Variante, die einem normalerweise eingefallen wäre (also forXy und Simple) schnell genug für eine normale Anwendung.

Wenn man beim Programmieren Matrizen benutzt, möchte man meist sehr viel rechnen. Und in einem solchen Fall gibt es kein "schnell genug". Stell dir vor bei Doom 3 hätte sich der Programmierer der Matrizenmultiplikation gesagt "brauch ich nicht optimieren, ist schnell genug".

Die meisten Spiele rechnen nicht selber, sondern benutzen Libs und meistens sogar die Graphikkarte, um solche Dinge zu berechnen. Klar kommt es drauf an, was ich damit tun will (aber dann kann ich immer noch optimieren s.o.). Aber um ein LP zu lösen, würde das bei meinen Problemen nicht viel Unterschied machen :-)

Und davon ab, werden selbst die Doom 3 Programmierer an genug Stellen gesagt haben "passt schon, ist schnell genug".

This post has been edited 1 times, last edit by "dluebke" (Aug 8th 2006, 2:14pm)