tifyty

pure Java, what else ?

É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.

11 responses to “És a JIT optimalizál? De még mennyire!

  1. leningrad július 15, 2012 1:06 du.

    🙂 csak egy tipp, es lehet mar nem valid:

    for( i = 0; i egy utasitassal erteknoveles
    i++ -> temporalis int letrehozasaval jar

    Bar ugy remlik az ujabb gcc-k ezt C++ eseten mar kiszurjak, es kioptimalizaljak, ha az i “eredeti” erteket nem hasznalod fel.

    • leningrad július 15, 2012 1:24 du.

      No, akkor innen a blogmotor jovoltabol kimaradt a lenyeg:

      🙂 nem tudom milyen compilerrel forditottal, illetve pure C eseten is meg van-e okositva a fordito, de ez egy lehetseges optimalizalasi lehetoseg:
      for (i=0; i<LENGTH, ++i)

      ++i: pre-inkrement, egyetlen utasitassal erteknoveles
      i++: poszt-inkrement, i erteke egy temporalis objektumban orzodik meg, hogy visszaadhato legyen, az eredeti objektumon erteknoveles, majd a temporalis int megszuntetese.

      (es itt jon az h gcc egy ideje C++ kodban ezt mar kioptimalizalja automatice)

      • v július 15, 2012 2:32 du.

        Nem látok lényeges különbséget a pre és a post inkremens között, és az sem magyarázná meg, hogy miért gyorsabb lényegesen a rendezett verzió a rendezetlennél.

  2. leningrad július 15, 2012 1:09 du.

    (remelem csak a moderaciora valo varakozas miatt latom kozepen megkurtitottnak a kommentemet, a jelenlegi formajaban kb ertelmetlen 🙂 Fingers crossed.)

  3. Viktor Tamas július 16, 2012 10:20 du.

    A JIT főleg a metódusok belépési címeinek a feloldásában tud segíteni, de ez ebben a példában (rendezett vagy rendezetlen tömb) nem számít.

    A JVM bájtkódban a metódushívások név szerint történnek, ami első körben egyáltalán nem hatékony, de amikor a futtató rendszer találkozik egy metódushívással, lecseréli az eredeti JVM utasítást egy olyanra, ami már direkt memóriacímzést használ, vagy legalábbis valami natívat, amihez nem kell további szoftveres számolás.

    A dolgot az bonyolítja meg, hogy az objektumok típusa -és hogy ez alapján valójában melyik (override-olt) metódust kell meghívni- néha az adott pillanatban derül ki. De néha már előre lehet tudni hogy mindig ugyanaz a metódus lesz meghívva, mert a lehetséges futási idejű típusokon belül nincs override-olva.

    Nyilván még más dolgokat is csinál a JIT, sok varázslatot el tudok képzelni hogyan működik együtt a processzorok pipeline-jával. A lényeg, hogy a C kód optimalizálása befejeződik a fordításnál. A Java kód optimalizálása viszont futásidőben is tovább folyik, alkalmazkodva az adott platformhoz és az adott helyzethez, ami egy elég komoly előny a java (és egyéb virtuális gépen futó nyelvek) mellett.

  4. Kofa május 14, 2013 10:13 du.

    Most találtam róla anyagot, hogy mi történik: http://www.infoq.com/presentations/JVM-Mechanics 30. perc “uncommon trap”

  5. Geri július 9, 2013 6:38 du.

    tipikus félprogramozói okoskodás. még azt sem tudod, hogy gcc-ben -o3-mal kell bekapcsolni az optimizációt. szánalmas.

    • Geri július 9, 2013 6:48 du.

      ja, és nehogy azt mondja bárki, hogy csak trollkodom, és pofázok
      http://reverseblade.blogspot.hu/2009/02/c-versus-c-versus-java-performance.html

      itt a c++ 15x gyorsabb, mint a java hulladék, nahát, milyen érdekes
      üdvözöllek a valóságban

      • Peter Verhas július 13, 2013 8:17 du.

        A hivatkozott cikk nem releváns: három éves volt a ennek a blogbejegyzésnek az írásakor (most meg már négy), és korábbi Java verziót használtak a tesztek futtatására. (A bejegyzés szorosan kapcsolódik egy másik bejegyzéshez, ahol meg van adva pontosan a Java verzió.)

        Persze így most akkor hogyan hasonlítsuk össze a C++ és a Java sebességét? Az egyik cikk régi, a ez (is lassan már régi) meg nem erről szól, és ezért messze van attól, hogy teljességre törekedjen ebből a szempontból. Szóval akkor ebben a blogbejegyzésben: sehogy.

        A többire nem reflektálok, 18 év várbörtön után nem lehet könnyű 🙂 (Az email cím domain bejegyzése alapján gondolom.)

  6. ptl január 14, 2015 2:00 de.

    Igazából úgy lehetne optimalizálni a kódot, ha a feltételes elágazást lecserélnénk a feltételes operátorra. Java-ban nem jobb, de C-ben lehet. Konkrétan:
    if( a[i] > 0.5 ) s+=a[i]; //helyett
    s+= ( a[i] > 0.5 )?a[i]:0.0;

    Az optimalizációról, és a korrektség kedvéért: Az O3 kapcsoló nem garantálja a generált program helyes működését – az O2 még igen. Az architektúrát és tunningolási lehetőségeket pedig be kell állítani, pl. -march=native x86-on és x86_64-en automatikusan felismeri.

    Vannak utasításkészlet kiegészítések (SIMD utasítások), amiket lehet használni assembly-ben. Mivel a fordítók a vektor műveletek felismerésében általában elég rosszak, ezért érdemes lehet ISPC nyelven megírni a program lényeges részét.

    Példa sum.ispc:
    export uniform double sum_double(uniform double t[], uniform int length) {
    double sum = 0.0;
    foreach(i = 0 … length) {
    sum += t[i]>0.5?t[i]:0.0;
    }
    return reduce_add(sum);
    }

    A C kódban deklarálni kell a függvényt:
    double sum_double(double *t, int length);

    Majd lefordítani a sum.ispc-t és linkelni az eredeti fájllal.
    ispc -o sum.o sum.ispc
    gcc -O2 -march=native SortedNotSorted.c sum.o

    Amúgy egyetlen nyelv sem gyorsabb a másiknál, de lehet különbség a teljesítmény kézbentartottságában. A C++ tipikusan jobban kézben tartja a memória kezelést, ennek lehetnek bizonyos helyzetben előnyei. Egy Java-s hosszú ideig futó program esetén speciálisan az alkalmazás ciklusához beállított garbage collector-ral lehet jobb teljesítményű, csak ilyen helyzetet előállítani sem könnyű.

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s

%d blogger ezt kedveli: