Názory k článku
Architektury mikroprocesorů

Dobry clanek.

Jenom mne vrta hlavou, jak je reseny garbage collector u procesoru pro javu. Je to soucast procesoru, nebo je to az soucasti programu nebo se na nejakou praci s pameti u takovychto procesoru kasle a pocita se s tim, ze se o to postara prekladac?

Alokátor paměti v Javě je strašně primitivní věc (mnohem jednodušší než C alokátor).

Zjednodušeně funguje asi tak, že máme dvě stejně velké oblasti a do jedné z nich ukazuje ukazatel. Při alokaci objektu o velikosti N se k ukazateli přičte N a vrátí se stará hodnota ukazatele --- čili ty objekty se tam skládají jeden za druhým.

Až se dojde na konec oblasti, tak se začne alokovat ve druhé oblasti a současně s tím se prochází dosažitelné objekty a ty se přesouvají z první do druhé oblasti. Až se všechny projdou, tak se první oblast celá uvolní --- ta pak čeká na použití, až se zase zaplácá druhá oblast).

Takže bych tipoval, že to bude tak, že alokace objektu bude v hardware a až ta oblast přeteče, tak to vyvolá nějaký exception. Ale detaily neznám.

A to je prave to co by me zajimalo - kdo nebo co je zodpovedny(e) za praci s pameti a jak je to technicky resene. Procesor je totiz relativne primitivni soucastka, co se tohoto tyce, ale v pripade javy by se mohlo neco takoveho vyplatit.

Hardwarovou podporu správy paměti měly už lispové procesory. To není nic tak složitého, ale je třeba si uvědomit, že tehdejší stroje byly často word-oriented a měly navíc tagovanou paměť... To odstraňuje spoustu problémů, které se dnes složitě řeší softwarově, jako jsou typové kontroly a optimalizace.

Aha takze Java alokuje 2x vic pameti nez potrebuje?

Java je jenom jazyk. ;-) A typ garbage collectoru, pokud vím, není povinný. Jsou i úspornější řešení, ne?

Dokonce víc než dvakrát. Leo Galamboš (dělá na MFF vyhledávač v javě) zjistil, že to sežere spoustu další paměti na kdovíco. Má počítač s 4GB, javě dal 2GB a navíc to vyžralo další necelý 1GB z neznámého důvodu.

První implementace javy (bez tohohle garbage collectoru, co současně i přesouvá a defragmentuje) žraly mnohem víc, prý tam jakýkoli objekt sežral asi 2kB.

Tak to muselo být nějaký úchylný. To už Lisp to měl dvacet let před Javou vyřešený líp, s MacLispem na PDP-10 podobný problémy určitě nebyly, kdepak dvě kila na objekt...

Nechápu, proč by nurseries mělo být víc, a už vůbec nechápu, co to má společného s čtením před psaním. :-) Přijde mi, že to může jedině zesložitit řešení write barriers v dalších generacích heapu, a ty by měly mít co nejmenší overhead. A osm bajtů je na 32b stroji celkem jasných - hlavička objektu a reference na třídu/typ.

Zapomnel jsi dodat, ze trpis poruchu osobnosti ;)

Jako by to nebylo zrejme z jeho prispevku. ;-)

Ano, poruchu mám, jsem psychopat.

zaujimave, ze zjednodusujes strasne primitivnu vec ;-)

No, pokud vím, tak způsob práce s pamětí v Javě není předepsaný, a tenhle naivní kopírovací princip se určitě nepoužívá.

O Javě od Sunu se dá dočíst, že používá hybridní generační přístup: všechny objekty vznikají v Eden Space, když se ten zaplní, tak se živé objekty z něj a z jednoho Survivor Space přesunou do druhého Survivor Space (to je skoro to, co popisuješ, ale Survivor Spaces jsou oproti ostatním částem heapu velmi malé), a to se opakuje dokud nedojde místo i tam. Přičemž se počítá s tím, že velká většina objektů zanikne velmi brzy po svém vzniku, takže se nedostanou ani z Edenu. Přeživší objekty se pak přesouvají do Tenured Space, kde se pro čištění používá mark and sweep. V základu je to všechno Stop The World, existují i paralelní implementace. Jak se řeší zvětšování heapu netuším. U IBM to dělají zase nějak jinak (nevím jak).

Tak blbí vážně nejsou :-)

To, co jsem popsal, pochází z nějakého popisu javy od IBM. Odtud plyne to známé ponaučení, že se nemá alokovat objekt v cyklu. Sunu asi došlo, že to plýtvá pamětí, a tak to vylepšil.

Když budeš alokovat objekt v cyklu, nic hrozného se nestane. Pokud na objekty nebude žádná reference zvenčí nursery, tak je systém šmahem zahodí s minimální vynaloženou prací. Navíc nursery má dobrou cache locality, je obvykle docela malá. Ty alokace skutečně nemusejí být drahé, alespoň ne v porovnání s mallocem. Samozřejmě že nealokovat vůbec a mít všechno, co se zpracovává najednou, hezky při sobě, jak je to v Cčku nebo ve Forthu celkem běžné, je nejlepší alternativa, pokud je to z povahy problému možné, ale pokud člověk potřebuje náhodné alokace (třeba na obecné stromy s různými typy a velikostmi uzlů a tak), nemyslím, že by na tom malloc a free byly nějak líp - tedy aspoň ne normální malloc a free. Řekl bych, ře dobře napsaná Cčková aplikace bude rychlejší než aplikace v Javě právě tehdy, pokud bude mít citlivě navrženou práci s pamětí a nebude moc cvičit malloc, protože hodně dynamická správa paměti asi nebude silná stránka Cčka (nepoužije li člověk libgc nebo něco podobného). A jak už jsem psal, recyklovat objekt místo vytvoření nového stylem "změním jednu referenci ve starém objektu, aby ukazovala na nový, co teď právě vytvářím" může oproti vytvoření nového objektu vyjít v Javě nebo Lispu (s generačním GC) překvapivě draho. Aby správce paměti dokázal vysledovat reference na objekty v nursery (které je nutné časem přemístit), jsou nad objekty v "dynamické části heapu" (druhá generace a i ty další) nasazené write barriers, protože správce paměti musí reference vedoucí do nursery sledovat.

Zakladni podpora pro multithreading a sberac smeti je opravdu implementovana uz v procesoru, viz http://www.cs.ualberta.ca/~macg/C429/Extras/picoJava.htm Detaily moc neznam (Sun jaksi picoJavu nedokazal protlacit na trh), ale predpokladam, ze tam stejne jako normalne pobezi uklizeci vlakno, ktere s podporou procesoru bude pamet cistit (resp. to cisteni je zNULLovani par ukazatelu, pardon referenci :-)

Prekladac se o to postarat v mnoha pripadech nemuze, je to veci runtime.

"Celková velikost programového kódu je u zásobníkových procesorů obecně menší, než u RISC procesorů. RISC procesory totiž mají velké množství registrů, pro jejichž specifikaci (adresaci) je nutné použít většího množství bitů v kódu instrukce. Dokonce se uvádí vtip, že velikost vyrovnávací paměti (cache) u RISC procesoru musí být větší než kapacita CELÉ operační paměti u zásobníkového procesoru, přičemž na obou procesorech běží programy stejnou rychlostí."

Ono je to ještě o něco lepší. :-) Jelikož dnešní zásobníkové procesory zvládnou skok do podprogramu ("slova") za jeden takt a návrat za nula taktů (typicky návratovým bitem), není prakticky zapotřebí inlajnovat kód. Věci, které mají být rychlé, se pak prostě dají do rychlé paměti, a může to být i jeden několikabajtový fragment kódu volaný z mnoha míst, o kterém se zjistilo, že se volá příliš často. V RISCu nebo na x86 by se inlajnoval, ale musel by přitom být opakovaný na mnoha místech. Cache tedy v RISCu nebo x86 klidně může po vykonání kusu kódu flushout jednu sekvenci instrukcí jen proto, aby ji nahradila téměř stejná sekvence instrukcí jinde. :-) Tady to není nutné, ten kousek bude vyfaktorovaný do rychlé paměti. S tímhle zjednodušením odpadá i potřeba CAMky pro řídicí logiku cache, což je taky taková křemíková kráva. Není divu, že se Chuckovy procesory vejdou doslova do pár tisíc tranzistorů. ;-)

..ze poslednich nekolik clanku od tohohle autora je jak urovni, tak zpracovanim presne to, co jeste pred pul rokem na rootu chybelo (a zavanelo Administrator.cz ;-))
JEN TAK DAL! :-)

Mozna nejen "nekolik poslednich".

Me v tom prehledu chybi procesor z Terminatora II http://www.youtube.com/watch?v=QrRyE28BI4Q (vystrizena scena). Rad bych vedet, zda je to RISC nebo MISC 8-)

Muzete mi prosim nekdo vysvetlit co by melo znamenat slovo ortogonalita v nasledujicim contextu "platforma x86 je architekturou CISC, i když do ortogonality své instrukční sady měla zejména v minulosti daleko" ? Ortogonalita je vzdy pravouhlost a instrukcni sada narozdil treba od trojuhelniku pravouhla byt nemuze, takze nechapu proc se tady objevil takovy blabol.

David ti to vysvětlí. http://www.majda.cz/zapisnik/?31 Už chápeš?

Ortogonalita je mnohem vic nez pravouhlost, i kdyz je to skutecne jeji prvotni vyznam :-)

Je to docela prijemna vlastnost (hlavne pro vyvojare pisiciho v assembleru). Jde v podstate o to, ze kdyz se u ortogonalni ISA naucite par zakladnich instrukci (ADD, SUB, MUL, AND, RR atd.) a adresni rezimy, ktere dana ISA podporuje (napr. konstanta, registr, prima adresa, neprima adresa, adresa+index, adresa+index*konstanta), tak u teto instrukcni sady uz vlastne znate spoustu ruznych kombinaci instrukci, protoze vsechny adresni rezimy lze pouzit pro velkou cast instrukci. Tj. napriklad by melo jit napsat:

ADD neprima adresa, adresa+index*konstanta

U neortogonalnich ISA si musite pamatovat, co muze mit ktera instrukce za operandy, napriklad ze MUL vzdy nasobi registr A s necim jinym (je to jenom priklad, ale trosku vychazi z puvodni ISA x86), nebo ze u instrukce MOV nelze provest presun pamet-pamet (opet Intel).

Detailne je to vysvetlene napriklad na Wiki: http://en.wikipedia.org/wiki/Orthogonal_instruction_set

Kdyz ono tu ortogonalitu muzes brat doslova jako pravouhlost (kolmost) v matematice (geometrii) stredoskolske urovne. Pronikl-li bys do matematiky hloubeji, tak bys zjistil, ze pak uz je to kolikrat jen "pravouhlost" (tedy jen v prenesenem slova smyslu) a treba v neeuklidovskych geometriich bys podle svych kriterii kolikrat jen tezko oznacil primky za primky a kolme za kolme.

To je kdyz tabulky instrukci v datasheetu jsou kresleny podle trojuhelniku s ryskou,
pak je instrukcni sada ortogonalni. Kdyz jsou kresleny od ruky a svisle a vodorovne
cary nesviraji uhel presne 90 stupnu, pak se rika, ze procesor ma instrukcni sadu neortogonalni.

http://en.wikipedia.org/wiki/Orthogonality

priklad ortogonality: muz ma lulinka, zena ma pipinku. sulinek a pipinka (muz vs. zena) jsou ortogonalni, maji navzajem nezamenitelne role! hermafrodit s lulinkem i pipinkou zaroven uz neni ortogonalni k zene ani muzovi, protoze je to jejich linearni kombinace.
je to jako by muz byl bazovy vektor (0,1) a zena bazovy vektor (1,0), navzajem jsou
ortogonalni. hermafrodit by byl vektor (sqrt(2),sqrt(2)) a to neni bazovy vektor.

Máš za tři. (2,2) zcela klidně může být bázový vektor, pokud k němu přidáš ještě jeden vektor takový, že budou navzájem lineárně nezávislé. Bázové vektory jsou lineárně nezávislá podmnožina vektorového prostoru, která vektorový prostor generuje (tj. každý prvek vektorového prostoru se dá vyjádřit jako lineární kombinace bází). Není tam ani slovo o tom, že všechny báze musejí být ortogonální.

Ani tvrzení "hermafrodit s lulinkem i pipinkou zaroven uz neni ortogonalni k zene ani muzovi, protoze je to jejich linearni kombinace" není správné, protože lineární kombinací vektorů (0,1) a (1, 0) získám třeba i vektor (2, 0) a ten je ortogonální vůči (0, 1). To, že X je lineární kombinací Y a Z prostě ještě neznamená, že Z nemůže být ortogonální k Y nebo k Z - nemůžu tohle tvrzení použít v implikaci.

Proti matematické argumentaci nelze nic namítat, ale nesmí být nepřesná, jinak je lepší mlčet. :-)

Proč za tři? Legendární asistent Pytlíček by za tohle vyhodil ještě mezi dveřma a neopomněl to okomentovat, že ani za 14 dnů to nebude umět tak, aby se to neopakovalo :-D

Jo jo, Pytlicek rulez. V jeho podani je linearni algebra stejne tezka jako matematicka analyza.

Tak na Pytlíčka taky moc rád vzpomínám. To byl vyhazov od zkoušky s elegancí. :-D

Přitom algebra v jeho podání měla velké kouzlo, které jsem ale bohužel objevil až na poslední přednášce prvního semestru. Do té doby byla celá algebra nesouvisejícím pelmelem mnoha různých fragmentů, které ač zajímavé, nedávaly příliš smysl. Poslední přednáška to celé spojila a SKORO jsem začal algebru milovat. Jenže doučit jsem se to nezvládl (to nevyčítám ani tak Pytlíčkovi, jako jisté tradiční rostlině přidávané do "smíchovské polívky") a tak jsem si prožil tři letecké dny (z toho dvakrát na numerickém přehlédnutí v maticích, což tak trošku zamrzí). Mno, aspoň jsem si tehdy do dalšího školního roku prodloužil prázdniny...

Pytlíček byl rozhodně zajímavou killer aplikací...

:) ty titulky v pohledu terminatora jsou dobre :) pred ocekavanym shutdownem - PORT OPEN - Address checksum verified :) Prep for shutdown... a pak jeho reboot :) Zkontroluje si jak dlouho byl off, checkuje napajeni :)) hehe ... Každopádně je to verze 2.4, což hlásí po rebootu. Zřejmě nějaké starší 2.4kové jádro :)))

Kdyz se tu mluvi o tech zasobnikovych CPU, to jsem mel za ukol v praci napsat interpret Basicu
tak jsem to s Bisonem a Flexem intuitivne napsal presne takhle. Kdyz jsem se pak pozdejc dovedel, ze podobne funguje Java, doslo mi, ze Java neni vlastne nic jineho nez BASIC, kolem ktereho se dela spousta hype.

:-D

Jasne bytekod v JVM sice Sun prezentoval jako cosi revolucniho, co ovladne nase mikrovlnky atd. ale ze je idea bytekodu stara tak, jako interpretovane jazyky uz nikdo nerekl (P-code, nektere Basicy, muj oblibeny Forth atd.).

S Javou bys to mel trosku slozitejsi, je to LALR(1) gramatika, takze vysledny kod, co z neho vyleze bude IMHO dost obludny.

Jeden rozdil tady je: pro Basic staci cca 512 bytu RAM a 2 kB ROM (+dalsi 2 kB kdyz budes chtit screen editor, ale to neni potreba), kdezto u Javy je to trosicku vic.

Myslenka bytekodu a VM neni vubec nova a vubec nepochazi z Javy. Viz napr. Smalltalk, ktery existoval mnohem drive.

No jistě. A dokonce pravě basic už v první verzy běžel v interpretu - VM takže je to recht.

Ehm... Cosi jako GC rozhodně měl! Nebo snad jste musel pro řetězce alokovat a dealokovat nějaký prostor?

Budou v nejakem dilu i dalsi architerty, jakou uz zminana VLIW, pripadne takove specialitky jako OISC/TTA?

VLIW proberu urcite (mozna uz priste), ale priznam se, ze o OISC toho moc nevim :-(

co jsem nasel na wikipedii, ze OISC ma jednu jedinou instrukci :-)

Jj, už to vidím. Docela minimalistické :-) Vlastně to nemá ani opkód, jenom adresní část instrukce, pravý opak MISC...

TTA (transfer-trigered architecture) je jeste jednodussi - ta nema ani adresu, kazda "instrukce" jen otevira propojeni mezi dvema bloky (registry, ALU, pristup do pameti atd.), akce se vyvola tim, ze se do neceho zapise (proto tranfer-trigered). "Instrukce" obsahuji jen cisla zdroju a cilu. Je to jako by byl klasicky procesor programovany primo v mikrokodu a obdobne jako VLIW prenasi paralelizsmus na stranu prekladace/programatora, protoze musi pocitat s latencemi jednotlivych bloku.

Problém je, že u jazyku typu C neurčíš nijak latence instrukcí přistupujících do paměti.

Není znám algoritmus, který by se podíval na zdroják nebo na assembler a s rozumnou přesností určil, která proměnná se bude nahrávat z L1 cache, která z L2 cache a která z hlavní paměti.

Proto mají ty x86 procesory out-of-order vykonávání, protože tohle kompilátor neudělá.

Kdybys chtěl určovat latence kompilátorem, tak bys musel mít just-in-time kompilátor --- kde se to za běhu naměřit dá.

Mimochodem, z tohoto důvodu existuje pár případů, kdy je java rychlejší než C (v podstatě se v té javě nesmí nic alokovat jenom dělat operace už s naalokovanými poli --- pak to JIT může zkompilovat líp než C kompilátor)

A BLEKu, proc to nezkompilovat nejdriv s testem, pak to nechat probehnout nejakymi testy a na zaklade tech testu odhadnout, ktera promenna se bude cist z ktere cache, a pomoci teto informace to pak staticky zkompilovat? Nechces namet na dalsi projekt? ;-)

Jak přesně si to představujete? Cache je víceméně transparentní, až na tu latenci, samozřejmě... Možná by zaangažovat nástroj typu Intel VTune, ale podle mě by v tom bylo docela dost hádání. Buďme rádi, že už máme aspoň těch šestnáct general-purpose registrů! Vivat AMD!

Nebejt AMD a jejího šílenýho x86 everywhere, třeba se mohlo časem prosadit Itanium se 128 GPR integer registrama. Smrt AMD :-)

Itanium se potopilo samo (tím, že je přepatlané featurami => drahé a pomalé). Nikdo si nebude kupovat počítač, který je 20x dražší než běžné PC a navíc ještě pomalejší.

Ruku na srdce - nebyl by nejlepší MIPS? ;-) Jednoduchý, pěkný, energeticky úsporný... :-) (Nebo MMIX :-D)

Vsak neboj, MIPS se pouziva docela casto. Absolutni cisla asi nikdo nevi, ale rekl bych, ze MIPSu se vyrobi vic nez neceho na bazi x86.

No, jak si to predstavuju, copak jsem BLEK, abych resil tenhle problem? :) Ja jenom navrhuji postup, jak obecne dohnat vyhodu JIT kompilatoru proti statickemu kompilatoru tim, ze se ta staticka kompilace provede na zaklade nejake statistiky bezneho chovani programu. Sam BLEK pise, ze se ta latence zmerit da, takze asi vi jak na to, ja o tom nemam tuseni. A ani me to nezajima, protoze vim o mnohem lepsi tride optimalizaci zalozenych na tomto principu, ale nehodlam to zatim nikde sirit, protoze si to chci vyzkoumat sam. :)

To umí gcc pouze pro určení skoků, zda se provedou nebo ne. S cachovaností proměnných by to bylo zajímavé. Kdyby se mezi každým přístupem do paměti četly performance-monitoring-countery, tak by to asi ten program šíleně zpomalilo.

Ale možná by bylo zajímavé udělat tohle:

Pustit si timer a občas z zapnout Trace flag a z trap signálu si číst performance countery (a po několika stovkách instrukcí ho zase vypnout, aby ten program taky mohl běžet). Tím získat profil nejen, kde to nejvíc čeká, ale i na čem to nejvíc čeká (cache apod). Kdybych byl ještě na škole, nebylo by špatný to vypsat jako projekt/diplomku :)

Nebo už je nějaký nástroj, který tohle dělá?

http://microblog.routed.net/2008/04/18/ic-friday-intels-80386-dx

mozno by nebolo zle popisat neskor aj ARM proc. a dalsie, predsalen sa pouzivaju hojne dnes. V kazdom pripade dakujem sa skvelu seriu

ARM je vubec nepravem pomijeny. Pouziva ho kazdy druhy, ale obvykle se pri popisech architektur zcela vynechava.

Vsak se ARMu dockame, taky se na nej chystam :-)

Nevím jestli to už bylo v seriálu uvedeno, ale celkem bych to potřeboval vědět.

Jak jsou uloženy základní datové typy v paměti počítače a jak s nimi procesor pracuje?
(předpokládám, že prostě na určité adrese se do paměti uloží nějaká data, která se pak přečtou. Jak se ale pozná co tam je za data (byte, int, real)? Nebo jak s tím pc (procesor) pracuje?)

Zdravim, samozrejme se timto tematem budeme jeste zabyvat, ale v kratkosti:

V pameti neni (pri praci na tak nizke urovni, jako je strojovy kod, assembler ci jazyky typu C ci Pascal) zadna informace o tom, co se na konkretni bunce nachazi, takze je mozne napriklad na nejakou adresu ulozit integer (32 bitu) a precist ho jako realne cislo (float, taky 32 bity), nebo jako sekvenci ctyr ASCII znaku.

Tedy informace o typu je ulozena v programu, sam programator si musi ohlidat, co v pameti je a jak se s ni ma pracovat. Samozrejme prakticky vsechny jazyky (od assembleru vyse) mu s timto pomahaji, protoze pouzivaji takove abstraktni veci jako datove typy a objekty, ovsem i tak je mozne (a vlastne i nutne) nekdy tento typovy system obchazet.

díky všem, takže v samotné paměti nic o tom, jaký tam je uložený typ nic není(kromě samotného programu), to je velmi zajímavé (sem netušil, že datové typy jsou jenom abstraktní záležitostí, ale asi to tak je nejjednodušší).. :-)

Už se těším na díl s vysvětlenou touto problematikou. (a jak se vytvářejí ze základní sady instrukcí tyto abstraktní vymoženosti/nejen datové typy/. :-) )