schroefdraad code - Threaded code

Niet te verwarren met multi-threaded programmeren .

In de informatica is threaded code een programmeertechniek waarbij de code een vorm heeft die in wezen volledig bestaat uit oproepen naar subroutines . Het wordt vaak gebruikt in compilers , die code in die vorm kunnen genereren of zelf in die vorm kunnen worden geïmplementeerd. De code kan worden verwerkt door een tolk of het kan eenvoudigweg een reeks machinecode- oproepinstructies zijn.

Threaded-code heeft een betere dichtheid dan code die wordt gegenereerd door alternatieve generatietechnieken en door alternatieve belconventies . In cache-architecturen kan het iets langzamer worden uitgevoerd. Een programma dat klein genoeg is om in de cache van een computerprocessor te passen, kan echter sneller werken dan een groter programma dat veel cache-missers heeft . Kleine programma's kunnen ook sneller van thread wisselen, wanneer andere programma's de cache hebben gevuld.

Threaded code is vooral bekend vanwege het gebruik in veel compilers van programmeertalen , zoals Forth , vele implementaties van BASIC , sommige implementaties van COBOL , vroege versies van B en andere talen voor kleine minicomputers en voor amateurradiosatellieten .

Geschiedenis

De gebruikelijke manier om computerprogramma's te maken is door een compiler te gebruiken om de broncode (geschreven in een symbolische taal ) te vertalen naar machinecode . Het resulterende uitvoerbare bestand is meestal snel, maar omdat het specifiek is voor een hardwareplatform , is het niet draagbaar. Een andere benadering is het genereren van instructies voor een virtuele machine en het gebruik van een interpreter op elk hardwareplatform. De interpreter instantieert de omgeving van de virtuele machine en voert de instructies uit. Dus alleen de interpreter moet worden gecompileerd.

Vroege computers hadden relatief weinig geheugen. De meeste Data General Nova , IBM 1130 en veel van de eerste microcomputers hadden bijvoorbeeld slechts 4 kB RAM geïnstalleerd. Bijgevolg werd er veel tijd besteed aan het zoeken naar manieren om de omvang van een programma te verkleinen, zodat het in het beschikbare geheugen zou passen.

Een oplossing is om een ​​tolk te gebruiken die de symbolische taal beetje bij beetje leest en functies aanroept om de acties uit te voeren. Omdat de broncode doorgaans veel dichter is dan de resulterende machinecode, kan dit het totale geheugengebruik verminderen. Dit was de reden waarom Microsoft BASIC een tolk is: zijn eigen code moest het 4 kB geheugen van machines als de Altair 8800 delen met de broncode van de gebruiker. Een compiler vertaalt van een brontaal naar machinecode, dus de compiler, de bron en de uitvoer moeten allemaal tegelijkertijd in het geheugen staan. In een tolk is er geen uitvoer. Code wordt regel voor regel gemaakt, uitgevoerd en vervolgens weggegooid.

Threaded-code is een opmaakstijl voor gecompileerde code die het geheugengebruik minimaliseert. In plaats van elke stap van een bewerking bij elke gebeurtenis in het programma weg te schrijven, zoals bijvoorbeeld gebruikelijk was in macro-assemblers , schrijft de compiler elk gemeenschappelijk stukje code in een subroutine. Elk bit bestaat dus maar op één plaats in het geheugen (zie " Herhaal jezelf niet "). De toepassing op het hoogste niveau in deze programma's kan bestaan ​​uit niets anders dan subroutine-aanroepen. Veel van deze subroutines bestaan ​​op hun beurt ook uit niets anders dan subroutine-aanroepen op een lager niveau.

Mainframes en sommige vroege microprocessors zoals de RCA 1802 vereisten verschillende instructies om een ​​subroutine aan te roepen. In de toepassing op het hoogste niveau en in veel subroutines wordt die reeks voortdurend herhaald, waarbij alleen het adres van de subroutine van de ene oproep naar de andere verandert. Dit betekent dat een programma dat uit veel functieaanroepen bestaat, ook aanzienlijke hoeveelheden herhaalde code kan hebben.

Om dit aan te pakken, gebruikten threaded-codesystemen pseudo-code om functieaanroepen in een enkele operator weer te geven. Tijdens runtime scant een kleine "interpreter" de code op het hoogste niveau, haalt het adres van de subroutine uit het geheugen en roept het op. In andere systemen wordt hetzelfde basisconcept geïmplementeerd als een vertakkingstabel , verzendtabel of virtuele methodetabel , die allemaal bestaan ​​uit een tabel met subroutineadressen.

In de jaren zeventig hebben hardware-ontwerpers veel moeite gedaan om subroutine-oproepen sneller en eenvoudiger te maken. Bij de verbeterde ontwerpen wordt slechts één instructie gebruikt om een ​​subroutine aan te roepen, dus het gebruik van een pseudo-instructie bespaart geen ruimte. Bovendien is de uitvoering van deze oproepen vrijwel vrij van extra overhead. Tegenwoordig, hoewel bijna alle programmeertalen zich richten op het isoleren van code in subroutines, doen ze dit voor de duidelijkheid en onderhoudbaarheid van de code, niet om ruimte te besparen.

Threaded-codesystemen besparen ruimte door die lijst met functieaanroepen, waar alleen het subroutine-adres van de ene aanroep naar de andere verandert, te vervangen door een lijst met uitvoeringstokens, die in wezen functieaanroepen zijn waarbij de aanroepcode(s) zijn verwijderd, waardoor alleen een lijst met adressen.

In de loop der jaren hebben programmeurs veel variaties gemaakt op die "interpreter" of "kleine selector". Het specifieke adres in de lijst met adressen kan worden geëxtraheerd met behulp van een index, register voor algemene doeleinden of aanwijzer . De adressen kunnen direct of indirect zijn, aaneengesloten of niet-aaneengesloten (gekoppeld door pointers), relatief of absoluut, opgelost tijdens het compileren of dynamisch gebouwd. Geen enkele variatie is "beste" voor alle situaties.

Ontwikkeling

Om ruimte te besparen, hebben programmeurs de lijsten met subroutine-aanroepen in eenvoudige lijsten met subroutine-adressen geperst en een kleine lus gebruikt om elke subroutine om de beurt aan te roepen. De volgende pseudocode gebruikt deze techniek bijvoorbeeld om twee getallen A en B toe te voegen. In het voorbeeld is de lijst gelabeld als thread en volgt een variabele ip (Instruction Pointer) onze plaats in de lijst. Een andere variabele sp (Stack Pointer) bevat een adres elders in het geheugen dat beschikbaar is om tijdelijk een waarde vast te houden. 

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


De oproeplus op topis zo eenvoudig dat deze aan het einde van elke subroutine inline kan worden herhaald. De besturing springt nu één keer, van het einde van een subroutine naar het begin van een andere, in plaats van twee keer te springen via top. Bijvoorbeeld: 

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

Dit wordt direct threaded code (DTC) genoemd. Hoewel de techniek ouder is, is het eerste wijdverbreide gebruik van de term "threaded code" waarschijnlijk het artikel "Threaded Code" van James R. Bell uit 1973.

In 1970 bedacht Charles H. Moore een compacter arrangement, indirecte threaded code (ITC), voor zijn Forth virtuele machine. Moore kwam tot deze regeling omdat Nova minicomputers een indirecte bit in elk adres hadden, wat ITC gemakkelijk en snel maakte. Later zei hij dat hij het zo handig vond dat hij het in alle latere Forth-ontwerpen uitbreidde.

Tegenwoordig genereren sommige Forth-compilers code met directe threads, terwijl andere code met indirecte threads genereren. De uitvoerbare bestanden werken hoe dan ook hetzelfde.

Modellen inrijgen

Vrijwel alle uitvoerbare threaded-code gebruikt een van deze methoden voor het aanroepen van subroutines (elke methode wordt een "threading-model" genoemd).

Direct inrijgen

Adressen in de thread zijn de adressen van machinetaal. Dit formulier is eenvoudig, maar kan overhead hebben omdat de thread alleen uit machine-adressen bestaat, dus alle verdere parameters moeten indirect uit het geheugen worden geladen. Sommige Forth-systemen produceren direct-threaded code. Op veel machines is direct draadsnijden sneller dan subroutine draadsnijden (zie onderstaande referentie).

Een voorbeeld van een stapelmachine kan de volgorde "push A, push B, add" uitvoeren. Dat kan worden vertaald naar de volgende thread en routines, waar ipwordt geïnitialiseerd naar het adres met het label thread(dwz het adres waar het &pushAis opgeslagen). 

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

Als alternatief kunnen operanden in de thread worden opgenomen. Dit kan enige indirectheid verwijderen die hierboven nodig is, maar maakt de draad groter: 

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

Indirect draadsnijden

Indirecte threading maakt gebruik van verwijzingen naar locaties die op hun beurt verwijzen naar machinecode. De indirecte aanwijzer kan worden gevolgd door operanden die zijn opgeslagen in het indirecte "blok" in plaats van ze herhaaldelijk in de thread op te slaan. Indirecte code is dus vaak compacter dan direct-threaded code. De indirecte maakt het meestal langzamer, maar meestal nog steeds sneller dan bytecode-interpreters. Waar de handler-operanden zowel waarden als typen bevatten, kan de ruimtebesparing ten opzichte van direct-threaded code aanzienlijk zijn. Oudere FORTH-systemen produceren doorgaans code met indirecte threads.

Als het doel bijvoorbeeld is om "push A, push B, add" uit te voeren, kan het volgende worden gebruikt. Hier, ipgeïnitialiseerd om te adresseren &thread, wordt elk codefragment ( push, add) gevonden door dubbele indirecting door ipen een indirect blok; en alle operanden voor het fragment worden gevonden in het indirecte blok dat volgt op het adres van het fragment. Dit vereist dat de huidige subroutine in wordt gehouden ip, in tegenstelling tot alle voorgaande voorbeelden waar deze de volgende subroutine bevatte die moet worden aangeroepen. 

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)

Subroutine threading

Zogenaamde "subroutine-threaded code" (ook "call-threaded code") bestaat uit een reeks machinetaal "call" -instructies (of adressen van functies om te "callen", in tegenstelling tot het gebruik van "jump" door directe threading. ). Vroege compilers voor ALGOL , Fortran, Cobol en sommige Forth-systemen produceerden vaak code met subroutine-threads. De code in veel van deze systemen werkte op een last-in-first-out (LIFO)-stapel operanden, waarvoor de compilertheorie goed ontwikkeld was. De meeste moderne processors hebben speciale hardware-ondersteuning voor subroutine "call"- en "return"-instructies, zodat de overhead van één extra machine-instructie per verzending enigszins wordt verminderd.

Anton Ertl, de mede-maker van de Gforth- compiler, verklaarde dat "in tegenstelling tot populaire mythen, subroutine threading meestal langzamer is dan directe threading". Uit de meest recente tests van Ertl blijkt echter dat subroutine threading sneller is dan directe threading in 15 van de 25 testgevallen. Meer specifiek ontdekte hij dat directe threading het snelste threading-model is op Xeon-, Opteron- en Athlon-processors, indirecte threading het snelst is op Pentium M-processors en subroutine-threading het snelst is op Pentium 4-, Pentium III- en PPC-processors.

Als voorbeeld van gespreksthreading voor "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

Token inrijgen

Token-threaded code implementeert de thread als een lijst met indices in een tabel met bewerkingen; de indexbreedte is natuurlijk zo klein mogelijk gekozen voor dichtheid en efficiëntie. 1 byte / 8-bits is de natuurlijke keuze voor programmeergemak, maar kleinere formaten zoals 4-bits, of groter zoals 12 of 16 bits, kunnen worden gebruikt, afhankelijk van het aantal ondersteunde bewerkingen. Zolang de indexbreedte smaller wordt gekozen dan een machineaanwijzer, zal deze natuurlijk compacter zijn dan de andere draadsnijtypes zonder veel speciale inspanning van de programmeur. Het is gewoonlijk de helft tot driekwart van de grootte van andere threadings, die zelf een kwart tot een achtste zijn van de niet-threaded code. De aanwijzers van de tabel kunnen indirect of direct zijn. Sommige Forth-compilers produceren token-threaded code. Sommige programmeurs beschouwen de " p-code " die door sommige Pascal- compilers wordt gegenereerd , evenals de bytecodes die worden gebruikt door .NET , Java , BASIC en sommige C- compilers, als token-threading.

Historisch gezien is een veelgebruikte benadering bytecode , die doorgaans 8-bits opcodes gebruikt met een op stapels gebaseerde virtuele machine. De archetypische bytecode- interpreter staat bekend als een "decodeer- en verzendinterpreter" en volgt de vorm: 

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

Als de virtuele machine alleen instructies op byte-formaat gebruikt, decode()is dit eenvoudig een fetch van thread, maar vaak zijn er veelgebruikte 1-byte-instructies plus enkele minder gebruikelijke multibyte-instructies (zie complexe instructieset computer ), in welk geval decode()dit complexer is. Het decoderen van opcodes van één byte kan heel eenvoudig en efficiënt worden afgehandeld door een vertakkingstabel waarbij de opcode direct als index wordt gebruikt.

Voor instructies waarbij de afzonderlijke bewerkingen eenvoudig zijn, zoals "push" en "add", is de overhead die nodig is om te beslissen wat moet worden uitgevoerd groter dan de kosten om het daadwerkelijk uit te voeren, dus dergelijke interpreters zijn vaak veel langzamer dan machinecode. Voor complexere ("samengestelde") instructies is het overheadpercentage echter proportioneel minder significant.

Er zijn momenten waarop code met token-threads soms sneller kan worden uitgevoerd dan de equivalente machinecode, wanneer die machinecode uiteindelijk te groot wordt om in de L1-instructiecache van de fysieke CPU te passen. De hogere codedichtheid van threaded code, met name token-threaded code, kan het mogelijk maken om volledig in de L1-cache te passen wanneer deze anders niet zou hebben, waardoor cache-thrashing wordt vermeden. Echter, threaded code verbruikt zowel instructiecache (voor de implementatie van elke bewerking) als datacache (voor de bytecode en tabellen) in tegenstelling tot machinecode die alleen instructiecache verbruikt; dit betekent dat threaded-code het budget opslokt voor de hoeveelheid gegevens die op een bepaald moment door de CPU kan worden verwerkt. In elk geval, als het probleem dat wordt berekend het toepassen van een groot aantal bewerkingen op een kleine hoeveelheid gegevens inhoudt, kan het gebruik van threaded code een ideale optimalisatie zijn.

Huffman draadsnijden

Huffman-threaded-code bestaat uit lijsten met tokens die zijn opgeslagen als Huffman-codes . Een Huffman-code is een reeks bits met variabele lengte die een uniek token identificeert. Een Huffman-threaded interpreter lokaliseert subroutines met behulp van een indextabel of een boom met aanwijzers die kunnen worden genavigeerd door de Huffman-code. Huffman-threaded code is een van de meest compacte representaties die bekend is voor een computerprogramma. De index en codes worden gekozen door de frequentie van oproepen naar elke subroutine in de code te meten. Frequente oproepen krijgen de kortste codes. Bewerkingen met ongeveer gelijke frequenties krijgen codes met bijna gelijke bitlengtes. De meeste Huffman-threaded-systemen zijn geïmplementeerd als Forth-systemen met directe threads en worden gebruikt om grote hoeveelheden langzaam lopende code in kleine, goedkope microcontrollers te verpakken . De meeste gepubliceerde toepassingen zijn geweest in smartcards, speelgoed, rekenmachines en horloges. De bit-georiënteerde tokenized-code die in PBASIC wordt gebruikt, kan worden gezien als een soort Huffman-threaded code.

Minder gebruikte schroefdraad

Een voorbeeld is stringthreading, waarbij bewerkingen worden geïdentificeerd door strings, meestal opgezocht door een hashtabel. Dit werd gebruikt in Charles H. Moore's vroegste Forth-implementaties en in de experimentele hardware-geïnterpreteerde computertaal van de University of Illinois . Het wordt ook gebruikt in Bashforth .

RPL

HP 's RPL , voor het eerst geïntroduceerd in de HP-18C rekenmachine in 1986, is een soort propriëtaire hybride direct-threaded en indirect-threaded threaded-geïnterpreteerde taal die, in tegenstelling tot andere TIL's, het inbedden van RPL-"objecten" in de "runstream" mogelijk maakt. " dwz. De stroom van adressen waar de interpreter-aanwijzer doorheen gaat. Een RPL "object" kan worden gezien als een speciaal gegevenstype waarvan de structuur in het geheugen een adres bevat naar een "object proloog" aan het begin van het object, waarna gegevens of uitvoerbare code volgen. De objectprolog bepaalt hoe de body van het object moet worden uitgevoerd of verwerkt. Met behulp van de "RPL inner loop", die in 1986 werd uitgevonden en gepubliceerd (en gepatenteerd) door William C. Wickes en gepubliceerd in "Programming Environments", Institute for Applied Forth Research, Inc., 1988, volgt de uitvoering als volgt:

  1. Dereferentie het IP (instructiewijzer) en sla het op in O (huidige objectwijzer)
  2. Verhoog het IP-adres met de lengte van één adreswijzer
  3. Dereferentie O en het adres opslaan in O_1 (dit is het tweede niveau van indirectie)
  4. Breng de besturing over naar de volgende aanwijzer of ingesloten object door de pc (programmateller) in te stellen op O_1 plus één adreswijzer
  5. Ga terug naar stap 1

Dit kan nauwkeuriger worden weergegeven door: 

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

Waar hierboven, O de huidige objectaanwijzer is, is I de interpreteraanwijzer, is Δ de lengte van één adreswoord en staat de "[]"-operator voor "dereferentie".

Wanneer de besturing wordt overgedragen aan een objectaanwijzer of een ingesloten object, gaat de uitvoering als volgt verder: 

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 )

Op HP's Saturn- microprocessors die RPL gebruiken, is er een derde niveau van indirectheid mogelijk gemaakt door een architecturale / programmeertruc die een snellere uitvoering mogelijk maakt.

Takken

In alle interpreters verandert een vertakking eenvoudig de draadaanwijzer ( ip) in een ander adres in de draad. Een voorwaardelijke sprong-als-nul-tak die alleen springt als de top-of-stack-waarde nul is, kan worden geïmplementeerd zoals hieronder wordt getoond. In dit voorbeeld wordt de ingebedde parameterversie van direct threading gebruikt, dus de &thread[123]regel is de bestemming waarheen moet worden gesprongen als de voorwaarde waar is, dus deze moet worden overgeslagen ( ip++) als de vertakking niet wordt genomen. 

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

Gemeenschappelijke voorzieningen

Het scheiden van de gegevens en het retourneren van stapels in een machine elimineert een groot deel van de stapelbeheercode, waardoor de omvang van de schroefdraadcode aanzienlijk wordt verkleind. Het dual-stack principe is drie keer onafhankelijk ontstaan: voor Burroughs grote systemen , Forth en PostScript . Het wordt gebruikt in sommige virtuele Java-machines .

Drie registers zijn vaak aanwezig in een virtuele machine met schroefdraad. Een andere bestaat voor het doorgeven van gegevens tussen subroutines ('woorden'). Dit zijn:

  • ip of i ( instructiewijzer ) van de virtuele machine (niet te verwarren met de programmateller van de onderliggende hardware die de VM implementeert)
  • w (werkwijzer)
  • rp of r (return stack pointer)
  • sp of s ( parameter stack pointer voor het doorgeven van parameters tussen woorden)

Vaak hebben virtuele machines met threads , zoals implementaties van Forth, in wezen een eenvoudige virtuele machine, bestaande uit drie primitieven . Die zijn:

  1. nest , ook wel docol . genoemd
  2. unnest , of semi_s (;s)
  3. De volgende

In een virtuele machine met indirecte threads, degene die hier wordt gegeven, zijn de bewerkingen: 

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

Dit is misschien wel de eenvoudigste en snelste tolk of virtuele machine.

Zie ook

Opmerkingen:

Referenties

Externe links