जब compiler आपको चौंका दे

 (xania.org)
1 पॉइंट द्वारा GN⁺ 2025-12-26 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • एक साधारण integer summation function को compile करते समय GCC और Clang की optimization में अंतर देखने का मामला
  • GCC loop के भीतर एक बार में दो संख्याएँ जोड़ने वाली x*2 + 1 रूप की loop optimization करता है
  • Clang loop को पूरी तरह हटा देता है और गणना को v(v - 1)/2 के closed-form formula से बदल देता है
  • इस रूपांतरण से कोड O(n) से O(1) में बदल जाता है, और गणितीय simplification अपने-आप हो जाती है
  • 20 साल से अधिक समय से compiler के साथ काम कर रहे लेखक को भी चौंका देने वाला यह उदाहरण, compiler की intelligent optimization क्षमता दिखाता है

GCC की loop optimization

  • जब एक साधारण integer summation function लिखा गया, तो GCC ने loop-आधारित efficient summation code generate किया
    • loop के भीतर lea edx, [rdx+1+rax*2] instruction का उपयोग करके दो संख्याएँ एक साथ जोड़ी गईं
    • यह x और x+1 को जोड़ने की operation को x*2 + 1 में बदलने का रूप है
  • optimization level को -O3 तक बढ़ाने पर parallel addition (vectorization) के जरिए loop को और तेज़ी से process किया जाता है
  • यह तरीका loop को बनाए रखते हुए भी operation efficiency को अधिकतम करने वाली पारंपरिक optimization का रूप है

Clang की गणितीय optimization

  • वही कोड Clang से compile करने पर loop पूरी तरह गायब हो जाता है
    • Clang input value के positive होने की जाँच करने के बाद lea, imul, shr instructions की एक श्रृंखला से गणना करता है
    • नतीजतन, इसे (v² - v)/2, यानी integer sum के closed-form formula में बदला जाता है
  • यह रूपांतरण loop को हटाकर constant-time (O(1)) calculation से बदल देता है
  • लेखक ने इस परिणाम को “integer sum का गणितीय हल compiler ने खुद खोज लिया” जैसा बताया

सूत्र के विस्तार की प्रक्रिया

  • Clang द्वारा generate किए गए assembly code को गणितीय रूप से उल्टा समझने पर निम्नलिखित रूपांतरण दिखाई देता है
    • v + ((v - 1)(v - 2) / 2) - 1
    • इसे विस्तार और सरलीकरण करने पर यह (v² - v)/2 बन जाता है
  • अंततः यह v(v - 1)/2 के रूप में आता है, जो 1 से v तक के योग के सूत्र से मेल खाता है
  • इसे compiler द्वारा गणितीय pattern पहचानकर की गई optimization के उदाहरण के रूप में प्रस्तुत किया गया है

compiler का intelligent व्यवहार

  • Clang इस विशेष instruction sequence का उपयोग क्यों करता है, इसे overflow से बचाव और induction variable tracking के तरीके से समझाया गया है
  • सटीक internal behavior का कारण पूरी तरह स्पष्ट नहीं है, लेकिन इसे Clang की internal optimization logic के संयुक्त प्रभाव का परिणाम बताया गया है
  • लेखक ने इस नतीजे को “विनम्र बनाने वाला और प्रेरक अनुभव” कहा

समापन और series का संदर्भ

  • यह लेख ‘Advent of Compiler Optimisations 2025’ series का 24वाँ लेख है
  • इसमें यह देखा गया है कि compiler code transformation के जरिए गणितीय simplification और performance improvement कैसे हासिल करता है
  • लेखक कहते हैं, “compiler आज भी मुझे चौंकाते हैं,” और लंबे अनुभव के बावजूद बने रहने वाले तकनीकी विस्मय पर ज़ोर देते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-12-26
Hacker News की राय

  • इस feature को implement करने वाला code ScalarEvolution.cpp और IndVarSimplify.cpp में है

    • यह हैरान करने वाला है और साथ ही थोड़ा असहज भी लगता है कि एक file में लगभग 16,000 lines का code है

  • इस तरह की optimization वाकई दिलचस्प है
    compiler optimization को मोटे तौर पर दो हिस्सों में बाँटा जा सकता है — data flow analysis और pattern recognition तथा replacement
    पहला ज़्यादातर programs में असरदार होता है, और दूसरा धीरे-धीरे कम return देने वाले patterns को जमा करने का काम है
    linked example समझदार और मज़ेदार है, लेकिन असल में इसकी बहुत ज़्यादा value नहीं है। 45 साल में मैंने ऐसा loop कभी नहीं लिखा
    बेशक, इस तरह के pattern substitution high-level code से अपने-आप generate होते हैं, इसलिए ये अब भी महत्वपूर्ण हैं
    सच कहूँ तो, शायद मैं थोड़ा इसलिए बड़बड़ा रहा हूँ क्योंकि मेरा optimizer ऐसी optimization नहीं कर पाता

    • असल में इसकी value सोच से ज़्यादा हो सकती है। LLVM का SCEV(Scalar Evolution) मुख्य रूप से analysis के लिए इस्तेमाल होता है, और math loop के अलावा दूसरी optimizations को भी संभव बनाता है
    • यह स्पष्ट नहीं है कि कौन-सी optimization की गई। पहले जब मैं एक niche compiler बना रहा था, तब मुझे याद है कि compiler ने चीज़ों को मेरी अपनी लिखी optimization से ज़्यादा समझदारी से handle किया था, और मैं हैरान रह गया था

  • यह Scalar Evolution(SCEV) नाम की feature है, और LLVM में यह काफ़ी जटिल तरीके से implement की गई है

  • इसी तरह की optimization का एक और उदाहरण “Do not optimize away” लेख में है

    • उस लेख की शुरुआती व्याख्या थोड़ी ग़लत है। code 0 से N तक जोड़ता है, लेकिन N शामिल नहीं होता, इसलिए सही मान N(N-1)/2 है। गणित में 1 से N तक का योग N(N+1)/2 होता है, इसलिए upper bound को exclude करने के लिए N को (N-1) से बदलना चाहिए
    • मुझे लगता है compiler अभी भी इसे optimize कर सकता है। constant folding version और non-constant version अलग-अलग बनाकर runtime पर branch किया जा सकता है

  • इस optimization की असली शानदार बात यह है कि यह generic है
    यह सिर्फ “finite integer sequence का sum” pattern पहचानने तक सीमित नहीं है, बल्कि सामान्य रूप से लागू होती है — यही प्रभावशाली है

  • लगता है compiler में और ज़्यादा closed form जोड़े जा सकते हैं। पता नहीं यह इसके लायक होगा या नहीं
    इससे जुड़ी एक अवधारणा Wilf–Zeilberger pair है

  • एक बार फिर GCC, Clang से धीमा निकला, यह देखकर हैरानी हुई
    GCC को 20 साल की बढ़त मिली थी, फिर भी अब भी ऐसे मामले हैं जहाँ Clang ज़्यादा तेज़ code निकालता है
    पहले bit extraction करते समय Clang ने सिर्फ दो shifts किए थे, जबकि GCC ने तीन

    • GCC और LLVM/Clang के बीच compiler technology की एक पीढ़ी का अंतर है। GCC अब भी एक शानदार project है, लेकिन सुना है कि modern optimization techniques लागू करने में उसकी संरचना बाधा बनती है
    • वास्तविक performance दोनों compilers की काफ़ी मिलती-जुलती है। दोनों के optimization passes अलग हैं, इसलिए परिस्थिति के हिसाब से नतीजे बदलते हैं
    • GCC की शुरुआती license-केंद्रित idealistic design की वजह से इसकी extensibility कम थी। अब इसमें काफ़ी ढील आ चुकी है, लेकिन code generator अब भी जटिल है। दूसरी ओर Clang की संरचना सरल है, इसलिए optimization implement करना आसान है। व्यक्तिगत तौर पर मुझे MSVC और ICC का output भी काफ़ी अच्छा लगता है
    • क्या यह शायद bitfield से जुड़ा code था? GCC उस हिस्से की optimization में खास तौर पर कमज़ोर है

  • सोच रहा हूँ क्या किसी ने graph coloring problem को constant से replace करने वाली optimization आज़माई है

    • graph coloring एक NP-hard problem है, इसलिए इसे O(1) में बदलना आसान नहीं है। अगर graph planar हो तो 4-color theorem लागू होती है, लेकिन जवाब हमेशा एक जैसा नहीं होगा। बस graph theory की बात करने का मन था

  • यह implementation और specification की सीमा को धुंधला करने वाला उदाहरण है
    हम सोचते हैं कि हम implementation लिख रहे हैं, लेकिन असल में हम specification के proxy लिख रहे होते हैं
    यानी compiler imperative machine के illusion का निर्माण करता है

  • शुरुआत में यह देखकर हैरानी हुई कि Matt को इस तरह के behavior के बारे में पता नहीं था
    मैंने भी कॉलेज के दिनों में LLVM IR के साथ खेलते हुए recursion का multiplication में simplify हो जाना देखा था, और चौंक गया था
    अगर Matt को यह नहीं पता था, तो शायद इसका मतलब है कि यह optimization सिर्फ उन सरल cases पर लागू होती है जिनसे उसका वास्ता नहीं पड़ता

    • दरअसल, उसे यह पहले से पता था। उसने 2017 की एक talk में यही उदाहरण खुद दिया था
      YouTube वीडियो लिंक