3 कमांड में leap year की जाँच करना

• केवल 3 CPU instructions से leap year पहचानने वाला एक function implement किया गया है
• यह तरीका bit operations और multiplication का उपयोग करके पारंपरिक branching के बिना काम करता है
• यह तरीका 0~102499 वर्ष की range में सटीक है
• benchmark परिणामों में मौजूदा तरीके की तुलना में लगभग 3.8 गुना तेज प्रदर्शन दिखा

---

अवलोकन और समस्या

• 0 से 102499 के बीच के वर्षों के लिए, केवल 3 CPU instructions का उपयोग करके leap year जाँचने वाला function
  • उपयोग किया गया वास्तविक function ((y * 1073750999) & 3221352463) <= 126976 संरचना का है
• इस bit-twiddling तकनीक के सिद्धांत, कार्यविधि और व्यावहारिक उपयोगिता की व्याख्या

पारंपरिक leap year जाँच तरीका

• आम तौर पर leap year जाँच division (modulo) और conditional branching से implement की जाती है
  • जाँचा जाता है कि क्या 4 से पूरी तरह विभाजित होता है, 100 से विभाजित नहीं होता, और 400 से विभाजित होता है
  • उदाहरण कोड:

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

मानक approach का optimization

• (y % 100) जाँच को (y % 25) से, और (y % 400) जाँच को (y % 16) से बदला जा सकता है
  • कारण यह है कि पहले ही 4 से भाग दिया जा चुका है, इसलिए 25 और 16 के गुणन संबंध का उपयोग किया जा सकता है
• (y % 25) operation को division के बिना multiplication और comparison में बदलने वाला magic constant
  • उदाहरण: x * 3264175145 > 171798691 में बदला जा सकता है
• bitmask जोड़कर (y & 3) या (y & 15) से 4 या 16 से divisibility की जाँच की जा सकती है
• compiler ऐसे transformations को स्वचालित कर सकता है, लेकिन इन्हें सीधे दूसरी languages में भी उपयोग किया जा सकता है

branchless implementation

• इसे branchless रूप में भी बदला जा सकता है:

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

• ऐसा तरीका code golf जैसी स्थितियों में code length घटाने के लिए उपयुक्त है

magic constants की खोज: bit-twiddling approach

• leap year expression को और सरल बनाने के लिए combinatorial search और SMT Solver Z3 का उपयोग किया गया
  • रूप: ((y * f) & m) <= t
• शर्तों को पूरा करने वाले constants f, m, t को Z3 से खोजा गया
  • 0~102499 range में सही परिणाम देने वाले मान खोजे गए
  • अंतिम परिणाम (y * 1073750999) & 3221352463 <= 126976 है

function का सिद्धांत और आंतरिक संरचना

• constants का binary analysis करके उन्हें तीन प्रमुख bit क्षेत्रों A, B, C में बाँटा गया
  • हर क्षेत्र की bit state के आधार पर leap year जाँच की 3 शर्तों को कवर किया जाता है
• function का तार्किक विभाजन:
  • A क्षेत्र: (y % 4) != 0 सहित 4 के multiple होने की शर्त की जाँच
  • B क्षेत्र: (y % 100) != 0 को अलग-अलग patterns (जैसे अंतिम अंक 14, 57, 71 आदि) से filter करना
  • C क्षेत्र: (y % 16) == 0, यानी 16 के multiple होने की जाँच
• multiplication वास्तव में remainder निकाले बिना कई शर्तों को जोड़ता है, इसका सिद्धांत समझाया गया है
  • magic constant से गुणा करने पर 100 के multiples जैसी संख्याओं में विशिष्ट bit patterns बनते हैं
  • साथ ही multiplication error और कई अंकों के patterns से जुड़ी गणितीय आंतरिक संरचना का विश्लेषण भी शामिल है

अतिरिक्त range और bit width विस्तार की संभावना

• 64-bit तक विस्तार करने पर उपयुक्त magic constant combinations खोजने का तरीका भी बताया गया है
  • f, m, t मानों को अलग-अलग बदलकर सबसे लंबी range खोजी जा सकती है
  • StackExchange पर भी optimal combination और Z3 के उपयोग से जुड़े प्रमाण के उदाहरण मौजूद हैं

benchmark और वास्तविक performance तुलना

• benchmark परिणाम:
  • 2025 जैसे अनुमानित values में 0.65~0.69ns के साथ लगभग कोई अंतर नहीं
  • random input पर is_leap_year_fast ने लगभग 3.8 गुना तेज performance दिखाई
  • input pattern के अनुसार जब branching अप्रत्याशित हो, तब यह काफी लाभ देता है

निष्कर्ष और वास्तविक उपयोग

• वास्तविक अनुप्रयोगों में जब values अनुमानित हों तो लाभ कम है, लेकिन बड़ी मात्रा के random data में यह बहुत उपयोगी है
• Python या C# जैसी standard libraries को वास्तव में बदलने से पहले पूरे प्रोग्राम के यथार्थवादी benchmark की आवश्यकता है
• यह विचार और implementation अपने-आप में रोचक हैं, और कुछ स्थितियों में performance के लिहाज़ से आकर्षक समाधान हैं

[chickendreamtree]

Fast inverse sqrt की याद दिलाने वाली पोस्ट

[GN⁺]

Hacker News राय

• यह देखकर हैरानी हुई कि gcc या clang जैसे आधुनिक compiler is_leap_year1 जैसे कोड को अपने-आप is_leap_year2 की तरह optimize कर देते हैं, इसलिए C source स्तर पर हाथ से optimization करना ज़रूरी नहीं लगता, हालांकि दूसरी भाषाओं में यह अब भी उपयोगी हो सकता है, खासकर cal प्रोग्राम के नवीनतम version के source code में leap year check को बहुत सरल तरीके से handle करना प्रभावशाली लगा
  • अच्छा लगा कि linux कोड हर बार तीन लगातार conditions को उलटने और default return value का सहारा लेने के बजाय कहीं ज़्यादा आसानी से समझ आता है, ऐसी जटिल code structure debugging के समय सच में पागल कर देती है
• ((y * 1073750999) & 3221352463) <= 126976 यह कोड कैसे काम करता है, इसकी व्याख्या जटिल होगी ही—इसमें ज़रा भी हैरानी नहीं, बल्कि यही स्वाभाविक है
• मुश्किल से समझ आने वाली magic number optimization तकनीकें मुझे बहुत पसंद हैं, ऐसी चीज़ें देखते ही सोचता हूँ कि पुराने assembly में inner loops लिखने के दौर की कितनी optimization techniques मुझसे छूट गई होंगी, अगर ऐसी तकनीकों का कोई collection हो तो साझा करें
  • कई bit manipulation tricks के संग्रह के links साझा किए गए, UNIX शैली comparison के लिए efficient CMP(X, Y) macro, signum function optimization के उदाहरण, Motorola 68000 के assembly code उदाहरणों के links, OpenSolaris से आए bit macros के संग्रह आदि जैसी विभिन्न optimization techniques के links दिए गए, साथ ही यह अफसोस भी जताया गया कि Open Solaris blog अब नहीं रहा, code optimization में रुचि रखने वालों के लिए सिफारिश
  • "Hacker's Delight" किताब की सिफारिश, जिसमें तरह-तरह की bit tricks और low-level optimization techniques भरी पड़ी हैं
  • supercompilation तकनीक देखने का सुझाव
  • पहले के समय में ऐसी तकनीकें छूटी नहीं थीं; उस दौर में multiplication इतनी महंगी थी कि वही चीज़ optimization मानी जाती थी
• ज़रा भी उम्मीद नहीं थी कि leap year check इतना दिलचस्प निकलेगा, शायद low-level programmers ने बहुत पहले ही ऐसे tricks ढूँढ लिए थे लेकिन उनका कोई रिकॉर्ड नहीं छोड़ा, ऐसा लगता है कि पुराना code आज भी ऐसी चीज़ें छुपाए हो सकता है, अगर ऐसी तकनीकों का कोई संग्रह हो तो सच में उसे खंगालना चाहूँगा
  • 80 के दशक में z80 पर घर पर खुद सीखी गई चीज़ें थीं, लेकिन ज़्यादातर भूल चुका हूँ, कभी-कभी 20s में पहुँचे अपने बच्चों को दिखाता हूँ तो मानो जादू कर रहा हूँ
• अगर 6000 साल से पहले के leap years जानने हों, तो खुद बनाया गया interactive calculator और visualization tool इस्तेमाल करें, भले machine instructions कुछ ज़्यादा हों, लेकिन यह बहुत तेज़ी से हज़ारों calculations कर सकता है, गणितीय trick भी काफ़ी प्रभावशाली है
• bit manipulation chapter पढ़ते हुए ख्याल आया कि "शायद solver इस्तेमाल किया जा सकता है", और सच में लेखक ने वही तरीका अपनाया—यह देखकर चकित हुआ, इतना बारीक approach संतोषजनक लगा
• ऐसे leap year check function को current-time-api में जोड़ने का सुझाव
• संख्याओं को binary में देखने पर मज़ेदार patterns दिखते हैं, यह दिलचस्प लगा कि 2 को छोड़कर सभी prime numbers 1 पर समाप्त होते हैं
  • यह मज़ेदार लग सकता है, लेकिन सभी odd numbers 1 पर समाप्त होते हैं और prime numbers स्वभावतः 2 को छोड़कर even नहीं हो सकते, इसलिए इसमें कोई खास अर्थ नज़र नहीं आता—ऐसा सवाल उठाया गया
• leap year समस्या में 0 के न होने की ओर ध्यान दिलाया गया; असल में "वर्ष 0" होता ही नहीं, 1 BC से सीधे 1 AD पर जाते हैं, इसलिए 0 check का कोई अर्थ नहीं
  • लेख की शुरुआत में ही समझाया गया है कि leap year algorithm के design की पूर्वधारणा proleptic Gregorian calendar और astronomical year numbering है, यह शर्त न हो तो leap year check locale के हिसाब से जटिल हो जाता है
  • astronomical year numbering इस्तेमाल करें तो वर्ष 0 आता है, और year/month management जैसी चीज़ों में यह तरीका उलटे ज़्यादा साफ़-सुथरा है; अंदरूनी data में astronomical notation रखें और बाहरी output में ही BCE/CE conversion करें—ऐसा सुझाव
  • Gregorian calendar लागू होने से पहले calendars की बुनियाद ही अस्पष्ट थी और क्षेत्र के अनुसार अलग-अलग थी, 1582 में तो एक ही बार में 10 दिन हटा दिए गए थे, इसलिए उससे पहले की तारीख़ों पर गणना भरोसेमंद नहीं, रोमन युग के पुरोहित leap years को अंधविश्वास या रिश्वत जैसी वजहों से मनमाने ढंग से समायोजित भी करते थे, इसलिए मामला और जटिल है
  • ISO8601 standard वर्ष 0 को अनुमति देता है, और astronomical calendar में वर्ष 0 का अर्थ 1 BC होता है, BCE years सभी -1 से offset हो जाते हैं
• ऐसा बहुत कम होता है कि source code सचमुच ज़ोर से हँसा दे, इसलिए यह बेहद आनंददायक अनुभव था