Codi enfilat

De Viquipèdia
Dreceres ràpides: navegació, cerca

En ciències de la computació, el terme codi enfilat es refereix a una tècnica d'implementació del compilador on el codi generat té una forma que essencialment consisteix enterament en crides a subrutina s. El codi pot ser processat per un intèrpret, o simplement pot ser una seqüència d'instruccions de crides a codi de màquina.

Una dels principals avantatges del codi enfilat és que és molt compacte, comparat al codi generat per tècniques alternatives de generació del codi i de convenció de crides. Aquest avantatge usualment ve a costa d'una velocitat d'execució lleugerament més lenta (usualment amb prou feines una sola instrucció de màquina). No obstant això, de vegades hi ha un efecte sinergètic - de vegades un codi més compacte és més petit i significativament més ràpid que el codi no enfilat. [1] Un programa suficientment petit per cabre enterament en la memòria d'accés aleatori pot córrer més ràpid que un programa menys compacte en l'espai d'intercanvi que requereix un constant accés mecànic de la unitat de disc, encara que pateixi de la sobrecàrrega en la interpretació del codi enfilat. Similarment, un programa prou petit per cabre enterament en el memòria cau de l'processador de l'ordinador pot córrer més ràpid que un programa menys compacte que sofreixi falles de caché constants.

El codi enfilat és ben conegut com la tècnica d'implementació comunament usada en el llenguatge de programació Forth. També va ser usat en les versions primerenques del llenguatge de programació B, així com en moltes implementacions de BASIC, i algunes implementacions de COBOL i d'altres llenguatges per a petits microcomputadors.

Història que va portar al codi enfilat[modifica | modifica el codi]

La manera comuna de fer programes d'ordinador és usant un compilador per "traduir" un programa escrit en una cert llenguatge simbòlic al codi de màquina. El codi és típicament ràpid però no és portable, ja que el codi binari executable és dissenyat per una plataforma de maquinari específica. Un acostament diferent usa un conjunt d'instruccions d'una màquina virtual - que no té una destinació particular de maquinari. Un intèrpret l'executa en cada nou maquinari de destinació.

Els computadors primerencs tenien relativament poca memòria. Per exemple, la majoria dels Data General Nova, IBM 1130, i moltes computadors Apple II tenien solament 4 k paraules de memòria RAM instal·lada. Conseqüentment es passava molt temps intentant trobar formes de reduir la grandària dels programes de tal manera que poguessin cabre en la memòria disponible. Alhora, els computadors eren relativament lents, així que la interpretació simple era perceptiblement molt més lenta que executar el codi de màquina.

En comptes d'escriure cada pas d'una operació en cada part del programa on era necessària, els programadors estalviaven memòria escrivint cada pas de tals operacions una sola vegada i posant-lo en una subrutina (veure "no et repeteixis").

Aquest procés - la refactorització de codi - és usat avui, encara que per diverses raons. En aquests programes, l'aplicació del nivell superior pot consistir de res més que crides a subrutines. Al seu torn, moltes d'aquestes subrutines, també no consisteixen sols que crides a subrutines de nivell inferior.

Els mainframe es i alguns microprocessadors primerencs tals com el RCA 1802 requerien diverses instruccions per cridar a una subrutina. En l'aplicació de nivell superior i en moltes subrutines, aquesta seqüència és constantment repetida, només canviant l'adreça de la subrutina des d'una crida a la següent. Usant la memòria per emmagatzemar les mateixes instruccions repetidament era un desaprofitament.

La resposta simple va ser una taula de salts (és a dir una taula consistint només en les adreces contigües de les subrutines - usualment extretes usant un índex, un registre de propòsits generals o un punter). Les adreces poden ser directes o indirectes, contigües o no contigües (encadenades per punters), relatives o absolutes, resoltes en de temps de compilació o construïdes dinàmicament - però el programa es converteix en una llista de punts d'entrada al codi real a ser executat. Aquesta tècnica "s'ha reinventat" amb els noms de "codi enfilat", "taula de despatx" o "taula de mètode virtual" - totes aquestes tècniques omplen propòsits similars.

Desenvolupament del codi enfilat[modifica | modifica el codi]

Per estalviar espai, els programadors van esprémer les llistes codis de crides a subrutines i les van convertir en simples llistes amb solament les adreces de les subrutines, i van usar un petit loop per cridar a cada subrutina una per una. Per exemple:

start: thread: pushA: * sp++= A
 tp = & thread & pushA jump top
top: & pushB pushB: * sp++= B
 jump * tp++& add jump top
 ... add: * sp++= * - sp+* - sp
 jump top

En aquest cas, la descodificació dels bytecodes es realitza una sola vegada, durant la compilació o la càrrega de programa, així que no és repetida cada vegada que una instrucció és executada. Això pot estalviar molt temps i espai quan la sobrecàrrega per la descodificació (decode) i l'enviar (dispath) és gran comparat al cost de l'execució.

Observeu, però, que les direccions en thread per & pushA , & pushB , etc., Tenen dos o més byte s, comparats a típicament un byte, per l'intèrpret de descodificar (decode) i enviar (dispath) descrit a dalt. En general les instruccions per a un intèrpret de decodificar i enviar poden ser de qualsevol mida. Com a exemple, un intèrpret de descodificar i enviar per simular un Intel Pentium descodifica les instruccions amb un rang d'1 a 16 bytes. No obstant això, els sistemes de bytecode trien típicament codis d'1 byte per a les operacions més comuns. Així, el enfilat sovint té un cost d'espai més alt que els bytecodes. En la majoria dels usos, la reducció en cost de descodificar compensa l'augment en cost d'espai.

Observeu també que mentre que els bytecodes són nominalment independents de la màquina, el format i el valor dels punters en el enfilat generalment depenen de la màquina destí que està executant a l'intèrpret. Així, un intèrpret pot carregar un programa bytecode portable, descodificar els bytecodes per generar codi enfilat independent de la plataforma, després executar el codi enfilat sense referència addicional als bytecodes.

El loop és simple, així que està duplicat en cada handler, remenant jump top de la llista d'instruccions de màquina necessàries per executar cada instrucció de l'intèrpret. Com a exemple:

start: thread: pushA: * sp++= A
 tp = thread & pushA jump * tp++
 jump * tp++& pushB pushB: * sp++= B
 & Add jump * tp++
 ... add: * sp++= * - sp+* - sp
 jump * tp++

Això es diu codi enfilat directe (DTC). Encara que la tècnica sigui més vella, el primer ús extensament circulat del terme "codi enfilat" és probablement l'article "codi enfilat" de Bell de 1973. [2]

El 1970, Charles H. Moore va inventar una notació més compacta per a la seva màquina virtual Forth: el codi enfilat indirecte (ITC). Originalment, Moore va inventar això perquè era fàcil i ràpid en els miniordinadors de NOVA, que tenien un bit d'indirecció en cada direcció. Moore va dir (en comentaris publicats en l'edició de la revista Byte sobre Forth) que ell va trobar això tan convenient que ho va propagar en tots els dissenys Forth posteriors.

Alguns compiladors Forth compilen els programes Forth en codi enfilat directe, mentre que altres fan codi enfilat indirecte. Els programes actuen igual de qualsevol manera.

Models d'enfilat[modifica | modifica el codi]

Pràcticament tot el codi enfilat executable usa un o altre d'aquests mètodes per invocar subrutines (cada mètode és anomenat un "model d'enfilat").

Enfilat directe[modifica | modifica el codi]

Les adreces en el enfilat són les adreces del llenguatge de màquina. Aquesta forma és simple, però pot tenir sobrecàrregues perquè l'enfilat consisteix solament d'adreces de màquina, així que tots els altres paràmetres han de ser carregats indirectament des de la memòria. Alguns sistemes Forth produeixen codi enfilat directe. En moltes màquines l'enfilat directe és més ràpid que el enfilat de subrutina (veure la referència a baix).

Com exemple, màquina de pila pot executar la seqüència "push A, push B, add". Això pot ser traduït a l'enfilat i rutines següents, on el tp és inicialitzat apuntant cap a la direcció de & thread .

thread: pushA: * sp++= A pushB: * sp++= B add: * sp++= * - sp+* - sp
 & PushA jump * tp++jump * tp++jump * tp++
 & PushB
 & Add
 ...

Alternativament, els operands poden estar inclosos en el enfilat. Això pot remoure alguna indirección necessària a dalt, però fa el enfilat més gran:

thread: push: * sp++= * tp++add: * sp++= * - sp+* - sp
 & Push jump * tp++jump * tp++
 & A
 & Push
 & B
 & Add

Enfilat indirecte[modifica | modifica el codi]

El enfilat indirecte usa punters que apunten cap a localitzacions que al seu torn apunten al codi de màquina. El punter indirecte pot ser seguit pels operands que són emmagatzemats en el "bloc" indirecte en comptes d'estar emmagatzemats repetidament en el enfilat. Així, el codi indirecte és sovint més compacte que el codi enfilat directe, però la indirecció típicament també ho fa més lenta, encara que usualment encara més ràpida que els intèrprets de bytecode. On els operands de l'handler inclouen tant valors com tipus, els estalvis d'espai sobre el codi enfilat directe poden ser significatius. Els sistemes Forth més antics produïen típicament codi enfilat indirecte.

Com a exemple, si la meta és executar el "psuh A, push B, add", el següent pot ser usat. Aquí, el tp és inicialitzat apuntant a l'adreça & thread, cada fragment del codi ( push , add ) és trobat per doble indirección mitjançant del tp , i els operands per a cada fragment de codi són trobats en el primer nivell d'indirecció seguint la direcció del fragment.

thread: i_pushA: push: add:
 & I_pushA & push * sp++= * (* tp+1) * sp++= * - sp+* - sp
 & I_pushB & A jump * (* tp++) jump * (* tp++)
 & I_add i_pushB:
 & Push
 & B
 i_add:
 & Add

Enfilat de subrutina[modifica | modifica el codi]

El "codi enfilat de subrutina" (també anomenat "codi enfilat de crida") consisteix en una sèrie d'instruccions "call" en llenguatge de màquina (o només les adreces de les funcions "call", en oposició al enfilat directe el qual usa "jump"). Els compiladors primerencs per al ALGOL, FORTRAN, COBOL i alguns sistemes Forth van produir sovint codi enfilat de subrutina. El codi en molts d'aquests sistemes operava una pila d'operands LIFO (last-in-firs-out), que tenia una ben desenvolupada teoria del compilador. La majoria dels processadors moderns tenen suport especial del maquinari per a les subrutines amb les instruccions "call" i "return", així que la sobrecàrrega d'una instrucció de màquina addicional per enviament és disminuïda, però segons mesuraments d'Antón Ertl, "en contrast amb els mites populars, el enfilat de subrutina és usualment més lent que el enfilat directe ". [3] Proves més recents d'Ertl demostren que el enfilat directe és el model d'enfilat més ràpid en els processadors Xeon, Opteron, i Athlon, mentre que el enfilat indirecte és el model d'enfilat més ràpid en processadors Pentium M, i el enfilat de subrutina és el model d'enfilat més ràpid en el Pentium 4, el Pentium III, i processadors PPC.

Com un exemple d'enfilat de crida, el "push A, push B, add":

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

Enfilat de token[modifica | modifica el codi]

El codi enfilat de token utilitza llistes d'índexs de 8 o 12 bits a una taula de punters. El codi enfilat de token és notablement compacte, sense molt esforç especial per un programador. Té usualment entre la meitat i tres quartes parts la grandària d'altres codis enfilats, els quals al seu torn tenen entre la quarta i la vuitena part de la mida del codi compilat. Els punters de la taula poden ser tant indirectes com directes. Alguns compiladors Forth produeixen codi enfilat de token. Alguns programadors consideren al "p-code" generat per alguns compiladors de Pascal, igual que els bytecodes usats per . NET, Java, BASIC, i alguns compiladors C, com enfilat de token.

Històricament, un acostament comú és el bytecode, que utilitza opcodes de 8 bits i, sovint, una màquina virtual basada en pila. Un interpretador típic és conegut com "decode and dispatch interpreter" i segueix la forma:

bytecode: top: pushA: pushB: add:
 0/* pushA */i = decode (VPC++) * sp++= A * sp++= B * sp++= * - sp+* - sp
 1/* pushB */addr = table [i] jump top jump top jump top
 2/* add */jump * addr

Si la màquina virtual usa només instruccions de la mida d'un byte, el decode () és simplement un ferch des del bytecode , però sovint hi ha instruccions comunes d'1 byte més instruccions menys comunes de múltiples bytes (veure CISC), en aquest cas, decode () és més complex. La decodificació de opcodes d'un sol byte pot ser molt simple i eficientment manejat per una taula de salts utilitzant el opcode directament com un índex.

Per, en les instruccions on les operacions individuals són simples, per exemple "push" i "add", la sobrecàrrega implicada a decidir el que s'ha d'executar és més gran que el cost real de l'execució, tals intèrprets són sovint molt més lents que el codi de màquina. No obstant això per a instruccions ("compostes") més complexes, el percentatge de sobrecàrrega és proporcionalment menys significatiu.

Enfilat de Huffman[modifica | modifica el codi]

El codi enfilat d'Huffman consisteix en llistes de codis Huffman. Un codi de Huffman és una cadena de bits de longitud variable usada per identificar un element únic. Un intèrpret d'enfilat d'Huffman localitza les subrutines usant una taula d'índex o un arbre de punters que poden ser navegats pel codi Huffman. El codi enfilat d'Huffman és una de les més compactes representacions conegudes per a un programa d'ordinador. Bàsicament l'índex i els codis estan organitzats mesurant la freqüència en què cada subrutina ocorre en el codi. A les crides freqüents se li donen els codis més curts. Les operacions amb freqüències aproximadament iguals se li donen codis amb longituds de bits gairebé iguals. La majoria dels sistemes enfilats d'Huffman han estat implementats com a sistemes Forth d'enfilat directe, i són usats per a grans quantitats de paquets de codi corrent lentament dins de petits i barats microcontroladors. La majoria de les aplicacions publicades han estat en joguines, calculadores o rellotges.

Enfilats menys usats[modifica | modifica el codi]

  • Enfilat de cadena, on les operacions són identificades per cadenes, usualment buscats en una taula hash. Això va ser usat per Charles H. Moore en les implementacions més primerenques de Forth i en el llenguatge de computadora experimental interpretat per maquinari de la Universitat Illinois. També s'utilitza en Bashforth.

Bifurcacions[modifica | modifica el codi]

Els exemples de dalt no mostren bifurcacions. Per a tots els intèrprets, una bifurcació canvia el punter de l'enfilat (a dalt indicat com tp ). Com a exemple, una bifurcació condicional quan el valor límit de la pila és zero pot ser codificada com segueix. Noteu que l' & thread [123] és la localització a saltar (jump), no la direcció d'un handler, i així que ha de ser saltada ( tp++) independentment de si la bifurcació és presa.

thread: brz:
 ... tmp = * tp++
 & Brz if (* sp++== 0)
 & Thread [123] tp = tmp
 ... jump * tp++

Amenitats comuns[modifica | modifica el codi]

A les màquines, la separació de les piles de dades i de retorn elimina molt del codi per al maneig de la pila, reduint substancialment la grandària del codi enfilat. El principi de la doble pila va ser originat tres vegades independentment: per als grans sistemes de Burroughs, el Forth i el PostScript, i és usat en algunes màquines virtuals de Java.

Tres registres estan sovint presents en una màquina virtual enfilada. Un altre existeix per passar dades entre les subrutines ("paraules"). Aquests són:

  • IP oi (punter d'instrucció); anomenat tp en els exemples de dalt
  • W (punter de treball)
  • Rp o r (punter de pila de retorn)
  • SP us (punter de pila de paràmetres, usat per passar paràmetres entre les paraules)

Sovint, les màquines virtuals enfilades tals com les implementacions de Forth tenen una màquina virtual simple en el seu cor, consistint en tres primitives. Aquestes són:

  • nest , també anomenat docol
  • unnest , o semi_s (; s)
  • next

En una màquina virtual d'enfilat indirecte, la qual està donada aquí, les operacions és:

next: (ip)+--> w; jmp (w)+
nest: ip --> - (rp); w --> ip; next
unnest: (rp)+--> ip; next

Aquest és potser l'intèrpret més simple i més ràpid o màquina virtual.

Referències[modifica | modifica el codi]

  1. Speed ​​of various interpreter dispatch techniques V2
  2. James R. Bell, "threaded Code", CACM, 1973, 16, 6, pp 370-372

Lectura addicional[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]