GitHub, büyük/küçük harf katlama veya Case Folding işlemini, yazılım döngüsünü ilk ASCII olmayan baytta durmayacak, bunun yerine veri bağımlı kontrol dallanmaları olmadan tüm arabelleği tarayacak şekilde yeniden tasarlayarak tek çekirdekte saniyede 45 gigabaytın üzerinde çalıştırmayı başardı. Şirket bu işlemi, 180 milyondan fazla depoyu ve 480 terabayttan fazla kaynak kodunu dizine ekleyen Blackbird kaynak kodu arama motorunda kullanıyor.
Alexander Neubeck ve Greg Orzell, bu tasarımın ayrıntılarını 31 Temmuz 2026'da GitHub blogunda yayımlanan bir yazıda sundu. Yazı ayrıca sonucun casefold adlı açık kaynaklı bir Rust kütüphanesinde kullanıma sunulduğunu duyurdu.
Büyük/küçük harf katlama yalnızca küçük harfe dönüştürme değildir
Arama motorları ve metin eşleştiren araçlar, büyük/küçük harf bakımından farklı olan dizelerin karşılaştırmada eşit olmasını sağlayan standart bir gösterime ihtiyaç duyar. Bu ihtiyaç aramada, büyük/küçük harfe duyarsız düzenli ifadelerde, kullanıcı adlarında ve ana bilgisayar adlarında görülür.
Ancak metni küçük harfe dönüştürmek aynı sonucu vermez. Küçük harfe dönüştürme dile ve bağlama bağlı olabilir; örneğin Yunanca sigma harfinin kelime sonunda ve kelime içinde farklı biçimlere sahip olması veya Türkçedeki I harfinin kurallarının farklı olması gibi. Büyük/küçük harf katlama ise karşılaştırma için tasarlandığından dilden ve bağlamdan bağımsızdır. Ayrıca Almanca ß harfi, Türkçe İ harfi ve son Yunanca sigma gibi durumlarda da sonuç farklıdır.
Kütüphane, Unicode karakter veritabanına ait CaseFolding.txt dosyasındaki C ve S durumlarına göre bire bir basit katlama gerçekleştirir. ß harfinin ss'ye dönüştürülmesi gibi birden çok karakter içeren katlama işlemlerini veya Türkçeye özgü katlama işlemlerini gerçekleştirmez.
Döngüyü yavaşlatan optimizasyonun kaldırılması
Kaynak kodu çoğunlukla ASCII karakterlerden oluştuğu için en hızlı yol, A ile Z arasındaki büyük Latin harflerini küçük harflere dönüştürmeye odaklanır. Sezgisel tasarım, ASCII olmayan bir bayt bulur bulmaz duruyor, ardından metnin geri kalanını Unicode yoluna aktarıyordu. Ancak Apple M4 işlemcisindeki testler, bu yöntemin saniyede yaklaşık 3 gigabaytı aşamadığını gösterdi.
Başlıca neden döngü içindeki kontrol dallanmalarıydı. Her baytı test edip erkenden durmak yerine algoritma, tüm baytların en yüksek bitlerini tek bir değişkende topluyor, ardından tarama tamamlandıktan sonra sonucu test ediyor. Baytın büyük harf aralığında olup olmadığının testi ise A karakterinin çıkarılması, taşmanın sarılması ve sonucun 26 sayısıyla karşılaştırılması yoluyla aritmetik olarak gerçekleştiriliyor. Ardından beşinci biti ayarlamak için bir aritmetik maske kullanılıyor; böylece büyük harf, dallanma veya koşullu yazma olmadan küçük harfe dönüştürülüyor.
Bu yapı, LLVM derleyicisinin Apple M4 üzerinde NEON kullanarak her seferinde 16 baytı işleyen vektörleştirilmiş talimatlar oluşturmasına olanak tanıyor. Sonuç saniyede 45 gigabaytı aşıyor ve bellek bant genişliği sınırına yaklaşıyor. GitHub'ın ölçümleri, erken çıkışın kaldırılmasının vektörleştirmeyi mümkün kılan etken olduğunu gösteriyor; veriye dayalı çıkış korunduğunda, döngünün geri kalanı dallanmasız hâle gelse bile vektörleştirilmiş talimatlar oluşturulamıyor.
Birleşik tarama neden her zaman daha hızlı değildir?
GitHub, önce ASCII'yi bloklar hâlinde tarayan, ardından ASCII önekini dönüştüren bir orta yol çözümünü test etti. Bu yöntem verileri iki kez okuyor, ancak ilk ASCII olmayan blokta durabilme yeteneğini korurken saniyede yaklaşık 23 gigabayta ulaştı; bu da saf döngüden çok daha hızlıydı.
Öte yandan tarama ve dönüştürmeyi 16 baytlık bloklar üzerinde çalışan tek bir döngüde birleştirmek daha yavaştı: iki geçişli çözümün saniyede 23 gigabaytına karşılık yaklaşık 8,7 gigabayta ulaştı. Yazıya göre her bloktan sonra gerçekleşen erken çıkış dalı, derleyicinin döngüyü açmasını veya okuma, test etme, dönüştürme ve yazma arasındaki bekleme süresini gizlemesini engelliyor. Bu nedenle iki temiz ve vektörleştirilebilir döngü, verilere daha az kez dokunan ancak içeriğe bağlı bir dal içeren tek bir döngüden daha iyi performans gösterdi.
Bellek ayırmalarının azaltılması
simple_fold işlevi, bir String'i sahiplik yoluyla alıyor; bu da arabelleğini değiştirmesine ve doğrudan geri döndürmesine olanak tanıyor. Metin tamamen ASCII ise aynı bellek, karakterler yerinde dönüştürüldükten sonra ikinci bir arabellek veya ek kopyalama olmadan geri döndürülüyor.
ASCII olmayan karakterler bulunduğunda algoritma, uzunluğu veya içeriği değişen bir karaktere ulaşana kadar yeni bir arabellek oluşturmuyor. Yazı, çoğu katlama işleminin UTF-8 uzunluğunu koruduğunu veya azalttığını, ancak U+023A ve U+023E karakterlerinin her birinin uzunluğunun iki bayttan üç bayta çıkabildiğini açıklıyor. Bu nedenle algoritma, arabelleği kademeli olarak büyütüp verileri yeniden kopyalamak yerine, giriş uzunluğunun yaklaşık 1,5 katına eşit azami kapasiteyi tek seferde ayırıyor.
Ayrıca değişmeyen bayt dizilerini bayt bayt kopyalamak yerine copy_nonoverlapping kullanarak taşıyor. CJK, Hangul, Kana, Arapça, İbranice ve semboller gibi Latin dışı bazı metinler, katlanması gereken karakterler içermediklerinde özgün ayırmalarında tutuluyor.
Unicode'u bayt uzayında işleme
Unicode 16.0, 1484 basit katlama işlemi içeriyor; ancak GitHub, katlanabilir karakterlerin 64 kod noktası büyüklüğündeki sayfalarda kümelenmesinden yararlanarak tablosunu 1776 bayta sıkıştırdı. Bir karakterin katlanmaya ihtiyaç duyup duymadığını test etmek için algoritma bir bit haritası kullanıyor; karşılık gelen bit etkin değilse karakter, UTF-8'i çözmeden veya bir karma tablosunda arama yapmadan hemen reddediliyor.
Katlama işlemleri içeren sayfaların içinde algoritma, her kod noktası için ayrı bir kayıt yerine bitişik aralıklar depoluyor. Aralıklar başlangıç, bitiş, adım ve fark ile tanımlanıyor; böylece yaklaşık 1484 işlem, 59 sayfaya dağıtılmış 238 aralığa indirgeniyor. Uygun aralığı belirlemek için aynı anda sekiz anahtar üzerinde paralel karşılaştırma da kullanılıyor.
Aralık bulunduktan sonra katlanmış karakterler, karakteri bir kod noktasına çözüp yeniden kodlamak yerine, aralığa özgü bir sabitle UTF-8 düzeyinde iki baytın toplanmasıyla hesaplanıyor. Bu, uzunluk değişikliklerinin ele alınmasını sağlıyor; örneğin kelvin işareti U+212A'nın üç bayttan tek baytlık k harfine dönüştürülmesi veya U+023A'nın üç baytlık bir karaktere dönüştürülmesi gibi.
Bu yöntem, girdinin geçerli ve kısaltılmış UTF-8 olduğunu varsayıyor; Rust'taki String ve str türleri bu varsayımı garanti ediyor. Başka kaynaklardan gelen ham veriler ise bu hesaplamalar kullanılmadan önce doğrulanmalı veya normalleştirilmelidir.
Sonuç ve ölçümlerin sınırları
Yaygın ASCII durumunda kütüphanenin hızı saniyede 45 gigabaytı aşıyor ve yazıda yer alan ölçümlere göre tamamen eşdeğer olmayan str::to_lowercase işlevinden %50'den fazla daha hızlı. Karakterlerinin çoğunun katlanması gereken en kötü giriş durumlarında, bayt uzayındaki hesaplamalara dayanan çözümler, UTF-8'i çözüp yeniden kodlayan optimize edilmiş yoldan yaklaşık iki kat daha hızlıydı.
GitHub, sayıların ve karşılaştırma oranlarının yol gösterici olduğunu, işlemciler arasında kelimesi kelimesine aktarılabilir olmadığını belirtiyor; çünkü bunlar otomatik vektörleştirmeye, SWAR'a, little-endian bayt hesaplamalarına, ayrıca bellek bant genişliğine ve işlemci mimarisine bağlı. Yazı fikri iki ilkeyle özetliyor: yaygın yolu dallanma olmadan tamamen taramak ve Unicode'a özgü nadir yolu karakterleri çözüp yeniden kodlamak yerine bayt uzayında gerçekleştirmek.