Gevindskode - Threaded code

For ikke at forveksle med programmering med flere tråde .

I datalogi er gevindkode en programmeringsteknik, hvor koden har en form, der i det væsentlige udelukkende består af opkald til underrutiner . Det bruges ofte i kompilatorer , som kan generere kode i denne form eller selv blive implementeret i denne form. Koden kan behandles af en tolk eller det kan simpelthen være en sekvens af maskine kode call instruktioner.

Gevindskode har bedre densitet end kode, der genereres ved alternative generationsteknikker og ved alternative opkaldskonventioner . I cachelagrede arkitekturer kan det køre lidt langsommere. Men et program, der er lille nok til at passe ind i en computer-processor 's cache kan køre hurtigere end et større program, der lider mange cache misses . Små programmer kan også være hurtigere ved trådskift, når andre programmer har fyldt cachen.

Gevindskode er bedst kendt for dens anvendelse i mange kompilatorer af programmeringssprog , såsom Forth , mange implementeringer af BASIC , nogle implementeringer af COBOL , tidlige versioner af B og andre sprog til små minicomputere og til amatørradiosatellitter .

Historie

Den almindelige måde at lave computerprogrammer på er at bruge en kompilator til at oversætte kildekode (skrevet på et symbolsk sprog ) til maskinkode . Den resulterende eksekverbare fil er typisk hurtig, men fordi den er specifik for en hardwareplatform , er den ikke bærbar. En anden tilgang er at generere instruktioner til en virtuel maskine og bruge en tolk på hver hardware -platform. Tolken instantinerer det virtuelle maskinmiljø og udfører instruktionerne. Det er således kun tolken, der skal kompileres.

Tidlige computere havde relativt lidt hukommelse. For eksempel havde de fleste Data General Nova , IBM 1130 og mange af de første mikrocomputere kun 4 kB RAM installeret. Derfor blev der brugt meget tid på at forsøge at finde måder at reducere et programs størrelse til at passe ind i den tilgængelige hukommelse.

En løsning er at bruge en tolk, der læser symbolsproget lidt ad gangen, og kalder funktioner til at udføre handlingerne. Da kildekoden typisk er meget tættere end den resulterende maskinkode, kan dette reducere den samlede hukommelsesforbrug. Dette var grunden til, at Microsoft BASIC er en tolk: dens egen kode skulle dele 4 kB hukommelse på maskiner som Altair 8800 med brugerens kildekode. En kompilator oversætter fra et kildesprog til maskinkode, så kompilatoren, kilden og output skal alle være i hukommelsen på samme tid. I en tolk er der ingen output. Kode oprettes en linje ad gangen, udføres og kasseres derefter.

Gevindskode er en formateringsstil for kompileret kode, der minimerer brug af hukommelse. I stedet for at skrive ud alle trin i en operation på sit hver forekomst i programmet, som var almindeligt i makro montører for eksempel, compileren skriver hver fælles stykke kode ind i en subrutine. Hver bit findes således kun ét sted i hukommelsen (se " Gentag dig ikke "). Programmet på topniveau i disse programmer kan ikke bestå af andet end subrutineopkald. Mange af disse subrutiner består til gengæld også af andet end underprogrammeanrop på lavere niveau.

Mainframes og nogle tidlige mikroprocessorer som RCA 1802 krævede flere instruktioner for at kalde en underprogram. I applikationen på topniveau og i mange underrutiner gentages denne sekvens konstant, idet kun underprogramadressen ændres fra et opkald til det næste. Det betyder, at et program bestående af mange funktionsopkald også kan have betydelige mængder gentagen kode.

For at løse dette brugte trådede kodesystemer pseudokode til at repræsentere funktionsopkald i en enkelt operatør. På løbetid ville en lille "tolk" scanne over koden på øverste niveau, udtrække underrutinens adresse i hukommelsen og kalde den. I andre systemer er det samme grundlæggende koncept implementeret som en filialtabel , forsendelsestabel eller virtuel metodetabel , der alle består af en tabel med underrutineadresser.

I løbet af 1970'erne brugte hardwaredesignere en betydelig indsats på at foretage subrutineopkald hurtigere og enklere. På de forbedrede designs bruges kun en enkelt instruktion til at kalde en underprogram, så brugen af ​​en pseudo-instruktion sparer ikke plads. Derudover er udførelsen af ​​disse opkald næsten fri for ekstra omkostninger. I dag, selvom næsten alle programmeringssprog fokuserer på at isolere kode i underrutiner, gør de det for kodens klarhed og vedligeholdelse, ikke for at spare plads.

Gevindede kodesystemer sparer plads ved at erstatte listen over funktionsopkald, hvor kun underrutinadressen ændres fra det ene opkald til det næste, med en liste over eksekveringstokener, som i det væsentlige er funktionsopkald med opkaldsopkoderne fjernet og efterlader kun en liste over adresser.

I årenes løb har programmører skabt mange variationer af den "tolk" eller "lille vælger". Den særlige adresse på listen over adresser kan udtrækkes ved hjælp af et indeks, et generelt register eller en markør . Adresserne kan være direkte eller indirekte, sammenhængende eller ikke-sammenhængende (forbundet med pointer), relative eller absolutte, løst på kompileringstidspunktet eller dynamisk bygget. Ingen enkelt variation er "bedst" ​​til alle situationer.

Udvikling

For at spare plads pressede programmerere listerne over subrutineopkald ind i enkle lister med underrutineadresser og brugte en lille sløjfe til at kalde hver subrutine efter tur. For eksempel bruger følgende pseudokode denne teknik til at tilføje to tal A og B. I eksemplet er listen mærket tråd, og en variabel ip (Instruction Pointer) sporer vores sted på listen. En anden variabel sp (Stack Pointer) indeholder en adresse andre steder i hukommelsen, der er tilgængelig til midlertidigt at holde en værdi. 

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


Opkaldsløkken på toper så enkel, at den kan gentages inline i slutningen af ​​hver underprogram. Kontrol springer nu en gang, fra slutningen af ​​en underprogram til starten af ​​en anden, i stedet for at hoppe to gange via top. For eksempel: 

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++

Dette kaldes direct threaded code (DTC). Selvom teknikken er ældre, er den første udbredte brug af udtrykket "gevindskåret kode" sandsynligvis James R. Bells artikel fra 1973 "Trådskode".

I 1970 opfandt Charles H. Moore et mere kompakt arrangement, indirekte gevindkode (ITC), til hans Forth virtuelle maskine. Moore nåede frem til dette arrangement, fordi Nova minicomputere havde en indirekte bit i hver adresse, hvilket gjorde ITC let og hurtigt. Senere sagde han, at han fandt det så bekvemt, at han forplantede det til alle senere Forth -designs.

I dag genererer nogle Forth-kompilatorer kode med direkte gevind, mens andre genererer kode med indirekte gevind. Eksekverbare filer handler på samme måde.

Gevindmodeller

Praktisk talt al eksekverbar gevindskåret kode bruger en eller anden af ​​disse metoder til påkaldelse af underrutiner (hver metode kaldes en "trådningsmodel").

Direkte trådning

Adresser i tråden er adresserne på maskinsprog. Denne formular er enkel, men kan have omkostninger, fordi tråden kun består af maskinadresser, så alle yderligere parametre skal indlæses indirekte fra hukommelsen. Nogle Forth-systemer producerer kode med direkte gevind. På mange maskiner er direkte-threading hurtigere end subrutine-threading (se reference nedenfor).

Et eksempel på en stakmaskine kan udføre sekvensen "skub A, skub B, tilføj". Det kan oversættes til følgende tråd og rutiner, hvor ipinitialiseres til adressen mærket thread(dvs. adressen, hvor der &pushAer gemt). 

#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++

Alternativt kan operander være inkluderet i tråden. Dette kan fjerne en vis indirektion, der er nødvendig ovenfor, men gør tråden større: 

#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++

Indirekte trådning

Indirekte trådning bruger pointer til steder, der igen peger på maskinkode. Den indirekte markør kan efterfølges af operander, der er gemt i den indirekte "blok" i stedet for at gemme dem gentagne gange i tråden. Således er indirekte kode ofte mere kompakt end kode med direkte gevind. Indirektionen gør det typisk langsommere, men normalt stadig hurtigere end bytecode -tolke. Hvor behandleroperanderne inkluderer både værdier og typer, kan pladsbesparelserne i forhold til kode med direkte gevind være betydelige. Ældre FORTH-systemer producerer typisk kode med indirekte gevind.

For eksempel, hvis målet er at udføre "skub A, skub B, tilføj", kan følgende blive brugt. Her ipinitialiseres til adressering &thread, hvert kodefragment ( push, add) findes ved dobbeltindirekte gennem ipog en indirekte blok; og eventuelle operander til fragmentet findes i den indirekte blok efter fragmentets adresse. Dette kræver, at den aktuelle underrutine holdes inde ip, i modsætning til alle tidligere eksempler, hvor den indeholdt den næste underprogram, der skal kaldes. 

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)

Underrutine gevindskæring

Den såkaldte "subroutine-threaded code" (også "call-threaded code") består af en række maskinsprogede "call" -instruktioner (eller adresser til funktioner til "call", i modsætning til direkte threading's brug af "jump" ). Tidlige kompilatorer til ALGOL , Fortran, Cobol og nogle Forth-systemer producerede ofte underrutine-gevindkode. Koden i mange af disse systemer opererede på en last-in-first-out (LIFO) stabel med operander, som kompilatorteorien var veludviklet til. De fleste moderne processorer har særlig hardware -understøttelse til underrutine "opkald" og "retur" instruktioner, så omkostningerne til en ekstra maskininstruktion pr. Forsendelse reduceres noget.

Anton Ertl, Gforth- kompilatorens medskabere, udtalte, at "i modsætning til populære myter er underrutinetråd normalt langsommere end direkte trådning". Ertls seneste test viser imidlertid, at underrutine -trådning er hurtigere end direkte trådning i 15 ud af 25 testcases. Mere specifikt fandt han ud af, at direkte trådning er den hurtigste gevindmodel på Xeon-, Opteron- og Athlon -processorer, indirekte trådning er hurtigste på Pentium M -processorer, og subroutine -trådning er hurtigste på Pentium 4, Pentium III og PPC -processorer.

Som et eksempel på opkaldstrådning for "skub A, skub B, tilføj": 

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

Trækning af token

Token-threaded kode implementerer tråden som en liste over indekser i en operationstabel; indeksbredden er naturligvis valgt til at være så lille som muligt for densitet og effektivitet. 1 byte / 8-bit er det naturlige valg for nem programmering, men mindre størrelser som 4-bit eller større som 12 eller 16 bit kan bruges afhængigt af antallet af understøttede operationer. Så længe indeksbredden er valgt til at være smallere end en maskinpeger, vil den naturligvis være mere kompakt end de andre gevindtyper uden særlig særlig indsats fra programmøren. Det er normalt halv til tre fjerdedele af størrelsen på andre tråde, der selv er en fjerdedel til en ottendedel af størrelsen på ikke-gevindskåret kode. Tabellens tip kan enten være indirekte eller direkte. Nogle Forth-kompilatorer producerer token-threaded kode. Nogle programmører betragter " p-koden ", der genereres af nogle Pascal- kompilatorer, samt bytecodes, der bruges af .NET , Java , BASIC og nogle C- kompilatorer, som token-threading.

Historisk set er en almindelig tilgang bytecode , der typisk bruger 8-bit opcodes med en stakbaseret virtuel maskine. Den arketypiske bytekode fortolkeren er kendt som en "afkode og afsendelse fortolker" og følger formen: 

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

Hvis den virtuelle maskine kun bruger byte-størrelse instruktioner, decode()er simpelthen en hentning fra thread, men ofte er der almindeligt anvendte 1-byte instruktioner plus nogle mindre almindelige multibyte instruktioner (se kompleks instruktionssæt computer ), i hvilket tilfælde decode()er mere kompleks. Afkodningen af ​​enkeltbyte -opcoder kan meget enkelt og effektivt håndteres af en filialtabel ved hjælp af opkoden direkte som et indeks.

For instruktioner, hvor de enkelte operationer er enkle, f.eks. "Push" og "add", er omkostningerne involveret i at beslutte, hvad der skal udføres større end omkostningerne ved faktisk at udføre det, så sådanne tolke er ofte meget langsommere end maskinkode. For mere komplekse ("sammensatte") instruktioner er overheadprocenten imidlertid proportionalt mindre signifikant.

Der er tidspunkter, hvor token-threaded kode nogle gange kan køre hurtigere end den tilsvarende maskinkode, når maskinkoden ender med at blive for stor til at passe i den fysiske CPU's L1-instruktionscache. Den højere kodetæthed for gevindskåret kode, især token-threaded kode, kan tillade, at den passer helt ind i L1-cachen, når den ellers ikke ville have undgået cache-thrashing. Trådkode bruger imidlertid både instruktionscache (til implementering af hver operation) såvel som datacache (for bytecode og tabeller) i modsætning til maskinkode, som kun bruger instruktionscache; dette betyder, at gevindskåret kode vil spise i budgettet for mængden af ​​data, der til enhver tid kan opbevares til behandling af CPU'en. Under alle omstændigheder, hvis det problem, der beregnes, indebærer at anvende et stort antal operationer på en lille mængde data, kan brug af gevindkode være en ideel optimering.

Huffman -trådning

Huffman -gevindkode består af lister over tokens gemt som Huffman -koder . En Huffman-kode er en række bit med variabel længde, der identificerer et unikt token. En tolk med Huffman-gevind lokaliserer underrutiner ved hjælp af en indekstabel eller et træ af pointer, der kan navigeres ved hjælp af Huffman-koden. Huffman-gevindkode er en af ​​de mest kompakte repræsentationer kendt for et computerprogram. Indekset og koderne vælges ved at måle hyppigheden af ​​opkald til hver underprogram i koden. Hyppige opkald får de korteste koder. Operationer med omtrent lige store frekvenser får koder med næsten lige bitlængder. De fleste Huffman-gevindsystemer er blevet implementeret som Forth-systemer med direkte gevind og bruges til at pakke store mængder langsomt kørende kode i små, billige mikrokontrollere . De fleste publicerede anvendelser har været i smartkort, legetøj, lommeregnere og ure. Den bitorienterede tokeniserede kode, der bruges i PBASIC, kan ses som en slags Huffman- gevindkode .

Mindre brugt gevind

Et eksempel er strengtrådning, hvor operationer identificeres ved strenge, normalt slået op af en hashtabel. Dette blev brugt i Charles H. Moores tidligste Forth-implementeringer og i University of Illinois 'eksperimentelle hardware-fortolkede computersprog. Det bruges også i Bashforth .

RPL

HP 's RPL , der først blev introduceret i HP-18C- lommeregneren i 1986, er en type proprietær hybrid direkte-gevind og indirekte-gevind-fortolket sprog, der i modsætning til andre TIL'er tillader indlejring af RPL "objekter" i "runstream" "dvs. Adressestrømmen, gennem hvilken tolkemarkøren går videre. Et RPL "objekt" kan betragtes som en særlig datatype, hvis struktur i hukommelsen indeholder en adresse til en "objektprolog" ved objektets start, og derefter følger data eller eksekverbar kode. Objektprologen bestemmer, hvordan objektets krop skal udføres eller behandles. Ved hjælp af "RPL inner loop", som blev opfundet og udgivet (og patenteret) af William C. Wickes i 1986 og offentliggjort i "Programming Environments", Institute for Applied Forth Research, Inc., 1988, følger udførelsen således:

  1. Ændrer IP (instruktionsmarkøren), og gem den i O (nuværende objektmarkør)
  2. Forøg IP'en med længden af ​​en adressemarkør
  3. Dereference O og gem dens adresse i O_1 (dette er det andet niveau af indirekte)
  4. Overfør kontrol til næste markør eller indlejret objekt ved at indstille pc'en (programtælleren) til O_1 plus en adressemarkør
  5. Gå tilbage til trin 1

Dette kan repræsenteres mere præcist ved: 

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

Hvor ovenfor, O er den aktuelle objektmarkør, I er tolkemarkøren, Δ er længden af ​​et adresseord og "[]" -operatoren står for "dereference".

Når kontrol overføres til en objektmarkør eller et integreret objekt, fortsætter udførelsen som følger: 

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 )

På HP's Saturn -mikroprocessorer, der bruger RPL, er der et tredje niveau af indirektion muliggjort af et arkitektonisk / programmeringstrick, der muliggør hurtigere udførelse.

Grene

I alle tolke ændrer en gren simpelthen trådmarkøren ( ip) til en anden adresse i tråden. En betinget spring-hvis-nul-gren, der kun springer, hvis værdien i toppen af ​​stakken er nul, kan implementeres som vist nedenfor. Dette eksempel bruger den integrerede parameterversion af direkte trådning, så &thread[123]linjen er destinationen for, hvor der skal springes, hvis betingelsen er sand, så den skal springes over ( ip++), hvis grenen ikke tages. 

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++

Fælles faciliteter

Adskillelse af data- og returstablerne i en maskine eliminerer en stor mængde stakkestyringskode, hvilket reducerer størrelsen af ​​den trådede kode væsentligt. Dual-stack-princippet opstod tre gange uafhængigt: for Burroughs store systemer , Forth og PostScript . Det bruges i nogle virtuelle Java -maskiner .

Tre registre er ofte til stede i en gevindskåret virtuel maskine. En anden findes for at videregive data mellem underrutiner ('ord'). Disse er:

  • ip eller i ( instruktionsmarkør ) på den virtuelle maskine (må ikke forveksles med programtælleren for den underliggende hardware, der implementerer VM)
  • w (arbejdsmarkør)
  • rp eller r (return stack stack )
  • sp eller s ( parameter stack pointer til at overføre parametre mellem ord)

Ofte har gevindskårne virtuelle maskiner , såsom implementeringer af Forth, en simpel virtuel maskine på hjerte, der består af tre primitiver . De er:

  1. rede , også kaldet docol
  2. unnest eller semi_s (; s)
  3. Næste

I en indirekte trådet virtuel maskine, den her angivne, er operationerne: 

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

Dette er måske den enkleste og hurtigste tolk eller virtuelle maskine.

Se også

Noter

Referencer

eksterne links