- Membagikan strategi perancangan dan implementasi langsung Lexer super cepat untuk bahasa purple-garden, beserta data performa hasil pengukuran nyata
- Menerapkan berbagai teknik optimasi seperti Threaded Lexing (berbasis jump table), 0-copy·window string, interning, dan bump allocator
- Memaksimalkan kecepatan parsing melalui hashing token dan perbandingan hash kamus keyword yang sudah dihitung sebelumnya; dibanding
switch sederhana, jump table lebih unggul dalam efisiensi cache CPU
- Memetakan seluruh file dengan mmap dan meminimalkan alokasi dinamis untuk memangkas biaya IO·manajemen memori secara signifikan pada input berukuran besar
- Dibuktikan hingga lebih dari 10x lebih cepat dibanding lexer populer yang sudah ada (mis. flex, handcoded), dengan angka microbenchmark untuk tiap tahap parsing/runtime
Gambaran umum lexing dan pipeline kompilasi
- Lexer (tokenizer) mengubah string input menjadi daftar token yang bermakna, lalu parser menerimanya untuk membangun AST (abstract syntax tree)
- Desain token pada bahasa purple-garden mempertahankan struktur minimal dengan enum TokenType dan hanya menyimpan informasi string·tipe
Desain lexer minimal dan contoh kode
- Struct lexer hanya menyimpan string input dan posisi saat ini
- Menggunakan
switch untuk membuat token berdasarkan tiap karakter
- Untuk debugging, digunakan array pemetaan tipe-ke-string serta inisialisasi per tipe
Threaded Lexing (berbasis jump table)
- Menggunakan jump table alih-alih
switch untuk menangani pemisahan token (computed goto)
- Dalam array 256 byte, tiap nilai karakter dipakai sebagai indeks untuk memetakan label penanganan masing-masing
- Pada percabangan kode nyata, makro
JUMP_TARGET langsung mengeksekusi lompatan
- Kelebihan:
- Eksekusi lebih cepat berkat pengurangan cache miss dan optimasi branch prediction
- Kekurangan:
- Tidak didukung MSVC (hanya Clang, GCC), dan lebih sulit di-debug
Manajemen memori dan abstraksi allocator
- Mendefinisikan antarmuka untuk berbagai strategi alokasi memori seperti bump allocator (struct Allocator)
- Menyederhanakan log verbose dan penerusan context dengan makro
CALL
- Menyajikan contoh struktur dan kode untuk alokasi·dealokasi·statistik aktual
Pemrosesan string 0-copy berbasis window
- Untuk pemrosesan efisien di C, diperkenalkan struct Str (pointer, panjang, hash)
- Mengimplementasikan sendiri slice, concat, eq, hashing, konversi angka, dan lainnya
- Slice string dapat dibuat seketika hanya dengan menggeser pointer, tanpa alokasi memori
- Konversi angka juga memakai algoritme konversi karakter-ke-integer yang diimplementasikan langsung
Hashing token dan perbandingan keyword dengan hash prahitung
- Menghitung hash (FNV-1a) saat token dibuat untuk mengoptimalkan perbandingan berulang dan interning
- Untuk keyword konstan seperti
true/false, percabangan dilakukan langsung lewat nilai hash (meningkatkan performa)
is_alphanum (pemeriksaan alfabet/angka/karakter khusus) juga dioptimalkan lewat operasi bit dan lookup
Efisiensi parsing angka dan pemindahan ke tahap kompilasi
- Di lexer, token angka hanya menyimpan window·hash; konversi integer/floating-point yang sebenarnya dilakukan sekali saja di tahap kompilasi tanpa duplikasi
- Saat mem-parsing nilai numerik yang berulang, terkonfirmasi peningkatan throughput lebih dari 64%
Percepatan IO file besar
- Alih-alih metode
fread yang ada, digunakan mmap untuk memetakan seluruh file langsung ke memori
- Fungsi
IO_read_file_to_string me-mmap seluruh input, dan pada data besar terbukti memberi peningkatan performa 6~35x
Benchmark nyata dan perbandingan performa
- Pada laptop: input 25MB dengan 1,000,000+ baris mencapai 44ms (hanya tokenisasi)
- Pada desktop: untuk input yang sama, tercapai 30ms (maksimum 848MB/s)
- Dibanding lexer lain, hingga lebih dari 10x lebih cepat (
0.3 detik vs 2~13 detik)
- Dalam microbenchmark, dampak tiap optimasi dikuantifikasi (mis. penggunaan bump allocator 1.58x, string 0 alloc 1.4~1.5x, memindahkan parsing angka ke tahap kompilasi 2.8x, dll.)
Ringkasan strategi implementasi
- Percabangan langsung berbasis jump table (threaded lexing)
- Struktur token window 0-copy
- Interning token konstan
- Manajemen memori berbasis bump allocator
- Hashing token dan perbandingan hash prahitung
- Lazy parsing dan interning untuk token angka·string
- Penanganan file besar dengan
mmap
- Sebagai pekerjaan lanjutan, diusulkan pemanfaatan SIMD, algoritme hashing yang lebih cepat, penyelarasan memori·prefetch, dan optimasi jump table per jenis input
Belum ada komentar.