C से {n} गुना तेज़ गति

 (owen.cafe)
1 पॉइंट द्वारा GN⁺ 2023-07-07 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • छोटे C loop के लिए भी compiler output हमेशा सबसे बेहतर नहीं होता; x86_64 assembly को हाथ से tune करने पर conditional branch हटाने वाला version clang output से 6.73 गुना तेज़ निकला
  • Target function किसी string में 's' को +1, 'p' को -1, और '\0' को समाप्ति के रूप में संभालता है; clang 16 output ने इस flow को 3 conditional branches में बाँटा
  • Branch order बदलने, basic blocks को re-layout करने, और jumps को arithmetic से replace करने के बाद runtime 3.23 सेकंड से घटकर 2.87 सेकंड हो गया, और इस चरण में GCC 12 जैसी speed तक पहुँच गया
  • सबसे तेज़ version ने cmove से हर character के लिए जोड़ने वाली value 0, 1, -1 में से चुनी और हमेशा add किया; इसने 0.48 सेकंड और 1.94GiB/s throughput दर्ज किया
  • Benchmark AMD Ryzen 5 5625U और Linux 6.1.33 पर 10 लाख random 'p'/'s' characters की list को 1000 बार process करके किया गया, और कई runs में से सबसे अच्छा result इस्तेमाल हुआ

Experiment वाली function और compiler output

  • Target function string pointer को एक-एक करके आगे बढ़ाती है और character के हिसाब से integer res को update करती है
    • 's': res += 1
    • 'p': res -= 1
    • '\0': res return
    • बाकी characters: कोई बदलाव नहीं
  • शुरुआत इस उम्मीद से हुई कि function छोटी है, इसलिए gcc या clang इसे काफ़ी अच्छे, शायद optimal तरीके से optimize कर पाएँगे
  • clang ने जो शुरुआती assembly बनाई, उसने चारों cases को तीन conditional branches (je, je, jne) में बाँटा
    • res = 0 से शुरू
    • character पढ़कर पहले जाँचना कि वह '\0' है या नहीं
    • फिर 'p', 's' की comparison
  • शुरुआती clang result
    • Execution time: 3.23 सेकंड
    • Throughput: 295.26MiB/s
  • GCC ने थोड़ा ज़्यादा code generate किया, लेकिन वह थोड़ा तेज़ था

Rare termination condition से पहले common characters check करना

  • Loop termination सिर्फ null terminator character '\0' मिलने पर होती है, और इस function में null terminator अधिकतम एक बार ही आता है
  • clang output में '\0' को सबसे पहले check किया गया था, जिससे हर 'p' और 's' character पर पहले termination condition ही check होती थी
  • पहला manual change comparison order बदलकर 'p' और 's' को पहले check करना था
  • Result
    • Execution time: 3.10 सेकंड
    • Speedup: 1.04 गुना
    • Throughput: 307.64MiB/s

Basic block re-layout और jumps कम करना

  • दो common cases, 'p' और 's', दोनों loop start पर वापस jump करते हैं, इसलिए एक block को loop के ऊपर रखकर branch कम की जा सकती है
  • 's' block को loop के ठीक पहले रखने पर 's' process होने के बाद अलग jump के बिना flow loop में चला जाता है
  • इसके बदले function start पर 's' block को skip करने के लिए loop में एक बार jump करना पड़ता है
    • Function start jump सिर्फ एक बार होता है
    • 's' character कई बार मिल सकता है, इसलिए इसे acceptable trade-off माना गया
  • Result
    • Execution time: 2.98 सेकंड
    • Overall speedup: 1.08 गुना
    • Throughput: 320.02MiB/s

Arithmetic से एक unconditional jump हटाना

  • p: block से loop में लौटने वाले unconditional jmp को हटाने के लिए arithmetic का इस्तेमाल किया गया
  • एक decrement को sub eax, 2 के बाद inc eax से वही effect दिया जा सकता है, इसलिए 'p' process होने के बाद flow को 's' block में जाने दिया गया
  • इस तरीके से एक और branch instruction हट गई
  • Result
    • Execution time: 2.87 सेकंड
    • Overall speedup: 1.12 गुना
    • Throughput: 332.29MiB/s
  • इस point पर performance GCC 12 द्वारा generate किए code जैसी ही थी
    • GCC 12 code भी 2.87 सेकंड में चला
    • Manual version में 13 instructions थे
    • GCC output में 19 instructions थे
    • GCC code ने loop को unroll किया और case blocks को कुछ हद तक reuse किया लगता है

Conditional branches को cmove से replace करना

  • अगर conditional branches bottleneck हैं, तो branch predictor पर निर्भर हुए बिना conditional branch को ही हटाया जा सकता है
  • सबसे तेज़ version ने cmove, यानी condition equal move, का इस्तेमाल किया
  • नियम सरल हैं
    • Default value 0
    • Current character 's' हो तो 1
    • Current character 'p' हो तो -1
    • हर iteration में चुनी गई value को हमेशा res में add करना
  • इस तरीके ने control-flow graph से कई arrows हटा दिए
  • Result
    • Execution time: 0.48 सेकंड
    • Overall speedup: 6.73 गुना
    • Throughput: 1.94GiB/s
  • हाथ से लिखी गई compact C loop assembly में compiler द्वारा automatically न की गई optimization से 6 गुना से अधिक speedup संभव हुआ

Register बचाने की कोशिश और failed extra experiments

  • x86_64 के sete का इस्तेमाल करके 1-byte register को conditionally 0 या 1 पर set करने वाला version भी आज़माया गया
  • इस version ने r8d का इस्तेमाल हटाया, लेकिन सिर्फ cmov इस्तेमाल करने वाले version से धीमा था
  • Result
    • Execution time: 0.51 सेकंड
    • Overall speedup: 6.33 गुना
    • Throughput: 1.83GiB/s
  • कम registers इस्तेमाल करने या 32-bit operations की जगह 8-bit operations इस्तेमाल करने से speed बेहतर नहीं हुई
  • अतिरिक्त कोशिशों ने भी performance घटा दी
    • Best version का loop unroll: धीमा हुआ
    • Loop start को 16-byte boundary पर align करना: धीमा हुआ
    • GNU assembler में label से पहले .align <bytes> डालने पर nop insert किया जा सकता है

Benchmark environment और code

  • Code list GitHub पर है
  • Benchmark environment
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • CPU family 25, 6 cores, प्रति core 2 threads, 1 socket
    • clang: 16.0.1
    • gcc: 12.2.0
  • C version को -march=native से compile किया गया, ताकि specific CPU के लिए suitable code generate हो सके
  • Benchmark random 'p' और 's' से बनी 10 लाख characters की list पर किया गया
    • हर function version ने इस list को 1000 बार process किया
    • हर version को कई बार run किया गया और सबसे अच्छा result चुना गया
  • Follow-up article के रूप में part two linked है

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

1 टिप्पणियां

 
GN⁺ 2023-07-07
Hacker News टिप्पणियाँ

  • सही निष्कर्ष हाथ से लिखा assembly, C से 6 गुना तेज है नहीं, बल्कि jump, conditional arithmetic की तुलना में काफ़ी धीमा हो सकता है के ज़्यादा करीब है
    C में भी switch का उपयोग किए बिना, एक-दो if से इसे आसानी से वही प्रभाव दिया जा सकता है। C फ़ंक्शन को इस तरह बदलने पर कि s हो तो बढ़े, p हो तो घटे, और \0 हो तो समाप्त हो, 5.5 गुना तेज़ी मिली, और उदाहरण रन में समय 3.58 सेकंड से घटकर 0.65 सेकंड हो गया

    • बढ़िया। भाग 2 में C को फिर से लिखकर 12 गुना speedup मिला: https://owen.cafe/posts/the-same-speed-as-c/
      जैसा दूसरों ने कहा, input को adjust करने के बाद algorithm को vectorize भी किया जा सकता है। मैंने इसे एक शैक्षिक अभ्यास के रूप में देखा, और सच में उम्मीद है कि बिना पर्याप्त कारण किसी को assembly तक नीचे नहीं जाना पड़े
    • jump, conditional arithmetic से धीमा है यह बात तब सही है जब jump predict नहीं किया जा सकता। अगर jump predictable हो, तो jump ज़्यादा तेज़ होता है
      Linus ने भी पहले लंबा लिखा था कि predictable branch में cmov उपयोगी नहीं होता: https://yarchive.net/comp/linux/cmov.html
    • यह जानना दिलचस्प होगा कि कौन सा GCC version इस्तेमाल हो रहा है। Ubuntu और Windows दोनों में एक जैसी performance मिली, और gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 में lone और ltwo दोनों लगभग 3.58 सेकंड थे
    • यह जानना रोचक है कि switch को कई if में बदलना क्या हमेशा तेज़ होता है। यह भी जानना चाहूँगा कि कितने cases के बाद switch तेज़ हो जाता है, और अगर यह consistent है तो शायद यह compiler optimization में होना चाहिए
    • लगता है compiler को कम से कम इस स्तर का transform तो कर पाना चाहिए

  • मुझे लगता है कि मूल code compiler-friendly तरीके से लिखा नहीं गया था। अगर इसे result += *s == 's'; result -= *s == 'p'; की तरह लिखा जाए, तो compiler उपयुक्त branchless sete/cmov code बनाता है, और लेख के optimized assembly जितनी ही speed मिलती है
    हालाँकि यह loop unrolling या vectorization नहीं करता। अगर string size अलग से पास करके size ज्ञात हो, तो compiler को loop का आकार पता चल जाता है, इसलिए वह unroll कर सकता है, और संभव हो तो AVX-512 instructions भी उपयोग करता है। बड़े input पर यह काफ़ी तेज़ है, लेकिन खुद benchmark करने की आलस है। जो C programmer string length को track नहीं करते, वे अपनी मर्ज़ी करें, लेकिन सच कहूँ तो ऐसा नहीं करना चाहिए: https://godbolt.org/z/rde51zMd8

    • compiler-friendly version भाग 2 में है: https://owen.cafe/posts/the-same-speed-as-c/
      उस version ने 3.88GiB/s हासिल किया। जानबूझकर vectorization तक नहीं गया; दायरा छोटा रखते हुए लेख के assembly tips और tricks दिखाना चाहता था। बाद में input string को pad करके algorithm को vectorize करने पर भी एक लेख लिखा जा सकता है
    • code में एक महत्वपूर्ण पंक्ति गायब है: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • Nim में भी लगता है यह इस तरह trigger होता है: {.overflowChecks:off.} चालू करें और input पर iterate करते हुए 's' == c हो तो बढ़ाएँ, 'p' == c हो तो घटाएँ
      Apple M1 पर लगभग 5 गुना speedup मिला, और overflow checks चालू होने पर baseline C version की तुलना में लगभग 2 गुना तक ही तेज़ हुआ। SIMD optimization को trigger करने वाले अच्छे patterns जानना हमेशा उपयोगी है
    • “ऐसा नहीं करना चाहिए” से क्या मतलब string length को track नहीं करना है?

  • optimization expert के नज़दीक नज़रिए से मैं इस समस्या को पूरी तरह अलग तरीके से हल करता। मेरे कंप्यूटर पर शुरुआती C version 389MB/s था, और अगर लेख का assembly वही 6.2 गुना सुधार देता है, तो वह लगभग 2.4GB/s बनता है
    लंबे buffer पर यह C++ version मेरे कंप्यूटर पर 24GB/s से ऊपर जाता है: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    assembly के बिना, सिर्फ़ AVX2 intrinsic के आधार पर, मूल version की तुलना में 61 गुना तेज़

    • दिलचस्प। ymm register में counter रखने के बजाय movemask और popcnt का उपयोग करके prologue को vectorize किया जा सकता है
      यह अभी untested code है इसलिए benchmark चाहिए, लेकिन s, p, \0 masks बनाकर tzcnt, bzhi से string end तक के bits गिनने वाला तरीका संभव लगता है
    • जिज्ञासा है कि क्या यह std::experimental::simd से भी किया जा सकता है: https://en.cppreference.com/w/cpp/experimental/simd
    • अच्छा होगा अगर इसे @414owen के repository के साथ compatible रूप में फिर से लिखा जाए
    • AVX सीखने और अभ्यास करने के लिए अच्छे resources जानना चाहता हूँ

  • यह code SIMD के लिए वाकई बहुत उपयुक्त लगता है। अगर prototype को बदलकर explicit length लिया जा सके, तो 16-byte chunks पढ़कर process करना आसान होगा
    comparison results को सीधे जोड़-घटा सकते हैं, और function की शुरुआत में strlen() कॉल करके explicit length लेना ही शायद पर्याप्त रूप से फ़ायदेमंद होगा

  • मैंने जल्दी से एक RISC-V vectorized implementation बना लिया। यह rvv से string पढ़ता है, \0 की position ढूँढता है, फिर s और p की गिनती vcpop से करता है
    Mangopi MQ Pro(C906, rv64gc + rvv 0.7.1, 128-bit vector length) पर switch 0.19 Bytes/Cycle था, table C implementation 0.17 Bytes/Cycle था, और rvv 1.57 Bytes/Cycle था, जो लगभग 30KiB के बाद 1.35 तक गिर गया। अगर pointer को page-align करें और vl को page size से बड़ा न होने दें, तो 2/1.7 Bytes/Cycle तक संभव है

    • पूरी तरह सही करने के लिए load को fault-only-first load होना चाहिए। rvv में यह सुविधा है, नहीं तो null byte अगर allocated memory के बिल्कुल अंत से ठीक पहले हो, तो यह fail कर सकता है

  • यह x86 architecture की खासियत लगती है। branch न करने की लागत इतनी सस्ती है कि तुलना में branch महँगी दिखती है: https://wordsandbuttons.online/challenge_your_performance_in...
    लेकिन दूसरे processors पर ऐसा ज़रूरी नहीं है: https://wordsandbuttons.online/using_logical_operators_for_l...
    बड़ा सवाल यह है कि आम तौर पर C की ज़रूरत ही क्यों है। अगर किसी खास hardware पर सबसे अच्छा चलाने के लिए हाथ से tune करना है, तो C गलत tool है, और assembly के साथ एक ठीक-ठाक macro system चाहिए। C का मूल लक्ष्य system-level code को एक platform से दूसरे platform पर ले जाना आसान बनाना था, और इस प्रक्रिया में efficiency loss अपेक्षित था। यह कुछ वैसा है जैसे Hindi कविता को Urdu में अनुवाद करने के बजाय Esperanto में लिखकर मनचाही भाषा में auto-translate करना। आपको दो शानदार कविताएँ नहीं मिलेंगी, बल्कि जल्दी से दो कम-गुणवत्ता वाले अनुवाद मिलेंगे, और C की भूमिका वही है

  • FDO/PGO के साथ build करने पर branch और block rearrangement निश्चित रूप से हो सकते हैं। FDO के बिना compiler यह नहीं जान सकता कि कौन-सा branch कितनी बार चुना जाएगा। कुछ मामलों में FDO cmov को भी enable कर सकता है
    लेकिन cmov सामान्य test/jump से बेहतर है या नहीं, यह काफी हद तक इस पर निर्भर करता है कि branch कितनी predictable है, और आम तौर पर branch बहुत unpredictable हो तो cmov बेहतर चलता है। अगर cmov से 6 गुना तेजी मिली, तो मेरा अनुमान है कि test input लगभग पूरी तरह s और p वाली random strings है। यह गलत नहीं है, लेकिन benchmark को डेटा की बिना बताई गई विशेषता के हिसाब से optimize किया गया है, इसलिए लेख थोड़ा भ्रामक लग सकता है

    • test code यहाँ है: https://github.com/414owen/blog-code/blob/master/02-the-same...
      इसमें random रूप से 's' या 'p' चुना जाता है, और characters में 's', 'p', terminating null के अलावा कुछ नहीं आ सकता। अगर यह input property पता हो, तो result += (1 | *s++) - 'r'; जैसी जरूरत से ज़्यादा clever optimization भी संभव है। कोड बहुत ही smart है, लेकिन data properties के उपयोग वाली बात को पूरी तरह दिखाता है
    • string के अंदर '\0' फ़ंक्शन के return होने की वजह से ज़्यादा से ज़्यादा एक बार ही मिल सकता है, जबकि दूसरे characters कई बार आ सकते हैं। यह ऐसी जानकारी लगती है जो compiler को PGO के बिना भी उपलब्ध होनी चाहिए
      बेशक PGO मदद करता है, और मेरे computer पर 2.80 सेकंड आया, जो Rearranging blocks section के अंत वाले code से बेहतर था। input Benchmarking setup में समझाया गया है और repository में भी है: https://github.com/414owen/blog-code/blob/master/01-six-time...
      लेख के नीचे link किए गए part 2 में C code को जितना संभव हो उतना तेज बनाकर इस लेख की सारी assembly को हरा दिया गया है। मैंने कभी यह नहीं कहा कि assembly लिखना ज़रूर अच्छा विचार है; optimization और compiler output को समझना एक दिलचस्प चुनौती और अच्छा सीखने का मौका है

  • लगता है मैंने लेख और उसके follow-up से भी तेज बना लिया है। हालाँकि इसकी कीमत यह है कि यह उन strings के लिए specialized है जो सिर्फ 's' और 'p' से बनी हैं
    benchmark भी सिर्फ 's' और 'p' वाली strings को test करता है, इसलिए मुझे यह fair लगता है। मुख्य बिंदु यह है कि अगला character s हो तो res को 1 बढ़ाना है, लेकिन res += c - 'r' में s के लिए 1 मिलता है, जबकि p के लिए -2 मिलता है, इसलिए यह fail हो जाता है। लेकिन अगर 'p' - 'r' को unsigned integer माना जाए, तो underflow होगा और carry flag set हो जाएगा, और x64 का adc दो registers और carry flag को साथ जोड़ता है। इसलिए दो cmp, cmov को एक sub, adc से बदला जा सकता है। यह version follow-up लेख के C version से 1.08 गुना और मौजूदा x64-7 से 1.66 गुना तेज था। बेशक SWAR/SIMD से और सुधार संभव है

    • दिलचस्प तरीका है। शायद मुझे यह साफ़ कहना चाहिए था कि 02-the-same-speed-as-c/loop-5.x64.s की कुछ हद तक simple assembly ही मेरे पास मौजूद सबसे तेज version था
      मेरे computer पर loop-5.x64.s के लिए 0.244 सेकंड, और ऊपर वाले implementation के लिए 0.422 सेकंड आता है। यह फर्क क्यों है, ठीक-ठीक नहीं पता, और देखने में तो ऊपर वाला implementation तेज लगना चाहिए। इसलिए हमेशा उसी hardware पर benchmark करना चाहिए जहाँ वास्तव में चलाना है
    • एक और सरल तरीका यह हो सकता है कि array के सारे elements को जोड़ लिया जाए, फिर अंत में 'p' * len घटाया जाए, और ('s' - 'p') से भाग देकर s की गिनती निकाली जाए। p की गिनती len - s_count होगी
      शुरुआती summation भी आसानी से vectorize की जा सकती है। अगर मुझसे कोई गलती नहीं हुई, तो यह काम करेगा; एकमात्र समस्या accumulated sum के overflow की संभावना है। खुद benchmark करने का उत्साह नहीं है। सुधार: मैं s देखने पर घटने वाले हिस्से को भूल गया था, इसलिए अंतिम result p_count - s_count है

  • strlen() शायद काफ़ी तेज implement किया गया होगा, और अगर buffer size पता हो तो compiler inner loop को auto-vectorize कर सकता है
    वास्तव में len = strlen(buf) के बाद for loop में (buf[i] == 's') - (buf[i] == 'p') जोड़ने वाला code auto-vectorize हो जाता है: https://gcc.godbolt.org/z/qYfadPYoq

  • मैंने पहले SBCL के लिए Common Lisp UTF-8 decoder लिखा था। built-in decoder पहले से था, इसलिए यह अभ्यास के लिए था
    साफ़ तौर पर आसान optimizations को छोड़ दें, तो लगभग हर performance improvement कोड को इस तरह structure करने से आया कि compiler branch के बजाय cmov* instructions generate करे

    • जानना चाहूँगा कि आपने code किस तरह बदला। और क्या आपने सही instructions इस्तेमाल हो रहे हैं या नहीं यह देखने के लिए function को बार-बार disassemble किया, या benchmark से वास्तविक सुधार की पुष्टि की
    • अगर branch सही तरह predict हो जाए, तो उसके conditional move से तेज होने की संभावना अधिक है। क्योंकि branch critical path length नहीं बढ़ाता
      UTF-8 decoder आम तौर पर ऐसे input पर बहुत चलता है जो पूरा ASCII होता है। जानना चाहूँगा कि benchmark किस input पर किया गया था