एक बेकार-से if से कोड का प्रदर्शन 4 गुना बढ़ाना

 (purplesyringa.moe)
1 पॉइंट द्वारा GN⁺ 3 시간 전 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • डोमेन-विशिष्ट compressor के optimal encoding path को traverse करने वाले loop में सिर्फ एक condition जोड़कर, synthetic benchmark का execution time 320µs से 80µs तक घटा दिया गया
  • हर iteration में memory address पिछले iteration के j पर निर्भर करता है, इसलिए एक अकेला mov instruction भी instruction-level parallelism का लाभ नहीं ले पाता और memory access latency से बंधा रहता है
  • next_j[i][j] अधिकतर मामलों में मौजूदा j के बराबर रहता है; इस गुण को branch prediction में परिलक्षित करने पर CPU iterations के बीच की dependency को bypass करके कई iterations को speculative execution से चला सकता है
  • compiler अर्थ की दृष्टि से अनावश्यक if को हटाए नहीं, इसके लिए volatile cast का उपयोग किया गया। LLVM में [[unlikely]] या __builtin_expect(..., 0) भी काम करते हैं, लेकिन volatile बेहतर code बनाता है और GCC भी इसे support करता है
  • अधिक यथार्थपरक प्रयोगों में लगभग 2 गुना performance improvement मिला, जो LLVM के suboptimal code generation की वजह से हो सकता है; और अगर j का अनुमान लगाना कठिन हो, तो 1-cycle latency वाला pshufb एक विकल्प हो सकता है

compressor के optimal path का traversal

  • input string को कई chunks में बाँटा जाता है और हर chunk के लिए सबसे छोटा encoding चुनना होता है
    • हर encoding अलग-अलग characters को बेहतर compress करता है, इसलिए chunk boundaries तुरंत तय करना आसान नहीं होता
    • पिछली पोस्ट का algorithm इस समस्या को grid पर shortest path search में बदल देता है
  • हर cell में अगला optimal cell दर्ज किया जाता है जहाँ जाना है
    • पहले cell से आखिरी cell तक references को follow करने पर optimal encoding sequence मिल जाता है
  • next_j भरने वाला पहला loop पहले से ही SIMD से optimize किया गया है
    • असली bottleneck नीचे जैसा सरल path-traversal loop है
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • write को छोड़ दें तो मुख्य operation j = next_j[i][j] एक single mov instruction में compile होता है

single instruction भी dependency से धीमा हो सकता है

  • आधुनिक CPU instruction-level parallelism का उपयोग करके कई instructions और अलग-अलग iterations के काम को एक साथ चला सकते हैं
    • इसी वजह से सामान्य loop में i < n_symbols जाँच और i++ की cost दूसरे काम को नहीं रोकती
  • लेकिन एक-दूसरे पर निर्भर instructions साथ में execute नहीं हो सकते
    • मौजूदा iteration का memory address next_j[i][j] निकालने के लिए पिछले iteration से मिला j चाहिए
    • अगला iteration, पिछले iteration का result आने तक शुरू नहीं हो सकता; इसलिए data cache में होने पर भी memory access latency का असर पड़ता है

branch prediction को value speculation की तरह इस्तेमाल करना

  • इस compressor में chunks की संख्या बहुत अधिक न होने की उम्मीद है, इसलिए next_j[i][j] अधिकतर समय पुराने j के बराबर रहता है
  • CPU को सीधे यह नहीं बताया जा सकता कि address calculation में j वही रहेगा, लेकिन branch prediction का उपयोग करके लगभग वही असर बनाया जा सकता है
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • अगर CPU यह predict करे कि if body नहीं चलेगी, तो वह j को update करने वाली inter-iteration dependency को नज़रअंदाज़ करके कई iterations को speculative execution से चला सकता है
  • जब condition वास्तव में true होती है, तो branch misprediction recovery होती है
    • गलत speculation में की गई writes को discard कर दिया जाता है
    • सही j के साथ execution फिर से शुरू होता है
  • जब तक j लगभग बदलता नहीं, loop का bottleneck latency से throughput में बदल जाता है

compiler को if हटाने से रोकना

  • compiler की नज़र में condition वाला code और मूल code अर्थ की दृष्टि से समान हैं
    • अगर j memory में होता, तो अनावश्यक write या read-only memory पर write से बचा जा सकता था, लेकिन यहाँ यह register value है
    • common subexpression elimination (CSE) जैसी optimizations condition और duplicate access को हटा सकती हैं
  • सामान्य compiler hints का उपयोग branch हटाने के लिए किया जाता है, लेकिन यहाँ उल्टा branch-free code को branch वाले code के रूप में बनाए रखना ज़रूरी है
  • condition check और assignment के memory access को स्वतंत्र दिखाने के लिए assignment वाली तरफ volatile cast लगाया गया
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • 13 जुलाई की अतिरिक्त पुष्टि में, ibookstein द्वारा खोजे गए तरीके की तरह [[unlikely]] या __builtin_expect(..., 0) का उपयोग करने पर भी LLVM में वही प्रभाव मिला
  • volatile वाला तरीका बेहतर code बनाता है और GCC में भी काम करता है

benchmarks में दिखा performance change

  • synthetic benchmark में loop का execution time 320µs से 80µs तक घटा, यानी 4 गुना तेजी
    • एक बार के execution में समय का अंतर छोटा है, लेकिन compression process में loop कई बार चलता है, इसलिए कुल cost में यह जुड़ जाता है
  • अधिक realistic experiment में लगभग 2 गुना performance improvement दर्ज किया गया
    • संभव है कि यह LLVM के suboptimal code generation के प्रभाव से जुड़ा हो, फिर भी यह लागू करने लायक सुधार था

bitmask-आधारित representation एक विकल्प के रूप में

  • इस algorithm में next_j[i][j] केवल दो में से एक value ले सकता है
    • अधिकतर समय यह वर्तमान j होता है
    • बाकी स्थिति में यह ऐसा value होता है जो j से स्वतंत्र और सिर्फ i पर निर्भर होता है
  • 8-element array next_j[i] को replacement value और bitmask की pair से बदला जा सकता है
    • इस representation में if अर्थ की दृष्टि से वास्तव में ज़रूरी होता है, इसलिए volatile workaround की आवश्यकता नहीं रहती
    • लेकिन x86 पर variable position वाले bit की जाँच करने वाला operation compare से धीमा हो सकता है, इसलिए कुल performance उल्टा घट भी सकती है

जब j का अनुमान लगाना मुश्किल हो

  • value speculation से linked list traversal तेज़ करने वाली पोस्ट में भी इसी तरीके से performance बढ़ाने की चर्चा है
  • अगर j को predict करना कठिन हो, तो vector indexing operation pshufb का उपयोग किया जा सकता है
    • pshufb की latency 1 cycle है, इसलिए speculative execution के बिना इसे और कम करना कठिन है
    • vector operations से हर संभावित शुरुआती j के path को parallel में compute किया जा सकता है
    • काम को कई threads में बाँटकर बाद में results merge करने का तरीका भी संभव है

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

1 टिप्पणियां

 
GN⁺ 3 시간 전
Lobste.rs की टिप्पणियाँ

  • C++20 का [[unlikely]] attribute अगर if statement पर लगाया जाए, तो clang को उस code को हटाने से रोकने के लिए यह पर्याप्त लगता है: https://clang.godbolt.org/z/r4xYWfPfe
    दूसरे compilers में जाँच नहीं की

    • दोबारा जाँचने पर पता चला कि LLVM में यह सच में काम करता था; शायद शुरुआत में मैंने गलती से GCC पर test किया था, जहाँ इसका असर नहीं था
      हालांकि [[unlikely]] code को fast path से बाहर move कर देता है, इसलिए LLVM नीचे जैसा कुछ कम efficient code generate करता है 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      अगला रूप ज्यादा उचित लगता है 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      साथ ही, memory से value को कई बार पढ़ने से बचाने के लिए optimize करते हुए यह hot loop में एक instruction भी जोड़ देता है। इसलिए volatile का इस्तेमाल करने वाली technique अब भी उपयोगी है, लेकिन यह जानकर अच्छा लगा कि मूल code भी वैसे ही काम कर सकता है

  • इस technique को दूसरी जगहों पर value speculation कहा जाता है: https://mazzo.li/posts/value-speculation.html

    • इस method को दोबारा सोच निकालने के बाद मैंने सबसे पहले सोचा कि इसे arena में stored linked list पर भी apply किया जा सकता है, और linked article बिल्कुल यही बात cover करता है, इसलिए मैंने अपने लेख में भी link जोड़ दिया

  • मुझे उत्सुकता है कि 2–3 साल बाद, जब developers LLM के output को लेकर धीरे-धीरे और उदासीन हो जाएंगे, तब भी क्या वे इस तरह के blog posts में रुचि रखेंगे

    • अभी भी इसमें दिलचस्पी रखने वाले बहुत कम हैं, और पूरे programming क्षेत्र के हिसाब से यह niche knowledge है
      फिर भी जिन लोगों की इसमें रुचि है, उनके लिए यह अब भी बहुत उपयोगी और अच्छा लेख है
    • Godbolt बहुत popular है। code न पढ़ने की आदत की आलोचना होने पर LLM में डूबे developers “क्या assembly तक देखते हो?” को जैसे कोई बड़ा counterargument समझकर पेश करते हैं, लेकिन असल में हम assembly देखते हैं और आगे भी देखते रहेंगे
      जो developer details को महत्वपूर्ण नहीं मानता, उसके लिए अच्छा developer बनना मुश्किल है। जैसे एक बेहतरीन civil engineer बड़े project के bolts और nuts तक पर ध्यान देता है, वैसे ही बेहतरीन developer को भी छोटी-छोटी details में उतरना चाहिए। पूरी चीज details से मिलकर बनती है, इसलिए अगर आप अपने बनाए result को महत्व देते हैं, तो इससे बच नहीं सकते
    • मुझे लगता है कि यह आज से मूल रूप से अलग नहीं होगा। अभी भी ज्यादातर लोग इंसान द्वारा लिखे code के compiler output में रुचि नहीं रखते
      AI द्वारा लिखे code का compiler output देखने वाले लोग और कम हो सकते हैं, लेकिन basic picture शायद नहीं बदलेगी
    • बदलने वाली चीज रुचि का होना या न होना नहीं, बल्कि optimization priorities की फिर से जमावट है
      10 साल पहले अगर कोई Bash script थोड़ी धीमी होती, तो हम सबसे पहले instruction-level parallelism या CPU branch prediction के बारे में नहीं सोचते। किसी compilable और optimizable language में लिखा performance-critical हिस्सा हो सकता है, उसके भीतर detail में देखने लायक hot path हो सकता है, और फिर उसके भीतर एक-दो hot loops हो सकते हैं जहाँ vectorization या modern CPUs के व्यवहार में फर्क देखना meaningful हो
      LLM इस्तेमाल करने पर भी performance के लिहाज से सबसे hot points exceptional cases के रूप में manually review करने लायक होते हैं। output की कम quality को जानबूझकर स्वीकार करना, या LLM से 70% बनाकर बाकी 30% हाथ से ठीक करने वाला तरीका 85:15 तक सुधर सकता है, फिर भी यह लेख अब भी top 1% स्तर के detailed area को ही cover करता है
    • मैं C++ नहीं लिखता, इसलिए उस अर्थ में यह अभी भी मेरे direct interest का विषय नहीं है, लेकिन फिर भी इसे पढ़ना interesting लगा और लगता है कि 2–3 साल बाद भी ऐसी चीजें मजेदार रहेंगी