GitHub Casefold: Kaynak Kodda Bellek Hızında Katlama

⏱️ 10 dk okuma📅 1 Ağustos 2026

GitHub’ın kod arama motoru Blackbird, 180 milyonun üzerinde depoyu ve 480 TB’ı aşan kaynak kodu indeksliyor. Bu ölçekte her bayt, önce arama indeksine eklenmeden önce, sonra da her olası sorgu sonucu için tekrar “case folding” (büyük-küçük harf katlama) işleminden geçiyor. Sıradan görünen bu işlemin milisaniyeleri bu boyutta ciddi bir maliyete dönüşüyor. GitHub mühendisi Alexander Neubeck, işlemi bellek hızına yaklaştırdıkları çalışmayı ve ortaya çıkan casefold adlı Rust kütüphanesini anlattı. Yazının en şaşırtıcı bulgusu sezgiye aykırı: ASCII hızlı yolundaki en büyük kazanç bir optimizasyonu eklemekten değil, kaldırmaktan geldi.

Katlama, küçük harfe çevirmek değildir

İlk refleks str::to_lowercase kullanmak olsa da küçük harfe çevirme (lowercasing) ile katlama (case folding) farklı amaçlara hizmet eder:

Küçük harfe çevirme görüntüleme içindir; yerel ayara ve bağlama duyarlıdır. Yunanca son sigma kelime sonunda ς, başka yerde σ olur; Türkçe “I” harfinin küçültülmesi İngilizce’dekinden farklıdır.
Case folding ise karşılaştırma içindir; kasıtlı olarak bağlamdan ve yerel ayardan bağımsızdır. Amaç, A’nın B’ye katlanıyorsa B’nin de her yerelde A’ya katlanmasını sağlayan simetrik ve kararlı bir ilişki kurmak. Unicode Karakter Veritabanı bunun için ayrı bir CaseFolding.txt yayınlar.

İki işlem ß, İ, son sigma gibi karakterlerde ayrışır; küçük harfe çevirmeyi katlama yerine kullanmak sessizce yanlış eşleşmelere yol açar. GitHub’ın kütüphanesi yalnızca 1’e 1 basit katlamaları (CaseFolding.txt içindeki C ve S statüsündekileri) uyguluyor; ß → ss gibi “tam” çok karakterli katlamaları veya Türkçe’ye özgü noktalı İ katlamalarını kapsamıyor. Bu, ripgrep gibi araçlarla tutarlılığı korumak için bilinçli bir tercih olarak sunuluyor.

Sezgiye aykırı temel: Erken durma

Kaynak kod büyük ölçüde ASCII olduğundan asıl kritik nokta, ASCII yolunu bellek hızında çalıştırmak. ASCII bir harfin katlanması da son derece basit: A..=Z aralığı a..=z‘ye eşlenir, geri kalanı olduğu gibi kalır. Böyle bir döngü için akla ilk gelen kod “ilk ASCII olmayan bayta rastlayınca döngüyü kır ve Unicode yoluna devret” mantığıyla yazılır:

let bytes = s.as_bytes_mut();
for (i, b) in bytes.iter_mut().enumerate() {
if *b >= 0x80 {
break; // ASCII olmayan bayt: gerisini Unicode yoluna bırak
}
if b.is_ascii_uppercase() {
*b += 32; // 'A'..='Z' → 'a'..='z'
}
}

Bu kod Apple M4’te yaklaşık 3 GiB/s hıza ulaşıyor. Kulağa iyi geliyor ama “optimum” düşünüldüğünde 15 kattan fazla geride. Nedeni, dalların (if) varlığı derleyicinin döngüyü vektörleştirmesini engelliyor.

Dalları tek tek kaldırmak

Ekipteki yaklaşım her dalı ayıklamak oldu:

if b >= 0x80 { break } yerine hiç durmayıp tüm baytları bir biriktiriciye OR’lamak ve döngüden sonra bir kez kontrol etmek: high_bit_acc |= *b. Aynı bilgi, gövdede sıfır dal.
A..=Z aralık testini aritmetiğe çevirmek: b.wrapping_sub(b'A') < 26 tam olarak bu aralıkta doğrudur ve dalsız bir 0/1 maskesi üretir.
Koşullu yazımı maskeye katmak: | (is_upper << 5) ile 5. bit ayarlanır; büyük harfi küçük harfe çevirir, diğerlerinde etkisizdir. Bayt her zaman yazılır, dallanma yoktur.

let mut high_bit_acc: u8 = 0;
for b in &mut bytes {
high_bit_acc |= *b;
let is_upper = b.wrapping_sub(b'A') < 26;
*b |= u8::from(is_upper) << 5;
}
if high_bit_acc & 0x80 == 0 {
return bytes; // Saf ASCII: yerinde katlandı, ikinci tampon gerekmedi
}

Veriye bağlı akış kontrolü kalmayan bu döngüyü LLVM önemsizce vektörleştiriyor: 16 baytlık NEON komutlarıyla hız 45 GiB/s‘nin üzerine çıkıyor, yani pratikte bellek bant genişliği. Üstelik high_bit_acc sayesinde döngü biter bitmez ASCII olmayan bir iş kalıp kalmadığı da biliniyor.

Adım adım kazanımlar (Apple M4, 5,7 KB tampon, saf ASCII)

Sürüm	Verim	Vektörleşme
Naif (break + dallı test)	3,1 GiB/s	Yok
Dalsız test/yazım, break duruyor	2,6 GiB/s	Yok
Erken çıkış (break) kaldırıldı	7,6 GiB/s	Kısmi (25 vektör komutu)
Dalsız test + dalsız yazım (döngü)	>45 GiB/s	Tam (41 vektör komutu)

Buradaki kritik ders: Veriye bağlı erken çıkış tek başına vektörleşmeyi bloklamaya yetiyor. Bir başka önemli gözlem, gövdeyi dalsız yapıp break’i tutmak (2,6 GiB/s) naif dallı sürümden (3,1 GiB/s) daha yavaş çıkıyor. Sebebi derleme çıktısında saklı: Dallı sürümde yazma yalnızca büyük harf tespit edildiğinde gerçekleşiyor; gerçek metnin büyük çoğunluğunu oluşturan küçük harf, rakam ve boşluklarda iyi tahmin edilen dal bu yazımı atlıyor. Dalsız sürüm ise her iterasyonda koşulsuz yazma yaparak gereksiz bellek trafiği üretiyor. Yani “dalsız gövde”, ancak vektörleşmeyi tetiklediği zaman kazandırıyor; skaler kodda tek başına maliyet yaratabilir.

Standart kütüphane yolu ve iki geçişli yaklaşım

Ara bir çözüm de var: [u8]::is_ascii gibi yordamlar veriyi bayt bayt değil, 64 bitlik makine sözcükleri halinde tarar; iki u64 şeridini OR’layıp tek bir & 0x8080_8080_8080_8080 maskesiyle yüksek bitleri kontrol eder. ASCII ön ekini bu yolla bulup ardından dalsız (vektörleşebilir) dönüşümü uygulamak mümkün. Bu yaklaşım erken çıkış yeteneğini koruyor ama veriyi iki kez okuyor (bir tarama, bir dönüştürme) ve yaklaşık 23 GiB/s ile tek geçişli dalsız süpürmenin yarısı kadar hızda kalıyor. Yine de naif break döngüsünün yaklaşık 7 katı; genel amaçlı bir varsayılan olarak sağlam.

İki geçişi tek geçişte birleştirmek daha hızlı olmaz mı? Ölçümde bu kaynaşık (fused) yaklaşım ~2,6 kat daha yavaş çıkıyor: 8,7 GiB/s’e karşılık iki geçişli 23 GiB/s. İç blok dönüştürücü tek bir 16 baytlık vektör işlemine derlense de her 16 baytta bir veriye bağlı erken çıkış dalı, derleyicinin bloklar arasında unroll veya software pipelining yapmasını engelliyor. Her iterasyon yükleme → test → dal → dönüştürme → yazma gecikmesini gizleyemeden ödüyor. Sonuç aynı: Sıcak döngüde dal düşmandır.

Heap’ten kaçınmak

45 GiB/s’nin diğer yüzü, gereksiz tahsisatı sıfıra indirmek. simple_fold girdi String‘i değer olarak alıyor; böylece heap tamponunun sahibi olup üzerinde değişiklik yapabiliyor. OR biriktiricisinin yüksek biti temizse girdi zaten saf ASCII olarak yerinde katlanmıştır ve aynı tahsisat ikinci bir tampon veya kopya olmadan geri döner. Aksi halde memchr ile ilk ASCII olmayan bayta atlanıyor ve buradan itibaren taranıyor; farklı baytlara katlanan bir karakter görülene kadar çıktı tamponu boşta bekliyor (null yazma imleci). Çok baytlı içeriği hiç katlanmayan metinler (CJK, Hangul, Kana, Arapça, İbranice, semboller) orijinal tahsisatı hiç dokunulmadan geri dönduruyor.

Neden yerinde değil, ikinci tampon?

Çünkü katlama diziyi uzatabiliyor. Katlamaların neredeyse tamamı UTF-8 uzunluğunu korur ya da kısaltır; ama iki istisna büyür: U+023A (Ⱥ) ve U+023E (Ɀ) 2 baytlık karakterler olup 3 baytlık karakterlere (ⱥ, ɀ) katlanır. Böyle bir karakter göründüğü anda çıktı artık girdinin baytlarına sığmaz.

Tampon en kötü duruma göre tek seferde tahsis ediliyor; kademeli reserve çağrıları kapasite kontrolü, ara sıra yeniden tahsis, önceden yazılmış her şeyin kopyalanması ve ek kayıt tutma demektir. Tek seferlik tahsisat ise ham bir yazma imlecinin bu yüklerden bağımsız çalışmasına izin verir. Yukarıdaki iki istisna büyüme oranına da üst sınır veriyor: Her 2 girdi baytı en fazla 3 çıktı baytı üretir; bu da çıktıyı girdinin 1,5 katıyla sınırlar:

out = Vec::with_capacity(bytes.len() + bytes.len() / 2 + 4);

Bundan sonra döngü ham bir işaretçi üzerinden kapasite kontrolü yapmadan yazıyor ve sonda bir kez set_len çağrılıyor. İki katlanmış karakter arasındaki değişmemiş bayt dizisi tek bir copy_nonoverlapping ile taşınıyor. Her katlama, imleci yalnızca katlanmış uzunluk kadar (1–4) ilerletmeden önce koşulsuzca 4 baytlık bir little-endian sözcüğü yazıyor; böylece çıktı uzunluğu üzerindeki bir dal sıcak yoldan kaldırılıyor. Tahsisattaki + 4 ise son karakterin fazla yazımını güvenli kılan tampon.

Unicode yolunu da ucuzlatmak

Bir karakter gerçekten katlandığında bile UTF-8 çözme, hash araması, yeniden kodlama üçlüsüne düşmek istenmiyor. Unicode 16.0’da 1484 basit katlama eşlemesi var, ama bunlar son derece seyrek ve son derece yapılandırılmış bir ilişki. Dört gözlem bunları 1776 bayta sıkıştırıyor ve katlamayı tam karakter çözmeden yapmayı mümkün kılıyor.

Öncelik “katlama var mı?” sorusunun ucuzluğu

ASCII olmayan yolda bile karakterlerin büyük çoğunluğu katlanmıyor. Yani sıcak işlem aslında “bu karakter katlanır mı?” ve cevap neredeyse her zaman hayır. Bu olumsuz test mümkün olduğu kadar ucuz olmalı. Bu öncelik, HashMap<u32, u32>‘un neden yanlış bir yapı olduğunu da açıklıyor: Hash haritaları isabet için optimize edilmiştir; ıskalama hash haritasının en sevmediği sorgudur, çünkü yokluğu kanıtlamak için hala hash hesaplaması ve prob dizisinde yürüme gerekir.

1. Katlanabilir kod noktaları 64’lük “sayfalarda” kümelenir

Kod uzayı 64 kod noktalı sayfalara dilimlendiğinde, ~1484 katlama olası ~1960 sayfadan yalnızca 59‘una dokunuyor. Sayfa başına bir bitlik bir varlık bitmap’i olumsuz testi tek başına yanıtlıyor: Temiz bir bit “kesinlikle katlanmaz” demek. Ayarlanmış bir bit görüldüğünde ise ikinci bir yapıya, kümülatif popcount yan tablosuna başvuruluyor. Bu yan tablo sayfanın “sıra numarasını” veriyor ve yalnızca dolu sayfalar için yer tutuyor.

let (word_idx, bit_idx, c_len) = if lead < 0xE0 {
(0usize, lead & 0x1F, 2usize)
} else if lead < 0xF0 {
((lead & 0x0F) as usize, bytes[read + 1] & 0x3F, 3)
} else {
(
(((lead & 0x07) as usize) << 6) | (bytes[read + 1] & 0x3F) as usize,
bytes[read + 2] & 0x3F,
4usize,
)
};
if word_idx >= PAGE_BITMAP.len() || (PAGE_BITMAP[word_idx] >> bit_idx) & 1 == 0 {
read += c_len;
continue;
}

word_idx yalnızca lead bayta (ve dört baytlık dizilerde ilk devam bayta) bağlı olduğu için bitmap yüklemesi erken başlatılabiliyor.

2. Sayfa içinde katlamalar diziler halinde gelir

Bitişik kod noktaları çoğu zaman aynı deltayı paylaşır: A–Z’nin tamamı +32; Latin Extended ise 0x0100, 0x0102, 0x0104… gibi her ikinci kod noktasının katlandığı alternatif dizilerle doludur. Kod noktası başına giriş yerine diziler (start, end, stride, delta) saklanıyor; 1 bitlik bir stride bayrağı hem ardışık hem her ikinci durumu kapsıyor. Bu aralık sıkıştırması ~1484 tekil katlamayı 59 sayfa üzerinde yalnızca 238 diziye indiriyor (sayfa başına ~4). Sayfa içi arama artık düzinelerce değil, birkaç kayda bakıyor. Bu, Go’nun unicode paketinden ödünç alınmış bir kodlama; CaseRange kayıtları Lo/Hi aralık artı büyük/küçük deltalar tutar, UpperLower nöbetçisi ise alternatif blokları işaretler. Diziler sayfa sınırlarında bölünüyor.

3. Bir dizi kaydı iki temiz bayt

Her iki uç bir sayfa içinde 6 bite sığdığı için iki diziye ayrılıyor: RUN_END_LOW[i] = end & 0x3F tarama anahtarı, RUN_START_STRIDE[i] = (start & 0x3F) | ((stride − 1) << 6) yalnızca isabet halinde okunuyor. Anahtar tek bir temiz bayt olduğundan sayfa içi arama genişletilebiliyor: cp & 0x3F anahtarı dizilerle tek tek karşılaştırmak yerine, 8 end_low baytı bir u64‘e yükleniyor ve tek bir dalsız SWAR adımıyla hepsi aynı anda test ediliyor.

#[inline]
fn scan_end_low(lo: usize, n: usize, low_v: u8) -> usize {
const HIGH: u64 = 0x8080_8080_8080_8080;
const ONES: u64 = 0x0101_0101_0101_0101;
let bcast = (low_v as u64).wrapping_mul(ONES);
let mut base = 0;
while base < n {
let chunk = u64::from_le_bytes(
RUN_END_LOW[lo + base..lo + base + 8]
.try_into()
.expect("8-byte slice"),
);
let ge = (chunk | HIGH).wrapping_sub(bcast) & HIGH;
if ge != 0 {
let j = base + (ge.trailing_zeros() / 8) as usize;
return if j < n { j } else { n };
}
base += 8;
}
n
}

Bir sayfada ortalama ~4 dizi bulunuyor; 8 genişliğindeki bu karşılaştırma aramaların neredeyse tamamını tek adımda çözüyor. 30 diziye sahip talihsiz bir sayfada karşılaştırma kısa bir döngüye giriyor, ama bu döngü tüm Unicode’da yalnızca tek bir sayfada ve yalnızca birkaç kez tetikleniyor. Her durumda dizi başına dal yok, kod noktası yeniden inşası da yok.

4. Katlama, little-endian bir bayt toplamıdır

Little-endian bir makinede katlanmış karakterin UTF-8 baytları u32 olarak okunduğunda, kaynak baytların u32‘sine dizi başına sabit bir değer ekleyerek elde ediliyor. Paralel bir BYTE_DELTA[i] tablosu, tüm katlamayı maskelenmiş bir yükleme, tek bir wrapping_add ve 4 baytlık bir yazmaya indirgiyor:

let word = u32::from_le_bytes(next_four_bytes) & length_mask;
let folded = word.wrapping_add(BYTE_DELTA[i]);
write_u32_le(dst, folded);
dst += utf8_len(folded);

Bu satırlardaki iki uzunluk (kaynak karakter için length_mask ve hedef için “katlanmış uzunluk kadar ilerle”) bir başka küçük numaradan geliyor: Bir UTF-8 dizisinin uzunluğu, lead baytının üst dört biti tarafından belirlenir. 16 olası uzunluk, tek bir 64 bitlik sabite (0x4322_1111_1111_1111) her biri bir nibble olacak şekilde paketleniyor; uzunluk artık bir kaydırma ve maske işlemine iniyor.

Neden önemli?

Case folding; kod arama motorlarından regex (?i) bayrağına, büyük/küçük harf duyarsız kullanıcı adı ve host adı karşılaştırmalarına kadar pek çok yerde yatay bir işlem. GitHub’ın deneyimi, “temel operasyonların” da doğru bakış açısıyla ele alındığında bir mikromimari egzersizine dönüşebileceğini gösteriyor. Buradaki en akılda kalıcı ders belki de en beklenmedik olanı: Sıcak döngüde erken çıkış refleksinin kendisi, vektörleşmenin önündeki en büyük engel olabiliyor.

Kaynaklar ve İleri Okuma

github.blog

Bu yazı yapay zeka (büyük dil modelleri) ile hazırlanmış, insan editör tarafından incelenmiştir. İçerik üretim sürecimiz.

Aşkın KILIÇYazar

20+ yıl deneyimli Azure Solutions Architect. Microsoft sertifikalı bulut mimari ve DevOps danışmanı. Azure, yapay zekâ ve bulut teknolojileri üzerine Türkçe teknik içerikler üretiyor.

AZ-305AZ-104AZ-500AZ-400DP-203AI-102