Memeriksa Tahun Kabisat dengan 3 Instruksi

• Mengimplementasikan fungsi untuk menentukan tahun kabisat hanya dengan 3 instruksi CPU
• Metode ini bekerja tanpa percabangan tradisional dengan memanfaatkan operasi bit dan perkalian
• Pendekatan ini akurat untuk rentang tahun 0~102499
• Hasil benchmark menunjukkan performa sekitar 3,8 kali lebih cepat dibanding metode lama

---

Gambaran umum dan perumusan masalah

• Untuk tahun antara 0 dan 102499, ada fungsi yang menentukan tahun kabisat hanya dengan 3 instruksi CPU
  • Fungsi yang digunakan adalah struktur ((y * 1073750999) & 3221352463) <= 126976
• Dijelaskan prinsip, cara kerja, dan kegunaan praktis dari teknik bit-twiddling ini

Metode tradisional untuk menentukan tahun kabisat

• Biasanya penentuan tahun kabisat diimplementasikan dengan pembagian modulo dan percabangan kondisi
  • Memeriksa apakah habis dibagi 4, tidak habis dibagi 100, atau habis dibagi 400
  • Contoh kode:

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

Optimasi pendekatan standar

• Pemeriksaan (y % 100) dapat diganti dengan (y % 25), dan (y % 400) dengan (y % 16)
  • Alasannya, karena sebelumnya sudah dibagi 4, hubungan perkalian 25 dan 16 bisa digunakan
• Operasi (y % 25) dapat diubah menjadi perkalian dan perbandingan tanpa pembagian menggunakan konstanta ajaib
  • Contoh: bisa diubah menjadi x * 3264175145 > 171798691
• Dengan menambahkan bitmask, (y & 3) atau (y & 15) dapat menggantikan pembagian oleh 4 atau 16
• Compiler dapat mengotomatiskan transformasi ini, tetapi pendekatan tersebut juga bisa dimanfaatkan langsung di bahasa lain

Implementasi tanpa percabangan (branchless)

• Juga dapat diubah ke bentuk tanpa percabangan:

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

• Pendekatan seperti ini cocok untuk code golf, misalnya ketika ingin mempersingkat panjang kode

Mencari konstanta ajaib: pendekatan bit-twiddling

• Untuk membuat ekspresi penentuan tahun kabisat lebih sederhana, digunakan pencarian kombinatorial dan Z3, sebuah SMT Solver
  • Bentuknya: ((y * f) & m) <= t
• Konstanta f, m, t yang memenuhi syarat dicari dengan Z3
  • Ditemukan nilai yang menghasilkan hasil akurat pada rentang 0~102499
  • Hasil akhirnya adalah (y * 1073750999) & 3221352463 <= 126976

Penjelasan prinsip fungsi dan struktur internal

• Konstanta dianalisis dalam bentuk biner lalu dibagi menjadi tiga area bit utama: A, B, C
  • Bergantung pada status bit di tiap area, tiga syarat penentuan tahun kabisat dapat dicakup
• Pemecahan logika fungsi:
  • Area A: memeriksa kondisi kelipatan 4, termasuk apakah (y % 4) != 0
  • Area B: memfilter apakah (y % 100) != 0 dengan berbagai pola, misalnya akhiran 14, 57, 71, dan lain-lain
  • Area C: memeriksa apakah (y % 16) == 0, yaitu apakah merupakan kelipatan 16
• Dijelaskan prinsip bahwa perkalian secara efektif menggabungkan berbagai kondisi tanpa benar-benar menghitung sisa bagi
  • Saat mengalikan dengan konstanta ajaib, pola bit khusus terbentuk pada kelipatan 100 dan kasus lain
  • Selain itu, juga dibahas struktur matematis internal seperti galat perkalian dan pola angka multigit yang muncul

Kemungkinan perluasan rentang dan lebar bit

• Jika diperluas ke 64-bit, juga dijelaskan cara mencari kombinasi konstanta ajaib yang sesuai
  • Dengan mencoba berbagai nilai f, m, t, dapat dicari rentang terpanjang
  • Di StackExchange juga ada contoh kombinasi optimal dan pembuktian dengan Z3

Benchmark dan perbandingan performa nyata

• Hasil benchmark:
  • Untuk nilai yang dapat diprediksi seperti 2025, hampir tidak ada perbedaan pada 0.65~0.69ns
  • Untuk input acak, is_leap_year_fast menunjukkan performa sekitar 3,8 kali lebih cepat
  • Jika pola input membuat percabangan sulit diprediksi, pendekatan branching ini memiliki keuntungan besar

Kesimpulan dan apakah layak diterapkan

• Dalam aplikasi nyata, keuntungannya kecil jika nilainya mudah diprediksi, tetapi sangat berguna dalam situasi dengan data acak dalam jumlah besar
• Jika ingin mengganti pustaka standar nyata seperti di Python atau C#, perlu dilakukan benchmark program secara keseluruhan yang realistis
• Ide dan metode implementasinya sendiri menarik, dan dalam situasi tertentu merupakan solusi yang atraktif dari sisi performa

[chickendreamtree]

Tulisan yang mengingatkan pada fast inverse sqrt

[GN⁺]

Opini Hacker News

• Terkejut mengetahui bahwa compiler terbaru seperti gcc atau clang secara otomatis mengoptimalkan kode seperti is_leap_year1 menjadi seperti is_leap_year2, jadi rasanya tidak terlalu perlu melakukan optimisasi langsung di level source C, meskipun ini mungkin masih berguna di bahasa lain, terutama karena menarik melihat versi terbaru source code cal menangani pemeriksaan tahun kabisat dengan sangat sederhana
  • Saya suka bahwa kode linux jauh lebih mudah dipahami karena membalik tiga kondisi berurutan setiap kali dan tidak memakai nilai balik default, pengalaman men-debug struktur kode rumit seperti ini benar-benar bisa bikin gila
• Sama sekali tidak heran bahwa penjelasan tentang cara kerja kode ((y * 1073750999) & 3221352463) <= 126976 pasti rumit; justru itu memang wajar
• Sangat suka teknik optimisasi dengan magic number yang sulit dipahami; setiap kali melihat hal seperti ini, jadi penasaran berapa banyak teknik optimisasi yang dulu terlewat saat menulis inner loop dalam assembly, dan kalau ada koleksi teknik seperti ini rasanya ingin dibagikan
  • Membagikan tautan kumpulan berbagai trik manipulasi bit, makro CMP(X, Y) yang efisien untuk perbandingan gaya UNIX, contoh optimisasi fungsi signum, contoh kode assembly untuk Motorola 68000, kumpulan makro bit yang berasal dari OpenSolaris, dan berbagai teknik optimisasi lain, sambil menyesalkan blog Open Solaris sudah hilang; direkomendasikan untuk orang yang tertarik pada optimisasi kode
  • Merekomendasikan buku "Hacker's Delight", yang penuh dengan berbagai trik bit dan teknik optimisasi tingkat rendah
  • Menyarankan untuk mencari teknik supercompilation
  • Dulu bukan berarti teknik seperti ini terlewat; pada masa itu perkalian sangat mahal, jadi hal seperti itulah yang justru disebut optimisasi
• Sama sekali tidak menyangka bahwa pemeriksaan tahun kabisat bisa semenarik ini; mungkin programmer level rendah sudah lama menemukan trik seperti ini tetapi tidak meninggalkan catatan, dan rasanya mungkin saja hal seperti ini masih tersembunyi di dalam kode lama; kalau ada koleksi teknik seperti ini benar-benar ingin dieksplorasi
  • Dulu pernah belajar sendiri hal-hal seperti ini di rumah dengan z80 pada era 80-an, tetapi sekarang sebagian besar sudah lupa; kadang saat ditunjukkan ke anak-anak yang sudah berusia 20-an, rasanya seperti sedang melakukan sulap
• Jika perlu mengetahui tahun kabisat sebelum tahun 6000, gunakan kalkulator interaktif dan alat visualisasi buatan sendiri; meskipun jumlah instruksi mesin sedikit lebih banyak, alat itu bisa memproses ribuan perhitungan dengan sangat cepat, dan trik matematikanya juga mengagumkan
• Saat membaca bab manipulasi bit, sempat terpikir "jangan-jangan bisa pakai solver", lalu terkejut karena ternyata penulis memang benar-benar memakai cara itu; puas dengan pendekatan yang sangat teliti
• Ada usulan bahwa fungsi pemeriksaan tahun kabisat seperti ini sebaiknya ditambahkan ke current-time-api
• Kalau angka dilihat dalam bentuk biner, terlihat pola-pola yang menarik; menarik bahwa semua bilangan prima selain 2 berakhir dengan 1
  • Memang mungkin terlihat menarik, tetapi semua bilangan ganjil berakhir dengan 1, dan karena bilangan prima pada dasarnya tidak bisa genap selain 2, muncul pertanyaan apakah itu sebenarnya punya makna khusus
• Muncul komentar bahwa dalam masalah tahun kabisat tidak ada 0; sebenarnya tidak ada "tahun 0", karena dari 1 BC langsung berpindah ke 1 AD, jadi pemeriksaan 0 tidak ada artinya
  • Jika melihat bagian paling awal tulisan, dijelaskan bahwa prasyarat perancangan algoritme tahun kabisat ini adalah kalender Gregorian proleptik dan penomoran tahun astronomis; ditekankan bahwa tanpa syarat ini, pemeriksaan tahun kabisat akan menjadi rumit tergantung locale
  • Jika memakai notasi tahun astronomis, maka tahun 0 memang muncul, dan untuk pengelolaan tahun/bulan dan semacamnya justru lebih rapi diperlakukan seperti itu; usulnya, data internal memakai notasi astronomis dan hanya output eksternal yang dikonversi ke BCE/CE
  • Kalender sebelum adopsi Gregorian sendiri punya dasar yang kabur dan berbeda-beda menurut wilayah; pada tahun 1582 bahkan ada "penghapusan 10 hari" ketika sepuluh hari langsung dilewati, jadi operasi tanggal sebelum itu tidak bisa diandalkan, dan imam pada era Romawi juga kadang menyesuaikan tahun kabisat secara sewenang-wenang karena takhayul atau suap, sehingga makin rumit
  • Standar ISO8601 mengizinkan tahun 0, dan dalam kalender astronomis tahun 0 berarti 1 BC; semua tahun BCE bergeser dengan offset -1
• Jarang sekali source code benar-benar membuat orang tertawa terbahak-bahak, jadi ini pengalaman yang sangat menyenangkan