GPERF: Mükemmel Bir Hash Fonksiyonu Üreteci

Douglas C. Schmidt
schmidt@cs.wustl.edu
http://www.cs.wustl.edu/~schmidt/
Bilgisayar Bilimi Bölümü
Washington University, St. Louis 63130

1 Giriş

Mükemmel hash fonksiyonları, statik arama kümelerinin zaman ve bellek açısından verimli bir uygulamasıdır. Statik arama kümesi; initialize, insert ve retrieve işlemlerine sahip soyut bir veri türüdür (ADT). Statik arama kümeleri sistem yazılımı uygulamalarında yaygındır.

Tipik statik arama kümeleri; derleyici ve yorumlayıcıların ayrılmış sözcükleri, assembler komut anımsatıcıları, kabuk yorumlayıcısının yerleşik komutları ve CORBA IDL derleyicilerini içerir. Arama kümesi elemanlarına anahtar sözcükler (keywords) denir. Anahtar sözcükler kümeye yalnızca bir kez eklenir; bu işlem genellikle derleme zamanında çevrimdışı olarak gerçekleştirilir.

gperf, kullanıcı tarafından sağlanan bir anahtar sözcük listesinden otomatik olarak mükemmel hash fonksiyonları oluşturan, C++ ile yazılmış ve serbestçe erişilebilen bir mükemmel hash fonksiyonu üretecidir. lex [1] ve yacc [2] gibi araçların yaklaşımından esinlenerek tasarlanmıştır ve zaman ve bellek açısından verimli anahtar sözcük tanıyıcılarını elle kurma sürecindeki zahmeti ortadan kaldırmayı amaçlar.

gperf, kullanıcı tarafından belirtilmiş n elemanlı bir anahtar sözcük listesini — keyfile olarak adlandırılır — k elemanlı bir arama tablosu ve aşağıdaki iki fonksiyonu içeren kaynak koda dönüştürür:

• hash, keyfile içindeki anahtar sözcükleri 0..k-1 aralığına benzersiz biçimde eşler; burada k ≥ n koşulu sağlanır. Eğer k = n ise hash, minimal mükemmel hash fonksiyonu olarak kabul edilir.
• in_word_set, hash fonksiyonunu kullanarak belirli bir karakter dizisinin keyfile içinde bulunup bulunmadığını belirler ve yaygın durumda en fazla bir kez dize karşılaştırması yapar.

gperf, birkaç bin anahtar sözcük içeren keyfile dosyaları için hızlı çalışacak şekilde tasarlanmıştır. Çıktı olarak verimli ANSI ve K&R C ile C++ kaynak kodu üretir. GNU C/C++ [3] ve TAO CORBA IDL compiler [4] dahil olmak üzere çeşitli üretim ve araştırma derleyicilerinde ve dil işleme araçlarında kullanılan sözcüksel çözümleyiciler için ayrılmış anahtar sözcük tanıyıcıları geliştirmede kullanılmıştır.

Bu makale şu şekilde düzenlenmiştir:

• Bölüm 2, alternatif statik arama kümesi uygulamalarını ana hatlarıyla açıklar ve bunları gperf tarafından üretilen hash tablolarıyla karşılaştırır.
• Bölüm 3, örnek bir giriş keyfile dosyası sunar.
• Bölüm 4, gperf geliştirilirken kullanılan tasarım kalıplarını ve uygulama stratejilerini vurgular.
• Bölüm 5, gperf tarafından üretilen tanıyıcılarla ayrılmış sözcük araması için kullanılan diğer popüler teknikler arasında yapılan deneysel karşılaştırmaların sonuçlarını gösterir.
• Bölüm 6, gperf’in sınırlamalarını ve olası geliştirmeleri ana hatlarıyla açıklar.
• Bölüm 7, sonuç değerlendirmelerini sunar.

2 Statik Arama Kümesi Uygulamaları

Statik arama kümelerinin çok sayıda uygulama yöntemi vardır. Yaygın örnekler arasında sıralı ve sırasız diziler ile bağlı listeler, AVL ağaçları, optimal ikili arama ağaçları, dijital arama trie yapıları, deterministik sonlu durum otomatları ve açık adresleme ile bucket zincirleme gibi çeşitli hash tablosu şemaları bulunur [5].

Farklı statik arama yapıları, bellek kullanımı ile arama süresi verimliliği ve öngörülebilirliği arasında çeşitli denge noktaları sunar. Örneğin, n elemanlı sıralı bir dizi bellek açısından verimlidir. Ancak sıralı bir dizi üzerinde ikili arama kullanılarak gerçekleştirilen erişim işlemlerinin ortalama ve en kötü durum zaman karmaşıklığı O(log n) ile orantılıdır [5].

Buna karşılık, zincirli hash tablosu uygulamaları bir tablo girişini ortalama olarak sabit zamanda, yani O(1) sürede bulur. Ancak hashleme genellikle bağlantı işaretçileri ve/veya kullanılmayan hash tablosu bucket’ları nedeniyle ek bellek yükü getirir. Ayrıca hashleme en kötü durumda O(n) performans sergiler [5].

Bir minimal mükemmel hash fonksiyonu, aşağıdaki iki özellikle tanımlanan bir statik arama kümesi uygulamasıdır:

Mükemmel özelliği:
Bir tablo girişinin bulunması O(1) zaman gerektirir; yani statik arama kümesi içinde anahtar sözcük tanıma işlemi için en fazla bir dize karşılaştırması gerekir.

Minimal özelliği:
Anahtar sözcükleri depolamak için ayrılan bellek, anahtar sözcük kümesi için tam olarak yeterlidir ve bundan daha büyük değildir.

Minimal mükemmel hash fonksiyonları, statik arama kümeleri için teorik olarak zaman ve bellek açısından en uygun çözümü sağlar [5]. Ancak olası mükemmel hash fonksiyonlarının arama uzayı son derece geniş olduğu için bunları verimli biçimde üretmek zordur. Bu nedenle özellikle binlerce anahtar sözcük içeren uygulamalarda aşağıdaki varyasyonlar çoğu pratik hashleme uygulaması için daha uygun olur.

Minimal Olmayan Mükemmel Hash Fonksiyonları

Bu fonksiyonlar minimal özelliğe sahip değildir çünkü tablodaki anahtar sözcüklerin toplam sayısından daha geniş bir hash değeri aralığı döndürürler. Ancak mükemmel özelliğe sahiptirler çünkü bir dizenin tabloda bulunup bulunmadığını belirlemek için en fazla bir dize karşılaştırması gerekir.

Minimal olmayan hash fonksiyonlarının tercih edilmesinin iki nedeni vardır:

1. Üretim verimliliği – Minimal olmayan mükemmel fonksiyonları geliştirmek genellikle minimal mükemmel hash fonksiyonları geliştirmekten çok daha hızlıdır [6, 7].
2. Çalışma zamanı verimliliği – Minimal olmayan mükemmel hash fonksiyonları, tabloda bulunmayan elemanları ararken minimal olanlara göre daha hızlı çalışabilir; çünkü “null” girişine daha sık ulaşılır. Bu durum özellikle bir derleyicide programlama dili ayrılmış sözcükleri tanınırken sık görülür [8].

Neredeyse Mükemmel Hash Fonksiyonları

Neredeyse mükemmel hash fonksiyonları mükemmel özelliğe sahip değildir çünkü benzersiz olmayan anahtar sözcük hash değerlerine izin verirler [9] (minimal özelliğe sahip olabilirler veya olmayabilirler). Bu teknik, üretilen kodun çalışma süresini artırma karşılığında fonksiyon üretim süresini azaltan bir uzlaşma yaklaşımıdır.

Neredeyse mükemmel hash fonksiyonları, ana belleğin sınırlı olduğu durumlarda yararlıdır çünkü minimal olmayan mükemmel hash fonksiyonlarına göre çok daha küçük arama tabloları üretme eğilimindedirler.

gperf, aşağıda açıklanan şekilde minimal mükemmel, minimal olmayan mükemmel ve neredeyse mükemmel hash fonksiyonları geliştirebilir.

3 GPERF ile Etkileşim

Bu bölüm, son kullanıcıların gperf ile nasıl etkileşime girebileceğini açıklar.

Varsayılan olarak gperf, standart girişten bir anahtar sözcük listesi ve isteğe bağlı ilişkili öznitelikleri içeren keyfile dosyasını okur. Anahtar sözcükler, varsayılan değeri ',' olan kullanıcı tarafından belirlenebilir bir alan ayırıcı ile ayrılmış rastgele karakter dizileri olarak belirtilir. Böylece anahtar sözcükler boşluklar ve diğer ASCII karakterlerini içerebilir. İlişkili öznitelikler herhangi bir C sabiti olabilir.

Örneğin, aşağıdaki anahtar sözcükler yılın aylarını temsil eder. İlişkili öznitelikler struct months yapısındaki alanlara karşılık gelir. Bunlar her ayın artık yıl ve normal yıl gün sayılarını ve ayrıca ayların sıra numaralarını içerir; yani january = 1, february = 2, ..., december = 12.

%{
#include <stdio.h>
#include <string.h>
/* Command-line options:
   -C -p -a -n -t -o -j 1 -k 2,3
   -N is_month */
%}

struct months {
    char *name;
    int number;
    int days;
    int leap_days;
};

%%
january,   1, 31, 31
february,  2, 28, 29
march,     3, 31, 31
april,     4, 30, 30
may,       5, 31, 31
june,      6, 30, 30
july,      7, 31, 31
august,    8, 31, 31
september, 9, 30, 30
october,  10, 31, 31
november, 11, 30, 30
december, 12, 31, 31
%%

/* Auxiliary code goes here... */
#ifdef DEBUG
int main () {
    char buf[BUFSIZ];

    while (gets(buf)) {
        struct months *p = is_month(buf, strlen(buf));
        printf("%s is%s a month\n",
               p ? p->name : buf,
               p ? "" : " not");
    }
}
#endif

gperf’in giriş biçimi UNIX yardımcı programları lex ve yacc ile benzerdir. Aşağıdaki yapıyı kullanır:

bildirimler ve metin eklemeleri
%%
anahtar sözcükler ve isteğe bağlı öznitelikler
%%
yardımcı kod

İlk sütunda yer alan ardışık iki % sembolü, bildirimleri anahtar sözcük listesi ve isteğe bağlı özniteliklerden ayırır. C veya C++ kaynak kodu ve yorumlar %{ %} sınırlayıcıları içine alınarak üretilen çıktı dosyasına aynen eklenir. Çıktı dosyası oluşturulurken bu sınırlayıcılar kaldırılır.

Kullanıcı tarafından sağlanan isteğe bağlı bir struct bildirimi, bildirim bölümünün sonunda ve %% ayırıcısından hemen önce yerleştirilebilir. Bu özellik tipli öznitelik başlatma işlemini mümkün kılar.

Örneğin, önceki keyfile içinde struct months yapısı ay adları ve bunlara karşılık gelen değerler için verilen başlatıcı değerlerle eşleşen dört alan içerir:

january,  1, 31, 31
february, 2, 28, 29
march,    3, 31, 31
...

lex ve yacc araçlarında olduğu gibi, başlangıç bildirim bölümünü tamamen atlamak da mümkündür. Bu durumda keyfile, yorum olmayan ilk satırla başlar (# ile başlayan satırlar yorum olarak kabul edilir ve yok sayılır). Bu biçim, ilişkili öznitelikleri olmayan anahtar sözcük kümesi tanıyıcıları geliştirmek için yararlıdır.

Örneğin, sık kullanılan İngilizce kelimeler için bir mükemmel hash fonksiyonu, anahtar sözcük bağlamlı dizinleme uygulamasında “the”, “as” ve “this” gibi bilgi değeri düşük kelimeleri verimli şekilde elemek için kullanılabilir [5].

Yine lex ve yacc araçlarında olduğu gibi, isteğe bağlı üçüncü yardımcı kod bölümündeki tüm metin üretilen çıktı dosyasına aynen eklenir. Bu ekleme son %% işaretinden hemen sonra başlar ve keyfile dosyasının sonuna kadar devam eder. Eklenen kodun geçerli C veya C++ olmasını sağlamak kullanıcının sorumluluğundadır.

Önceki örnekte bu yardımcı kod, oluşturulan C veya C++ kodu derlenirken DEBUG sembolü etkinleştirilmişse koşullu olarak dahil edilen bir test sürücüsü sağlar.

4 Uygulama Genel Bakışı

Birçok makale mükemmel hashleme [10, 7, 11, 12] ve minimal mükemmel hashleme algoritmalarını [8, 13, 6, 14, 15] açıklar. Ancak genel amaçlı bir mükemmel hashleme üretim aracının tasarımını ve uygulamasını ayrıntılı biçimde ele alan çalışmalar azdır. Bu bölüm, gperf içindeki veri yapıları, algoritmalar, çıktı biçimi ve yeniden kullanılabilir bileşenleri açıklar.

gperf, yaklaşık 4.000 satır C++ kaynak kodu ile yazılmıştır. C++, C dilinin verimliliğini ve ifade gücünü korurken veri soyutlamasını C’den daha iyi desteklediği için uygulama dili olarak seçilmiştir [16].

gperf’in mükemmel veya neredeyse mükemmel bir hash fonksiyonu geliştirmek için kullandığı üç ana aşama şunlardır:

1. Komut satırı seçeneklerini işlemek, anahtar sözcükleri ve öznitelikleri okumak (giriş biçimi Bölüm 3’te açıklanmıştır) ve iç nesneleri başlatmak.
2. Mükemmel bir hash fonksiyonu bulmak için geri izleme içermeyen ve sezgisel olarak yönlendirilen bir arama gerçekleştirmek.
3. Komut satırı seçeneklerine göre biçimlendirilmiş C veya C++ kodu üretmek.

Bir sonraki bölüm gperf’in mükemmel hash fonksiyonu üretim algoritmalarını ve iç nesnelerini ana hatlarıyla açıklar, üretilen kaynak kod çıktısını inceler, yeniden kullanılabilir sınıf bileşenlerini tanımlar ve programın mevcut sınırlamaları ile gelecekte yapılabilecek geliştirmeleri tartışır.

gperf uygulamasının merkezi iki iç nesne etrafında şekillenir:

• keyword signatures list (Key List)
• associated values array (asso_values)

Kullanıcı tarafından belirtilen her anahtar sözcük ve öznitelikleri keyfile dosyasından okunur ve Key List adı verilen bağlı listede bir düğümde saklanır.

gperf, mükemmel bir hash fonksiyonu ararken her anahtar sözcüğün karakterlerinin yalnızca bir alt kümesini dikkate alır. Bu alt kümeye keyword signature veya keysig adı verilir.

Anahtar sözcükleri ve ilişkili öznitelikleri içeren satırlar keyfile dosyasının keywords and optional attributes bölümünde bulunur. Her satırın ilk alanı her zaman anahtar sözcüğün kendisini içerir; bu alan ilk sütuna hizalıdır ve tırnak işaretleri içermez. Anahtar sözcüğü takiben ek öznitelik alanları bulunabilir.

Öznitelikler, alan ayırıcılar kullanılarak anahtar sözcükten ve birbirlerinden ayrılır ve satır sonu karakterine kadar devam eder. Varsayılan satır sonu karakteri yeni satır karakteridir ('\n').

Öznitelik alanı değerleri, bildirim bölümünün sonunda yer alan kullanıcı tarafından sağlanan struct yapısının bileşenlerini başlatmak için kullanılır.

4.1 İç Nesneler

keysig, otomatik olarak geliştirilen tanıma fonksiyonunun bir anahtar sözcüğün hash değerini hesaplamak için kullandığı belirli karakter alt kümesini temsil eder. Keysigs, keyfile dosyası ilk kez gperf tarafından işlenirken oluşturulur ve Key List içindeki her düğümde önbelleğe alınır.

İlişkili değerler dizisi asso_values, keysig ile yakından ilişkili bir nesnedir. Aslında bu dizi keysig karakterleriyle indekslenir. Dizi gperf tarafından dahili olarak oluşturulur ve mükemmel bir hash fonksiyonu aranırken sık sık başvurulur.

gperf’in C/C++ kod üretim aşamasında, ilişkili değerler dizisinin ASCII gösterimi üretilen hash fonksiyonunda statik yerel bir dizi olarak çıktı dosyasına yazılır. Bu dizi şu şekilde tanımlanır:

unsigned int asso_values[MAX_ASCII_SIZE];

Mükemmel bir hash fonksiyonu aranırken gperf, keysig girdileri tarafından belirlenen bazı asso_values elemanlarına tekrar tekrar farklı değerler atar. Arama sürecinin her adımında asso_values dizisinin içeriği, mevcut ilişkili değerler yapılandırmasını temsil eder.

Minimal mükemmel hash fonksiyonları üretilecek şekilde yapılandırıldığında (varsayılan davranış budur), gperf tüm n keysig değerlerini tekrar etmeyen hash değerlerine eşleyen bir ilişkili değerler yapılandırması arar. gperf, her keysig değerini üretilen arama tablosunda benzersiz bir konuma eşleyen bir yapılandırma bulduğunda mükemmel bir hash fonksiyonu elde edilir.

Elde edilen mükemmel hash fonksiyonu şu aralıkta bir unsigned int değer döndürür:

0 .. (k − 1)

burada

k = (maksimum anahtar sözcük hash değeri + 1)

k = n olduğunda minimal mükemmel hash fonksiyonu elde edilir. k değeri n’den büyük olduğunda arama tablosunun doluluk oranı n / (toplam tablo boyutu) olur.

Bir anahtar sözcüğün hash değeri genellikle keysig karakterlerinin ilişkili değerleri ile uzunluğunun birleştirilmesiyle hesaplanır. Varsayılan olarak hash fonksiyonu, bir anahtar sözcüğün ilk indeks konumunun ilişkili değerini ve son indeks konumunun ilişkili değerini uzunluğuna ekler:

hash_value =
  asso_values[keyword[0]]
+ asso_values[keyword[length - 1]]
+ length;

Pratikte çoğu zaman başka kombinasyonlar gerekir. Örneğin varsayılan hash fonksiyonu C++ ayrılmış sözcükleri için kullanıldığında delete ve double arasında bir çakışma oluşur. Bu çakışmayı çözmek ve C++ ayrılmış sözcükleri için mükemmel bir hash fonksiyonu elde etmek amacıyla keysig’e ek bir karakter dahil edilmelidir:

hash_value =
  asso_values[keyword[0]]
+ asso_values[keyword[1]]
+ asso_values[keyword[length - 1]]
+ length;

Geliştiriciler, oluşturulan hash fonksiyonunun içeriğini "-k" seçeneğini kullanarak gperf’e keysig elemanları olarak kullanılacak anahtar sözcük indeks konumlarını açıkça belirterek kontrol edebilir. Varsayılan değer -k 1,$ biçimindedir; burada $ anahtar sözcüğün son karakterini temsil eder.

Tablo 1, Şekil 1’deki keyfile dosyasında gösterilen her ay için anahtar sözcükleri, keysig değerlerini ve hash değerlerini gösterir. Bu keysig değerleri -k 2,3 seçeneği kullanılarak elde edilmiştir.

Keysig değerleri çoklu kümelerdir (multiset) çünkü belirli karakterlerin birden fazla kez bulunmasına izin verirler. Bu yaklaşım, bir anahtar sözcüğün hash değerini hesaplarken yalnızca ilk ve son karakterler ile uzunluğu dikkate alan diğer mükemmel hash fonksiyonu üretim tekniklerinden [8] farklıdır.

gperf tarafından oluşturulan hash fonksiyonu, belirtilen bir indeks konumundan daha kısa anahtar kelimeleri, anahtar kelimenin uzunluğunu aşan karakterleri atlayarak doğru şekilde ele alır. Buna ek olarak kullanıcılar, -k* seçeneği aracılığıyla gperf’e bir anahtar kelimenin tüm karakterlerini keysig içinde dahil etmesini söyleyebilir.

4.2 Mükemmel Hash Fonksiyonlarının Oluşturulması

Bu alt bölüm, gperf’in mükemmel hash fonksiyonlarını nasıl oluşturduğunu açıklamaktadır.

gperf, toplam anahtar kelime sayısının n olduğu durumda 1 ≤ i ≤ n olacak şekilde i adet anahtar kelimeden oluşan liste boyunca sıralı olarak yineleme yapar. Her yineleme sırasında gperf, benzersiz şekilde hash’lenmiş anahtar kelimeler kümesini 1 artırmaya çalışır. Hesaplanan hash değeri i numaralı anahtar kelime için, önceki i − 1 benzersiz şekilde hash’lenmiş anahtar kelimeyle çakışmıyorsa bu işlem başarılı olur.

Algoritma, i = n olduğunda ve çözülmemiş hiçbir hash çakışması kalmadığında sona erer ve bir mükemmel hash fonksiyonu oluşturur. Dolayısıyla bu algoritma için en iyi durum asimptotik zaman karmaşıklığı anahtar kelime sayısına göre doğrusaldır; yani Θ(n).

Şekil 3’te özetlendiği gibi gperf, belirli ilişkili değerleri artırarak anahtar kelime hash çakışmalarını çözmeye çalışır. Aşağıda gperf’in çakışma çözümünü hızlandırmak için kullandığı stratejiler ele alınmaktadır.

Ayrık Birleşim

Gereksiz işlemler yapmamak için gperf, ilişkili değerleri değiştirirken seçici davranır. Özellikle yalnızca çakışan anahtar kelimelerin keysig’lerinin ayrık birleşimini oluşturan karakterleri dikkate alır.

İki keysig A ve B için ayrık birleşim şu şekilde tanımlanır:

(A ∪ B) − (A ∩ B)

Ayrık birleşim kullanımını göstermek için Şekil 1’deki january ve march anahtar kelimelerini ele alalım. Tablo 1’de gösterildiği gibi bu anahtar kelimelerin keysig değerleri sırasıyla "an" ve "ar"’dır.

Dolayısıyla

• asso_values['a'] = 0
• asso_values['n'] = 0
• asso_values['r'] = 0

hepsi 0 olduğunda, gperf çalışması sırasında bir çakışma meydana gelir. Bu çakışmayı çözmek için gperf yalnızca 'n' ve/veya 'r' için ilişkili değerleri değiştirmeyi dikkate alır. 'a' değerini herhangi bir artışla değiştirmek çakışmayı çözemeyecektir, çünkü 'a' her iki keysig içinde de aynı sayıda bulunur.

Varsayılan olarak tüm asso_values değerleri 0 olarak başlatılır. Bir çakışma algılandığında gperf, ilgili ilişkili değeri bir sıçrama artışı kadar artırır. Komut satırı seçeneği "-j", bu sıçrama artışını sabit veya rastgele bir miktar kadar artırmak için kullanılabilir.

Genel olarak daha küçük bir sıçrama artışı seçmek (örneğin -j 1), oluşturulan hash tablosunun boyutunu azaltır; ancak bu durum gperf’in çalışma süresini artırabilir.

Şekil 1’deki aylar örneğinde -j 1 seçeneği kullanılmıştır. Bu nedenle gperf, january ve march arasındaki çakışmayı asso_values['n'] değerini 1 artırarak hızlıca çözer. Tablo 2’de gösterildiği gibi bu değer nihai değeridir.

Arama Sezgiselleri

gperf, mükemmel bir hash fonksiyonu oluşturmak için gereken süreyi azaltmak amacıyla çeşitli arama sezgiselleri kullanır.

Örneğin ayrık birleşimdeki karakterler, artan görülme sıklığına göre sıralanır; böylece daha seyrek kullanılan karakterler, daha sık kullanılan karakterlerden önce artırılır. Bu strateji, daha az kullanılan karakterlerin önce artırılmasının, zaten birbirlerine göre benzersiz şekilde hash’lenmiş anahtar kelimeler üzerindeki olumsuz etkiyi azaltacağı varsayımına dayanır.

Tablo 2, aylar örneğinde tüm keysig karakterleri için ilişkili değerleri ve görülme sıklıklarını göstermektedir.

İlişkili değer yapılandırmasına yapılan artışlar, Anahtar Listesi’nin sonuna ulaşıldığında tüm anahtar kelime çakışmalarını ortadan kaldırıyorsa gperf bir mükemmel hash fonksiyonu oluşturur.

Bu algoritma için en kötü durum asimptotik zaman karmaşıklığı:

O(n · l)

şeklindedir; burada l, çakışan anahtar kelime keysig’leri arasındaki en büyük ayrık birleşimde bulunan karakter sayısını ifade eder. Birçok keyfile üzerinde gperf ile yapılan deneyler, bu tür en kötü durum davranışının pratikte nadiren ortaya çıktığını göstermektedir.

Birçok mükemmel hash fonksiyonu oluşturma algoritması [6, 7], anahtar kelimelerin ele alınma sırasına duyarlıdır. Bu sıralama etkisini azaltmak için gperf, -o komut satırı seçeneği etkinleştirildiğinde Anahtar Listesi içindeki anahtar kelimeleri isteğe bağlı olarak yeniden sıralar.

Bu yeniden sıralama, gperf ana algoritmayı çalıştırmadan önce iki aşamalı bir ön geçiş sırasında gerçekleştirilir. İlk olarak Anahtar Listesi, keysig karakterlerinin görülme sıklığı azalan sıraya göre sıralanır. Ardından ikinci yeniden sıralama geçişi, değerleri zaten belirlenmiş keysig’lerin listede daha erken görünmesini sağlayacak şekilde Anahtar Listesi’ni yeniden düzenler.

Bu sezgiseller, oluşturma sürecinin erken aşamalarında kaçınılmaz çakışmaları ele alarak arama uzayını daraltmaya yardımcı olur.

Tablo 1: Aylar Örneği için Anahtar Kelimeler, Keysig’ler ve Hash Değerleri

Tablo 2: Keysig Karakterleri için İlişkili Değerler ve Görülme Sıklıkları

Şekil 3: gperf’in Ana Algoritması

for i = 1 to n loop
  if hash(i-th key) collides with any hash(1st key ... (i−1)th key) then
    modify disjoint union of associated values to resolve collisions
    based upon certain collision resolution heuristics
  end if
end loop

4.3 Oluşturulan Çıktı Biçimi

Şekil 4, Şekil 1’de gösterilen keyfile’a karşılık gelen ve gperf tarafından oluşturulan minimal mükemmel hash fonksiyonundan üretilen C kodunu göstermektedir. Sun SPARC 20 iş istasyonunda çalışma süresi ihmal edilebilir düzeydeydi (0.0 kullanıcı ve 0.0 sistem zamanı).

Aşağıdaki bölüm, gperf’in oluşturduğu çıktı biçiminin çeşitli yönlerini açıklamak için bu kodun bazı kısımlarını çalışma örneği olarak kullanır.

4.3.1 Oluşturulan Sembolik Sabitler

gperf çıktısı, Şekil 1’deki keyfile’a Şekil 3’teki algoritmanın uygulanmasının sonuçlarını özetleyen aşağıdaki yedi sembolik sabiti içerir.

• gperf şu durumda minimal mükemmel hash fonksiyonu oluşturur:

  • HASH_VALUE_RANGE = TOTAL_KEYWORDS
  • DUPLICATES = 0

• Şu durumda minimal olmayan mükemmel hash fonksiyonu oluşur:

  • DUPLICATES = 0
  • HASH_VALUE_RANGE > TOTAL_KEYWORDS

• Şu durumda neredeyse mükemmel hash fonksiyonu oluşur:

  • DUPLICATES > 0
  • DUPLICATES ≤ TOTAL_KEYWORDS

Varsayılan olarak gperf’e girdi olarak bir keyfile verildiğinde, arama tablosunda anahtar kelimeleri tanımak için en fazla bir string karşılaştırması kullanan bir mükemmel hash fonksiyonu oluşturulmaya çalışılır.

Arama tablosu bir dizi (array) ya da bir switch ifadesi olarak gerçekleştirilebilir.

Örnek Oluşturulan Kod

#include <stdio.h>
#include <string.h>

/* Komut satırı seçenekleri:
   -C -p -a -n -t -o -j 1 -k 2,3
   -N is_month */

struct months {
  char *name;
  int number;
  int days;
  int leap_days;
};

enum {
  TOTAL_KEYWORDS = 12,
  MIN_WORD_LENGTH = 3,
  MAX_WORD_LENGTH = 9,
  MIN_HASH_VALUE = 0,
  MAX_HASH_VALUE = 11,
  HASH_VALUE_RANGE = 12,
  DUPLICATES = 0
};

static unsigned int
hash (const char *str, unsigned int len)
{
  static const unsigned char asso_values[] = {
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,12,12,
    2,9,5,12,0,12,7,12,12,12,12,
    6,12,1,11,0,12,2,12,5,0,0,
    12,12,6,12,12,12,12,12,12
  };

  return asso_values[str[2]] + asso_values[str[1]];
}

const struct months *
is_month (const char *str, unsigned int len)
{
  static const struct months wordlist[] = {
    {"september", 9, 30, 30},
    {"june", 6, 30, 30},
    {"april", 4, 30, 30},
    {"january", 1, 31, 31},
    {"march", 3, 31, 31},
    {"december", 12, 31, 31},
    {"july", 7, 31, 31},
    {"august", 8, 31, 31},
    {"may", 5, 31, 31},
    {"february", 2, 28, 29},
    {"october", 10, 31, 31},
    {"november", 11, 30, 30}
  };

  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH) {
    int key = hash(str, len);

    if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE) {
      char *s = wordlist[key].name;

      if (*str == *s && !strcmp(str + 1, s + 1))
        return &wordlist[key];
    }
  }

  return 0;
}

enum {
  TOTAL_KEYWORDS = 12,
  MIN_WORD_LENGTH = 3,
  MAX_WORD_LENGTH = 9,
  MIN_HASH_VALUE = 0,
  MAX_HASH_VALUE = 11,
  HASH_VALUE_RANGE = 12,
  DUPLICATES = 0
};

Asso Values Dizi Arama Tablosu

gperf varsayılan olarak, minimum bellek kullanımından ziyade çalışma zamanı hızını vurgulayan bir dizi üretir. Bu dizi asso_values olarak adlandırılır ve Şekil 4’teki hash fonksiyonunda gösterilmiştir. asso_values dizisi, hash değerlerini hesaplayan ve tablo araması gerçekleştiren iki oluşturulan fonksiyon tarafından kullanılır.

gperf ayrıca geliştiricilerin bellek boyutu ile yürütme süresi arasında seçim yapmasına olanak tanıyan komut satırı seçenekleri de sağlar. Örneğin hash değerleri aralığını genişletmek, daha seyrek bir arama tablosu oluşturur. Bu genellikle daha hızlı anahtar kelime aramaları sağlar ancak ek bellek gerektirir.

Dizi tabanlı asso_values yaklaşımı, HASH_VALUE_RANGE değerinin TOTAL_KEYWORDS değerinden çok daha büyük olmadığı durumlarda en iyi sonucu verir. Ancak anahtar kelime sayısı çok fazla olduğunda ve hash değerleri aralığı bundan da büyük olduğunda, Şekil 4’teki is_month fonksiyonundaki wordlist dizisi son derece büyük hale gelebilir. Bu durumda birkaç sorun ortaya çıkar:

• Seyrek doldurulmuş dizinin derlenmesi için gereken süre aşırı olur.
• Büyük bir dizi, işletim sisteminde sanal belleğin daha fazla “thrashing” yaşamasına neden olabilir.
• Dizinin boyutu ana bellekte saklanamayacak kadar büyük olabilir.

Switch Tabanlı Arama Tablosu

Yukarıda açıklanan sorunları ele almak için gperf, arama tablosunu gerçekleştirmek amacıyla bir veya daha fazla switch ifadesi de oluşturabilir. Altta yatan derleyicinin switch optimizasyon yeteneklerine bağlı olarak switch tabanlı yöntem, büyük ve seyrek doldurulmuş diziye kıyasla daha küçük ve daha hızlı kod üretebilir. Şekil 5, aylar örneğinin gperf’in "-S 1" seçeneği ile üretildiğinde switch ifadesi kodunun nasıl göründüğünü göstermektedir.

Aylar örneği biraz yapay olduğundan, dizi ve switch yaklaşımı arasındaki denge çok belirgin değildir. Bununla birlikte iyi C++ derleyicileri, switch ifadesinin case etiketleri en küçük ve en büyük case etiketleri arasındaki aralığa kıyasla seyrek olduğunda etiketlerin ikili araması (binary-search-of-labels) şemasını gerçekleştiren assembly kodu üretir [3]. Bu teknik, gereksiz boş dizi konumları veya atlama tablosu yuvaları üretmeyerek büyük miktarda alan tasarrufu sağlayabilir. Bu yaklaşımın sağladığı zaman ve alan kazancı, kullanılan derleyicinin optimizasyon stratejisine göre değişir.

gperf, diziyi veya switch ifadesine dayalı arama tablosunu derleme zamanında kuran kaynak kod üretir. Bu nedenle anahtar kelimelerin ve bunlara bağlı özelliklerin başlatılması, tanıyıcı fonksiyon çalıştırıldığında ek çalışma zamanı yükünü çok az artırır. “Başlatma” işlemi, programın ikili görüntüsü diskten ana belleğe yüklendiğinde otomatik olarak gerçekleştirilir.

switch (key)
{
case 0:  rw = &wordlist[0];  break;
case 1:  rw = &wordlist[1];  break;
case 2:  rw = &wordlist[2];  break;
case 3:  rw = &wordlist[3];  break;
case 4:  rw = &wordlist[4];  break;
case 5:  rw = &wordlist[5];  break;
case 6:  rw = &wordlist[6];  break;
case 7:  rw = &wordlist[7];  break;
case 8:  rw = &wordlist[8];  break;
case 9:  rw = &wordlist[9];  break;
case 10: rw = &wordlist[10]; break;
case 11: rw = &wordlist[11]; break;
default: return 0;
}

if (*str == *rw->name && !strcmp(str + 1, rw->name + 1))
  return rw;
return 0;

Şekil 5: Switch Tabanlı Arama Tablosu

4.3.3 Oluşturulan Fonksiyonlar

gperf bir hash fonksiyonu ve bir arama fonksiyonu oluşturur. Varsayılan olarak bunlar hash ve in_word_set olarak adlandırılır; ancak in_word_set için farklı bir ad "-N" komut satırı seçeneği kullanılarak verilebilir.

Her iki fonksiyon da iki argüman gerektirir:

• NUL ile sonlandırılmış ('\0') bir karakter dizisine işaretçi: const char *str
• Bir uzunluk parametresi: unsigned int len

Oluşturulan Hash Fonksiyonu (hash)

Şekil 4, Şekil 1’de gösterilen girdi keyfile’ından elde edilen hash fonksiyonunu göstermektedir. Bu test için "-k 2,3" komut satırı seçeneği etkinleştirilmiştir. Bu seçenek, hash fonksiyonuna str argümanındaki 2. ve 3. karakterlerin ASCII değerlerini yerel statik asso_values dizisinde kullanarak hesaplanan bir unsigned int hash değeri döndürmesini söyler. Elde edilen iki sayı toplanarak str’nin hash değeri hesaplanır.

asso_values dizisi, gperf tarafından Bölüm 4.1.2’deki algoritma kullanılarak oluşturulur. Bu dizi, kullanıcı tarafından tanımlanan anahtar kelimeleri benzersiz hash değerlerine eşler. MAX_HASH_VALUE değerinden büyük olan tüm asso_values dizi girişleri (yani Şekil 4’teki dizide görülen tüm “12” değerleri), yılın aylarında ikinci veya üçüncü karakter olarak hiç görünmeyen ASCII karakterlerini temsil eder.

Şekil 4’teki is_month fonksiyonu, ay adı olamayacak girdi stringlerini hızlıca elemek için bu bilgiyi kullanır.

Oluşturulan Arama Fonksiyonu (in_word_set)

in_word_set fonksiyonu, mükemmel hash arama fonksiyonunun giriş noktasıdır. Buna karşılık hash fonksiyonu static olarak tanımlanmıştır ve uygulama programları tarafından doğrudan çağrılamaz.

Fonksiyonun ilk parametresi char *str geçerli bir kullanıcı tanımlı anahtar kelime ise in_word_set, ilgili anahtar kelimeyi ve ona bağlı özellikleri içeren kayda bir işaretçi döndürür; aksi halde NULL işaretçisi döndürülür.

Şekil 4, "-N" komut satırı seçeneği kullanılarak in_word_set fonksiyonunun is_month olarak yeniden adlandırılabildiğini göstermektedir.

Dikkat edilirse gperf, len parametresini ve elde edilen hash fonksiyonunun dönüş değerini şu sembolik sabitlerle karşılaştırır:

• MAX_WORD_LENGTH
• MIN_WORD_LENGTH
• MAX_HASH_VALUE
• MIN_HASH_VALUE

Bu kontrol, ay isimleri olmayan birçok girdiyi hızlıca eler. Kullanıcılar tüm girdi stringlerinin geçerli anahtar kelimeler olduğunu önceden biliyorsa gperf, "-O" seçeneği ile bu ek kontrolü bastırır.

Eğer gperf’e dizi tabanlı bir arama tablosu oluşturması söylenmişse üretilen kod oldukça kısa olur. Hash değerinin uygun aralıkta olduğu belirlendiğinde kod basitçe şu şekildedir:

{
  char *s = wordlist[key];
  if (*s == *str && !strcmp(str + 1, s + 1))
    return s;
}

*s == *str ifadesi, hesaplanan hash değerinin “null” bir tablo yuvasına indekslendiğini hızlı biçimde tespit eder; çünkü bu durumda *s, NUL karakteridir ('\0'). Bu kontrol, seyrek bir anahtar kelime arama tablosunda arama yapılırken faydalıdır; çünkü böyle bir tabloda null bir girdinin bulunma olasılığı daha yüksektir. Eğer null bir girdi bulunursa, tam bir dize karşılaştırması yapmaya gerek kalmaz.

Aylar örneği minimal mükemmel bir hash fonksiyonu ürettiğinden, null girdiler hiçbir zaman ortaya çıkmaz. Bununla birlikte bu kontrol yine de yararlıdır; çünkü str değişkeninin ilk harfi arama tablosundaki anahtar kelimelerden hiçbiriyle eşleşmediğinde dize karşılaştırma fonksiyonunun çağrılmasını engeller.

Yazılım Mimarisinin Bileşenleri

Şekil 6, gperf yazılım mimarisinde kullanılan temel bileşenleri göstermektedir. gperf, ACE framework [17] içindeki yeniden kullanılabilir bileşenlerden oluşturulmuştur. Her bir bileşen, özel amaçlı araçlardan başlayarak “aşağıdan yukarıya” doğru gelişmiş ve yeniden kullanılabilir yazılım bileşenlerine dönüşmüştür.

Dikkat çeken bazı yeniden kullanılabilir sınıflar aşağıdaki bileşenleri içerir.

ACE Bool Array

Gperf’in önceki sürümlerinde, çok sayıda çakışma oluşturan büyük giriş anahtar dosyaları üzerinde çalışma zamanı kod profilleyicisi kullanılmıştır. Sonuçlar, gperf’in Şekil 3’teki algoritmayı yürütürken zamanının yaklaşık %90 ila %99’unu tek bir fonksiyon içinde harcadığını göstermiştir.

Bu fonksiyon, Gen_Perf::affects_previous, ilişkili değerlerdeki değişikliklerin daha önce hash’lenmiş anahtar kelimeleri nasıl etkilediğini belirler. Özellikle, program yürütülmesi sırasında ortaya çıkan yinelenen hash değerlerini tespit eder.

Bu fonksiyon çok sık çağrıldığından, yürütme maliyetini en aza indirmek önemlidir. Bu nedenle gperf, bu süreci hızlandırmak için ACE_Bool_Array adlı bir boolean dizi bileşeni kullanır. Sınıfın C++ arayüzü Şekil 7’de gösterilmiştir.

Yalnızca tek bir kopya gerektiğinden, BOOL_ARRAY, ACE Singleton adapter kullanılarak bir Singleton olarak typedef edilmiştir. Bu şablon, Singleton ve Adapter tasarım kalıplarını kullanarak bir sınıfı otomatik biçimde Singleton’a dönüştürür [18].

class ACE_Bool_Array
{
public:
  // Yapıcı
  ACE_Bool_Array(void);

  // Dinamik belleği serbest depoya geri verir
  ~ACE_Bool_Array(void);

  // k elemanlı dinamik bir dizi ayır
  void init(u_int k);

  // <value> değerinin yinelenip yinelenmediğini kontrol eder
  int in_set(u_int value);

  // Ayarlanmış tüm elemanları FALSE olarak yeniden başlatır
  void reset(void);

private:
  // Mevcut nesil sayacı
  u_short generation_number_;

  // Dinamik olarak ayrılmış depolama arabelleği
  u_short *array_;

  // Dinamik olarak ayrılmış dizinin uzunluğu
  u_int size_;
};

// Bir Singleton oluştur
typedef ACE_Singleton<ACE_Bool_Array, ACE_Null_Mutex> BOOL_ARRAY;

Şekil 7: ACE Boolean Dizi Bileşeni

in_set yöntemi, verilen bir ilişkili değerler yapılandırması için yinelenen anahtar kelime hash değerlerini verimli biçimde tespit eder. Bir değer kümede zaten varsa sıfırdan farklı bir değer, aksi halde sıfır döndürür. Bir yinelenme tespit edildiğinde, arama sürecinin sonraki yinelemeleri için dizideki tüm elemanları yeniden “boş” duruma getirmek amacıyla reset yöntemi çağrılır.

Eğer çok sayıda hash çakışması meydana gelirse, reset yöntemi gperf algoritmasının yinelenme tespit ve giderme aşamasında sık sık çalıştırılır. Büyük anahtar dosyalarının işlenmesi (örneğin 1.000’den fazla anahtar kelime içerenler) genellikle toplam anahtar kelime sayısı olan n’den çok daha büyük bir maksimum hash değeri k gerektirir.

Aralığın büyük olması nedeniyle, dizideki tüm elemanları açıkça tekrar boş duruma getirmek maliyetli hale gelir; özellikle de yinelenen hash değerleri açısından gerçekten kontrol edilen anahtar kelime sayısı görece küçük olduğunda.

Bu sorunu çözmek için gperf, tüm diziyi açık biçimde yeniden başlatmadan arama sürecini iyileştiren generation numbering adlı bir desen kullanır.

Nesil Numaralandırma

Nesil numaralandırma şu şekilde çalışır:

1. Bool_Array::init yöntemi k adet unsigned short tamsayı için dinamik alan ayırır ve array_ işaretçisini bu belleğe yönlendirir. Başlangıçta tüm k dizi elemanlarına 0 atanır ("boş" anlamında) ve nesil sayacı 1 olarak ayarlanır.

2. gperf, yinelenen anahtar kelime hash değerlerini tespit etmek için in_set yöntemini kullanır. Eğer array_ içindeki hash(keyword) indeks konumunda saklanan sayı mevcut nesil numarasına eşit değilse, bu hash değeri kümede henüz bulunmamaktadır. Bu durumda o konuma mevcut nesil numarası atanır.

3. Eğer array_[hash(keyword)] değeri nesil numarasına eşitse, bir yinelenme vardır ve algoritmanın çakışmayı gidermek için bazı ilişkili değerleri değiştirmesi gerekir.

4. Bir yinelenme tespit edildiğinde, sonraki yinelemeler için dizi elemanları sıfırlanır. reset yöntemi yalnızca nesil numarasını 1 artırır. Tüm dizi yalnızca nesil numarası unsigned short tamsayısının aralığını aştığında yeniden 0 değerine ayarlanır; bu durum pratikte nadiren gerçekleşir.

Gperf uygulamasının tamamında kullanılan bir tasarım stratejisi şudur: önce temiz bir işlem ve arayüz kümesi belirlemek, ardından uygulamayı kademeli olarak ayarlamak. Nesil numaralandırma örneğinde bu iyileştirme, her sıfırlamada tüm boolean diziyi açıkça temizleyen önceki yönteme kıyasla büyük anahtar dosyaları için gperf’in yürütme süresini ortalama %25 azaltmıştır.

ACE Read Buffer

Gperf girişindeki her satır, isteğe bağlı ilişkili özniteliklerle birlikte tek bir anahtar kelime içerir ve satır sonu karakteri ('\n') ile biter.

Read_Buffer::read üye fonksiyonu, girişten satır sonu ile biten keyfi uzunluktaki bir karakter dizisini dinamik olarak ayrılmış bir arabelleğe kopyalar. Özyinelemeli yardımcı fonksiyon Read_Buffer::rec_read, her giriş satırı için new operatörüne yalnızca bir kez başvurulmasını sağlar. Böylece arabelleklerin tekrar tekrar yeniden ayrılması ve dinamik olarak yeniden boyutlandırılması gerekmez.

Bu sınıf, GNU libg++ stream library [19] ve ACE network programming toolkit [17] içine dahil edilmiştir.

ACE Hash Table

Bu sınıf, double hashing [5] kullanılarak uygulanmış bir arama kümesi sağlar. Program başlatılırken gperf, bu sınıfın bir örneğini kullanarak anahtar dosyası girdilerinden kesin olarak yinelenen hash değerleri üretecek olanları tespit eder.

Bu tür yinelenmeler, anahtar kelimelerin hem aynı keysig değerlerine hem de aynı uzunluklara sahip olduğu durumlarda ortaya çıkar (örneğin Bölüm 4.1.2’de açıklanan double ve delete çakışması).

Kullanıcıya yakın-mükemmel bir hash fonksiyonu istediğini belirtme seçeneği verilmedikçe, yinelenen keysig değerlerine ve aynı uzunluklara sahip anahtar kelimeler için mükemmel bir hash fonksiyonu üretmeye çalışmak sonuç vermez.

5 Deneysel Sonuçlar

Araç tarafından üretilmiş tanıyıcılar yazılım mühendisliği açısından yararlıdır; çünkü geliştirme süresini azaltır ve geliştirme hatalarının ortaya çıkma olasılığını düşürür. Ancak ortaya çıkan yürütülebilir kodun hızı tipik alternatif uygulamalarla rekabet edemiyorsa, üretim ortamındaki uygulamalar için her zaman avantaj sağlamaz.

Gperf tarafından üretilen mükemmel hash fonksiyonlarının etkinliğini diğer yaygın statik arama kümesi uygulamalarıyla karşılaştırmak amacıyla yedi test programı geliştirilmiş ve altı büyük giriş dosyası üzerinde çalıştırılmıştır. Her test programı aynı işlevi gerçekleştirmiştir: GNU içindeki ayrılmış sözcükler için bir tanıyıcı.

Fonksiyon, verilen bir giriş dizesi ayrılmış bir sözcük olarak tanımlanırsa 1, aksi halde 0 döndürür.

Yedi test programı aşağıda açıklanmıştır. Tablo 3’te gösterildiği gibi yürütme süresine göre artan sırada listelenmişlerdir. Test programlarında kullanılan giriş dosyaları Tablo 4’te açıklanmaktadır. Tablo 5 ise her test programının derlenmiş nesne dosyasının bayt cinsinden boyutunu artan sırada göstermektedir (patricia.o ve chash.o dinamik bellek kullandığından, toplam bellek kullanımları alttaki serbest depolama mekanizmasına bağlıdır).

Tablo 4: Her Giriş Dosyası İçin Toplam Tanımlayıcı ve Anahtar Kelime Sayısı

Tablo 5: Nesne Dosyalarının Bayt Cinsinden Boyutu

Program Açıklamaları

trie.exe: trie-gen yardımcı aracı kullanılarak otomatik biçimde oluşturulan tablo tabanlı bir arama trie’sine dayanan programdır. Bu araç GNU libg++ dağıtımıyla birlikte gelir.

flex.exe: "-f" (tablo sıkıştırması yok) seçeneği ile oluşturulmuş bir flex tanıyıcısıdır. Hem flex.exe hem de trie.exe sıkıştırılmamış, deterministik sonlu otomat (DFA) tabanlı tanıyıcılardır. Sıkıştırma kullanılmaması, üretilen tanıyıcıda en yüksek hızı sağlar; ancak bunun karşılığında tablolar çok daha büyük olur. Örneğin sıkıştırılmamış flex.exe programı, sıkıştırılmış comp-flex.exe programından neredeyse 5 kat daha büyüktür; yani 117,808 bayta karşılık 24,416 bayt.

gperf.exe: "-a -D -S 1 -k 1,{{ content }}quot; seçenekleriyle oluşturulmuş bir gperf tanıyıcısıdır. Bu seçenekler şu anlamlara gelir: “ANSI C prototipleri üret (-a), yinelenen anahtar kelimeleri işle (-D), tek bir switch ifadesi kullan (-S 1) ve keysig’i her anahtar kelimenin ilk ve son karakteri olarak belirle.”

chash.exe: AT&T’nin cfront 3.0 C++ derleyicisinde ayrılmış sözcükleri tanımak için kullanılan yapıya benzer dinamik zincirli bir hash tablosu arama fonksiyonudur. Tablonun yük faktörü 0.39’dur ve cfront 3.0 içindeki değerle aynıdır.

patricia.exe: PATRICIA trie tabanlı bir tanıyıcıdır. PATRICIA, “Practical Algorithm to Retrieve Information Coded in Alphanumeric” ifadesinin kısaltmasıdır. Tam bir PATRICIA trie uygulaması GNU libg++ sınıf kütüphanesi dağıtımında mevcuttur [19].

binary.exe: Tam dize karşılaştırmalarının sayısını en aza indirecek şekilde dikkatle kodlanmış bir ikili arama fonksiyonudur.

comp-flex.exe: Varsayılan "-cem" seçenekleri kullanılarak oluşturulmuş bir flex tanıyıcısıdır ve tablolar için en yüksek sıkıştırma düzeyini sağlar. Sıkıştırılmamış flex.exe (daha hızlı ve daha büyük) ile sıkıştırılmış comp-flex.exe (daha küçük fakat çok daha yavaş) arasındaki belirgin zaman/alan değiş tokuşuna dikkat edin.

Bu yedi test programına ek olarak, control.exe adlı basit bir C++ programı G/Ç ek yükünü ölçer ve kontrol eder.

Tablo 3: Ham ve Normalize Edilmiş CPU İşlem Süresi

Yukarıdaki tüm ayrılmış sözcük tanıyıcı programları GNU g++ 2.7.2 derleyicisi ile "-O2 -finline-functions" seçenekleri etkinleştirilerek derlenmiştir. Daha sonra 128 megabayt RAM’e sahip, aksi halde boşta olan bir SPARCstation 20 model 712 üzerinde test edilmiştir.

Testlerde kullanılan altı giriş dosyasının tümü, hem kullanıcı tanımlı tanımlayıcılar hem de g++ ayrılmış sözcükleri dahil olmak üzere çok sayıda sözcük içerir ve her satırda bir sözcük olacak şekilde düzenlenmiştir. Bu biçim, birkaç büyük C++ sisteminin ön işlenmiş kaynak kodu üzerinde şu UNIX komutunun çalıştırılmasıyla otomatik olarak elde edilmiştir:

tr -cs A-Za-z_ '\012'

Bu sistemler arasında ET++ pencereleme araç takımı (ET++.in), NIH sınıf kütüphanesi (NIH.in), GNU g++ 2.7.2 C++ derleyicisi (g++.in), InterViews 2.6 dağıtımındaki idraw şekil çizim aracı (idraw.in), AT&T cfront 3.0 C++ derleyicisi (cfront.in) ve GNU libg++ 2.8 C++ sınıf kütüphanesi (libg++.in) bulunmaktadır. Tablo 4, test giriş dosyaları için tanımlayıcı ve anahtar kelime sayılarının göreli dağılımını göstermektedir.

Tablo 3, her arama kümesi uygulamasının test programlarını yürütürken harcadığı zamanı, artan yürütme süresi sırasına göre göstermektedir. Her sütundaki ilk sayı, her tanıyıcı için kullanıcı-zamanı CPU saniyesini temsil eder. İkinci sayı ise “normalize edilmiş yürütme süresi”dir; yani kullanıcı-zamanı CPU saniyelerinin control.exe programının yürütme süresine oranıdır. Her teknik için normalize edilmiş yürütme süresi, giriş test dosyaları kümesinin tamamında oldukça tutarlıdır ve zamanlama sonuçlarının farklı kaynak kodu girdileri için temsil edici olduğunu gösterir.

Bu deneysel ölçümlerden birkaç sonuç elde edilmektedir:

Zaman/alan değiş tokuşu yaygındır: Sıkıştırılmamış DFA tabanlı trie (trie.exe) ve flex (flex.exe) uygulamaları hem en hızlı hem de en büyük uygulamalardır; bu durum zaman/alan değiş tokuşunu açık biçimde göstermektedir. Zamandan tasarruf etmenin alan tasarrufundan daha önemli olduğu uygulamalar bu yaklaşımlardan yarar sağlayabilir.

gperf her iki dünyanın avantajını da sağlayabilir: trie.exe ve flex.exe tanıyıcıları programcılara alan ile zaman arasında değiş tokuş yapma olanağı sunarken, gperf tarafından üretilen mükemmel hash fonksiyonu gperf.exe zaman ve alan açısından karşılaştırmalı olarak verimlidir.

Bu iddiaya deneysel destek, dinamik bellek ayırmayan programların verilerinden hesaplanabilir; yani trie.exe, flex.exe, gperf.exe, binary.exe ve comp-flex.exe. Yürütülebilir program ek yükünün baytı başına saniyede taranan tanımlayıcı sayısı gperf.exe için 5.6 iken, trie.exe, flex.exe ve comp-flex.exe için 1.0’dan küçüktür.

Gperf bağımsız bir tanıyıcı ürettiğinden, GNU C ve GNU C++ derleyicilerinde bulunanlar gibi elle yazılmış bir sözcüksel çözümleyiciye kolayca dahil edilebilir. Buna karşılık flex veya lex araçlarını bir sözcüksel çözümleyiciye kısmen entegre etmek daha zordur; çünkü genellikle “ya hep ya hiç” biçiminde kullanılırlar. Ayrıca flex ve lex, durum makinesinin boyutu iç DFA durum tabloları için fazla büyük olduğundan, son derece büyük anahtar dosyaları için tanıyıcı üretme yeteneğine sahip değildir.

6 Mevcut Sınırlamalar ve Gelecek Çalışmalar

gperf, uzun yıllardır GNU libg++ kütüphanesi ve ACE ağ programlama araç takımı ile birlikte şu adreste serbestçe dağıtılmaktadır:

www.cs.wustl.edu/~schmidt/ACE.html

Gperf pratikte oldukça yararlı olduğunu göstermiş olsa da bazı sınırlamaları bulunmaktadır. Bu bölüm, mevcut algoritmalarındaki değiş tokuşları ve uzlaşmaları açıklamakta ve nasıl geliştirilebileceğini ana hatlarıyla ortaya koymaktadır. Bununla birlikte gperf açık kaynak yazılım olduğundan, iyileştirmeler ve genişletmeler eklemek oldukça kolaydır.

Diğer bazı hash fonksiyonu üretme algoritmaları, mükemmel veya minimal mükemmel bir çözüm ararken bir tür geri izleme (backtracking) kullanır [6, 8, 9]. Örneğin Cichelli’nin [8] algoritması, tüm n anahtar kelimeyi 1..n aralığında farklı tamsayılara benzersiz biçimde eşleyen bir ilişkili değerler yapılandırması bulmaya özyinelemeli olarak çalışır. Bu yöntemde algoritma, program yürütmesi sırasında herhangi bir noktada mevcut anahtar kelimenin hash değerinin hesaplanması minimal mükemmel tablo boyutu kısıtını aşarsa “geri döner”. Daha sonra Cichelli’nin algoritması seçili hash tablosu girdilerini geri alarak farklı ilişkili değerler atar ve çözüm aramaya devam eder.

Ne yazık ki, geri izlemeli arama süreciyle ilişkili üstel büyüme oranı büyük anahtar dosyaları için basitçe fazla zaman alıcıdır. “Akıllıca yönlendirilen” kapsamlı arama bile birkaç yüz anahtar kelimeden fazlası için hızla pratik olmaktan çıkar.

Şekil 3’teki algoritmayı basitleştirmek ve ortalama durum performansını iyileştirmek için gperf, anahtar kelime hash çakışmaları meydana geldiğinde geri izleme yapmaz. Bu nedenle gperf, her anahtar kelime için benzersiz bir ilişkili değerler yapılandırması bulmadan da tüm anahtar dosyası girdisini işleyebilir; böyle bir yapılandırma mevcut olsa bile. Eğer benzersiz bir yapılandırma bulunamazsa, kullanıcıların iki seçeneği vardır:

1. gperf’e neredeyse mükemmel bir hash fonksiyonu üretmesini söyleyerek bir çözümü garanti altına alabilirler.

6.1 Tavizler ve Uzlaşmalar

Neredeyse mükemmel hash fonksiyonları, gperf’in aksi halde işleyemeyeceği anahtar kelime kümeleri üzerinde çalışmasına izin verir; örneğin anahtar dosyası yinelenen girdiler içeriyorsa veya çok büyük sayıda anahtar kelime varsa. Ortaya çıkan hash fonksiyonu artık “mükemmel” olmasa da, genellikle yalnızca az sayıda yinelenen değer kaldığından anahtar kelime üyeliği sorgularını verimli biçimde işler.

Hem yinelenen anahtar kelime girdileri hem de çözümlenmemiş anahtar kelime çakışmaları, Bölüm 3’te açıklanan switch tabanlı şemanın genelleştirilmesiyle ele alınır. gperf, yinelenen anahtar kelimeleri bir eşdeğerlik sınıfının üyeleri olarak ele alır ve benzersiz olmayan anahtar kelime hash değerlerini işlemek için bir case etiketi içinde ardışık if-else karşılaştırmaları içeren switch deyimi kodu üretir.

Örneğin, gperf varsayılan keysig seçim komut satırı seçeneği "-k 1,{{ content }}quot; ile C++ ayrılmış kelimeleri içeren bir anahtar dosyası üzerinde çalıştırıldığında, delete ve double anahtar kelimeleri arasında bir hash çakışması oluşur ve bu durum mükemmel bir hash fonksiyonunun oluşmasını engeller. "-D" seçeneğinin kullanılması, double dışındaki tüm anahtar kelimeler için en fazla bir dize karşılaştırmasına izin veren neredeyse mükemmel bir hash fonksiyonu üretir; double ise iki karşılaştırmadan sonra tanınır.

{
  char *rw;
  ...
  switch (hash (str, len)) {
    ...
    case 46:
      rw = "delete";
      if (*str == *rw
          && !strcmp (str + 1, rw + 1, len - 1))
        return rw;

      rw = "double";
      if (*str == *rw
          && !strcmp (str + 1, rw + 1, len - 1))
        return rw;
      return 0;

    case 47:
      rw = "default"; break;

    case 49:
      rw = "void"; break;
    ...
  }

  if (*str == *rw
      && !strcmp (str + 1, rw + 1, len - 1))
    return rw;

  return 0;
}

Aynı konuma hashlenen yinelenen anahtar kelimeler üzerinde basit bir doğrusal arama gerçekleştirilir. Doğrusal arama etkilidir çünkü çoğu anahtar kelime hâlâ yalnızca bir dize karşılaştırması gerektirir.

Yinelenen hash değerleri için destek, büyük girdi anahtar dosyaları (örneğin sözlükler), oldukça benzer anahtar kelime kümeleri (örneğin assembler komut anımsatıcıları) ve ikincil anahtarlar gibi çeşitli durumlarda yararlıdır. Son durumda, birincil anahtar kelimeler yalnızca ikincil anahtar karşılaştırmalarıyla ayırt edilebiliyorsa, kullanıcı arama anahtarını tamamen belirsizlikten arındırmak için üretilen kodu elle ya da otomatik bir betik aracılığıyla düzenleyebilir.

Mükemmel hash fonksiyonu üretim sürecinin tamamen otomatikleştirilmesi gperf’in en önemli tamamlanmamış genişletmesidir. Bir yaklaşım, gperf’in mevcut algoritmasını daha kapsamlı yöntemlerle [9, 7] değiştirmektir. gperf’in nesne yönelimli program tasarımı sayesinde bu tür değişiklikler genel program yapısını bozmayacaktır. Mükemmel hash fonksiyonu üretim modülü olan GenPerf sınıfı, diğer program bileşenlerinden bağımsızdır; gperf’in toplam kaynak kod satırlarının yalnızca yaklaşık yüzde 10’unu temsil eder.

Daha kapsamlı fakat hesaplama açısından daha pahalı bir yaklaşım, başlangıçta kullanılan ve hesaplama maliyeti daha düşük olan geri izleme içermeyen ilk geçiş mükemmel bir hash fonksiyonu üretmeyi başaramadığında geri izleme stratejisine geçmek olabilir. Arama kümelerinin nispeten küçük olduğu birçok yaygın kullanımda program geri izleme ek yükü oluşmadan başarıyla çalışacaktır. Uygulamada, önerilen bu değişikliklerin yararlılığı hâlâ açık bir sorudur.

Bir başka potansiyel olarak değerli özellik, gperf’in anahtar kelime dizin konumlarını otomatik olarak seçmesini sağlamaktır. Bu, kullanıcıların zaman veya bellek açısından verimli hash fonksiyonlarını hızlı ve kolay biçimde üretmesine yardımcı olacaktır. Şu anda kullanıcı varsayılan davranışı kullanmak ya da bu konumları komut satırı argümanlarıyla açıkça seçmek zorundadır. Son olarak, gperf’in çıktı fonksiyonları Java, Ada, Smalltalk, Module 3, Eiffel vb. gibi diğer diller için kod üretecek şekilde genişletilebilir.

6.2 İyileştirmeler ve Genişletmeler

gperf başlangıçta derleyiciler ve yorumlayıcı ayrılmış kelime kümeleri için anahtar kelime tanıyıcılarının oluşturulmasını otomatikleştirmek amacıyla tasarlanmıştır. Bu makalede açıklanan çeşitli özellikler, GNU derleyicilerinde kullanılmasıyla da görüldüğü üzere, bu hedefe ulaşmasını sağlar.

Buna ek olarak gperf aşağıdaki uygulamalarda da kullanılmıştır:

• TAO CORBA IDL derleyicisi [4], sunucu tarafı iskeletleri tarafından kullanılan işlem yönlendirme tablolarını [21] üretmek için gperf kullanır.
• National Library of Medicine tarafından sürdürülen ve biyomedikal literatüre ait büyük bir bibliyografik veritabanı olan MEDLINE’da dergi makalesi atıflarını indekslemek için kullanılan 15.400 adet “Medical Subject Headings” için bir hash fonksiyonu. Bu hash fonksiyonunun üretilmesi bir SPARC 20 iş istasyonunda yaklaşık 10 dakika CPU zamanı alır.

7 Sonuç Açıklamaları

Şekil 8: Neredeyse Mükemmel Arama Tablosu Parçası

• GNU indent C kodu yeniden biçimlendirme programı; burada mükemmel hashing kullanılması programı ortalama yüzde 10 hızlandırmıştır.

• Çift hassasiyetli FORTRAN kaynak kodunu tek hassasiyete dönüştüren (veya tersini yapan) kamu malı bir program, argümanlarının türlerine bağlı olan fonksiyon adlarını değiştirmek için gperf kullanır; örneğin LINPACK kıyaslamasında sgefa yerine dgefa kullanılması gibi. Bir fonksiyona karşılık gelen her ad gperf aracılığıyla tanınır ve uygun hassasiyet için olan sürümüyle değiştirilir.

• Bir konuşma sentezleyici sistemi; burada sentezleyici ile disk tabanlı daha büyük bir sözlük arasında bir önbellek bulunur. Bir kelime gperf kullanılarak hashlenir ve eğer kelime zaten önbellekteyse sözlükte arama yapılmaz.

Otomatik statik arama kümesi üreticileri pratikte iyi performans gösterdiğinden ve yaygın biçimde ücretsiz olarak bulunabildiğinden, çoğu uygulama için anahtar kelime tanıma fonksiyonlarını elle kodlamak için çok az teşvik olduğu görülmektedir.

Kaynaklar

[1] M. Lesk ve E. Schmidt, LEX – Bir Sözcüksel Çözümleyici Üreteci. Bell Laboratories, Murray Hill, N.J., Unix Programmers Manual baskısı.

[2] S. Johnson, YACC – Bir Başka Derleyici Derleyicisi. Bell Laboratories, Murray Hill, N.J., Unix Programmers Manual baskısı.

[3] R. M. Stallman, Using and Porting GNU CC. Free Software Foundation, GCC 2.7.2 baskısı.

[4] A. Gokhale, D. C. Schmidt ve S. Moyer, “DCE’den CORBA’ya Geçişin Otomatikleştirilmesi için Araçlar,” Proceedings of ISS 97: World Telecommunications Congress içinde, (Toronto, Kanada), IEEE Communications Society, Eylül 1997.

[5] D. E. Knuth, The Art of Computer Programming, cilt 1: Searching and Sorting. Reading, MA: Addison-Wesley, 1973.

[6] C. R. Cook ve R. R. Oldehoeft, “Harf Odaklı Minimal Mükemmel Hash Fonksiyonu,” SIGPLAN Notices, cilt 17, s. 18–27, Eyl. 1982.

[7] A. Tharp ve M. Brain, “Mükemmel Hashing’de Desen Çakışmalarını Ortadan Kaldırmak için Trie Kullanımı,” IEEE Transactions on Knowledge and Data Engineering, cilt 6, no. 2, s. 329–347, 1994.

[8] R. J. Cichelli, “Minimal Mükemmel Hash Fonksiyonlarını Basit Hale Getirmek,” Communications of the ACM, cilt 21, no. 1, s. 17–19, 1980.

[9] M. Brain ve A. Tharp, “Büyük Kelime Kümelerinin Neredeyse Mükemmel Hashlenmesi,” Software – Practice and Experience, cilt 19, no. 10, s. 967–978, 1989.

[10] R. Sprugnoli, “Mükemmel Hash Fonksiyonları: Statik Kümeler için Tek Sorgulu Erişim Yöntemi,” Communications of the ACM, s. 841–850, Kas. 1977.

[11] G. V. Cormack, R. Horspool ve M. Kaiserwerth, “Pratik Mükemmel Hashing,” Computer Journal, cilt 28, s. 54–58, Oca. 1985.

[12] M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. M. auf der Heid, H. Rohnert ve R. Tarjan, “Dinamik Mükemmel Hashing: Üst ve Alt Sınırlar,” SIAM Journal of Computing, cilt 23, s. 738–761, Ağu. 1994.

[13] G. Jaeschke, “Reciprocal Hashing: Minimal Mükemmel Hash Fonksiyonları Üretmek için Bir Yöntem,” Communications of the ACM, cilt 24, s. 829–833, Ara. 1981.

[14] T. Sager, “Minimal Mükemmel Hash Fonksiyonları için Polinom Zamanlı Bir Üreteç,” Communications of the ACM, cilt 28, s. 523–532, Ara. 1985.

[15] C. C. Chang, “Sıralı Minimal Mükemmel Hash Fonksiyonları Oluşturmak için Bir Şema,” Information Sciences, cilt 39, s. 187–195, 1986.

[16] Bjarne Stroustrup, The C++ Programming Language, 3. Baskı. Addison-Wesley, 1991.

[17] D. C. Schmidt, “ACE: Dağıtık Uygulamalar Geliştirmek için Nesne Yönelimli Bir Çerçeve,” Proceedings of the th USENIX C++ Technical Conference içinde, (Cambridge, Massachusetts), USENIX Association, Nisan 1994.

[18] E. Gamma, R. Helm, R. Johnson ve J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software. Reading, MA: Addison-Wesley, 1995.

[19] D. Lea, “libg++, the GNU C++ Library,” Proceedings of the 1st USENIX C++ Conference içinde, (Denver, CO), s. 243–256, USENIX, Eki. 1988.

[20] J. Kegler, “Minimal Mükemmel Hash Fonksiyonları için Polinom Zamanlı Bir Üreteç,” Communications of the ACM, cilt 29, no. 6, s. 556–557, 1986.

[21] A. Gokhale ve D. C. Schmidt, “Gerçek Zamanlı CORBA için Demultiplexing Stratejilerinin Performansının Değerlendirilmesi,” Proceedings of GLOBECOM ’97 içinde, (Phoenix, AZ), IEEE, Kasım 1997.