Çok Hızlı Bir Lexer Uygulama Stratejisi

• purple-garden dili için ultra hızlı bir Lexer’ın doğrudan nasıl tasarlanıp uygulandığına dair stratejiler ve ölçülmüş performans verileri paylaşılıyor
• Threaded Lexing (atlama tablosu tabanlı), 0 kopya pencere dizgileri, interning, bump allocator gibi çeşitli optimizasyon teknikleri uygulanıyor
• Token hashing ve önceden hash’lenmiş anahtar kelime karşılaştırmaları ile ayrıştırma hızı en üst düzeye çıkarılıyor; basit bir switch ifadesine kıyasla atlama tablosu CPU önbelleği verimliliğinde daha iyi sonuç veriyor
• Dosyanın tamamını mmap ile eşleme ve dinamik tahsisi en aza indirme sayesinde büyük girdilerde IO ve bellek yönetimi maliyeti ciddi biçimde düşürülüyor
• Mevcut popüler lexer’larla (ör. flex, handcoded) karşılaştırıldığında 10 katın üzerinde daha hızlı işleme gösteriliyor; parsing/runtime aşamalarının her biri için mikro benchmark değerleri sunuluyor

---

Lexing ve derleme hattına genel bakış

• Lexer (tokenizer), girdi dizgesini anlamlı token listelerine dönüştürür; ardından parser bunu alıp AST (soyut sözdizimi ağacı) üretir
• purple-garden dilindeki token tasarımı, TokenType enum’u ile yalnızca dizge ve tür bilgisini tutan minimal bir yapıyı korur

Minimal Lexer tasarımı ve kod örneği

• Lexer yapısı yalnızca girdi dizgesini ve mevcut konumu saklar
• Her karaktere göre token üretmek için switch ifadesi kullanılır
• Debugging için tür-dizge eşleme dizisi ve türe göre başlatma yaklaşımı kullanılır

Threaded Lexing (atlama tablosu tabanlı)

• switch ifadesi yerine token ayrımını işlemek için atlama tablosu (jump table) kullanılır (computed goto)
  • 256 baytlık bir dizide karakter değerleri indeks olarak kullanılarak ilgili işleme etiketleri eşlenir
  • Gerçek kod dallanmasında JUMP_TARGET makrosu ile doğrudan dallanma gerçekleştirilir
• Avantajları:
  • Önbellek kaçırmalarının azalması ve dal tahmini optimizasyonu gibi nedenlerle daha hızlı çalışır
• Dezavantajları:
  • MSVC desteği yoktur (yalnızca Clang, GCC), hata ayıklaması zordur

Bellek yönetimi ve Allocator soyutlaması

• bump allocator dahil çeşitli bellek tahsis stratejileri için bir arayüz tanımlanır (Allocator yapısı)
• CALL makrosu ile ayrıntılı loglama ve context iletimi sadeleştirilir
• Gerçek tahsis/serbest bırakma/istatistik yapıları ve kod örnekleri sunulur

0 kopya, pencere tabanlı dizge işleme

• C’de verimli işleme için Str yapısı (pointer, uzunluk, hash) tanıtılır
• slice, concat, eq, hashing, sayı dönüştürme gibi işlevler doğrudan uygulanır
• Dizge slice’ları yalnızca pointer kaydırılarak anında oluşturulur; bellek tahsisi gerekmez
• Sayı dönüştürme de karakter-tamsayı dönüşüm algoritması doğrudan uygulanarak yapılır

Token hashing ve önceden hash’lenmiş anahtar kelime karşılaştırmaları

• Token oluşturulurken hash (FNV-1a) hesaplanarak tekrar eden karşılaştırmalar ve interning optimize edilir
• true/false gibi sabit anahtar kelimeler, hash değerleriyle anında karşılaştırılarak dallandırılır (performans artışı)
• is_alphanum (alfabetik/sayısal/özel karakter ayrımı) da bit işlemleri ve lookup yaklaşımıyla optimize edilir

Sayı ayrıştırmayı verimli hale getirme ve bunu derleme aşamasına taşıma

• Lexer, sayı token’larında yalnızca pencere ve hash bilgisini saklar; gerçek tamsayı/kayan nokta dönüşümü derleme aşamasında tekrar olmadan yalnızca bir kez yapılır
• Tekrarlanan sayısal değerlerin ayrıştırılmasında toplam throughput’un %64’ten fazla arttığı doğrulanır

Büyük dosya IO’sunu hızlandırma

• Mevcut fread yaklaşımı yerine tüm dosya mmap ile doğrudan belleğe eşlenir
• IO_read_file_to_string fonksiyonu tüm girdiyi mmap ile alır; büyük dosyalarda 6 ila 35 kat performans artışı gözlenir

Gerçek benchmark’lar ve performans karşılaştırması

• Dizüstü bilgisayarda: 1.000.000+ satır, 25MB girdi için 44ms (yalnızca tokenization)
• Masaüstü bilgisayarda: aynı girdi için 30ms elde edilir (en fazla 848MB/s)
• Diğer lexer’larla karşılaştırıldığında 10 katın üzerinde hız gösterilir (0,3 saniye vs 2~13 saniye)
• Mikro benchmark’larda her optimizasyonun etkisi sayısallaştırılır (ör. bump allocator kullanımı 1,58 kat, dizgilerde 0 alloc 1,4~1,5 kat, sayı ayrıştırmayı derleme aşamasına taşıma 2,8 kat vb.)

Uygulama stratejisinin özeti

• Atlama tablosu tabanlı doğrudan dallanma (threaded lexing)
• 0 kopya pencere token yapısı
• Sabit token interning
• bump allocator tabanlı bellek yönetimi
• Token hashing ve önceden hash’lenmiş karşılaştırmalar
• Sayı ve dizge token’larında gecikmeli parsing ve interning
• Büyük dosyalar için mmap işleme
• Gelecek çalışmalar olarak SIMD kullanımı, daha hızlı hashing algoritmaları, bellek hizalama ve prefetch, girdi bazlı atlama tablosu optimizasyonu önerilir