Závitový kód - Threaded code

Nesmí být zaměňována s vícevláknovým programováním .

V informatice je závitový kód programovací technika, kde kód má formu, která v podstatě sestává výhradně z volání podprogramů . Často se používá v kompilátorech , které mohou generovat kód v této formě nebo být v této formě implementovány samy. Kód může zpracovat tlumočník nebo to může být jednoduše sekvence pokynů pro volání strojového kódu .

Vláknový kód má lepší hustotu než kód generovaný alternativními generačními technikami a alternativními konvencemi volání . V architekturách uložených v mezipaměti se může spouštět o něco pomaleji. Avšak program, který je dostatečně malý, aby se vešly do počítačového procesoru s mezipaměti může běžet rychleji než většího programu, který trpí mnoho vyrovnávací paměti mine . Malé programy mohou být také rychlejší při přepínání vláken, když mezipaměť zaplnily jiné programy.

Vláknový kód je nejlépe známý pro jeho použití v mnoha kompilátorech programovacích jazyků , jako je Forth , mnoho implementací BASIC , některé implementace COBOL , rané verze B a další jazyky pro malé minipočítače a pro amatérské rádiové satelity .

Dějiny

Běžným způsobem vytváření počítačových programů je použití překladače k překladu zdrojového kódu (napsaného v nějakém symbolickém jazyce ) do strojového kódu . Výsledný spustitelný soubor je obvykle rychlý, ale protože je specifický pro hardwarovou platformu, není přenosný. Jiným přístupem je generování pokynů pro virtuální počítač a použití tlumočníka na každé hardwarové platformě. Tlumočník vytvoří instanci prostředí virtuálního počítače a provede pokyny. Proto musí být kompilován pouze tlumočník.

Starší počítače měly relativně málo paměti. Například většina Data General Nova , IBM 1130 a řada prvních mikropočítačů měla nainstalované pouze 4 kB RAM. V důsledku toho bylo mnoho času věnováno hledání způsobů, jak zmenšit velikost programu, aby se vešel do dostupné paměti.

Jedním z řešení je použít tlumočník, který čte symbolický jazyk trochu najednou a volá funkce k provedení akcí. Protože zdrojový kód je obvykle mnohem hustší než výsledný strojový kód, může to snížit celkové využití paměti. To byl důvod, proč je Microsoft BASIC tlumočníkem: jeho vlastní kód musel sdílet 4 kB paměť strojů jako Altair 8800 se zdrojovým kódem uživatele. Kompilátor překládá ze zdrojového jazyka do strojového kódu, takže kompilátor, zdroj i výstup musí být všechny současně v paměti. V tlumočníkovi neexistuje žádný výstup. Kód je vytvořen řádek po řádku, spuštěn a poté zahozen.

Vláknový kód je styl formátování kompilovaného kódu, který minimalizuje využití paměti. Místo toho , aby kompilátor zapisoval každý krok operace při každém jejím výskytu v programu, jak to bylo například běžné v sestavovačích maker , zapisuje každý běžný bit kódu do podprogramu. Každý bit tedy existuje pouze na jednom místě v paměti (viz „ Neopakujte se “). Aplikace nejvyšší úrovně v těchto programech může sestávat pouze z podprogramových volání. Mnoho z těchto podprogramů zase také sestává pouze z volání podprogramů nižší úrovně.

Sálové počítače a některé rané mikroprocesory, jako je RCA 1802, vyžadovaly několik pokynů k volání podprogramu. V aplikaci nejvyšší úrovně a v mnoha podprogramech se tato sekvence neustále opakuje, přičemž se z jednoho volání na druhé mění pouze adresa podprogramu. To znamená, že program skládající se z mnoha volání funkcí může mít také značné množství opakovaného kódu.

Aby se to vyřešilo, systémy závitových kódů používaly pseudokód k reprezentaci volání funkcí v jednom operátorovi. Za běhu malý „tlumočník“ naskenoval kód nejvyšší úrovně, extrahoval adresu podprogramu do paměti a zavolal. V jiných systémech je stejný základní koncept implementován jako větevová tabulka , odesílací tabulka nebo tabulka virtuálních metod , z nichž všechny se skládají z tabulky adres podprogramů.

V 70. letech minulého století vynaložili designéři hardwaru značné úsilí na rychlejší a jednodušší volání podprogramů. U vylepšených návrhů je k vyvolání podprogramu vynaložena pouze jedna instrukce, takže použití pseudoinstrukce ušetří místo. Navíc výkon těchto hovorů je téměř bez dodatečné režie. Dnes se sice téměř všechny programovací jazyky zaměřují na izolaci kódu do podprogramů, ale dělají to kvůli přehlednosti a udržovatelnosti kódu, nikoli kvůli úspoře místa.

Systémy se závitovým kódem šetří místo tím, že nahradí tento seznam volání funkcí, kde se mění pouze podprogramová adresa z jednoho volání na druhé, seznamem prováděcích tokenů, což jsou v podstatě volání funkcí s odstraněnými operačními kódy volání, které zanechávají pouze seznam adres.

Za ta léta programátoři vytvořili mnoho variací na tento „tlumočník“ nebo „malý volič“. Konkrétní adresu v seznamu adres lze extrahovat pomocí rejstříku, obecného registru nebo ukazatele . Adresy mohou být přímé nebo nepřímé, souvislé nebo nesouvislé (propojené ukazateli), relativní nebo absolutní, vyřešené v době kompilace nebo dynamicky vytvořené. Žádná jediná variace není „nejlepší“ pro všechny situace.

Rozvoj

Aby ušetřili místo, programátoři vtěsnali seznamy volání podprogramů do jednoduchých seznamů adres podprogramů a pomocí malé smyčky postupně volali každý podprogram. Následující pseudokód například používá tuto techniku ​​k přidání dvou čísel A a B. V tomto příkladu je seznam označen vláknem a proměnná ip (Ukazatel ukazatele) sleduje naše místo v seznamu. Další proměnná sp (Stack Pointer) obsahuje adresu jinde v paměti, která je k dispozici pro dočasné uložení hodnoty. 

start:
  ip = &thread  // points to the address '&pushA', not the textual label 'thread'
top:
  jump *ip++  // follow ip to address in thread, follow that address to subroutine, advance ip
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  *sp++ = A  // follow sp to available memory, store A there, advance sp to next 
  jump top
pushB:
  *sp++ = B
  jump top
add:
  addend1 = *--sp  // Pop the top value off the stack
  addend2 = *--sp  // Pop second value off the stack
  *sp++ = addend1 + addend2  // Add the two values together and store the result on the top of the stack
  jump top


Volací smyčka na topje tak jednoduchá, že ji lze opakovat inline na konci každého podprogramu. Řízení nyní skočí jednou, od konce podprogramu na začátek jiného, ​​místo aby dvakrát skočilo přes top. Například: 

start:
  ip = &thread  // ip points to &pushA (which points to the first instruction of pushA)
  jump *ip++  // send control to first instruction of pushA and advance ip to &pushB
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  *sp++ = A  // follow sp to available memory, store A there, advance sp to next 
  jump *ip++  // send control where ip says to (i.e. to pushB) and advance ip
pushB:
  *sp++ = B
  jump *ip++
add:
  addend1 = *--sp  // Pop the top value off the stack
  addend2 = *--sp  // Pop second value off the stack
  *sp++ = addend1 + addend2  // Add the two values together and store the result on top of the stack
  jump *ip++

Toto se nazývá kód přímého vlákna (DTC). Ačkoli je tato technika starší, první široce rozšířené použití výrazu „závitový kód“ je pravděpodobně článek Jamese R. Bella z roku 1973 „Vláknový kód“.

V roce 1970 Charles H. Moore vynalezl kompaktnější uspořádání, nepřímý závitový kód (ITC), pro svůj virtuální stroj Forth. Moore k tomuto uspořádání dospěl, protože minipočítače Nova měly na každé adrese bit s nepřesností, díky čemuž bylo ITC snadné a rychlé. Později řekl, že mu to přišlo tak pohodlné, že to rozšířil do všech pozdějších Forthových návrhů.

Dnes některé kompilátory Forth generují kód s přímým vláknem, zatímco jiné generují kód s nepřímým vláknem. Spustitelné soubory fungují stejným způsobem.

Navlékání modelů

Prakticky všechny spustitelné podprocesové kódy používají jednu nebo druhou z těchto metod pro vyvolání podprogramů (každá metoda se nazývá „model vláken“).

Přímé navlékání

Adresy ve vlákně jsou adresy strojového jazyka. Tento formulář je jednoduchý, ale může mít režijní náklady, protože vlákno se skládá pouze z adres počítače, takže všechny další parametry musí být načteny nepřímo z paměti. Některé systémy Forth produkují kód s přímým vláknem. Na mnoha strojích je přímé vlákno rychlejší než podprogramové vlákno (viz odkaz níže).

Příkladem zařízení typu stack může být sekvence „push A, push B, add“. To může být přeloženo do následujícího vlákna a rutin, kde ipje inicializováno na adresu označenou thread(tj. Na adresu, kde &pushAje uložena). 

#define PUSH(x) (*sp++ = (x))
#define POP() (*--sp)
start:
  ip = &thread  // ip points to &pushA (which points to the first instruction of pushA)
  jump *ip++  // send control to first instruction of pushA and advance ip to &pushB
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  PUSH(A)
  jump *ip++ // send control where ip says to (i.e. to pushB) and advance ip
pushB:
  PUSH(B)
  jump *ip++
add:
  result = POP() + POP()
  PUSH(result)
  jump *ip++

Alternativně mohou být do vlákna zahrnuty operandy. To může odstranit některé indirection potřebné výše, ale zvětší vlákno: 

#define PUSH(x) (*sp++ = (x))
#define POP() (*--sp)
start:
  ip = &thread
  jump *ip++
thread:
  &push
  &A  // address where A is stored, not literal A
  &push
  &B
  &add
  ...
push:
  variable_address = *ip++ // must move ip past operand address, since it is not a subroutine address
  PUSH(*variable_address) // Read value from variable and push on stack
  jump *ip++
add:
  result = POP() + POP()
  PUSH(result)
  jump *ip++

Nepřímé navlékání

Nepřímé vlákno používá ukazatele na umístění, která zase ukazují na strojový kód. Za nepřímým ukazatelem mohou následovat operandy, které jsou uloženy v nepřímém „bloku“, než aby je opakovaně ukládaly do vlákna. Nepřímý kód je tedy často kompaktnější než kód s přímým vláknem. Indirection to obvykle zpomaluje, i když obvykle stále rychleji než tlumočníky bytecode. Pokud operandy obslužné rutiny zahrnují hodnoty i typy, mohou být úspory místa oproti kódu s přímým vláknem značné. Starší systémy FORTH obvykle produkují kód s nepřímým vláknem.

Pokud je například cílem provést „push A, push B, add“, lze použít následující. Zde ipje inicializován na adresu &thread, každý fragment kódu ( push, add) je nalezen dvojitým přesměrováním ipa nepřímým blokem; a všechny operandy fragmentu se nacházejí v nepřímém bloku za adresou fragmentu. To vyžaduje zachování aktuálního podprogramu ip, na rozdíl od všech předchozích příkladů, kde obsahoval další podprogram, který má být vyvolán. 

start:
  ip = &thread  // points to '&i_pushA'
  jump *(*ip)  // follow pointers to 1st instruction of 'push', DO NOT advance ip yet
thread:
  &i_pushA
  &i_pushB
  &i_add
  ...
i_pushA:
  &push
  &A
i_pushB:
  &push
  &B
i_add:
  &add
push:
  *sp++ = *(*ip + 1)  // look 1 past start of indirect block for operand address
  jump *(*++ip)  // advance ip in thread, jump through next indirect block to next subroutine
add:
  addend1 = *--sp
  addend2 = *--sp
  *sp++ = addend1 + addend2
  jump *(*++ip)

Podprocesové navlékání

Takzvaný „podprocesový podprocesový kód“ (také „kód podprocesu volání“) se skládá ze série instrukcí „volání“ ve strojovém jazyce (nebo adres funkcí k „volání“, na rozdíl od použití přímého vlákna pomocí „skoku“ ). Dřívější kompilátory pro systémy ALGOL , Fortran, Cobol a některé systémy Forth často vytvářely podprocesový podprocesový kód. Kód v mnoha z těchto systémů fungoval na zásobníku LIFO (last-in-first-out-out), pro který byla dobře vyvinutá teorie kompilátoru. Většina moderních procesorů má speciální hardwarovou podporu pro podprogramové instrukce „volání“ a „návrat“, takže režie jedné další strojové instrukce na odeslání je poněkud snížena.

Anton Ertl, spolutvůrce kompilátoru Gforth , uvedl, že „na rozdíl od populárních mýtů je podprogramové navlékání obvykle pomalejší než přímé navlékání“. Ertlovy nejnovější testy však ukazují, že podprogramové navlékání vláken je rychlejší než přímé navádění v 15 z 25 testovacích případů. Přesněji řečeno, zjistil, že přímé navlékání je nejrychlejším modelem navlékání na procesorech Xeon, Opteron a Athlon, nepřímé navlékání je nejrychlejší na procesorech Pentium M a podprogramové navlékání je nejrychlejší na procesorech Pentium 4, Pentium III a PPC.

Jako příklad volání vláken pro „push A, push B, add“: 

thread:
  call pushA
  call pushB
  call add
  ret
pushA:
  *sp++ = A
  ret
pushB:
  *sp++ = B
  ret
add:
  addend1 = *--sp
  addend2 = *--sp
  *sp++ = addend1 + addend2
  ret

Tokenové navlékání

Tokenový závitový kód implementuje vlákno jako seznam indexů do tabulky operací; šířka indexu je přirozeně zvolena tak, aby byla co nejmenší z hlediska hustoty a účinnosti. 1 bajt / 8 bitů je přirozenou volbou pro snadné programování, ale v závislosti na počtu podporovaných operací lze použít menší velikosti, jako jsou 4 bity, nebo větší, například 12 nebo 16 bitů. Dokud je šířka indexu zvolena užší než ukazatel na stroji, bude přirozeně kompaktnější než ostatní typy vláken bez velkého úsilí programátora. Obvykle je to polovina až tři čtvrtiny velikosti jiných vláken, které jsou samy o čtvrtinu až osminu velikosti nezávitového kódu. Ukazatele tabulky mohou být buď nepřímé, nebo přímé. Některé kompilátory Forth produkují kód se závitem tokenu. Někteří programátoři považují „ p-kód “ generovaný některými kompilátory Pascal a také bajtové kódy používané kompilátory .NET , Java , BASIC a některými C za tokeny s tokeny.

Běžným přístupem je historicky bytecode , který obvykle používá 8bitové operační kódy s virtuálním strojem založeným na zásobníku. Archetypální tlumočník bajtového kódu je známý jako „tlumočník dekódování a odesílání“ a má následující formu: 

start:
  vpc = &thread
dispatch:
  addr = decode(&vpc) // Convert the next bytecode operation to a pointer to machine code that implements it
  // Any inter-instruction operations are performed here (e.g. updating global state, event processing, etc)
  jump addr
CODE_PTR decode(BYTE_CODE **p) {
  // In a more complex encoding, there may be multiple tables to choose between or control/mode flags
  return table[*(*p)++];
}
thread:  /* Contains bytecode, not machine addresses.  Hence it is more compact. */
  1 /*pushA*/
  2 /*pushB*/
  0 /*add*/
table:
  &add    /* table[0] = address of machine code that implements bytecode 0 */
  &pushA  /* table[1] ... */
  &pushB  /* table[2] ... */
pushA:
  *sp++ = A
  jump dispatch
pushB:
  *sp++ = B
  jump dispatch
add:
  addend1 = *--sp
  addend2 = *--sp
  *sp++ = addend1 + addend2
  jump dispatch

Pokud virtuální stroj používá pouze pokyny o velikosti bajtů, decode()je to prostě načtení z thread, ale často existují běžně používané 1-bajtové pokyny plus některé méně běžné vícebajtové pokyny (viz počítač s komplexními instrukčními sadami ), v takovém případě decode()je to složitější. Dekódování jednobajtových operačních kódů lze velmi jednoduše a efektivně zpracovat pomocí větvící tabulky pomocí operačního kódu přímo jako indexu.

U pokynů, kde jsou jednotlivé operace jednoduché, například „push“ a „add“, je režie spojená s rozhodováním o tom, co provést, vyšší než náklady na její skutečné provedení, takže tito tlumočníci jsou často mnohem pomalejší než strojový kód. U složitějších („složených“) pokynů je však procento režie proporcionálně méně významné.

Existují případy, kdy může kód se závitem tokenu někdy běžet rychleji než ekvivalentní strojový kód, když je tento strojový kód příliš velký, aby se vešel do fyzické mezipaměti instrukcí L1 CPU. Vyšší hustota kódu podprocesového kódu, zejména kódu s podprocesem s tokeny, mu může umožnit zcela se vejít do mezipaměti L1, když by to jinak nemělo, čímž by se zabránilo vymývání mezipaměti. Vláknový kód však spotřebovává jak mezipaměť instrukcí (pro implementaci každé operace), tak i mezipaměť dat (pro bytecode a tabulky) na rozdíl od strojového kódu, který spotřebovává pouze mezipaměť instrukcí; to znamená, že závitový kód sníží rozpočet za množství dat, která může být v daném okamžiku držena pro zpracování CPU. V každém případě, pokud počítaný problém zahrnuje použití velkého počtu operací na malé množství dat, pak použití závitového kódu může být ideální optimalizací.

Huffmanovo navlékání

Huffmanův závitový kód se skládá ze seznamů tokenů uložených jako Huffmanovy kódy . Huffmanův kód je řetězec bitů s proměnnou délkou, který identifikuje jedinečný token. Tlumočník se závitem Huffman vyhledá podprogramy pomocí indexové tabulky nebo stromu ukazatelů, které lze navigovat pomocí Huffmanova kódu. Huffmanův závitový kód je jednou z nejkompaktnějších reprezentací známých pro počítačový program. Index a kódy se volí měřením frekvence hovorů na každý podprogram v kódu. Časté hovory mají nejkratší kódy. Operacím s přibližně stejnými frekvencemi jsou přiřazeny kódy s téměř stejnými bitovými délkami. Většina systémů se závitem Huffman byla implementována jako systémy Forth s přímým vláknem a slouží k zabalení velkého množství pomalu běžícího kódu do malých, levných mikrokontrolérů . Většina publikovaných použití byla v čipových kartách, hračkách, kalkulačkách a hodinkách. Bitově orientovaný tokenizovaný kód používaný v PBASIC lze považovat za jakýsi kód se závitem Huffman.

Méně používané navlékání

Příkladem je navlékání řetězců, ve kterém jsou operace identifikovány řetězci, obvykle vyhledanými pomocí hashovací tabulky. To bylo použito v nejranějších Forth implementacích Charlese H. Moora a v experimentálním hardwarově interpretovaném počítačovém jazyce University of Illinois . Používá se také v Bashforthu .

RPL

HP je RPL , nejprve představen v HP-18C kalkulačka v roce 1986, je druh vlastního hybridní přímé závitem a nepřímé závitem závitové-interpretovaný jazyk, který, na rozdíl od jiných TIL, umožňuje zapuštění RPL ‚objekty‘ do „runstream " tj. Proud adres, přes který postupuje ukazatel tlumočníka. „Objekt“ RPL lze považovat za speciální datový typ, jehož struktura v paměti obsahuje adresu „prologu objektu“ na začátku objektu a poté následují data nebo spustitelný kód. Objektový prolog určuje, jak má být tělo objektu provedeno nebo zpracováno. Pomocí "vnitřní smyčky RPL", kterou vynalezl a publikoval (a patentoval) William C. Wickes v roce 1986 a publikoval ji v "Programming Environments", Institute for Applied Forth Research, Inc., 1988, následuje provedení takto:

  1. Dereference IP (ukazatel instrukce) a uložte jej do O (aktuální objektový ukazatel)
  2. Zvyšte IP o délku jednoho ukazatele adresy
  3. Dereference O a uložte její adresu do O_1 (toto je druhá úroveň přesměrování)
  4. Přeneste řízení na další ukazatel nebo vložený objekt nastavením počítače (čítače programů) na O_1 plus jeden ukazatel adresy
  5. Vraťte se ke kroku 1

Přesněji to může představovat: 

    O  = [I]
    I  = I + Δ
    PC = [O] + Δ

Kde výše, O je aktuální ukazatel objektu, I je ukazatel tlumočníka, Δ je délka jednoho adresního slova a operátor „[]“ znamená „dereference“.

Když je ovládací prvek přenesen na ukazatel objektu nebo vložený objekt, provádění pokračuje následujícím způsobem: 

PROLOG -> PROLOG ( The prolog address at the start of the prolog code points to itself )
    IF O + Δ =/= PC
    THEN GOTO INDIRECT ( Test for direct execution )
        O = I - Δ ( Correct O to point to start of embedded object )
        I = I + α ( Correct I to point after embedded object where α is the length of the object )
    INDIRECT ( rest of prolog )

Na mikroprocesorech Saturn společnosti HP, které používají RPL, existuje třetí úroveň nepřímosti umožněná architektonickým / programovacím trikem, který umožňuje rychlejší provedení.

Pobočky

U všech tlumočníků pobočka jednoduše změní ukazatel vlákna ( ip) na jinou adresu ve vlákně. Podmíněnou větev jump-if-zero, která skočí pouze v případě, že je hodnota top-of-stack nulová, by mohla být implementována, jak je uvedeno níže. Tento příklad používá verzi přímého vlákna s integrovanými parametry, takže &thread[123]řádek je místo určení, kam se má přeskočit, pokud je podmínka splněna, takže ji musíte přeskočit ( ip++), pokud není větev převzata. 

thread:
  ...
  &brz
  &thread[123]
  ...
brz:
  when_true_ip = *ip++ // Get destination address for branch
  if (*--sp == 0)      // Pop/Consume top of stack and check if it's zero
    ip = when_true_ip
  jump *ip++

Společné vybavení

Oddělení datových a návratových zásobníků ve stroji eliminuje velké množství kódu pro správu zásobníků, čímž se podstatně zmenšuje velikost závitového kódu. Princip dual-stack vznikl třikrát nezávisle: pro velké systémy Burroughs , Forth a PostScript . Používá se v některých virtuálních strojích Java .

Ve virtuálním počítači se závitem jsou často přítomny tři registry . Další existuje pro předávání dat mezi podprogramy ('slova'). Tyto jsou:

Vláknové virtuální stroje , jako jsou implementace Forthu, mají často v jádru jednoduchý virtuální stroj, který se skládá ze tří primitiv . Ty jsou:

  1. hnízdo , nazývané také docol
  2. unnest , nebo semi_s (; s)
  3. další

Ve virtuálním počítači s nepřímým vláknem, zde uvedeném, jsou tyto operace: 

 next:
   *ip++ -> w
   jump **w++
 nest:
   ip -> *rp++
   w -> ip
   next
 unnest:
   *--rp -> ip
   next

Toto je možná nejjednodušší a nejrychlejší tlumočník nebo virtuální stroj.

Viz také

Poznámky

Reference

externí odkazy