Megoldás – Minifeladatok III.

A III-as számú minifeladat az érték és referencia típusok rendezési ideje közötti különbséget vizsgálja, 20 millió adat, és a quick sort algoritmus segítségével. Egy quick sort algoritmus húszmillió elem rendezése közben átlagos esetben körülbelül kétszázötvenmillió elemmozgatást végez. Ezek alapján, 32 bites rendszernél referencia típus esetében 1 gigabyte (2 giga 64 biten) adatot kell mozgatni, még a Minifeladat érték típusa esetében 6 gigabyte adatot.

Azt várnánk így, hogy class esetében gyorsabban végez a program, mint struct esetén. Az eredmények azonban első ránézésre meglepőek:

class: 40 sec.
struct: 13 sec.

Az érték típus a jelentősebb memóriamozgatás ellenére sokkal gyorsabb. Ez az eredmény még akkor is meglepő lenne, ha ugyanannyi adatot kellene mozgatni.

Miért van ez így?

Ez a feladat egy újabb jó példa volt arra, hogy egy háttérműködés ismeretére épülő mikrooptimalizációs lépés nagyon könnyen visszafelé sülhet el. Látszólag hatodoltuk a memóriamozgatást, mégis megháromszoroztuk a futásidőt (más gépen mások lehetnek az arányok). A jelenség megértéséhez két dolgot érdemes figyelembe venni.

Referenciák és indirekció

Egyrészt, a referencia típusok esetében az adatokat indirekt érjük el, ami egy plusz lépést jelent minden összehasonlításnál a rendezés alatt. A rendezendő tömbben referencia típusokat használva csak referenciák vannak, amelyek a memória egy területére hivatkoznak, ahol a rendezendő elem van. Emiatt amikor el kell érni az egyik elemet (például összehasonlítás miatt a rendezéshez), akkor a tömb n-ik eleméből venni kell a referenciát, majd második lépésként a referencia által mutatott memóriaterületet.

Értéktípus esetében az érték reprezentációja a tömbben van, nem kell plusz memóriacímzés az adatok eléréséhez. Az indirekt címzés azonban valószínűleg a kisebb veszteség.

A cache és az egybefüggő adatok

Ami a fő különbség, hogy érték típusokkal dolgozva a quick sort algoritmus pont a memória cache keze alá dolgozik, referencia típusok esetében viszont nem. Amit a cache-ről érdemes tudni, hogy az az adatokat kis csoportokban kezeli, amit cache line-nak neveznek. A cache line mérete különböző lehet processzoroknál, de 64 byte mérethez hasonló blokkokra kell gondolni. A cache az egész cache line-t egyszerre tudja mozgatni, és egy 64 byte-os cache line esetében az együtt mozgó blokk mindig egy 64-gyel osztható memóriacímen kezdődik. Így például amikor szükség van a 0x00001004-ös címen levő adatra, akkor a cache a 0x00001000-0x00001040 címen levő összes adatot egyszerre beolvassa. Ez egyben azt is jelenti, hogy ha a következő program utasítás a 0x00001004 után most a 0x00001008 címről olvas adatot, akkor az már a cache-ben az előző művelet miatt rendelkezésre áll.

Az általunk használt adatszerkezet 24 byte-ot foglal (referencia típus esetén erre még rájön 8 byte adminisztrációs adat 32 bites rendszeren). Érték típus esetében az adatok egymás mellett helyezkednek el a memóriában. Ez azt jelenti, hogy amikor a quick sort halad végig az elemeken (a particionálás szakaszban), akkor az első elem olvasásával azonnal beolvasódik a második, és még a harmadiknak egy része a cache-be, mivel egy cache line-on vannak. A második elemmel való művelet emiatt gyorsabb, a harmadiknál ugyan várni kell, de cserében beolvasódik teljesen a negyedik és ötödik elem, amire majd megint nem kell várni.

A rendezés során értékt típusoknál bár nagyobb adatot kell mozgatni, azok az adatok, amiken a rendező algoritmus a következő körben (a rekurzív híváskor) dolgozni fog, egymás mellé kerülnek, így a cache mindig beolvassa előre a szükséges adatokat.

Referencia típus esetében a értékeket reprezentáló adatok nem mozdulnak, csak a referenciák rendeződnek. Ez azt jelenti, hogy az első particionálás után a logikailag egymás mellé kerülő adatok már szanaszét vannak egymáshoz képest a memóriában. Ekkor, amikor az algoritmus veszi a tömbben az első elemet, a cache a 64 byte olvasásával nem a második elemet, és a harmadik felét fogja beolvasni, hanem valamilyen haszontalan adatot. A 64 byte-ni cache lineból csak 24 lesz hasznos, tehát kb csak a 35 százaléka lesz kihasználva a cache-nek. Emiatt sokkal többet kell várni az adatokra, és ez látszik meg a futásidőn.

És ez most tanulságos?

A hatást ugyan egy nagyon kiélezett helyzetben néztük meg, de ne gondoljuk, hogy nem általános dologról van szó. Ha például egy metódus lokális változóira gondolunk, és ezek érték típusúak, mivel a lokális változók egy helyen vannak a memóriában, ha elérjük az egyik változót, akkor az a cache line-ban jó eséllyel magával rántja az összes többit (64 byte az 16 int, vagy 8 double, tehát egész sok változó). Sőt, mivel a paraméterátadás is a vermen történik, emiatt már a metódushívás előkészítése a cache látókörébe helyezi a verem adott pontját.

Ha referencia típusokat használunk, akkor a cache csak a referenciákat “rántja be”. Amikor a konkrét példányt érjük el, akkor külön dolgoznia kell a cache-nek az adatokért.

De nem csak metódusok esetén van előnye az érték típusoknak a cache szempontjából. Ha egy osztálypéldányt veszünk, és annak érték típusú mezői vannak, akkor bármilyen módon hozzányúlunk a példányhoz, a cache 64 byte-nyit, tehát 16 darab int típusú mezőnyit beolvas, így azok elérése már nagyon gyors lesz később. Referencia típusú mezők esetében megint csak a referencia lesz meg gyorsan, az általa mutatott példányért még el kell menni a lassú memóriához.

Konklúzió

Az érték típusok egyik hátrányának tűnhet, hogy nagyobb adatmennyiség mozog általa. Ezt azonban az érték típusok más jellemzői, illetve a processzorok működése könnyen kiolthatják. Mint már sokszor, most is kiderült, hogy nehéz igazán jól kiismerni, hogy mi történik a programunk futtatása közben a színfalak mögött. Így ez egy újabb jó lecke arra, hogy programtervezés közben ne a futtatórendszer tulajdonságaira koncentráljunk.

  1. #1 by mjanoska on 2012. March 23. - 10:45

    Két dolog:

    – Disruptor (LMAX) – van .Net portja is. Ez a megfontolás erősen azt juttatja eszembe.

    – másrészt engem mindig az zavar, hogy vajon mennyire transzparensen lehet kiszámítani, hogy a milyen verziójú CLR majd milyen alacsony szintű kódra fordítja a programot.
    Elvben ezzel nem kéne foglalkoznia egy VM (CLR, JVM) szinten programozó embernek… ha pedig mégis foglalkozik vele, akkor tulajdonképpen olyan információkra épít, amelyek lehet, hogy épp igazak, később meg változhatnak.
    Pl tipikus a valuetype-ok tömbjének memóriabeli reprezentációja, éppen most épp úgy van, hogy kézenfekvő módon képződik le, de ez akár lehetne máshogy is…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: