3 komutla artık yıl olup olmadığını kontrol etmek

• Yalnızca 3 CPU komutu ile artık yılı belirleyen bir fonksiyon uygulanıyor
• Bu yöntem, geleneksel dallanma olmadan bit işlemleri ve çarpma kullanarak çalışıyor
• Bu yaklaşım 0~102499 yıl aralığında doğru sonuç veriyor
• Benchmark sonuçlarına göre mevcut yönteme kıyasla yaklaşık 3,8 kat daha hızlı performans sunuyor

---

Genel bakış ve problemin tanımı

• 0 ile 102499 arasındaki yıllar için, yalnızca 3 CPU komutu kullanarak artık yılı belirleyen bir fonksiyon
  • Kullanılan gerçek fonksiyonun yapısı ((y * 1073750999) & 3221352463) <= 126976 şeklinde
• Bu bit-twiddling tekniğinin mantığı, çalışma biçimi ve pratik faydası açıklanıyor

Geleneksel artık yıl belirleme yöntemi

• Genelde artık yıl kontrolü bölme(modulo) ve koşullu dallanma ile uygulanır
  • 4'e tam bölünüp bölünmediği, 100'e bölünüp bölünmediği ve 400'e tam bölünüp bölünmediği kontrol edilir
  • Örnek kod:

    if ((y % 4) != 0) return false  
    if ((y % 100) != 0) return true  
    if ((y % 400) == 0) return true  
    return false  
    

Standart yaklaşımın optimizasyonu

• (y % 100) kontrolü (y % 25) ile, (y % 400) kontrolü ise (y % 16) ile değiştirilebilir
  • Bunun nedeni, daha önce zaten 4'e bölme kontrolünün yapılmış olması ve bunun 25 ile 16 çarpan ilişkisine dönüştürülebilmesi
• (y % 25) işlemini bölme kullanmadan çarpma ve karşılaştırmaya dönüştüren sihirli bir sabit
  • Örnek: x * 3264175145 > 171798691 biçimine dönüştürülebilir
• Bir bit maskesi eklenerek (y & 3) ya da (y & 15) ile 4 veya 16'ya bölünebilirlik kontrolü yapılabilir
• Derleyiciler bu dönüşümleri otomatikleştirebilir, ancak başka dillerde doğrudan da kullanılabilir

Dallanmasız(branchless) uygulama yöntemi

• Dallanmasız bir biçime de dönüştürülebilir:

  return !(y & ((y % 25) ? 3 : 15))  
  

• Bu tür bir yaklaşım, code golf gibi kod uzunluğunu azaltmaya odaklı durumlara uygundur

Sihirli sabitleri bulmak: bit-twiddling yaklaşımı

• Artık yıl denklemini daha da basitleştirmek için kombinatoryal arama ve SMT Solver olan Z3 kullanılıyor
  • Biçim: ((y * f) & m) <= t
• Koşulları sağlayan f, m, t sabitleri Z3 ile aranıyor
  • 0~102499 aralığında doğru sonuç verebilen değerler bulunuyor
  • Nihai sonuç (y * 1073750999) & 3221352463 <= 126976 oluyor

Fonksiyonun mantığı ve iç yapısının açıklaması

• Sabitler ikili düzeyde analiz edilerek üç ana bit bölgesine, A, B, C, ayrılıyor
  • Her bölgedeki bit durumu, artık yıl belirlemenin 3 koşulunu kapsıyor
• Fonksiyonun mantıksal ayrıştırması:
  • A bölgesi: (y % 4) != 0 olup olmadığını da içerecek şekilde 4'ün katı olma koşulunu kontrol ediyor
  • B bölgesi: (y % 100) != 0 durumunu farklı desenlerle (ör. son iki hanesi 14, 57, 71 vb.) filtreliyor
  • C bölgesi: (y % 16) == 0, yani 16'nın katı olma durumunu kontrol ediyor
• Çarpmanın, aslında kalan hesabı yapmadan çeşitli koşulları birleştirmeyi nasıl başardığı açıklanıyor
  • Sihirli sabitle çarpıldığında 100'ün katları gibi değerlerde ayırt edici bit desenleri oluşuyor
  • Buna ek olarak, çarpma hatası ve çok basamaklı sayı desenlerinin ortaya çıktığı matematiksel iç yapı da inceleniyor

Ek aralıklar ve bit genişliğini artırma olasılığı

• 64 bit'e genişletildiğinde uygun sihirli sabit kombinasyonlarını arama yöntemi de sunuluyor
  • f, m, t değerleri değiştirilerek en geniş aralık bulunabilir
  • StackExchange üzerinde de en iyi kombinasyonlar ve Z3 ile ispat örnekleri yer alıyor

Benchmark ve gerçek performans karşılaştırması

• Benchmark sonuçları:
  • 2025 gibi öngörülebilir değerlerde 0.65~0.69ns ile neredeyse fark yok
  • Rastgele girdilerde is_leap_year_fast yaklaşık 3,8 kat daha hızlı performans gösteriyor
  • Girdi desenine bağlı olarak dallanma(branching) yaklaşımı öngörülemez olduğunda ciddi avantaj sağlıyor

Sonuç ve pratikte uygulanabilirlik

• Gerçek uygulamalarda değerler öngörülebilirse kazanç sınırlı, ancak büyük miktarda rastgele veri durumunda çok yararlı
• Python veya C# gibi dillerde standart kütüphaneyi değiştirmek için gerçekçi bütün program benchmark'ı gerekli
• Fikir ve uygulama yöntemi başlı başına ilgi çekici ve bazı durumlarda performans açısından cazip bir çözüm

[chickendreamtree]

Fast inverse sqrt'ı hatırlatan bir yazı

[GN⁺]

Hacker News görüşleri

• Modern derleyicilerde, örneğin gcc ya da clang'da, is_leap_year1 gibi bir kodun is_leap_year2 gibi otomatik optimize edilmesine şaşırdım; bu yüzden C kaynak kodu aşamasında elle optimizasyon yapmaya çok gerek olmadığı hissi var, ama diğer diller için hâlâ faydalı olabilir, özellikle de cal programının güncel sürüm kaynak kodunda leap year kontrolünün çok basit ele alınması etkileyici
  • Linux kodunun üç ardışık koşulu her seferinde tersine çevirip varsayılan dönüş değeri kullanmaması çok daha anlaşılır geldi; böyle karmaşık kod yapıları olduğunda debug ederken insanı gerçekten çıldırtıyor
• ((y * 1073750999) & 3221352463) <= 126976 kodunun nasıl çalıştığına dair açıklamanın karmaşık olmasına hiç şaşırmadım, hatta bu gayet doğal
• Anlaşılması zor magic number optimizasyon tekniklerini gerçekten seviyorum; bunları her gördüğümde, geçmişte assembly ile inner loop yazarken ne kadar çok optimizasyon tekniğini kaçırdığımı merak ediyorum, böyle teknikleri toplayan bir derleme varsa paylaşılmasını isterim
  • Çeşitli bit manipulation trick derlemelerine bağlantılar paylaşıldı; UNIX tarzı karşılaştırmalar için verimli CMP(X, Y) makrosu, signum fonksiyonu optimizasyon örnekleri, Motorola 68000 için assembly kodu örnekleri, OpenSolaris kökenli bit makroları derlemesi gibi farklı optimizasyon tekniklerine linkler verildi; Open Solaris blogunun artık olmamasına dair üzüntü de belirtildi, kod optimizasyonuna ilgi duyanlara tavsiye edildi
  • "Hacker's Delight" kitabı önerildi; çeşitli bit trick'leri ve düşük seviye optimizasyon teknikleriyle dolu
  • supercompilation tekniğine bakma önerisi
  • Eskiden bu teknikleri kaçırmış değildiniz; o zamanlar çarpma işlemi o kadar pahalıydı ki, bunlar zaten optimizasyonun kendisiydi
• Leap year kontrolünün bu kadar ilginç olacağını hiç beklemiyordum; muhtemelen düşük seviye programcılar bu tür trick'leri çok önce bulmuştu ama kayda geçirmemiş olabilirler diye düşünüyorum, bunların hâlâ eski kodların içinde saklı olabileceği hissi var, böyle bir teknik koleksiyonu olsa gerçekten incelemek isterim
  • 80'lerde z80 üzerinde evde kendi kendime öğrendiğim şeyler vardı ama çoğunu unuttum; bazen 20'li yaşlardaki çocuklarıma gösterince sanki sihir yapıyormuşum gibi oluyor
• 6000 yılından önceki leap year'ları bilmeniz gerekiyorsa, kendi yaptığım etkileşimli hesap makinesi ve görselleştirme aracını kullanabilirsiniz; makine komutu sayısı biraz fazla olsa da binlerce hesabı çok hızlı yapabiliyor, matematiksel trick'ler de ayrıca etkileyici
• Bit manipulation bölümünü okurken "acaba solver kullanılamaz mı" diye düşündüm ve yazarın gerçekten tam da bunu kullanmış olmasına şaşırdım, bu titiz yaklaşımı takdir ettim
• Böyle bir leap year kontrol fonksiyonunun current-time-api'ye eklenmesi iyi olabilir
• Sayılara ikili sistemde bakınca ilginç desenler görünüyor; 2 hariç tüm asal sayıların 1 ile bitmesi ilginçti
  • Eğlenceli görünebilir ama tüm tek sayılar 1 ile biter ve asal sayılar da özünde 2 hariç çift olamayacağı için, bunda özel bir anlam göremediğini söyleyen bir itiraz vardı
• Leap year meselesinde 0'ın olmadığına dair bir yorum vardı; aslında "0 yılı" yok, 1 BC'den doğrudan 1 AD'ye geçiliyor, dolayısıyla 0 kontrolünün bir anlamı olmadığı söyleniyor
  • Yazının en başında, leap year algoritmasının proleptic Gregoryen takvim ve astronomik yıl numaralandırmasını varsaydığı açıklanıyor; bu koşul olmazsa leap year kontrolü yerelden yere karmaşık hâle gelir
  • Astronomik yıl numaralandırması kullanılırsa 0 yılı ortaya çıkar ve yıl/ay yönetimi gibi işlerde bu yaklaşım aslında daha temizdir; iç verinin astronomik gösterimde tutulup dış çıktının yalnızca BCE/CE'ye dönüştürülmesi önerildi
  • Gregoryen takvimin kabulünden önce takvimlerin temeli zaten belirsizdi ve bölgeden bölgeye değişiyordu; 1582'de bir günde on günün atlandığı "10 gün silinmesi" de yaşandığı için, o tarihten önceki tarih hesaplarına güvenilemez; Roma döneminde rahipler leap year'ları batıl inanç ya da rüşvet gibi nedenlerle keyfi biçimde ayarladığı için konu daha da karmaşık
  • ISO8601 standardı 0 yılına izin verir ve astronomik takvimde 0 yılı 1 BC anlamına gelir; tüm BCE yılları birer yıl daha kaydırılmış olur
• Kaynak kodunun gerçekten kahkaha attırdığı anlar nadirdir, bu yüzden bu çok keyifli bir deneyimdi