Shader में mix()+step() conditional move optimization से बचना क्यों चाहिए

• GPU shader में ternary operator या साधारण if से value चुनने वाला code आमतौर पर conditional branch नहीं, बल्कि conditional move (select) के रूप में handle होता है
• step() और arithmetic masking में बदलने पर भी हटाने लायक branch होती ही नहीं, इसलिए तथाकथित branch removal optimization का आधार ही सही नहीं है
• AMD और Microsoft compiler output में comparison और conditional mask/move instructions दिखाई देते हैं, jump या branch instructions नहीं
• step() version पहले 0.0/1.0 mask बनाता है, फिर multiplication और addition से result synthesize करता है, इसलिए सीधे conditional move करने वाले code की तुलना में अनावश्यक operations बढ़ जाते हैं
• condition के अनुसार बड़े calculation block को skip करने वाली GPU branching अब भी उपयोगी है, लेकिन simple value selection के लिए generated machine code को देखना ज्यादा सुरक्षित है

---

साधारण value selection, GPU branch नहीं है

• example function snap45() input vector से x = abs(v.x) निकालने के बाद, दो ternary operators के जरिए तीन vec2 results में से एक return करता है
• यही logic सामान्य if statement से लिखने पर भी बनी रहती है
• समस्या वाली “optimization” ternary operator को step() और weighted synthesis में बदलने का तरीका है
  • w0, w1, w2 को step() से बनाया जाता है
  • res0, res1, res2 को अलग-अलग calculate किया जाता है
  • w0*res0 + w1*res1 + w2*res2 से final result synthesize किया जाता है
• यह transformation इस गलतफहमी से शुरू होता है कि original code conditional branch बनाता है
• simple register value selection instruction pointer को नहीं बदलता, और इससे branch misprediction, pipeline flush, या instruction cache invalidation भी नहीं होती
• GPU की वास्तविक branch condition के आधार पर बड़े calculation block को skip करना हो तो तेज और उपयोगी हो सकती है
• लेकिन उदाहरण की तरह simple value या calculation result चुनने के मामले में generated machine code में branch नहीं बनती, ऐसा माना जा सकता है

Compiler output क्या दिखाता है

• मूल GLSL ternary operator code AMD compiler में comparison और conditional mask instructions में बदलता है
  • comparison: v_cmp_gt_f32, v_cmp_ngt_f32
  • conditional mask: v_cndmask_b32
• Microsoft compiler output भी यही structure दिखाता है
  • comparison: lt
  • conditional move: movc
• दोनों compiler outputs में jump/branch instructions नहीं हैं

step() तरीका अधिक महंगा क्यों पड़ता है

• step() आधारित तरीका पहले conditional move से 0.0 या 1.0 mask बनाता है, फिर कई candidate results को multiplication और addition से mask करता है
• original code जरूरी values को सीधे conditional move करता है, इसलिए mask generation और arithmetic synthesis जोड़ने वाला step() तरीका उससे अधिक wasteful है
• अलग-अलग hardware पर step() आधारित version, original version की तुलना में काफी धीमा मापा जा सकता है
• example code में कुछ abs() GLSL calls अलग GPU instruction नहीं, बल्कि instruction modifier के रूप में शामिल होते हैं; ऐसे मामलों में abs() call लगभग free माना जा सकता है
• float a = mix(b, c, step(y, x)); को float a = x < y ? b : c; की optimization के रूप में सुझाना गलत तरीका है

[GN⁺]

Hacker News की राय

• TFA का निष्कर्ष सही लगता है, लेकिन अगर सिर्फ बेहतर version के code generation का नतीजा दिखाने के बजाय दोनों versions के code generation के नतीजे दिखाए जाते, तो तर्क और मजबूत होता
  quote में कहा गया है, “जिस version को optimized बताया जा रहा है वह original version से काफी धीमा है… दो multiplications और एक-दो additions बर्बाद करता है… generated machine code देखें”, लेकिन असल में सिर्फ वही अच्छा version दिखाया गया है जिसमें multiplication या addition नहीं है
  यह सिर्फ यह साबित करता है कि अच्छा version ठीक है; यह अभी साबित नहीं करता कि खराब version ज्यादा खराब है

  • मुख्य बात यह है कि condition ने असली branch नहीं बनाई
    दूसरे version का generated code दिखाने से शायद सिर्फ यह दिखता कि वह लंबा है, और उसमें भी branch बनने की उम्मीद नहीं थी, इसलिए उसका ज्यादा मूल्य नहीं होता
  • RDNA 1 के लिए generated code यहाँ है: https://shader-playground.timjones.io/5d3ece620f45091678dcee...

• अच्छा होता अगर यह जानने का कोई अच्छा तरीका होता कि if कब सच में branch को मजबूर करता है और कब नहीं
  लोग शायद ज्यादा महंगा हो सकने वाला mix/lerp इसलिए इस्तेमाल करते हैं क्योंकि थोड़े overhead को स्वीकार कर लेते हैं, लेकिन branch बनने से डरते हैं
  यह अच्छा है कि v = x > y ? a : b; जैसा सबसे स्पष्ट code असल में अच्छी तरह काम करता है, लेकिन यही if syntax कभी branch होता है और कभी नहीं—यह बात बेचैन करती है
  जिन contexts में सच में branch नहीं होना चाहिए, वहाँ branch-if और non-branching if अलग keywords होते तो अच्छा होता; non-branching keyword के लिए compiler अगर बिना branch बनाए code नहीं बना सकता तो compilation fail करे, और branching keyword के लिए अगर बिना branch बनाए code बन सकता है तो warning दे

  • इसके पीछे NVIDIA और cg/CUDA compilers की उलझाऊ documentation है
    शुरुआत में वे programmers को डराना नहीं चाहते थे, इसलिए execution model छिपाकर उसे “threads” abstraction से समझाया, और बाद में GPU promotion में भी “CUDA threads बहुत ज्यादा हैं” जैसी भाषा इस्तेमाल होती रही
    नतीजे में GPU coding को लेकर अजीब अंधविश्वास बन गए
    असल में code में branch होना अक्सर अच्छा भी हो सकता है, और branch अपने-आप में तेज होती है
    समस्या यह है कि SIMD lanes अपनी-अपनी अलग branch में नहीं निकल सकतीं, इसलिए compiler branch की जगह दोनों तरफ का code emit करता है और condition के हिसाब से result को mask करता है
    इसलिए shader input values, vertices, compute shader indices आदि पर आधारित calculations असली branch नहीं करते, बल्कि masking से sequentially execute होते हैं
    TFA के example में भी ? operator के दोनों तरफ की values calculate होती हैं, और SIMD value पर conditionals आम तौर पर ऐसे ही होते हैं
    हालांकि जब सभी lanes में एक ही value हो, तो calculation को तेजी से skip करने वाली short-circuit branch आ सकती है, लेकिन आम तौर पर true/false दोनों sides calculate होती हैं
    सिर्फ scalar register, यानी shader constants या uniform values पर आधारित conditionals ही असली branch बनाते हैं, और ऐसी branches बहुत तेज होती हैं
  • scalar CPU पर भी यही बात लागू होती है
    उदाहरण के लिए CMOV instruction 1995 में P6 core में आया था
    scalar architectures में भी branch महंगी होती है, और compiler जितना हो सके तय करता है कि कब alternative strategy इस्तेमाल करनी है
    कभी-कभी वह गलत होता है, लेकिन बहुत अक्सर नहीं
  • GPU में तो इसे उल्टा देखना चाहिए
    conditional move default है, और असली branch सिर्फ तब संभव performance optimization है जब वह uniform branch हो जिसमें पूरा workgroup एक ही direction में जाता हो
  • ऐसा example सोच सकते हैं: a = f(z); b = g(z); v = x > y ? a : b;
    अगर f() और g() calls की cost relatively बड़ी है, तो conditional code emit करना या दोनों को calculate करके select करना—यह trade-off बन जाता है
    यह simple choice नहीं है; फैसला compiler करता है
  • shader language में ऐसी capability हो तो दिलचस्प होगा
    code के सभी functions को branchable/non-branching की तरह रंगकर अलग किया जाए, और जिस function को non-branching mark किया गया हो उसमें if को conditional move में compile होना चाहिए तथा वह केवल non-branching functions ही call कर सके—ऐसा भी बनाया जा सकता है

• “GPU में branch धीमी होती है” वाले मिथक का बड़ा हिस्सा इसलिए है कि पुराने PlayStation 3 के समय में यह सच में काफी धीमी थी
  PS3 में NVIDIA RSX GPU था, और documentation के हिसाब से branch 6 cycles की थी—मुझे ऐसा याद है—लेकिन real measurements हमेशा उससे धीमे आए
  warp के सभी threads जब उसी path पर चलते थे, यानी पूरी तरह coherent branch में भी ऐसा था; और incoherent branch और धीमी थी, क्योंकि IFEH instruction ही 6 cycles का था और GPU को दोनों branches execute करनी पड़ती थीं
  मुझे लगता है आज तक चले आ रहे “GPU branch धीमी होती है” वाले मिथक की शुरुआत वहीं से हुई
  आजकल GPU branch, खासकर coherent branch, काफी सस्ती है

  • अगर कोई बस “branch” कहता है, तो मानना चाहिए कि उसका मतलब incoherent branch है
    आज branch mechanism का overhead कम हो गया हो सकता है, लेकिन branch के दोनों sides की throughput active threads के ratio जितनी घटती है—यह physical constraint वैसा ही है
    अगर दोनों branches execute होती हैं और instruction length भी समान है, तो दोनों तरफ की average performance कम से कम आधी हो जाती है
    इसलिए GPU में branch धीमी होती है—यह विश्वास लंबे समय तक टिकता है, और असल में सही भी है
    संभव हो तो problem को बिना branch के फिर से structure करने में ज्यादा कोशिश करना worthwhile है
  • coherent branch “free” के करीब होती है, लेकिन extra instructions register pressure बढ़ा देती हैं
    dynamic branch से बचने की मुख्य वजह यह नहीं कि branch अपने-आप में स्वभाव से धीमी है, बल्कि वजह इससे ज्यादा इसी तरफ है

• इस तरह का branch avoidance optimization कभी असरदार हुआ करता था
  मैंने Xbox 360 और पुराने Intel integrated GPU पर profiling की थी, लेकिन अब ऐसा न करना ही सही है
  bit extraction और दूसरे integer operations भी मिलते-जुलते हैं
  पहले उन्हें floating-point math से emulate करना तेज़ होता था, लेकिन अब सभी GPU में तेज़ integer operations हैं

  • “अब सभी GPU में तेज़ integer operations हैं” यह बात किस हद तक सच है, यह जानने की उत्सुकता है
    उदाहरण के लिए PS5 और Xbox Series S|X की architecture RDNA2 ISA को देखें, तो integer के लिए सिर्फ 32-bit scalar instructions ही दिखते लगते हैं
    [0] https://www.amd.com/content/dam/amd/en/documents/radeon-tech...
  • कम-से-कम “बड़े” GPU में यह पहले जितनी बड़ी समस्या नहीं रही, लेकिन यह लेख असल में branch avoidance के बारे में नहीं है
    दिया गया code पहले से ही branchless code है
    सलाह देने वाले लोग शायद source में conditional statement जैसा syntax है या नहीं, सिर्फ यही देखकर branch code का फैसला करते हैं, और सोचते हैं कि optimization के तौर पर उसे avoid कर रहे हैं

• यह लेख भी संबंधित है: https://medium.com/@jasonbooth_86226/branching-on-a-gpu-18bf...
  “अगर आप internet से GPU पर branch लिखने के बारे में पूछें, तो वह इसे ऐसे बता सकता है जैसे आप नरक का द्वार खोलकर दानवों को अंदर ला रहे हों। कहा जाएगा कि इसे हर कीमत पर avoid करना चाहिए, और ternary operator या step() जैसी अजीब math tricks से बचा जा सकता है। इस सलाह का ज़्यादातर हिस्सा अच्छे-से-अच्छे मामले में पुराना है, और कई बार सीधे-सीधे गलत भी है। आइए इसे ठीक करें।”

• processor भी बदलते हैं और compiler भी
  अगर ऐसी details अहम हैं, तो कई variants deploy करना और runtime पर सबसे तेज़ version चुनना सबसे अच्छा है
  जैसा मैंने पहले भी कुछ बार कहा है, मैंने hand-written assembly हटाकर साधारण C या मिलते-जुलते code से बदलकर चीज़ों को काफ़ी तेज़ बनाया है
  हो सकता है वह assembly 10–20 साल पहले तेज़ रही हो, लेकिन अब हालात बदल गए हैं

  • shader का सबसे तेज़ version runtime पर पता लगाना मुझे बहुत मुश्किल लगता है
    असल में ऐसा करने वाले game या engine मुझे ज़्यादा पता नहीं हैं
    सिद्धांत रूप में यह संभव हो सकता है
    D3D, GL, Vulkan जैसे ज़्यादातर API performance counters expose करते हैं, और vendor के हिसाब से reliability अलग हो सकती है, लेकिन representative test scene बनाकर उसे कई बार replay करते हुए optimization measure किया जा सकता है
    लेकिन कई games dynamically generated scenes और dynamically generated shaders इस्तेमाल करते हैं, इसलिए test करने वाले combinations की संख्या बाधा बन सकती है
    user से benchmark खत्म होने तक इंतज़ार करने को भी कहना पड़ सकता है
    अगर hardware उपलब्ध हो, तो हर vendor की कई GPU generations पर पहले से measure करके सिर्फ महत्वपूर्ण decisions hardcode किए जा सकते हैं, लेकिन ऐसी existing infrastructure के बारे में मुझे ज़्यादा जानकारी नहीं है
  • दिलचस्प बात यह है कि NVIDIA driver कुछ हद तक ऐसा काम करता है
    वह game shaders को intercept करके उन्हें NVIDIA द्वारा optimized custom shaders से बदल देता है
    इसलिए NVIDIA driver change log में “game X optimization, 40% faster execution” जैसी पंक्तियां दिखती हैं
  • एक shader और जोड़ने भर की बात हो तो ठीक है, लेकिन “modern” graphics API में कभी-कभी उसी shader के हजारों permutations चाहिए होते हैं, और हर variant जोड़ने पर उनकी संख्या 2 गुनी हो जाती है
    हर shader पर अनंत समय खर्च नहीं किया जा सकता
    जिस hardware की परवाह है उस पर profiling करें, और अगर चुना गया तरीका किसी काल्पनिक future processor पर धीमा है, तो कुछ नहीं किया जा सकता
    उम्मीद करनी चाहिए कि वह processor इतना तेज़ होगा कि समस्या न बने

• लगता है कि जिस गलती और भ्रम को यह लेख ठीक करना चाहता है, वही यहां भी दोहराया जा रहा है
  लेख यह दावा नहीं करता कि conditional branches free हैं
  मेरी नज़र में यह branch code की performance cost के बारे में बात करने वाला लेख भी नहीं है
  लेख का मुख्य point यह है कि दिए गए रूप की conditional logic, conditional branch code में compile नहीं होती
  और यह कि दिखने वाली हर conditional expression को जबरन छिपाने वाली नुकसानदेह सलाह फैलाते नहीं रहना चाहिए
  वास्तविक branch code के बारे में, यह साफ है कि branch code execute करना अधिक जटिल होता है
  free branch जैसी कोई चीज़ नहीं है, और reasonable सीमा में branches avoid करने से किसी भी code के तेज़ होने की संभावना बढ़ती है
  अच्छी बात यह है कि original code पहले से ही branchless code था
  हमेशा की तरह, कोई universal metric नहीं है जो बताए कि optimization वाकई worthwhile है या नहीं
  [0] यहां “दिखने वाली” महत्वपूर्ण है। मतलब उन मामलों से है जहां generated code में रुचि नहीं होती, सिर्फ इस बात की चिंता होती है कि source code conditional statement जैसा दिखता है या नहीं
  [1] बेशक यह किस्मत की बात नहीं थी। मेरा अनुमान है कि किसी ने IQ को shader code के लिए कोई ऐसा सुधार भेजा होगा जो देखने में obvious, लेकिन गलत था

• तो फिर compiler इतना smart क्यों नहीं है कि “optimized” version को वही code पहचान सके?
  क्या उसे step() समझकर step() = 0.0, step() == 1.0 cases को अलग से optimize नहीं कर पाना चाहिए?
  कम-से-कम एक multiplication तो हटाई जा सकती है, इसलिए आम तौर पर conditional load/store या किसी और चीज़ में बदलने पर भी यह हमेशा फायदेमंद लगता है

  • वास्तव में ऐसा हो भी सकता है
    कुछ compiler कुछ मामलों में ऐसी optimization कर सकते हैं, इसकी पूरी संभावना है, लेकिन ऐसा version लिखना भी साफ तौर पर संभव है जिसे compiler समझ न पाए
  • optimization की एक और समस्या यह है कि सभी possibilities आज़माने में बहुत ज़्यादा समय नहीं लगना चाहिए
    ज़्यादातर optimization driver side पर होती है, और बहुत ज़्यादा समय लेने वाला काम shader compilation stutter के रूप में सामने आता है
    मैं नहीं कह सकता कि यह optimization अभी सचमुच होती है या नहीं, लेकिन यह हमेशा ध्यान रखने लायक factor है

• समस्या वाले “optimized” version के धीमे होने की वजह यह है कि step() function असल में कुछ इस तरह implement होता है:
  float step( float x, float y ) { return x < y ? 1.0 : 0.0; }
  कैसे पता चले कि कोई OpenGL function GPU primitive को call करता है या emulate किया जाता है?

  • इसका एकमात्र तरीका मूल लेख की तरह shader को compile करना, disassemble करना और फिर assembly पढ़ना है
    मैंने HLSL shaders के साथ अक्सर ऐसा किया है, और virtual instruction set के बारे में बहुत कुछ सीखा है
    उदाहरण के लिए, यह दिलचस्प है कि GPU में sincos instruction होता है, लेकिन inverse trigonometric functions compile के दौरान emulate किए जाते हैं
  • यह जानना क्यों ज़रूरी है, यह उद्देश्य पर निर्भर करता है
    अगर performance महत्वपूर्ण है, तो इसे जानना पड़ सकता है
    लेकिन सिर्फ़ यह तथ्य कि step dedicated instruction नहीं है बल्कि conditional के ऊपर library function के रूप में implement है, dedicated instruction की तुलना में performance के बारे में कुछ नहीं बताता, इसलिए implementation पर बहुत ज़्यादा अटकने की ज़रूरत नहीं है
    अगर GPU architecture के बारे में जिज्ञासा है, तो disassembly, open source driver code, LLVM और ISA docs देखे जा सकते हैं
  • PC-style assembly में दिखने वाले functions के अलावा GPU के पास कोई खास primitives हों, ऐसा मैंने नहीं देखा
    decompiled shaders देखते समय वे आम तौर पर C में सोचे जाने वाले तरीके से मिलते-जुलते लगे
    OpenGL जैसी specifications कई built-in functions के behavior को define करती हैं, और implementation standard assembly instructions से उस specification को satisfy करती है
    ऐसी online sites खोजी जा सकती हैं जो कई architectures में decompile करती हैं
  • यह programming में आम तौर पर दिखने वाला अच्छा सवाल है, और optimization करते समय पहले measure करने की मुख्य वजह भी यही है
    आम तौर पर यह जानने या इसकी चिंता करने की ज़रूरत नहीं होती कि built-in function कैसे implement हुआ है
    अगर आप इसकी चिंता कर रहे हैं, तो शायद आप optimization के बारे में सोच रहे हैं, और उस समय जवाब है: “measure करके देखें कि कौन सा बेहतर है”
  • मेरे लिए उलझन वाली बात शायद यह है कि “branch” का hardware-specific अर्थ, उस अर्थ से ज़्यादा स्पष्ट रूप से defined है जो मैंने बड़े होते हुए सीखा था
    मैंने जो अर्थ सीखा, उसमें conditional statement branch होता है
    machine code level पर control flow runtime पर चुना जाता है, इसलिए conditional jump परिभाषा के अनुसार branch है
    step() इस्तेमाल करना logic को arithmetic में बदलना नहीं, बल्कि logic को library function call के अंदर छिपाना भर लगा
    step() built-in function हो या किसी math paper में आने वाला function, इससे बात नहीं बदलती
    math में भी step() की definition सचमुच conditional statement ही है
    conditional statement के बिना ठीक से optimize करना हो, तो desired result के समान कोई continuous function चुनना होगा और parameters adjust करके target के जितना करीब हो सके fit करना होगा
    आम तौर पर एक polynomial चुना जाता है, standard iterative approximation method चलाया जाता है, और फिर ऐसा f(x) बनता है जिसमें branch नहीं, सिर्फ़ addition, multiplication और “अजीब तरह से specific” constants होते हैं
    लेखक का यह ज़ोर देकर कहना कि conditional move “branch” नहीं है, मुझे ठीक से समझ नहीं आता
    abs() का GPU instruction न होकर instruction modifier में बदलकर free हो जाना इसलिए है क्योंकि integers के two's complement representation और IEEE-754 floating-point representation की वजह से sign bit को most significant bit की तरह handle किया जा सकता है
    इसलिए abs() बस most significant bit को बिना शर्त 0 बनाने या read करने वाले instruction में mask करने तक सीमित रहता है
    लेकिन step() या कोई arbitrary ternary operation, और मेरी जानकारी में conditional move instruction, ऐसे special cases नहीं हैं
    basic abs(), sqrt(), trigonometric functions वगैरह standard knowledge के करीब हैं, और बाकी चीज़ें शायद वैसे भी कितनी महत्वपूर्ण होंगी
    step() में कहीं न कहीं condition होना ही है, और उसे सीधे करें, library पर छोड़ें या hardware पर छोड़ें, उसकी fundamental nature नहीं बदलती

• मैं इस trap में फँस चुका हूँ
  Claude या ChatGPT भी इसे optimization के रूप में सुझाते हैं
  लेकिन हर बार measure करने पर performance घटी, और कभी-कभी काफ़ी ज़्यादा घटी

  • यह कोई अजीब बात नहीं है
    LLM बस training corpus में मौजूद चीज़ों को दोहराते हैं
    अगर internet का बड़ा हिस्सा इस तरह की conditional move “optimization” जैसी गलत चीज़ recommend करता है, तो LLM भी वही recommend करेगा
  • LLM internet पर लोग जो कहते हैं उसे दोहराते हैं, और लोग अक्सर गलत होते हैं