tifyty

pure Java, what else ?

Kategória archívok: C

És a JIT optimalizál? De még mennyire!

Egy korábbi postban volt szó róla, hogy a javac nem optimalizál. Most nézzünk meg, hogy a JIT optimalizál-e. A JIT-ről elvileg tudjuk, hogy optimalizál, sőt nem csak a hagyományos értelemben teszi, de futás közben a futási eredmények alapján is néha újrafordítja a kódot. De vajon mennyire látszik ez meg? Van egy nagyon egyszerű példa, ami megmutatja, hogy futási időben is mennyire meg tud változni egy adott kódrészlethez tartozó futási idő. Ebben a cikkben ezt fogom megmutatni. Mielőtt belemennénk, a következőt kérem tőled. Olvasd végig a posztot, és ne hülyézz le az elején, közepén, illetve/és ne maradj tudatlan mert nem olvasod végig. Ugyanis csalok, de csak egy kicsit. A nagy “durranás” a vége felé jön. Persze ha tudod, akkor nem olyan nagy durranás.

Spoiler alert. A következő text blokkban leírom, hogy mi a csalás, ha meg akarsz lepődni, akkor ne nyisd ki.

A két sebesség közötti különbség, ami a példákban látható nem a JIT hatása,
vagy nem csak a JIT hatása. A processzor maga is optimalizál, és ezt a
C kód bizonyítja, hiszen ott szó nincsen JIT-ről. 

Ha kinyitottad, akkor is van a cikk végén egy extra meglepetésem a számodra.

A következő kis metódust futtassuk:

	public static double summUp(double[] a) {
		double s = 0.0;
		for (double d : a) {
			if (d > 0.5)
				s += d;
		}
		return s;
	}

Ez annyit tesz, hogy a double[] a azon elemeit, amelyek nagyobbak, mint 0.5 összeadja. Elég egyszerű, mint a fék fapofa. A meghíváshoz írjunk egy kis programot, legyen a metódus neve main és public static a szokásos módon.

	public static void main(String[] args) {
		double[] a = new double[100_000_000];
		Random r = new Random();
		for (int i = 0; i < a.length; i++) {
			a[i] = r.nextDouble();
		}
		long tStart = System.currentTimeMillis();
		double s = summUp(a);
		long tEnd = System.currentTimeMillis();
		System.out.println(s);
		System.out.println(tEnd - tStart);
		Arrays.sort(a);
		tStart = System.currentTimeMillis();
		s = summUp(a);
		tEnd = System.currentTimeMillis();
		System.out.println(s);
		System.out.println(tEnd - tStart);
	}

Egy aprócska, alig százmillió elemet tartalmazó tömböt hozunk létre, feltöltjük 0.0 és 1.0 közötti értékekkel, és erre hívjuk meg a metódusunkat. Kétszer. Azért persze, hogy ne legyen olyan unalmas az élet közben sorba is rendezzük a tömböt, és kiíratjuk, hogy mennyi ideig futott az összegző program. Az eredmény pedig meglepő:

verhasp:java verhasp$ javac SortedNotSorted.java
verhasp:java verhasp$ java SortedNotSorted
3.750628033806522E7
537
3.750628033807129E7
173
verhasp:java verhasp$

Az összeget csak ellenőrzésképpen írjuk ki, hogy

  1. lássuk, hogy az összeadás sorrendjétől független eredményt kapunk, nincs valami vad hiba a programban
  2. lássuk, hogy double aritmetikával soha nem kapjuk ugyanazt az eredményt, de azért elég jó

Ami igazán érdekel bennünket, az a futási idő ms-ban. A rendezetlen tömb esetében az összegzés 537ms, majdnem fél másodperc (azért csak 50millió számot adtunk össze), míg rendezett esetben ennek kb. a fele. Mi történt itt? A JIT rájött, hogy rendezett a tömb, és csak a második felére futtatja a ciklust? Azért ez egy kicsit húzós lenne, ennyire azért nem jó az optimalizáció. De valami igazság mégiscsak van a dologban.

A futás során az if utasítás kiértékelése előre megtörténik, és amikor a tömb rendezett, akkor sokkal jobb eséllyel találja el a környezet, hogy mi lesz az eredmény, és ennek megfelelően a megfelelő ág futását elő tudja készíteni. Például olyan kódokat tölt be a processzor cache-be, amelyek annak az ágnak a futtatásához kellenek.

És itt vége is lehetne a cikknek, levontuk a konklúziót: a JIT bizony optimalizál, mégpedig igen jól, és okosan. De tényleg csak a JIT-től lett ilyen?

A futás során nem csak a JIT optimalizál, hanem a processzor is. ( ??? ) Hát bizony de. Ha fiatal vagy, és még nem tanultál ilyent, akkor most egy kicsit olvashatsz ilyesmiről, ha meg olyan öreg vagy, mint én, aki még z80-on kezdte az assembly-t és mégis meglepődsz, akkor nem haladtál a korral, csak öregedtél.

A processzorok szinte mindent cache-ből szeretnek csinálni. A Z80-hoz képest (4MHz) olyan sebességnövekedést értek el, hogy ma már a memória háttértárnak tekinthető. Olyan, mint régen a diszk. Ha a memóriához kell nyúlnia a processzornak, akkor az bizony lassú lesz. Ezért is kerüld a synchronized metódusokat és a volatile változókat ameddig csak lehet (miért is?). Ha pedig mégis a memóriához kell nyúlni, akkor a processzor megpróbálja beolvasni az adatokat előre. Megpróbálja kitalálni, hogy az elágazási feltételnek mi lesz az eredménye, és a találgatásnak megfelelően kezdi el betölteni, és néha végre is hajtani a kódot (legfeljebb eldobja az eredményt, amit közben kiszámolt, ha tévedett), és mire oda jut, hogy megvan az igazi eredmény, addigra a betöltés, végrehajtás már előre jár. Persze mindig csak annyit tud előre menni, amennyi a regiszterekbe, a cache-be befér, és amennyi számolás nem függ a még el nem végzett számolások eredményétől.

Hogyan tudnánk eldönteni, hogy a JIT-e az igazi nagyágyú, vagy a processzor? Írjuk meg ugyanezt a kódot assembly-ben, és nézzük meg annak a futását!

Na én se hülyülök már meg, hogy ilyeneket találok ki magamnak, de végső soron ez lenne az igazi. Most azonban elégedjünk meg azzal, hogy írjuk meg a kódot C-ben. Ma már a C legalább olyan, mint régen az assembly volt, csak a poros fiókból előhúzott öreg szakik ismerik, akik felváltva zsonglőrködnek FORTRAN, C, COBOL és RPG programokkal. De legyen, és íme:

#include <stdio.h>
#include <stdlib.h>

#define LENGTH 100000000

static double summUp(double *a){
  double s = 0.0;
  int i;
  for( i = 0; i < LENGTH ; i++ ){
      if( a[i] > 0.5 )
        s+=a[i];   
    }
  return s; 
}

long currentTimeMillis(){
  struct timeval tv;
  gettimeofday(&tv,NULL);
  return (tv.tv_sec*1000) + (tv.tv_usec/1000);
  }
  
int compareDouble(const void *x, const void *y) {
  return (*(double*)x > *(double*)y) ? 1 : -1;
}

int main(int argc, char *argv[]){
  double *a = (double *)malloc(LENGTH*sizeof(double));
  int i;
  for( i = 0 ; i < LENGTH ; i++ ){
    a[i] = rand()/((double)RAND_MAX + 1); 
    }
  long lStart = currentTimeMillis();
  double s = summUp(a);
  long lEnd =currentTimeMillis();
  printf("%lf\n%ld\n",s,lEnd-lStart);
  qsort(a,LENGTH,sizeof(double),compareDouble);
  lStart = currentTimeMillis();
  s = summUp(a);
  lEnd =currentTimeMillis();
  printf("%lf\n%ld\n",s,lEnd-lStart);
}

(Dobod el gyorsan! Nem szégyelled magad! C-ben programozni! Ki hallott ilyent!)

Ha már sikerült kiizzadni, futtassuk is le:

verhasp:java verhasp$ gcc SortedNotSorted.c
verhasp:java verhasp$ ./a.out 
37502647.627436
875
37502647.627257
428

És íme, láthatjuk, hogy a gyorsulás a C-ben megírt program esetében is tetten érhető. Ez tehát nem a JIT, hanem a processzor. Azaz… Várjunk csak? Hogy voltak ezek a millisecundumok? Gyorsabb a Java, mint a C?



Ez a cikk a Why is processing a sorted array faster than an unsorted array? cikk alapján készült, és nem sokat tesz ahhoz hozzá. (Eufemizmus, valójában semmit sem tesz hozzá.) Annyira meglepett amikor olvastam, hogy magam is ki akartam próbálni, és ha már megtettem, és kiizzadtam, a Java mellett a C verziót is, akkor már csak leírtam itt is, hogy aki nehezebben emészti az angol szövegeket, az is. Végül is megérdemlitek.

UPDATE

leningrad commentjei alapján elvégeztem a következő mérést:

verhasp:java verhasp$ sed s/i\+\+/\+\+i/ < SortedNotSorted.c > SortedNotSorted1.c
verhasp:java verhasp$ gcc -o SortedNotSorted1 SortedNotSorted1.c 
verhasp:java verhasp$ ./SortedNotSorted1 
37502647.627436
929
37502647.627257
469
verhasp:java verhasp$ gcc SortedNotSorted.c
verhasp:java verhasp$ ./a.out 
37502647.627436
889
37502647.627257
591

>>>Magyar László mint “poros fiókból előhúzott öreg szaki” magyarázatot kérek, hogy a C miért volt lassabb, mint a java??? csak mert nem volt kioptimalizálva a fordítás???<<<

verhasp:java verhasp$ gcc -O3 SortedNotSorted.c
verhasp:java verhasp$ ./a.out 
37502647.627436
601
37502647.627257
293

Sokat segít a -O3, de nem eleget. A Java/JIT páros még így is gyorsabb.