Dal tablosu - Branch table

Olarak bilgisayar programlama , bir dal tablo veya atlama tablo program kontrolü (aktarılması için bir yöntemdir dallanma (dinamik olarak yüklenmiş olabilir ya da ayrı bir program) bir programın başka bir kısmına) dalı ya da atlama bir tablo kullanılarak talimatlar . Çok yollu bir dal şeklidir . Dal tablosu yapısı genellikle montaj dilinde programlama yapılırken kullanılır, ancak özellikle değerleri yoğun bir şekilde bir araya getirilmiş optimize edilmiş anahtar ifadeleri uygularken derleyiciler tarafından da oluşturulabilir .

Tipik uygulama

Bir dal tablosu bir seri listesini içerir koşulsuz dalı bir kullanarak içine dallanmış talimatlar ofset tarafından oluşturulan çarpma bir sıralı (bellekte bayt sayısı her dal komutu tarafından işgal) kullanıcı uzunluğu indeksi. Dallanma için makine kodu talimatlarının sabit bir uzunluğa sahip olduğu ve çoğu donanım tarafından son derece verimli bir şekilde yürütülebildiği gerçeğine dayanır ve en çok , sıralı dizin değerlerine kolayca dönüştürülebilen ham veri değerleriyle uğraşırken yararlıdır . Bu tür veriler göz önüne alındığında, bir dal tablosu son derece verimli olabilir. Genellikle aşağıdaki 3 adımdan oluşur:

kabul edilebilir olduğundan emin olmak için giriş verilerinin isteğe bağlı olarak doğrulanması (bu, girişin tek bayt olması ve aşağıdaki ofseti doğrudan elde etmek için 256 baytlık bir çeviri tablosunun kullanılması durumunda bir sonraki adımın bir parçası olarak maliyet olmadan gerçekleşebilir). Ayrıca, girdinin değerleri hakkında herhangi bir şüphe yoksa, bu adım atlanabilir.
verileri bir ofsete dal tablosuna dönüştürün. Bu genellikle komut uzunluğunu hesaba katmak için çarpmayı veya değiştirmeyi (etkili bir şekilde 2 kuvvetiyle çarpmayı) içerir. Statik bir çeviri tablosu kullanılıyorsa, bu çarpma elle veya derleyici tarafından herhangi bir çalışma süresi maliyeti olmadan gerçekleştirilebilir.
dallanma tablosunun temel adresi artı yeni oluşturulan ofsetten oluşan bir adrese dallanma. Bu bazen ofsetin program sayaç yazmacına eklenmesini içerir (bazı komut setlerinde dallanma talimatı fazladan bir indeks kaydına izin vermedikçe ). Bu son adres genellikle bir dizi koşulsuz şube talimatına veya bunların hemen arkasındaki talimata işaret eder (tabloya bir girişi kaydederek).

Aşağıdaki sözde kod kavramı göstermektedir

 ... validate x                    /* transform x to 0 (invalid) or 1,2,3, according to value..)    */
       y = x * 4;                  /* multiply by branch instruction length (e.g. 4 )               */
       goto next + y;              /* branch into 'table' of branch instructions                    */
 /* start of branch table */
 next: goto codebad;               /* x= 0  (invalid)                                               */
       goto codeone;               /* x= 1                                                          */
       goto codetwo;               /* x= 2                                                          */
 ... rest of branch table
 codebad:                          /* deal with invalid input                                       */

Adresleri kullanarak alternatif uygulama

Bir dal tablo uygulanması için bir başka yöntem, bir ile dizi arasında işaretçiler gerekli olan , işlevin adresi alınır. Bu yöntem aynı zamanda son zamanlarda " gönderim tablosu " veya " sanal yöntem tablosu " gibi farklı isimler altında bilinmekte, ancak esasen tamamen aynı amacı gerçekleştirmektedir. Bu işaretçi işlevi yöntemi, bir makine talimatının kaydedilmesine neden olabilir ve dolaylı atlamayı önler (dal talimatlarından birine).

Sonuçta ortaya çıkan işlev işaretçileri listesi, doğrudan iş parçacıklı kodla neredeyse aynıdır ve kavramsal olarak bir kontrol tablosuna benzer .

Bir dal tablosunu uygulamak için kullanılan gerçek yöntem genellikle aşağıdakilere dayanır:

kodun çalıştırılacağı işlemcinin mimarisi,
derlenmiş veya yorumlanmış bir dil olup olmadığı ve
geç bağlanmanın dahil olup olmadığı.

Tarih

Dal tablolarının ve diğer ham veri kodlamalarının kullanımı, belleğin pahalı olduğu, CPU'ların daha yavaş olduğu ve kompakt veri gösteriminin ve verimli alternatiflerin seçilmesinin önemli olduğu hesaplamanın ilk günlerinde yaygındı . Günümüzde hala yaygın olarak kullanılmaktadırlar:

gömülü programlama
işletim sistemi geliştirme. Birçok işletim sistemlerinde, hem sistem çağrıları ve kütüphane işlevleri bir tarafından başvurulan edilebilir tamsayı bir dal tabloya indeksi.
IBM / 360 gibi bazı bilgisayar mimarileri, kesintileri dağıtmak için dal tabloları kullanır

Avantajlar

Dal tablolarının avantajları şunları içerir:

kompakt kod yapısı (tekrarlanan dal işlem kodlarına rağmen)
azaltılmış kaynak ifadeler (tekrarlayan If ifadelere karşı )
İade kodlarını tek tek test etmek için daha az gereksinim (eğer arama yerinde sonraki program akışını belirlemek için kullanılıyorsa )
Algoritmik ve kod verimliliği (verilerin yalnızca bir kez kodlanması gerekir ve dal tablosu kodu genellikle kompakttır) ve yüksek veri sıkıştırma oranlarına ulaşma potansiyeli . Örneğin, ülke adlarını ülke kodlarına sıkıştırırken, "Orta Afrika Cumhuriyeti" gibi bir dize tek bir dizine sıkıştırılabilir, bu da büyük tasarruf sağlar - özellikle dizi birçok kez göründüğünde. Ek olarak, bu aynı indeks ilgili verilere ayrı tablolarda erişmek için kullanılabilir ve bu da depolama gereksinimlerini daha da azaltır.

İçin kütüphane onlar tarafından başvurulan olabilir fonksiyonları, tamsayı :

sonraki yazılım sürümleriyle uyumluluğu artırın. Bir işlevin kodu ve giriş noktasının adresi değiştirilirse, yalnızca dallanma tablosundaki dallanma talimatının ayarlanması gerekir; kitaplığa karşı veya işletim sistemi için derlenen uygulama yazılımlarının modifikasyonuna gerek yoktur.

Ek olarak, normal uygulama programlamasında bazı durumlarda fonksiyonları numaraya göre çağırmak (tablo içindeki dizin) bazen yararlı olabilir.

Dezavantajları

Ekstra seviyesi dolaylama bir çoğunlukla küçük verimi düşürür.
Bazı programlama dillerinde kısıtlamalar, ancak çok yönlü dallanma temel kavramını uygulamanın genellikle alternatif yolları olsa da.

Misal

8-bit Microchip PIC montaj dilinde dal tablosu kullanımının basit bir örneği :

     movf    INDEX,W     ; Move the index value into the W (working) register from memory
     addwf   PCL,F       ; add it to the program counter. Each PIC instruction is one byte
                         ; so there is no need to perform any multiplication. 
                         ; Most architectures will transform the index in some way before 
                         ; adding it to the program counter.

 table                   ; The branch table begins here with this label
     goto    index_zero  ; each of these goto instructions is an unconditional branch
     goto    index_one   ; of code.
     goto    index_two
     goto    index_three

 index_zero
     ; Code is added here to perform whatever action is required when INDEX = zero
     return

 index_one
 ...

Not: bu kod yalnızca PCL <(tablo + index_last) ise çalışacaktır. Bu koşulu sağlamak için bir "org" yönergesi kullanabiliriz. Ve eğer GOTO (örneğin PIC18F) 2 bayt ise, bu tablo girişlerinin sayısını 128'den az ile sınırlar.

C'de atlama tablosu örneği

Başka bir basit örnek, bu sefer sadece bir dal tablosu yerine bir atlama tablosunu gösteriyor. Bu, şu anda etkin olan prosedür / fonksiyonun dışındaki program bloklarının çağrılmasına izin verir:

#include <stdio.h>
#include <stdlib.h>

typedef void (*Handler)(void);    /* A pointer to a handler function */

/* The functions */
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 value;

    /* Convert first argument to 0-3 integer (modulus) */
    value = atoi(argv[1]) % 4;

    /* Call appropriate function (func0 thru func3) */
    jump_table[value]();

    return 0;
}

PL / I'deki atlama tablosu örneği

PL / I , bir etiket değişkenleri dizisi olarak bir atlama tablosu uygular . Bunlar, abonelikli bir ifade etiketi kullanılarak alışılmadık bir şekilde başlatılabilir. PL / I etiket değişkenleri sadece ifadenin adresi değildir, ancak genellikle ait oldukları kod bloğunun durumu hakkında ek bilgiler içerir. Olağandışı başlatma olmadan, bu aynı zamanda çağrılar ve bir dizi giriş değişkenleri ile kodlanabilir.

    declare lab (10) label;
    declare x fixed binary;
    goto lab(x);
  lab(1): /* code for choice 1 */ ;
    ...
  lab(2): /* code for choice 2 */ ;
    ...

Derleyici tarafından oluşturulan dal tabloları

Programcılar, bilinen arama tuşlarından doğru seçimi mükemmel bir şekilde yapabileceğine inanarak, bir dal tablosu oluşturup oluşturmama kararını sıklıkla derleyiciye bırakır. Bu, arama anahtarlarının aralığının sınırlı olduğu nispeten basit durumlar için derleyicileri optimize etmek için doğru olabilir. Ancak, derleyiciler insanlar kadar zeki değildir ve 1, 2, 4, 6, 7, 20, 23, 40, 42 gibi bir dizi olası arama anahtar tam sayı değerine inanarak derin bir "bağlam" bilgisine sahip olamazlar. 50 & 1000, çok az avantaj için çok fazla sayıda boş girişe (900+) sahip bir dal tablosu oluşturacaktır. İyi bir iyileştirme derleyicisi, daha sonra değerleri önceden sıralayabilir ve 'ikinci en iyi' seçenek olarak ikili bir dilim araması için kod oluşturabilir . Aslında, uygulama son derece "zaman açısından kritik" olabilir ve bellek gereksinimi gerçekten bir sorun olmayabilir.

Bununla birlikte, biraz 'sağduyu' bu özel durumu ve diğer birçok benzer durumu çok büyük potansiyel tasarruflu basit iki aşamalı bir sürece dönüştürebilirken, yine de nihai seçimi derleyiciye bırakıp 'kararına yardımcı olur' önemli ölçüde:

İlk olarak, arama anahtarı = 1000 için test edin ve uygun dalı gerçekleştirin.
Derleyicinin kalan arama anahtarlarında (1-50) bir dal tablosu oluşturmayı 'seçmesine' izin verin.

Aralıklar arasında büyük bir boşluğa sahip iki grup kısa menzil olduğu durumlarda benzer çizgiler boyunca varyasyonlar kullanılabilir.

Hesaplanmış GoTo

Teknik artık 'dal tabloları' olarak bilinirken, ilk derleyici kullanıcıları Fortran derleyiciler serisinde bulunan talimata atıfta bulunarak uygulamayı ' hesaplanmış GoTo ' olarak adlandırdılar . Talimat sonunda Fortran 90'da kullanımdan kaldırıldı (kaynak düzeyinde SELECT & CASE ifadeleri lehine).

Dal tablosu için dizin oluşturma

Bir dal tablosu için açık bir tamsayı değeri bulunmadığında, yine de bir tür aritmetik dönüşümle bir arama anahtarından (veya bir arama anahtarının bir kısmından) oluşturulabilir veya basitçe bir veritabanının satır numarası veya giriş numarası olabilir. anahtarın önceki doğrulaması sırasında bulunan arama anahtarını içeren bir dizide.

Bazı durumlarda dizini oluşturmak için bir karma tablo gerekli olabilir. Bununla birlikte, AZ (veya daha uzun bir anahtarın ilk baytı) gibi tek baytlık girdi değerleri için, baytın kendisinin içeriği ( ham veriler ), bir elde etmek için iki aşamalı, " önemsiz karma işlevi " işleminde kullanılabilir. sıfır boşluklu dal tablosu için son dizin.

Dönüştürme ham veriler kendi sayısal eşdeğeri (örnek karakteri ASCII 'A' ==> 65 ondalık, 0x41 onaltılık)
İkinci bir dizin elde etmek için sayısal tamsayı değerini 256 baytlık bir diziye dizin olarak kullanın (geçersiz girişler 0; boşlukları temsil eder, aksi takdirde 1, 2, 3 vb.)

Dizi, olası tüm 16 bitlik işaretsiz (kısa) tam sayıları tutmak için (256 x 2) bayttan büyük olamaz. Doğrulama gerekmiyorsa ve yalnızca büyük harf kullanılıyorsa, dizinin boyutu (26 x 2) = 52 bayt kadar küçük olabilir.

Tekniğin diğer kullanımları

Dallanma tablosu kullanan dallanma tekniği en sık olarak yalnızca program akışını değiştirmek amacıyla - koşulsuz bir dal olan bir program etiketine atlamak için - kullanılsa da, aynı teknik başka amaçlar için de kullanılabilir. Örneğin, bırakmanın normal ve kasıtlı olduğu tekrarlanan talimatlar dizisinde bir başlangıç noktası seçmek için kullanılabilir. Bu, örneğin döngü açmada derleyicileri veya JIT derleyicileri optimize ederek kullanılabilir .

Ayrıca bakınız

Geç bağlama için kullanılan başka bir ada göre bir dal tablosu gönderme
Dal tablolarında kullanılan işlevlere adreslerin işlev işaretçi dizileri
Dolaylı şube
Arama tablosu , bazen önceden hesaplanmış sonuçları tutan, eşleştirilecek bir dizi öğe
Switch ifadesi , bir dal tablosu oluşturabilecek yüksek seviyeli bir dil koşullu ifadesi
Sanal yöntem tablosu , dağıtım için dinamik olarak atanan işaretçilerle başka bir ada göre bir dal tablosu (bkz. Gönderim tablosu)

Referanslar

Dış bağlantılar

[1] IBM S / 360 için Vikikitap'taki dal tablosu örneği
[2] C / C ++ 'da İşlev İşaretçi Dizileri aracılığıyla Atlama Tabloları örnekleri ve argümanları
[3] IF / ELSE'ye karşılık C'deki 'Switch / Case' dal tablosu tarafından oluşturulan örnek kod.
[4] Yapı boyutu 2'nin katlarına veya başka bir şekilde bölünebiliyorsa, dizi indeksleme için üretilen örnek kod.
[5] "Arrays of Pointers to Functions", Nigel Jones

Languages

In other projects