Monday, August 7th 2006, 3:00pm
|
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));
}
}
}
}
|
This post has been edited 1 times, last edit by "dluebke" (Aug 7th 2006, 3:04pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, August 7th 2006, 3:19pm
Hmm, gute Frage.
Quoted
Original von dluebke
Mal ohne das Ganze auszuführen: Welcher Variante ist die schnellste? Und viel interessanter: Warum?
This post has been edited 4 times, last edit by "Joachim" (Aug 7th 2006, 3:35pm)
Monday, August 7th 2006, 3:22pm
|
|
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;
}
}
}
|
Monday, August 7th 2006, 3:44pm
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.
Date of registration: Feb 18th 2003
Location: Göttingen
Occupation: Linux Coder (ex Mathe SR Inf Student)
Monday, August 7th 2006, 3:44pm
|
|
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;
}
}
}
|
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, August 7th 2006, 3:53pm
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.
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?
This post has been edited 1 times, last edit by "Joachim" (Aug 7th 2006, 3:54pm)
Monday, August 7th 2006, 5:27pm
Original von dluebke
Mal ohne das Ganze auszuführen: Welcher Variante ist die schnellste? Und viel interessanter: Warum?
This post has been edited 1 times, last edit by "DrChaotica" (Aug 7th 2006, 5:29pm)
Date of registration: Feb 18th 2003
Location: Göttingen
Occupation: Linux Coder (ex Mathe SR Inf Student)
Monday, August 7th 2006, 5:47pm
|
|
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 |
|
|
Source code |
1 2 3 4 5 6 7 |
MultiplyXyInitializer 12842 MultiplyYxInitializer 11369 ForXyInitializer 3396 ForYxInitializer 2997 SimpleInitializer 3360 SimpleInitializer2 3019 SimpleInitializer3 2535 |
Monday, August 7th 2006, 9:37pm
|
|
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;
}
|
This post has been edited 4 times, last edit by "Phill" (Aug 8th 2006, 6:23am)
Date of registration: Feb 18th 2003
Location: Göttingen
Occupation: Linux Coder (ex Mathe SR Inf Student)
Tuesday, August 8th 2006, 12:02am
|
|
Source code |
1 2 3 |
int array[100][100]; for(int i=5000;i--;) memset(array,0,sizeof(array)); |
Tuesday, August 8th 2006, 12:20am
Original von Dr.Chaotica
Macht es für eine Interpretersprache überhaupt Sinn, etwas derartig optimieren zu wollen?
Original von denial
Nur so zur Info,
braucht mit -O3 gebaut 685ms auf dem Rechner.
Source code
Java ist also schon sehr nah an der Grenze.
Original von Dr.Chaotica
Additionen und Vergleiche kosten das hundertfache von Multiplikationen, richtig?
Date of registration: Feb 18th 2003
Location: Göttingen
Occupation: Linux Coder (ex Mathe SR Inf Student)
Tuesday, August 8th 2006, 3:21am
|
|
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 |
Tuesday, August 8th 2006, 4:35am
Original von cowhen
Das finde ich sehr interessant. Vielfach hat sich ja die Meinung festgesetzt: "Java -> interpretiert -> langsam".
Tuesday, August 8th 2006, 6:31am
Original von maffe
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.
This post has been edited 3 times, last edit by "Phill" (Aug 8th 2006, 9:07am)
Tuesday, August 8th 2006, 9:45am
Original von cowhen
Original von Dr.Chaotica
Macht es für eine Interpretersprache überhaupt Sinn, etwas derartig optimieren zu wollen?
Original von denial
Nur so zur Info,
braucht mit -O3 gebaut 685ms auf dem Rechner.
Source code
Java ist also schon sehr nah an der Grenze.
Das finde ich sehr interessant. Vielfach hat sich ja die Meinung festgesetzt: "Java -> interpretiert -> langsam".
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
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.
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?
. 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...This post has been edited 1 times, last edit by "DrChaotica" (Aug 8th 2006, 12:21pm)
Tuesday, August 8th 2006, 11:20am
|
|
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] |
|
|
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);
}
}
}
|
This post has been edited 1 times, last edit by "dluebke" (Aug 8th 2006, 12:47pm)
Date of registration: Feb 18th 2003
Location: Göttingen
Occupation: Linux Coder (ex Mathe SR Inf Student)
Tuesday, August 8th 2006, 1:00pm
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.
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...
Original von dluebke
Dann sieht das auf Windows XP (Bürorechner...)
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.
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".
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.
Tuesday, August 8th 2006, 1:59pm
Original von Phill
Original von maffe
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).
Tuesday, August 8th 2006, 2:12pm
Original von denial
Original von dluebke
Dann sieht das auf Windows XP (Bürorechner...)
Bürorechner die 1GB/s in den Hauptspeicher blasen können... Geldverschwendung.
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.
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".
This post has been edited 1 times, last edit by "dluebke" (Aug 8th 2006, 2:14pm)
