wieso läuft es (angeblich) langsamer???

[pecunia]

Hallo!

Wieso

int array = new int[1000];

for(int x=0; x<100; x++)

for(int y=0; y<100; y++)

array[x+y*90] = 1;

soll wesentlich langsamer laufen als:

int array = new int[1000];

for(int y=0; y<100; y++)

for(int x=0; x<100; x++)

array[x+y*90] = 1;

Angeblich aus mehreren Gründen, die ich leider nicht verstehe...; hauptsächlich jedoch wegen Speicherzugriff...

Gruß

pecunia

[M.A.Knapp]

Der Effekt ist dieser: Der Computer ist gebaut für sequenziellen Speicherzugriff. Es wirden immer 32 oder 64 byte große Blöcke (Cache Lines) aus dem langsamen Hauptspeicher in den Cache geladen. Wenn du natürlich immer nur ein byte/int/... aus jeden Block brauchst, muß oft auf den Hauptspeicher zugegriffen werden. Daher geht die Performance beim ersten Beispiel merklich runter. Ob das bei Java auch (verglichen zu C++ etc) so ist, ist eine andere Frage. Vom Sourcecode weg bis zu den ausgeführten Action passiert viel mit dem Code. Das können nur Leute sagen, die die Interna des Java Compilers und der VM gut kennen. Vermutlich wird der Code so optimiert, daß er optimal läuft., d.h die Schleife gegebenenfalls umgedreht.

[pecunia]

Tja... die Interna des Java-Compilers und der VM sind für mich zwar keine Schwarze Magie , dennoch muß ich gewisse Defizite zugeben... Vielleicht habe ich etwas zu viel mit C++ gearbeitet... Und trotzdem ist es gegen jegliche Logik (meiner Meinung nach), aber jetzt bin ich bereit aufzugeben...:uli

Vielen Dank

pecunia

[kingofbrain]

Servus,

ich glaub, ich blick grad nicht, was Ihr meint. Warum soll das eine Beispiel langsamer sein als das Andere? Abgesehen davon, dass es nicht kompiliert, weil die int-Arrays nicht als solche deklariert sind, und nicht durchläuft, weil das Array zu klein ist, laufen die zwei Beispiele bei mir in jeweils zwei Millisekunden durch (sagt System.currentTimeMillis(), ist zwar nur bedingt genau, aber immerhin).

Peter

[BlackCoin]

eine idee wäre

erste schleife 100 * 100 berechnung von Y *90

zweite schleife 100 berechnungen von y *90 (wenn der compiler es erkennt)

eine möglichkeit der änderung für den compiler

int array = new int[1000];

int z =0;

for(int y=0; y<100; y++)

z = y*90;

for(int x=0; x<100; x++)

array[x+z] = 1;

mfg

[_Arvid_]

...ist zwar nur bedingt genau...

Richtig, vergleichende Zeitmessungen mit einem int-Array der Größe 1000 durchzuführen halte ich auch nur für begenzt sinnvoll. Ein Array der Größenordnung 10^10 (oder besser 10^1000000, aber dabei befürchte ich, dass ein PC langsam zu streiken beginnt) wäre da schon etwas geeigneter. Größer ist eben besser....

Was die Arrays angeht, muss ich zustimmen, die heißen nur so, sind aber keine.

Außerdem sollte das Programm während der Laufzeit tatsächlich mit einer ArrayIndexOutOfBoundsException abfliegen. Denn aller spätestens bei x=100 und y=100 (und natürlich schon wesentlich früher, das werde ich jetzt aber trotz der einfachen Gegebenheiten nicht rechnen) wird der Schleifendurchlauf mit besagter Exception unterbrochen, da die Wertzuweisung des Arrays im Index

array[x + y * 90] = 1;  //  entspricht bei x=99,y=99 [B]array[99 + 99 * 90][/B]

                        //  -> bissel zu hoher Index

nimmer klappen kann. Wahrscheinlich meintest du für den Code im Schleifenköper eher

array[x + y * 9] = 1

Das sollte dann auch klappen, denke ich.

[pecunia]

Wahrscheinlich meintest du für den Code im Schleifenköper eher

array[x + y * 9] = 1

Hallo!

Klar, Du hast Recht... Ich habe dies nur als Beispiel geschrieben ohne weiter nachzudenken... und wollte wissen, wieso das eine schneller ablaufen soll als das andere... Man hat versucht mir das zu erklären... leider erfolglos...:confused:

Gruß aus der Rattenfängerstadt

pecunia

[perdian]

die Interna des Java-Compilers und der VM sind für mich zwar keine Schwarze Magie, dennoch muß ich gewisse Defizite zugeben

Ich denke nicht, dass es hier wirklich den den Interna der Java VM liegt (der Compiler hat hier wenig bis gar nichts mit zu tun). Es liegt eher an der Tatsache, dass die Speicherverwaltung des Betriebssystems eher besser mit sequentiellen Zugriffen zurecht kommt. Ich habe gerade keinen C-Compiler vor Ort aber möchte fast wetten, dass das gleiche Beispiel in C oder C++ kompiliert auch kein anderes Laufzeitverhalten an den Tag legt.

[kingofbrain]

Ein Array der Größenordnung 10^10 (oder besser 10^1000000, aber dabei befürchte ich, dass ein PC langsam zu streiken beginnt) wäre da schon etwas geeigneter. Größer ist eben besser....

So, ich habe das Beispiel mal geringfügig aufgebohrt auf jeweils 10000 Schleifendurchläufe. Und selbst da ist das Ergebnis schon eindeutig. 2732ms für das erste, 545ms für das zweite Beispiel.

Man muss also die Werte nicht so irre hoch ansetzen.

Peter

[geloescht_Newlukai]

Ich hab' jetzt auch mal Testläufe mit jeweils 10.000 Schleifendurchläufen durchgeführt.

• II: 1.255.642.306ns
  
• I: 1.095.678.625ns
  
• II: 1.053.297.915ns
  
• I: 1.104.121.772ns
  
• I: 1.099.810.513ns
  
• II: 1.058.374.581ns
  
• II: 1.042.945.152ns
  
• I: 1.095.298.441ns
  
• I: 1.126.628.654ns
  
• II: 1.696.484.319ns
  
• II: 1.090.244.213ns
  
• I: 1.100.406.348ns
  

Große Unterschiede kann ich nicht erkennen. Laut Laufzeittheorie sind beide Algorithmen der Ordnung x: n*x und daher äquivalent.

[Jaraz]

Bei mir ist der Unterschied auch nur ca. 4%

[kingofbrain]

Servus,

auf welcher VM habt Ihr denn getestet? Meine Ergebnisse sind mit einer Apple VM 1.4.2_09 auf einem OS X (10.3.x) erzeugt worden.

Peter

[geloescht_Newlukai]

1.5.0_04 auf WinXP Pro

[Jaraz]

1.5.0_05-b05 xp pro

public static void main(String args[]) throws SQLException {

		// Vorlauf damit zwischendurch nicht eine Hotspot optimierung dazwischenfunkt

		for (int i = 0; i < 100; i++) {

			int[] array = new int[1000];

			for (int x = 0; x < 100; x++)

				for (int y = 0; y < 100; y++)

					array[x + y * 9] = 1;

		}

		for (int i = 0; i < 100; i++) {

			int[] array = new int[1000];

			for (int y = 0; y < 100; y++)

				for (int x = 0; x < 100; x++)

					array[x + y * 9] = 1;

		}

		// Ab hier Messung

		double summe1 = 0;

		double summe2 = 0;

		for (int h = 0; h < 10; h++) {


			long start = System.currentTimeMillis();

			for (int i = 0; i < 10000; i++) {

				int[] array = new int[1000];

				for (int x = 0; x < 100; x++)

					for (int y = 0; y < 100; y++)

						array[x + y * 9] = 1;

			}

			long end1 = System.currentTimeMillis();


			for (int i = 0; i < 10000; i++) {

				int[] array = new int[1000];

				for (int y = 0; y < 100; y++)

					for (int x = 0; x < 100; x++)

						array[x + y * 9] = 1;

			}

			long end2 = System.currentTimeMillis();


			summe1 += (end1 - start);

			summe2 += (end2 - end1);

			System.out.println("Block1: " + (end1 - start));

			System.out.println("Block2: " + (end2 - end1));

		}

		System.out.println("Summe1: " + summe1);

		System.out.println("Summe2: " + summe2);

		System.out.println("Summe2 braucht "+summe2/summe1*100+"% der Zeit von Summe1");

	}

[kingofbrain]

Servus Jaraz,

scheint schon ein wenig an der VM zu liegen. Mit Deiner main-Methode hier meine Ergebnisse:

> java -classpath "$CLASSPATH:/Users/pgoetz/Documents/temp" -ms32m -mx32m SpeedTest

Block1: 1974

Block2: 482

Block1: 1977

Block2: 476

Block1: 1975

Block2: 478

Block1: 1971

Block2: 475

Block1: 1965

Block2: 475

Block1: 1968

Block2: 475

Block1: 1970

Block2: 477

Block1: 1972

Block2: 523

Block1: 2050

Block2: 484

Block1: 1991

Block2: 477

Summe1: 19813.0

Summe2: 4822.0

Summe2 braucht 24.337556150002523% der Zeit von Summe1

Peter