Sprinkfield megoldó optimalizációja

Posted by | · · · · | Webstar Works | Nincs hozzászólás a(z) Sprinkfield megoldó optimalizációja bejegyzéshez

Ahogy korábbi cikkemben írtam, a Sprinkfield megoldójának több programnyelven is nekiálltunk, azt remélve, hogy elég gyors lesz a kód.

Programnyelv választása

Az egyik legfontosabb kérdés, ami nagyon meghatározza, hogy a későbbiek során miket lehet, érdemes, nem érdemes és nem lehet megcsinálnunk optimizáció terén.
Mivel az átállás egyik nyelvről a másikra valójában teljes kódújraírást jelent az esetek többségében, ezért ezt a lépést érdemes jól kivitelezni. Hát, mi kalandoztunk egyet…

JavaScript

A legelső nekifutás valójában csak egy proof-of-concept volt, JavaScript-ben készült el. Ekkor még a játék szabályai sem voltak végleges formában, így ez a megoldás ahhoz elég volt, hogy 1-1 egyszerűbb pálya megoldhatóságát gyorsan megnézzük.
Többet nem is érdemes erről írni, hamar kinőttük a JavaScriptet.

Java

A kézenfekvő lépés, hiszen ebben a nyelvben igen otthonosan mozgok. Bár tudjuk (sejtjük), hogy teljesítményben nem a legjobb, azért egy értelmezett scriptnyelvhez képest bezsírozott villám.

Pascal, C

Ahogy sejtettük (vagy csak az előítéletünk miatt?), a Java kód sem lett egyből annyira gyors, amire azt mondtuk volna, hogy ezen már nincs értelme javítani.
Így jött a következő pont: hagyjuk el a JVM-et, menjünk át natív szintre. Egy este alatt leporoltam Object Pascal (Delphi) tudásomat és a meglévő Java kódot átírtam. A Pascal kód tökéletesen futott, de kb ugyanazt tudta hozni, mint a Java. Egyedül memóriában vert rá, de ott nagyon (pár 10 MB szemben a Java 1 GBjával).
De ha már natív kód, akkor miért nem C? Nem is kellett több, C-ben is megírtuk a megoldót. Örültünk, mert egyrészt a 3-ik átírásnál már egy csomó bug kitisztult a kódból, másrészt pedig nagyjából 2-szer gyorsabb lett a megoldó!

Kód újrahasznosítás

Sajnos nem minden fekete vagy fehér. Amikor kész lett a C nyelvű megoldó, a megoldó algoritmusok még messze voltak az optimálistól (logikailag). (Optimális alatt a legutolsó verziót értem.)
Ezen idő tájt jött az ötlet, hogy próbáljuk meg az A* algoritmus memória limitált verzióját (Interval Heap-pel). Mivel a rendelkezésre álló időkeret véges volt, nem volt idő implementálni ezt az adatszerkezetet C-ben, és sajnos nem is találtunk használható kódrészletet.
Java nyelven viszont megtaláltuk az interval heap egy implementációját, így időhatékonysági okokból visszatértünk a Java-hoz.
Az újrahasznosítás egy nagyon jó dolog, és sajnos C-ben ez sokkal nehézkesebb, mint Java-ban. Főleg úgy, hogy nincs bejáratott eszközkészletünk.

Java speedup

Szóval a nyelvet sikerült kiválasztani. A korábbi munkáim során nem kellett ennyire teljesítmény-kritikus Java kódot írnom, így néhány eddigi konvenciót fel kellett rúgnom és helyette újakat behozni.

Az újabb jobb

Legalábbis a 7-es JDK-val fordított kód gyorsabb, mint a 6-os JDK-val fordított kód (Oracle). A különbség kb. 10%, ami a mi esetünkben jelentős nyereség, főleg úgy, hogy a kódban igazából egy betűt sem kell megváltoztatni (de ajánlott).

final

Encapsulation, accessors, mutators. A megoldó fő osztálya a Puzzle, aminek a feladata egy játékállapot teljes reprezentációja (méret, mezők pillanatnyi állapota: föld, búza, víz, stb., aktuális pontszám, stb.), és alapműveletek szolgáltatása.
A nagykönyv szerint elrejtettem minden információt a külvilágtól, amire viszont másnak is szüksége volt, arra írtam gettereket accessorokat. A probléma az, hogy ezek lassúak, mivel minden használatuk egy függvényhívás, amihez stack-et épít a nyelv.
Hogy megkerüljem a függvényhívást, a privát adattagokat láthatóbbá kellett tennem. Viszont az adatrejtés elvét sem akartam semmissé tenni, így a csak olvasható adattagokat végül public final deklarációval láttam el. Ennek több hasznos mellékhatása is volt:

  • NetBeans-t használva a hivatkozási helyeken szépen kiemelve látszanak ezek a változók
  • megszabadultam az olvashatóságot időnként nehezítő get szótól és az üres zárójelektől
  • néhány sorral rövidebb lett a Puzzle osztály

Sajnos ez a trükk egyedül a csak olvasható változókra működik. Az írható változókat meghagytam a klasszikus módon rejtve.

public

Az előbbiekhez kapcsolódva sajnos néhány olyan kritikus változója is van az osztálynak, ami változik (milyen furcsa viselkedés…), így a final kulcsszó ott nem működik. 2 esetben kellett nagyot nyelnem, és az adatrejtést beáldozni a teljesítmény oltárán.
Azaz csakis performancia szempontból két privát változót publikussá tettem. Ezt a lépést tényleg semmi nem indokolja logikailag, így fájó pontja a kódnak. Ilyet valójában nem lenne szabad csinálni. Persze a kivétel erősíti a szabályt.

Memória

A Java egy érzékeny területe, mivel a programozó lényegében semmilyen információt nem kap arról, hogy mennyi memóriát használnak az egyes változói. Az első implementáció során erre nem is figyeltem, csak azt vettem észre, hogy 2GB memória alatt egyszerűen “java.lang.OutOfMemoryError: Java heap space” történt.

Második nekifutásra viszont odafigyeltem, hogy szem előtt tartsam az alábbiakat:

  • minimalizáljam az objektumok közötti egymásra hivatkozásokat (hogy a GC jobb eséllyel szabadítson fel memóriát),
  • csak akkor hozzak létre új objektumot, amikor az valóban indokolt (egyébként egy létező példányt változtassak),
  • az előre kiszámolható dolgokat számoljam ki előre, és egy példányban tároljam,
  • a hash táblába (Zobrist kulcsok, vizsgált állapot figyelés) pedig csak a pálya egy ellenőrző-összegét tároltam, így a pálya objektumok felszabadíthatóvá váltak (azaz valójában így 1 példány elég is)

A fenti dolgok nem túl bonyolultak, ám ha az ember nem figyel oda, könnyen elszaporodnak a new utasítások.

Egy fontos (mellék)hatása az objektumok újrafelhasználásának, hogy nagyon figyelni kell azokra az esetekre, amikor egy konkrét állapotát akarjuk eltárolni egy objektumnak, akkor viszont kötelezően új példányt kell készíteni. Ez egy olyan hiba, amit nagyon nehéz észrevenni…

Összefoglalás

Az optimalizáció mindig egy összetett művelet, önmagában egy tudomány. Amire figyelni kell, hogy idő előtt nem szabad az optimalizációval foglalkozni, ám érdemes szem előtt tartani menet közben.
Előfordulhatnak esetek, amikor a teljesítmény növelése olyan lépéseket igényelne, amik a kód olvashatóságát – vagy úgy egyáltalán a minőségét – rontják. Ilyenkor nagyon körültekintően kell átgondolni, hogy megéri-e a lehetséges nyereség a minőségrontást (méréssel alátámasztani). A mi esetünkben ilyen volt az adatrejtés elvének megsértése, amit azért vállaltam be, mert a kód egy személyes, pici, és funkcionalitásában kvázi végleges volt az optimalizáció előtt. Nagy projektek esetén egy-egy ilyen lépés általában nem éri meg a nyereséget.

Sebesség vs. sebesség

A fejlesztés közben láttuk, hogy C nyelven kb. 2-szer gyorsabb kódot tudnánk készíteni, mint Java nyelven. Viszont azt is láttuk, hogy ha C-ben fejlesztünk, jelentősen lassabban készül el a kód (ami majd gyorsabban futna). Tehát a fejlesztési idő rovására nyertünk volna a futásidőn. De ez a lépés – számunkra – az idő előtti optimalizáció volt, ezért nem vállaltuk. Egészen pontosan 4-szeres sebességkülönbséget mértünk a C kód és az akkori Java kód között, de egy fél órás piszkálgatással a Java kódot is jelentősen fel tudtuk gyorsítani.
Ez indokolta, hogy Java nyelven készült el a megoldó, ami elég gyors lett, így feleslegessé vált a további optimalizáció. Tehát kifizetődött, hogy elkerültük a túl korai optimalizációt.


No Comments

Leave a comment