Grenbord

I datorprogrammering är en grentabell eller hopptabell en metod för att överföra programkontroll ( grening ) till en annan del av ett program (eller ett annat program som kan ha laddats dynamiskt) med hjälp av en tabell med gren- eller hoppinstruktioner . Det är en form av flervägsgren . Grentabellkonstruktionen används ofta vid programmering i assemblerspråk men kan också genereras av kompilatorer , speciellt när man implementerar optimerade switch-satser vars värden är tätt packade.

Typiskt genomförande

En grentabell består av en seriell lista med ovillkorliga greninstruktioner som förgrenas till att använda en offset skapad genom att multiplicera ett sekventiellt index med instruktionslängden (antalet byte i minnet som upptas av varje greninstruktion). Den förlitar sig på det faktum att maskinkodsinstruktioner för förgrening har en fast längd och kan exekveras extremt effektivt av de flesta hårdvara, och är mest användbar när man hanterar rådatavärden som lätt kan konverteras till sekventiella indexvärden. Givet sådana data kan en grentabell vara extremt effektiv. Den består vanligtvis av följande 3 steg:

  1. valfri validering av indata för att säkerställa att den är acceptabel (detta kan ske utan kostnad som en del av nästa steg, om indata är en enkel byte och en 256 byte översättningstabell används för att direkt erhålla offset nedan). Dessutom, om det inte råder någon tvekan om värdena för ingången, kan detta steg utelämnas.
  2. omvandla data till en offset till grentabellen. Detta innebär vanligtvis att multiplicera eller skifta (effektivt multiplicera med en potens av 2) för att ta hänsyn till instruktionslängden. Om en statisk översättningstabell används kan denna multiplikation utföras manuellt eller av kompilatorn, utan någon körtidskostnad.
  3. förgrening till en adress som består av basadressen för förgreningstabellen plus den just genererade offseten. Detta involverar ibland ett tillägg av förskjutningen till programräknarregistret (såvida inte, i vissa instruktionsuppsättningar , greninstruktionen tillåter ett extra indexregister) . Denna slutliga adress pekar vanligtvis på en av en sekvens av ovillkorliga greninstruktioner, eller instruktionen omedelbart efter dem (sparar en post i tabellen).

Följande pseudokod illustrerar konceptet

                       
                             
                        
 
                  
                       
                       
      ...  validera  x  /* transformera x till 0 (ogiltig) eller 1,2,3, beroende på värde..) */  y  =  x  *  4  ;  /* multiplicera med greninstruktionens längd (t.ex. 4 ) */  goto  next  +  y  ;  /* förgrena sig till 'tabell' av greninstruktioner */  /* början av grentabell */  nästa  :  goto  codebad  ;  /* x= 0 (ogiltig) */  goto  codeone  ;  /* x= 1 */  goto  codetwo  ;  /* x= 2 */  ...  resten  av  grentabellen  codebad  :  /* hantera ogiltig indata *  /

Alternativ implementering med adresser

En annan metod för att implementera en förgreningstabell är med en uppsättning pekare från vilka den önskade funktionens adress hämtas . Ursprungligen känd som överföringsvektor , den här metoden är också mer nyligen känd under så olika namn som " utskickningstabell " eller " virtuell metodtabell " men utför i huvudsak exakt samma syfte. Denna pekarfunktionsmetod kan resultera i att en maskininstruktion sparas och undviker det indirekta hoppet (till en av greninstruktionerna).

Den resulterande listan med pekare till funktioner är nästan identisk med direkt gängad kod och liknar konceptuellt en kontrolltabell .

Den faktiska metoden som används för att implementera en grentabell är vanligtvis baserad på:

  • arkitekturen för processorn på vilken koden ska exekveras,
  • om det är ett sammanställt eller tolkat språk och
  • om sen bindning är inblandad eller inte.

Historia

Användning av filialtabeller och annan rådatakodning var vanligt under de första dagarna av datoranvändning när minnet var dyrt, processorerna var långsammare och kompakt datarepresentation och effektivt val av alternativ var viktigt. Nuförtiden används de fortfarande ofta i:

Fördelar

Fördelarna med grenbord inkluderar:

  • kompakt kodstruktur (trots upprepade grenopkoder)
  • reducerade källsatser (mot upprepade If- satser)
  • minskat krav på att testa returkoder individuellt (om de används på anropsplatsen för att fastställa efterföljande programflöde )
  • Algoritmisk och kodeffektivitet (data behöver bara kodas en gång och grentabellskoden är vanligtvis kompakt), och potentialen att uppnå höga datakomprimeringsförhållanden . Till exempel, när man komprimerar landsnamn till landskoder, kan en sträng som "Centralafrikanska republiken" komprimeras till ett enda index, vilket resulterar i stora besparingar – särskilt när strängen förekommer många gånger. Dessutom kan samma index användas för att komma åt relaterade data i separata tabeller, vilket minskar lagringskraven ytterligare.

För biblioteksfunktioner , där de kan refereras av ett heltal :

  • förbättra kompatibiliteten med efterföljande programvaruversioner. Om koden för en funktion och adressen till dess ingångspunkt ändras, behöver bara greninstruktionen i grentabellen justeras; applikationsprogram som kompilerats mot biblioteket eller för operativsystemet behöver inte modifieras.

Dessutom kan det ibland vara användbart att anropa funktioner efter nummer (indexet i tabellen) i vissa fall i normal applikationsprogrammering.

Nackdelar

  • Extra nivå av inriktning , vilket medför en vanligtvis liten prestationsträff.
  • Restriktioner i vissa programmeringsspråk, även om det vanligtvis finns alternativa sätt att implementera grundkonceptet med flervägsgrening.

Exempel

Ett enkelt exempel på användning av grentabeller i 8-bitars Microchip PIC- assemblyspråk är: 

              
               
                         
                         
                         

                    
           
            
         
         

 
     
     

 
  movf  INDEX  ,  W  ; Flytta indexvärdet till W (arbets)registret från minnet   addwf  PCL  ,  F  ; lägg till den i programräknaren.  Varje PIC-instruktion är en byte   ; så det finns inget behov av att utföra någon multiplikation.   ; De flesta arkitekturer kommer att omvandla indexet på något sätt tidigare   ; lägga till den i programräknaren.   bord  ; Grentabellen börjar här med denna etikett   goto  index_zero  ; var och en av dessa goto-instruktioner är en ovillkorlig gren   goto  index_one  ; av kod.   goto  index_two  goto  index_three  index_noll  ; Koden läggs till här för att utföra den åtgärd som krävs när INDEX = noll   returnerar  index_one  ...

Obs: den här koden fungerar bara om PCL < (tabell + index_last). För att säkerställa detta villkor kan vi använda ett "org"-direktiv. Och om GOTO (PIC18F till exempel) är 2 byte, begränsar detta antalet tabellposter till mindre än 128.

Hopptabellsexempel i C

Ett annat enkelt exempel, den här gången visar det ett hoppbord snarare än bara ett grenbord. Detta gör att programblock utanför den för närvarande aktiva proceduren/funktionen kan anropas:

 
 

      


       
       
       
       

      

      
     

    
        

    
    

     0
 #include  <stdio.h>  #include  <stdlib.h>  typedef  void  (  *  Handler  )(  void  );  /* En pekare till en hanterarfunktion */  /* Funktionerna */  void  func3  (  void  )  {  printf  (  "3  \n  "  );  }  void  func2  (  void  )  {  printf  (  "2  \n  "  );  }  void  func1  (  void  )  {  printf  (  "1  \n  "  );  }  void  func0  (  void  )  {  printf  (  "0  \n  "  );  }  Handler  jump_table  [  4  ]  =  {  func0  ,  func1  ,  func2  ,  func3  };  int  main  (  int  argc  ,  char  **  argv  )  {  int  värde  ;  /* Konvertera första argumentet till 0-3 heltal (modul) */  värde  =  atoi  (  argv  [  1  ])  %  4  ;  /* Anropa lämplig funktion (func0 till func3) */  jump_table  [  värde  ]();  återvända  ;  }

Hopptabellsexempel i PL/I

PL/I implementerar en hopptabell som en array av etikettvariabler . Dessa kan initieras på ett ovanligt sätt genom att använda en prenumererad uttalandeetikett. PL/I-etikettvariabler är inte bara adressen till satsen, utan innehåller vanligtvis ytterligare information om tillståndet för kodblocket som de tillhör. Utan den ovanliga initieringen skulle detta också kunna kodas med anrop och en rad ingångsvariabler. 

deklarera lab (10) etikett; deklarera x fix binär; gå till lab(x); lab(1): /* kod för val 1 */ ; ... lab(2): /* kod för val 2 */ ; ...

Kompilatorgenererade grentabeller

Programmerare lämnar ofta beslutet om huruvida en grentabell ska skapas eller inte till kompilatorn, och tror att den är perfekt kapabel att göra det korrekta valet från de kända söknycklarna. Detta kan vara sant för att optimera kompilatorer för relativt enkla fall där utbudet av söknycklar är begränsat. Men kompilatorer är inte lika intelligenta som människor och kan inte ha en djup kunskap om "sammanhang", eftersom de tror att en rad möjliga söknyckelheltalsvärden som 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 & 1000 skulle generera en grentabell med ett överdrivet stort antal tomma poster (900+) för mycket liten fördel. En bra optimeringskompilator kan sedan försortera värdena och generera kod för en binär chop- sökning, som ett "näst bästa" alternativ. Faktum är att applikationen kan vara mycket "tidskritisk" och minneskrav kanske inte alls är ett problem.

Men lite "sunt förnuft" kan förvandla detta speciella fall, och många andra liknande fall, till en enkel tvåstegsprocess med mycket stora potentiella besparingar, samtidigt som det så småningom överlåter det ultimata valet till kompilatorn, men "assisterar dess beslut" betydligt:

  • Testa först för söknyckel=1000 och utför lämplig gren.
  • Tillåt kompilatorn att "välja" att generera en grentabell på de återstående söknycklarna (1-50).

Variationer längs liknande linjer kan användas i fall där det finns två uppsättningar av korta intervall med ett stort gap mellan intervall.

Beräknad GoTo

Medan tekniken nu är känd som "grentabeller", kallade tidiga kompilatoranvändare implementeringen " beräknad GoTo ", med hänvisning till instruktionen som finns i Fortran-serien av kompilatorer. Instruktionen fasades så småningom ut i Fortran 90 (till förmån för SELECT & CASE-satser på källnivå).

Skapar indexet för grentabellen

Om det inte finns något uppenbart heltalsvärde tillgängligt för en grentabell kan det ändå skapas från en söknyckel (eller del av en söknyckel) genom någon form av aritmetisk transformation, eller kan helt enkelt vara radnumret för en databas eller postnumret i en array som innehåller söknyckeln som hittades under tidigare validering av nyckeln.

En hashtabell kan krävas för att bilda indexet i vissa fall. Men för indatavärden för en byte som AZ (eller den första byten av en längre nyckel), kan innehållet i själva byten ( rådata ) användas i en tvåstegsprocess, " trivial hash-funktion" , för att erhålla en slutindex för en grentabell med noll luckor.

  1. Konvertera rådatatecknet till dess numeriska ekvivalent (exempel ASCII 'A' ==> 65 decimal, 0x41 hexadecimal)
  2. Använd det numeriska heltalsvärdet som index i en 256 byte-array för att få ett andra index (ogiltiga poster 0; representerar luckor, annars 1, 2, 3 etc.)

Arrayen skulle inte vara större än (256 x 2) byte – för att hålla alla möjliga 16-bitars osignerade (korta) heltal. Om ingen validering krävs, och endast versaler används, kan storleken på arrayen vara så liten som (26 x 2) = 52 byte.

Andra användningar av teknik

Även om tekniken att förgrena med en förgreningstabell oftast används enbart i syfte att ändra programflödet – för att hoppa till en programetikett som är en ovillkorlig förgrening – kan samma teknik användas för andra ändamål. Den kan till exempel användas för att välja en startpunkt i en sekvens av upprepade instruktioner där drop through är normen och avsiktlig. Detta kan användas till exempel genom att optimera kompilatorer eller JIT- kompilatorer i loopunrolling .

Se även

externa länkar

  • [1] Exempel på grentabell i Wikibooks för IBM S/360
  • [2] Exempel på och argument för hopptabeller via funktionspekarmatriser i C / C++
  • [3] Exempelkod genererad av "Switch/Case"-grentabell i C, kontra IF/ELSE.
  • [4] Exempelkod genererad för arrayindexering om strukturstorleken är delbar med 2 potenser eller annat.
  • [5] "Arrays of Pointers to Functions" av Nigel Jones
Hämtad från " https://en.wikipedia.org/w/index.php?title=Branch_table&oldid=1113038318 "