vTable / polimorfizam

Primetio sam da se dosta ljudi ne snalazi bas sa konceptom polimorfizma i da je neko cak i trazio objasnjenje kako radi vTable, pa ajd da pokusam da razjasnim.

1. Sta je vTable?

vTable je u najosnovnijem obliku niz "funkcijskih" pointera. Sa tom razlikom sto svaki od tih pointera ne pokazuje na neki podatak vec na kod odredjenog metoda. Prva greska koju ljudi prave je da vTable direktno asociraju sa OOP-om. Iako OOP ne moze funkcionisati bez vTable-a, nista vas ne sprecava da u C-u napravite niz function pointera, popunite tu listu i onda radite "indirektne" pozive preko tog niza (http://www.codeproject.com/cpp/PolyC.asp), mada se to naravno ne radi u praksi

2. Sta omogucava vTable?

Omogucava dve veoma vazne OOP tehnologije, polimorfizam i interfejse.

3. Kako to ustvari radi?

Ok, uzmimo ovo parce koda (C#):



Prilicno jednostavna klasa, jedno polje, jedan staticki metod, dva virtuelna overloaded metoda i jedan obicni metod. U Class1 instanciramo tu klasu i pozivamo sve sto treba.

C# za razliku od C++-e ne pravi native code, pa se necu zadrzavati mnogo na MSIL-u vec cemo tretirati kao da je sve to vec stiglo do native koda.

Kompajler, kad bilduje klasu, ima nekoliko aspekata.
Sva polja idu direktno u memorijski potpis klase. Staticke metode i obicne metode se linkuju staticki na ulaz u odgovarajuci kod metoda (jedina razlika izmedju statickih i obicnih metoda je da se statickom ne prosledjuje skrivena referenca na objekat ciji metod se poziva), vTable nema nikakav uticaj ovde.

E sad, za svaki virtual metod (i virtuelne property accessore), alocira se slot u vTable i u tu poziciju se "upuca" pointer na kod metoda. vTable se alocira van objekta na pocetku aplikcije i svaka klasa koja ima bar jedan virtuelni metod ima svoj vTable koji koriste svi objekti te klase. Na kraju, memorijski potpis ove klase izgleda ovako (bar u skolskom primeru, vise o tome posle):



Sta se desava pri pozivanju? Ovako izgleda MSIL kod u Class1




Prva stvar koja bode oci je d.Obicni(). Ako to nije virtuelni metod, zasto se koristi callvirt? Razlog je u tome sto sam C# kompajler uopste i ni na koji nacin ne radi sa vTable , c# kompajler samo daje odgovarajuce instrukcije u MSILu (ako je staticki metod onda call, ako je objektni onda callvirt) da bi JIT kompajler mogao da odradi konverziju u native kod i naposletku samo linkovanje koje nam je poznato iz C++-a, dakle JIT je taj koji bilduje i kreira vTable. Ovako izgleda finalni native kod:



Pa ajd da krenemo redom. Prva linija je pozivanje konstruktora i smestanje reference u lokaciju 0, na asmeblerskom delu se vide dva poziva, prvi je nevazan za pricu (alokacija), drugi je poziv konstruktora i smestanje reference u ESI registar (koji u stvari predstavlja MSILovu lokaciju 0).

Deda.Staticki();
MSIL koristi call konstrukciju, JIT koristi indirektan poziv (za one slabije sa asemblerom, call je direktan poziv na fisknu adresu unutar istog code segmenta, call dword ptr je indirektni poziv, tj, idi na adresu u operandu, uzmi adresu metoda i pozovi tu adresu)
Sada iskace pitanje, ako smo rekli da je u pitanju staticki poziv i ako znamo da JIT definitivno zna adresu na koju je smestio Staticki(), zasto se u asembleru koristi indirektni poziv (call dword ptr) a ne staticki poziv?
To pitanje je na mestu i odgovor malo kasnije, ali posledica trenutne implementacije JIT-a je da nikad (ali nikad) ne koristi staticke pozive za MSIL kod. Iako delimicno smanjuje performanse programa ovo nema toliko znacaja u funkcionisanju koliko ima u kasnijoj raspravi o early/late binding, al otom potom.

d.polje1 = 123;
MSIL ucitava lokaciju 0 (referenca na d), ucitava kosntantu 123 i koristi stfld da upuca vrednost u polje1. JIT to prevodi u indirektni mov (mov dword ptr). ESI nosi adresu reference, na 4 bajta udaljenosti od pocetka nalazi se memorijska lokacija polje1 i u nju upucava konstantu 7Bh (123). Ako pogeldate dijagram sa pocetka, na adresu ESI se nalazi objekat, na lokaciji ESI+0 je pointer na vTable, te je na lokaciji ESI+4 locirano polje1.

d.Metod();
ok, poziv virtuelnog metoda. MSIL ucitava lokaciju 0 (referencu kao skriveni parametar za metod) i poziva Metod() sa callvirt. JIT na osnovu metadata zakljucuje da je poziv virtuelnog metoda i koristi vTable.
Ovako, na adresi ESI+0 je pointer na vTable, pa je proces sledeci:
- mov ecx, esi - kopira referencu na objekat u exc (skriveni parametar)
- mov eax, eax,dword ptr [ecx] - kopira u eax cetiri bajta sa lokacije ecx+0 (tj esi+0), tj pointer na pocetak vTable. U ovom trenutku eax (navodno) pokazuje na vTable.
- call dword ptr [eax+38h] - ovo je pravi indirektni vTable-driven polimorficki poziv. . JIT zna da je na lokaciji 38h unutar vTable-a adresa metoda Metod(), procesor ucitava tu adresu i poziva metod.

d.Metod(1234);
Slicno kao gore, samo sto EDX nosi neskriveni parametar 1234. Takodje, vidi se da je lokacija u vTable sada +3Ch (sledeca lokacija u vTable)

d.Obicni();
Slicno kao Staticki(), poziva se indirektni metod, samo sto se pre poziva u ecx ubacije referenca (skriveni parametar), sto je jedina razlika izmedju pozivanja statickog i objektnog metoda.



4. Nasledjivanje...

ako dodamo sledecu klasu


Preskocicemo MSIL i dati samo asm:


Iz ovog se vidi da su dva poziva identicna (call dword ptr [eax+38h]), ali opet d.Metod() poziva Deda.Metod, a u.Metod poziva Unuk.Metod() iako su i u i d istog tipa (Deda).

"Tajna" je u vTable-u. U ovom primeru edi nosi referencu na d, a ebx nosi referencu na u. Jedina razlika je ta sto se na adresama edi+0 nalazi vTable za Deda klasu (u ovom primeru 9D5140h), a na ebx+0 adresa za vTable klase Unuk (9D51C8h), u te dve tabele na lokaciji 38h nalaze se dva razlicita funkcijska pointera, i to je nacin na koji vTable omogucava polimorfizam, bez obzira na to koji je tip reference, odluku o tome koji metod se poziva donosi odgovarajuca lokacija u vTable.


5. Kako to .NET radi za razliku od C++-a...

Ono sto mozda zapadne za oko je pitanje: ako Klasa Deda ima samo dva virtuelna metoda, zasto su funkcijski pointeri na lokacijama 34h i 38h a ne 0h i 4h?

Odgovor lezi u nacinu na koji JIT prevodi MSIL kod. Klasicni (C++) kompajler i linker, prevo prevede kod u prvom prolazu usput pamteci staticke lokacije metoda i lokacije sa kojih se poziva, onda linker na osnovu te tabele izbilda sve vTable-ove i upuca "staticke" lokacije u pozive.
JIT sa druge strane (verovatno zbog brzine prevodjenja) ima samo jedan prolaz kroz kompajler/linker. U takvom rezimu JIT kad prevodi poziv metoda ne zna gde se kod tog metoda nalazi pa da bi izbegao dvoprolaznost, ima mali korak na pocetku: za svaku klasu (iz metadata) JIT rezervise prostor za vTable koji sadrzi SVE metode, i staticke i obicne i virtuelne. Tako da iako u trenutku prevodjenja mozda ne zna gde ce se nalaziti npr. Deda.Staticki() ali ZNA da ce pointer na taj metod biti na lokaciji u vTable ciju adresu zna. I tako kako prolazi kroz metod po metod, generise native code i indirektne pozive drugih metoda i onda na kraju upuca entry-point u odgovarajucu lokaciju u vTable, bez potrebe da u drugom prolazu tu adresu stavi u sve pozive tog metoda, tako da vTabele za nase klase ustvari izgledaju ovako:



C++ programeri se u startu mrste na ovo zbog potpuno nepotrebnog gubitka memorije i u pravu su, nije bas idealno resenje sa stanovista optimizacije upotrebe memorije, i sa stanovista brzine pozivanja metoda, ali poprilicno ubrzava proces JIT kompajliranja.

6. Interfejsi

Interface je funkcionalno nista drugo do "ogoljena" referenca koja sadrzi samo pointer na vTable koji se nalazi unutar vTable klase koja ga implementira. Recimo da postoji Interface IDeda koji ima jedan metod (void Obicni()) i da klasa Deda implementira taj interface. vTable za IDeda ne pocinje na istoj lokaciji kao vTable za Deda klasu nego na lokaciji koja definise pointer na metod Obicni(). Naravno, ovo implicira da se svi metodi nekog interface-a u vTable klase koja ih sadrzi nalaze jedan iza drugog i tako je bilo bar do sada

Implementacija Interface-a na .NET JIT je komplikovana (konsultuju se tri tabele umesto jedne), pa cu tu pricu ostavitri za neki drugi put.


7. Early/Late binding

Kompjuterski naucnici definisu late binding kao poziv "necega" cija se adresa na zna do trenutka pozivanja. Po toj definiciji svi virtuelni metodi su late-bound (zato sto se adresa indirektno odredjuje iz vTable a pri kompajliranju se ne zna koji ce tacno vtable biti u referenci), dok su svi staticki i objektni metodi early-bound, i tako je bilo do skoro . Asemblerski receno, call je early-bound, [call dword ptr] je late bound.

Terenci (kao sto sam ja) uglavnom smatraju ovu definiciju zastarelom, narocito sa uvodjenjem .NET-a
Na osnovu prethodne diskusije vidi se da po toj definiciji uopste ne postoji early binding u .NETu posto su svi pozivi implementirani sa [call dword ptr]. Zabunu su pokusali da rese tvrdnjom da se definicija odnosi samo na sors code, ali je to uvelo jos vecu zabunu i otezalo odredjivanje sta je u stvari late a sta early binding, narocito za manje iskusne korisnike, a i efektivno cemu definicija ako nema neko utemeljenje u realnoj praksi, mozemo da se lazemo tri dana da je to early-binding kad je implementacija i early i late bound poziva ista

U celoj toj prici postoji i koncept dinamickog bindovanja kakav koristi COM gde se klasa dinamicki "ucitava" i onda konsultuje type-library da se locira ID metode i zatim pozivanje metoda obavlja kroz IDispatch interfejs (slican mehanizam za .NET postoji u refleksiji), i to je tehnika koja sa sobom vuce pad performansi, i koji se u VB terminlogiji tretira kao late binding, i sa kojim se i ja licno slazem.

Definicija koju ja prihvatam je da je early binding poziv nekog metoda cija adresa je poznata u trenutku prevodjenja ILI je prisutna u adresnom prostoru programa u trenutku poziva. Late bound su svi pozivi cija odredisna adresa mora da se "sracuna" prilikom pozivanja.





_{[Ovu poruku je menjao mmix dana 25.07.2006. u 12:31 GMT+1]}

---

Kolega Mitrovicu sedite, 10+

Za jos malo perverzija sa pointerima i "vTablama" - ATL Under the Hood - Part 1 (ima ih 5, pa ko voli...). Nema veza sa Frameworkom, ali je korisno znati - principi su isti...

---

Samo se vi zaje*avajte, sutra kontrolni

---

Najpre, svaka cast za znanje i za trud, i puno hvala na ovakvim postovima.
Ja nisam jos sve do kraja proucio, ali cini mi se da sam nabasao na jedan bug u ovom izlaganju. Ispravite me ako gresim:

...

Koliko ja razumem razliku izmedju overrajdinga i zaklanjanja, ovde smo samo zaklonili metod iz klase Deda, tako da ce i d.Metod() i u.Metod() pozivati Deda.Metod() jer su d i u deklarisani kao Deda. Nedostaje nam jedno overide u dekleraciji metoda u klasi Unuk da bi u.Method() pozvao Unuk.Method().
Ako sam u pravu, kako to onda utice na ostale zakljucke iz ovog teksta?
Pozdrav

Nije bug u tekstu, cisto typo, posto sam kod kucao u text editoru pa ga onda kopirao u VS da izgenerisem MSIL/asm. Naravno ispravio sam ga u VS-u (posto samo virtual bez new nije dovoljan za hiding). Medjutim zaboravio sam da pastujem ispravku nazad u tekst. Nema uticaja na ostatak teksta posto je asemblerski prikaz baziran na override. Izmenio sam post da ne bi bilo zabune.

Kad smo vec kod "new modifier", mali savet. Nemojte nikad to koristiti. To kreira novu lokaciju u vTable koja pocinje da vazi tek od ove klase, efektivno razbijajuci polimorfizam te i buducih klasa u odnosu na pretke. Ja jos nisam video primer u kome bi skrivanje bilo primenljivo u nekoj klasi.

U svakom slucaju hvala na uocenoj gresci...

---

Tacnije, proslo bi, ali uz upozorenje kompajlera da bi bilo pristojno od nas da mu lepo kazemo sta smo to zamislili... da li planiramo hiding (stavi new) ili overrajding (stavi override). Ako mu ne kazemo, podrazumevace hiding.

I jos jedno pitanje, kad smo vec tu: da je ostalo bez override, kakvu bi VTable za klasu Unuk napravio JIT?
Predpostavljam da bi se tad u njoj naslo mesta za jos jedan Deda.Metod(), a morao bi valjda da ostane i Unuk.Metod()?

Da. Ovo mi se "javilo" kada sam sve malo detaljnije proucio i razumeo.
Jos jednom: odlican prilog! Fala

vTable bi izgledao ovako:



Problem je jedino sto je potpis metoda isti pa ce kompajler pozvati Unuk.Metod() ako je referenca klase Unuk i njenih naslednika, a Deda.Metod() za sve klase pre Unuk u hijerarhiji. Tj, poziv vise ne zavisi od vTable-a koliko od tipa reference koji nosi instancu, sto je vrlo nesrecno sa stanovista OOP-a



ce pozvati Deda.Metod(), ne Unuk.Metod() posto je polimorficki niz za Metod() prekinut u klasi Unuk i prebacen na novu lokciju u vTable

---