SIMD एल्गोरिद्म को शुरुआत से डिज़ाइन करना

 (mcyoung.xyz)
2 पॉइंट द्वारा GN⁺ 2023-11-29 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Rust के std::simd से बने vb64 base64 codec में procedural loop को जस का तस vectorize करने के बजाय, data layout और operation flow को circuit की तरह फिर से design करना पड़ता है, तभी तेज़ और portable SIMD code बनता है
  • मुख्य optimization branching और memory access से होने वाले stall को घटाने में है; compare, mask, select और shuffle से ऐसी branchless structure बनाई जाती है जो input से स्वतंत्र होकर वही operations करती है
  • base64 decoding में ASCII characters को sextet में बदलने के लिए byte >> 4 और / correction का इस्तेमाल करते हुए perfect hash बनाया जाता है, और SIMD vector के अंदर lookup table व shuffle से offset खोजा जाता है
  • चार 6-bit sextet को तीन bytes में pack करते समय lane को u16 तक बढ़ाकर shift किया जाता है, फिर low/high byte अलग किए जाते हैं और rotate_lanes_left व OR से adjacent lane के byte fragments जोड़े जाते हैं
  • benchmark में -Zbuild-std, -Ctarget-cpu=native, N = 32 combination और remainder loading optimization के बाद crates.io की baseline base64 implementation की तुलना में लगभग पूरे range में करीब 2x performance दिखी

SIMD की ज़रूरत का भौतिक background

  • computer performance में सुधार सिर्फ theoretical CS से नहीं, बल्कि physical constraints से सीधे जुड़ा है
  • Moore’s law 2023 तक अब भी कायम दिखता है, लेकिन पिछले 15 सालों में Dennard scaling का असर टूट गया, जिससे अधिक dense transistors power consumption density बढ़ाने लगे
  • clock frequency को लगातार बढ़ाना मुश्किल होने के बाद, 2000s की शुरुआत से performance improvement की मुख्य दिशा ज़्यादा cores इस्तेमाल करने की ओर शिफ्ट हुई
  • multithreading में cores के बीच cooperation चाहिए, जिससे synchronization cost आती है; jump, virtual call और synchronization जैसे control flow stall पैदा करते हैं
  • stall के दो मुख्य कारण हैं
    • branching: if, loops, function calls, function returns, C का switch जैसे control flow
    • memory operations: load/store, खासकर cache-friendly न होने वाले access

Procedural code और instruction-level parallelism

  • modern CPU core code को line-by-line execute नहीं करता, बल्कि एक-दूसरे पर निर्भर न होने वाले operations को साथ-साथ issue करता है
  • a = x + y और b = x ^ y जैसे operations जो एक-दूसरे पर निर्भर नहीं हैं, add और xor circuits को साथ-साथ इस्तेमाल कर सकते हैं
  • यही तरीका instruction-level parallelism है, और इसे बाधित करने वाली dependencies को data hazard कहा जाता है
  • CPU जितना बेहतर functional units को saturate कर पाता है, उतने अधिक operations प्रति unit time process करता है
  • branch में अगला instruction fetch करने से पहले condition calculation का इंतज़ार करना पड़ता है, और memory operation में data को physically CPU तक पहुंचना होता है, इसलिए stall होता है
  • GPU images को vector-form pixels की तरह handle करता है और high locality वाले operations बहुत करता है, इसलिए वह batch operations और limited control flow के लिए design की गई SIMD machine के काफ़ी करीब है
  • SIMD का मतलब single instruction, multiple data है, यानी एक instruction कई data lanes पर parallel operation करता है

lane-level सोच

  • SIMD और vector अक्सर एक ही अर्थ में इस्तेमाल होते हैं, और SIMD instruction की basic unit fixed-size number array यानी vector होती है
  • vector के हर component को lane कहा जाता है
  • SIMD vector को register में fit होना होता है, इसलिए वह आम तौर पर छोटा होता है
    • example environment की maximum vector width 256 bits है
    • यह u8x32 के 32 bytes या f64x8 के 4 doubles के बराबर है
  • छोटा vector भी अगर pipeline saturation का burden 4x घटा सके, तो उतना ही latency improvement मिल सकता है

popcnt से दिखता divide-and-conquer

  • सबसे simple vector operations bitwise and/or/xor हैं
  • normal integer को भी bitwise operation के नज़रिए से 1-bit lanes के vector की तरह देखा जा सकता है
    • इस नज़रिए से i32, i1x32 जैसा है
  • popcnt integer के अंदर 1 bits की संख्या गिनने वाला operation है, और i32 को i1x32 मानें तो यह reduce operation है
  • 32 bits को array की तरह निकालकर जोड़ने वाली simple implementation खराब code बना सकती है
  • बेहतर तरीका है adjacent bit pairs को जोड़ना, फिर pairs के pairs को जोड़ना, यानी lane width बढ़ाते हुए sum करना
    • 0x55555555, 0xaaaaaaaa masks से even/odd bits अलग करना
    • shift से lanes align करके जोड़ना
    • फिर 2-bit, 4-bit, 8-bit, 16-bit units में दोहराना
  • यह implementation popcnt instruction में optimize नहीं होती, लेकिन ऐसे systems पर छोटा और तेज़ code बनती है जहाँ वह instruction नहीं है
  • u64 पर भी reduction का सिर्फ एक और step जोड़कर इसे लागू किया जा सकता है, और पूरे u64 addition की ज़रूरत नहीं होती
  • ऐसा divide-and-conquer approach SIMD programming का core pattern है

SIMD instruction set के मुख्य tools

  • real SIMD vectors scalar से ज़्यादा complex semantics देते हैं, और slow control flow को replace करने वाली capabilities खास तौर पर महत्वपूर्ण हैं
  • available instructions architecture पर काफी निर्भर करते हैं
    • x86 के कई high-performance cores AVX2 implement करते हैं
    • AVX2 256-bit ymm vectors देता है
    • registers में खुद lane count नहीं होता; instruction तय करता है कि lanes को कैसे interpret करना है
    • उदाहरण के लिए vpaddb, ymm को i8x32 की तरह interpret करता है
  • आम तौर पर उपलब्ध operations ये हैं
    • bitwise operations: lane width हमेशा implicitly 1 bit होती है
    • lane-wise arithmetic: addition, subtraction, multiplication, division, integer shift, min/max आदि
    • lane-wise comparison: m[i] = a[i] < b[i] जैसा mask vector बनाता है
    • select: mask का उपयोग करके दो vectors में से lane-wise value चुनता है
    • shuffle/swizzle: एक vector को lookup table की तरह देखकर index vector से lanes को rearrange करता है
  • mask vector के true/false आम तौर पर all-ones या all-zeros bit pattern इस्तेमाल करते हैं
  • comparison और select ऐसे core tools हैं जो SIMD code को branchless बनाए रखने में मदद करते हैं
  • branchless code input से स्वतंत्र होकर वही operations करता है, और x * 0 = 0, a ^ b ^ a = b जैसे properties से unnecessary results को discard करता है

shuffle से data position align करना

  • SIMD में data को “सही position” पर लाने के लिए shuffle core tool है
  • broadcast या splat ऐसा vector बनाता है जिसमें सभी lanes के पास वही scalar होता है, और इसे [0, 0, ...] index shuffle से express किया जा सकता है
  • interleave या zip/pack दो vectors a, b की lanes को बारी-बारी arrange करता है
    • c = [a[0], b[0], a[1], b[1], ...]
    • इसे shuffle2 से implement किया जा सकता है
  • deinterleave या unzip/unpack, interleave का उल्टा है
  • rotate b[i] = a[(i + j) % n] रूप में lanes को rotate करता है, और यह भी shuffle ही है
  • SIMD programming में integer से बड़े data blocks को अलग-अलग sizes के छोटे blocks के रूप में reinterpret और rearrange करना अक्सर होता है

intrinsics, target feature, portable SIMD

  • SIMD में उपयोग किए जा सकने वाले operations architecture और instruction set extension के अनुसार बदलते हैं
  • x86 में ऐसे operations हो सकते हैं जो ARM में नहीं हैं, और Intel AVX-512 की तरह एक ही vendor के भीतर भी ऐसे extensions हो सकते हैं जो केवल advanced server chips में मिलते हैं
  • toolchain ऐसे extensions को target feature के रूप में generalize करता है
    • Linux का lscpu CPU द्वारा पहचाने जाने वाले features दिखाता है
    • LLVM feature settings के अनुसार instruction selection अलग तरह से करता है
    • LLVM को ymm इस्तेमाल करने वाला code emit करने के लिए +avx2 होना ज़रूरी है
  • -march=native या -Ctarget-cpu=native build करने वाली machine के हिसाब से अच्छा code बना सकते हैं, लेकिन दूसरे processors पर portability घट सकती है
  • runtime feature detection वह तरीका है जिसमें CPU द्वारा support की जाने वाली capabilities की जाँच कर तय किया जाता है कि function का कौन-सा version call करना है; यह encryption libraries जैसे उन codebases में इस्तेमाल होता है जिन्हें कई तरह के devices पर deploy किया जाता है
  • C++ का SIMD code आम तौर पर _mm256_cvtps_epu32 जैसे intrinsics का उपयोग करता है
    • ये किसी specific instruction set के low-level operations को दर्शाते हैं
    • ये ज़रूरी नहीं कि हमेशा एक single instruction में map हों
    • compiler merging, duplicate removal और instruction selection optimization कर सकता है
  • अगर कई instruction sets के लिए मिलता-जुलता code बार-बार लिखना पड़े, तो assembly की तुलना में maintainability का लाभ बहुत बड़ा नहीं रह सकता
  • portable SIMD library का approach यह है कि library level पर कुछ instruction selection handle किया जाए और बाकी compiler पर छोड़ दिया जाए
  • vb64 implementation यह जाँचने का experiment है कि Rust का portable SIMD competitive code generate करता है या नहीं

base64 decoding को SIMD में बदलना

  • base64 arbitrary binary data को ASCII में encode करने का तरीका है
  • input byte sequence को bit vector मानकर उसे 6-bit chunks, यानी sextet, में बाँटा जाता है
  • sextet value को निम्न characters में map किया जाता है
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • base64 के कई variants हैं, लेकिन complexity का ज़्यादातर हिस्सा common है
  • ध्यान देने वाली दो बातें हैं
    • base64 ऐसा format है जिसमें byte के भीतर bits big endian होते हैं
    • input length 4 से divide न भी हो सकता है; सिद्धांततः इसे = padding से 4 के multiple में मिलाया जाता है, लेकिन गलत padding वाले messages भी handle किए जा सकते हैं
  • decoded length की गणना input / 4 * 3 में input % 4 के अनुसार बची हुई length जोड़कर की जाती है

branchless की ओर basic refactoring

  • simple base64 decoder में कई branches होते हैं
    • input को chunks में iterate करने वाला loop
    • chunk के भीतर byte loop
    • ASCII characters के अनुसार match
    • error होने पर return Err
    • decoded_len के भीतर match
    • Vec::extend_from_slice और allocator call की संभावना
  • optimization guideline है सभी branches हटाना
  • decoded_len का match, input % 4 की values 0, 1, 2, 3 को 0, 1, 1, 2 में map करता है
  • इसे mod4 - mod4 / 2 से बदलने पर branchless version बन जाता है
  • LLVM मूल match को switch table में fold कर सकता है, लेकिन इस area में अनावश्यक memory access performance घटाता है

सबसे hot loop को अलग करना

  • SIMD की ताकत यह है कि वह एक बार में बहुत सारा data process करके loop को strongly unroll कर सकता है और उसे branchless के करीब बना सकता है
  • hot loop का लक्ष्य अधिकतम 4 bytes पढ़ना, अधिकतम 3 bytes का decoded result बनाना, और syntax error है या नहीं यह भी बताना है
  • तीन facts का उपयोग किया जा सकता है
    • output length branchless decoded_len() से calculate की जा सकती है
    • invalid base64 को बहुत rare path माना जा सकता है, और error position चाहिए तो बाद में फिर से scan किया जा सकता है
    • base64 में A का मान 0 होता है, इसलिए truncated chunk को A से pad करने पर value नहीं बदलती
  • decode_hot() को इस रूप में अलग किया जाता है कि वह चार input bytes process करे और decoded result तथा success status का bool return करे
  • Option<[u8; 3]> के बजाय bool अलग से return करने पर आगे if !ok branch हटाना आसान होता है
  • SIMD version में input के रूप में Simd<u8, 4> लिया जाता है, और output को भी power-of-two lane count के अनुरूप Simd<u8, 4> रखा जाता है
    • वास्तव में आवश्यक output 3 bytes है
    • आखिरी lane इस्तेमाल नहीं होता

ASCII को sextet में बदलने का तरीका

  • ASCII character को sextet में बदलने वाले match का ज़्यादातर हिस्सा byte - C के रूप में व्यक्त किया जा सकता है
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • lane-wise offset vector बनाकर ascii - offsets किया जा सकता है
  • पहला approach compare-and-select है
    • A-Z, a-z, 0-9, +, / के लिए masks बनाए जाते हैं
    • जिस lane में कोई भी mask select नहीं हुआ, उसे invalid माना जाता है
    • हर mask से संबंधित offset को splat कर OR से combine किया जाता है
  • यह तरीका elegant और competitive code बना सकता है, लेकिन कुल 8 comparisons चाहिए और कई live values रहने से register pressure बन सकता है

SIMD hash table और perfect hash

  • A-Z, a-z, 0-9 की byte ranges क्रमशः 0x41..0x5b, 0x61..0x7b, 0x30..0x3a हैं और उनका high nibble अलग है
  • + और / क्रमशः 0x2b, 0x2f हैं, इसलिए सिर्फ byte >> 4 से ज़्यादातर distinction किया जा सकता है
  • / के case में एक घटाने पर range के लिए perfect hash बन जाता है
  • (byte >> 4) - (byte == '/') की mapping इस प्रकार है
    • A-Z → 4 या 5
    • a-z → 6 या 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • यह value छोटी है, इसलिए offset lookup table को SIMD vector के अंदर रखकर shuffle से lookup किया जा सकता है
  • इस perfect hash idea को GitHub issue में एक anonymous user ने सुझाया था
  • Simd::swizzle_dyn() में यह constraint है कि index array और lookup table की length समान होनी चाहिए
  • perfect hash method में sextet calculation के दौरान validation side effect के रूप में नहीं मिलती, इसलिए उसी GitHub issue के exact bloom filter का उपयोग करके byte validity check की जाती है
  • implementation example vb64 के simd.rs में है

चार sextets को तीन bytes में pack करना

  • चार 6-bit sextets को तीन bytes में combine करने वाला step अधिक tricky है
  • किसी specific input sextet को all-ones रखकर और output में bits कहाँ move होते हैं यह देखकर placement relationship trace किया जा सकता है
  • केवल byte-level shuffle पर्याप्त नहीं है
    • जिस target पर move करना है वह byte fragment है
    • सिर्फ shift भी पर्याप्त नहीं है
    • overshifted bits को adjacent lane में move करना होता है
  • समाधान है lane को बड़ा बनाना
  • sextets को u16 vector में cast करने के बाद lane-wise shift किया जाता है
    • input[0] को 2-bit shift
    • input[1] को 4-bit shift
    • input[2] को 6-bit shift
    • input[3] को 8-bit shift से adjust किया जाता है
  • shift result से low byte और high byte vectors अलग किए जाते हैं
  • hi.rotate_lanes_left::<1>() से high byte side के fragments को adjacent lane के साथ align करने के बाद lo | hi_rotated से combine किया जाता है
  • यह तरीका hardware primitives का actively उपयोग करता है, इसलिए code छोटा और efficient है

lane की संख्या बढ़ाना और garbage lane हटाना

  • Simd<u8, 4> x86 के न्यूनतम 128-bit vector register से भी छोटा है, इसलिए decode_hot() को lane की संख्या N के लिए generic बनाया गया
  • LaneCount<N>: SupportedLaneCount constraint से छोटी power-of-two lane संख्या सुनिश्चित होती है
  • lookup table और shift table tiled() helper के जरिए repeating pattern वाले vector बनाते हैं
  • N = 4 में आखिरी lane की garbage value को ignore करना काफी था, लेकिन N बड़ा होने पर every fourth lane में garbage मिल जाती है
  • इसे हटाने के लिए shuffle का उपयोग किया गया
    • वांछित संबंध है shuffled[i] = output[i + i / 3]
    • हर चौथे index को skip करके garbage lane हटाई जाती है
    • overflow वाला हिस्सा final output vector का ऊपरी 1/4 होता है, इसलिए उसे ignore किया जाता है
  • इससे decode_hot::<32>() के जरिए 32 base64 byte को parallel decode किया जा सकता है

outer loop optimization

  • decode() को भी अंदरूनी lane संख्या N के लिए generic बनाया गया
  • बची हुई लागतें इस प्रकार हैं
    • for chunks in ... की length comparison branch
    • [T]::copy_from_slice का variable-length memcpy
    • हर loop iteration में ok branch
    • Vec::extend_from_slice की allocator call की संभावना और एक और memcpy
  • output length पता होने के कारण out.reserve(final_len + N / 4) से पहले ही space reserve किया गया
  • इसके अलावा slop space रखकर variable-length memcpy के बजाय full SIMD store किया गया
  • हर iteration पूरा SIMD vector लिखता है, और अगला write 3/4 * N जितना आगे बढ़कर पिछली garbage byte को overwrite करता है
  • आखिरी garbage byte final Vec::set_len() में शामिल नहीं होती, इसलिए उसे हटाई गई मानकर handle किया जाता है
  • if !ok के कारण early return होने पर भी, set_len() से commit नहीं किया गया होता, इसलिए out unchanged state में रहता है

error handling को hot loop के बाहर टालना

  • हर iteration में if !ok से return करने के बजाय, error |= !ok से accumulate किया गया
  • final set_len() से ठीक पहले केवल एक बार error status check किया गया
  • यह मानते हुए कि ज्यादातर base64 blob valid होते हैं, error path को hot loop से बाहर धकेल दिया गया
  • syntax error होने पर भी बाद के SIMD operations मनमाने ढंग से misbehave नहीं करते, इसलिए garbage write commit नहीं होता और गायब हो जाता है
  • इसके बाद Vec::push() जैसी calls उसी buffer region को overwrite कर सकती हैं

unroll and jam और remainder handling

  • copy_from_slice के variable-length memcpy को घटाने के लिए unroll and jam लागू किया गया
  • loop को दो हिस्सों में बांटा गया
    • hot vectorized loop: हमेशा length N input ही process करता है
    • cold remainder part: i < N input को अधिकतम एक बार process करता है
  • Rust के Iterator::chunks_exact() का उपयोग करके hand-rolled unroll-and-jam implement किया गया
  • hot loop में Simd::from_slice() call करके single vector-sized load किया जाता है
  • bounds check ऐसा रूप ले लेता है जिसे compiler के लिए हटाना आसान होता है

benchmark और manual loading optimization

  • benchmark में length 0 से लगभग 200 या 500 byte तक के messages decode किए गए और crates.io के baseline base64 implementation से compare किया गया
  • compile options में -Zbuild-std और -Ctarget-cpu=native का उपयोग किया गया
  • tuning के परिणामस्वरूप N = 32 सबसे अच्छा निकला, और हर hot loop iteration में एक YMM register का उपयोग होता है
  • शुरुआत में baseline से बेहतर प्रदर्शन मिला, लेकिन data.len() % 32 से strongly correlated heartbeat जैसी performance variation दिखी
  • assembly देखने के बाद अनुमान लगाया गया कि copy_from_slice byte-wise load loop की तरह inline/unroll हुआ है
  • Simd::gather_or() भी आजमाया गया, लेकिन उसने और खराब assembly बनाई, इसलिए उसका उपयोग नहीं किया गया
  • इसके बजाय variable-length data के लिए manual loading function लिखा गया
    • hot part में loop के अंदर संभव सबसे बड़ा scalar load, यानी u128 load, किया गया
    • LLVM 16-byte chunk को XMM load में lower करता है
    • remainder के लिए overlapping u64, u32, u8 load का उपयोग किया गया
  • 15 byte पढ़ते समय p से u64, और p + 7 से u64 पढ़कर 1 byte overlap कराया गया और OR से combine किया गया
  • 4~7 byte के लिए overlapping u32 load इस्तेमाल किया गया
  • 1~3 byte के लिए p, p + len/2, p + len - 1 से पढ़कर कुछ bytes duplicate load हो सकते हैं, लेकिन branch count घटता है
  • नया loading code लागू करने के बाद variance बहुत कम हो गया, और baseline की तुलना में लगभग पूरे range में 2x performance दिखी

encoding और web-safe base64

  • encoding function के लिए decode_hot() के operations को उल्टा करने वाला encode_hot() implement करना होता है
  • decoding में इस्तेमाल किया गया perfect hash encoding के लिए fit नहीं बैठता, इसलिए नया hash चाहिए
  • encoder के आसपास का loading/storing code भी decoder से थोड़ा अलग है
  • vb64 efficient encoding routine भी implement करता है
  • web-safe base64 एक variant है जिसमें + और / को - और _ से बदला जाता है
  • web-safe base64 के perfect hash की संरचना अधिक कठिन है, और उदाहरण के तौर पर (byte >> 4) - (byte == '_' ? '_' : 0) जैसी method की जरूरत पड़ सकती है
  • vb64 अभी web-safe base64 support नहीं करता

निष्कर्ष

  • vb64 कोई ऐसी library नहीं है जो किसी महत्वपूर्ण bottleneck को solve करने का दावा करती हो, और लेखक बताते हैं कि उन्हें ऐसी जगह नहीं पता जहां base64 decoding सच में bottleneck हो
  • branchless code अक्सर overkill होता है, लेकिन यह समझने में मदद करता है कि compiler क्या कर सकता है और क्या नहीं
  • Rust का std::simd कुल मिलाकर अच्छा है और बेहतरीन code generate करता है
  • SIMD code को और सरल बनाने के लिए कुछ rough edges हैं जिन्हें ठीक किया जाना अच्छा होगा, लेकिन वर्तमान काम के परिणाम से संतुष्टि जताई गई
  • SIMD और performance optimization जटिल विषय हैं जिनमें बहुत-सी tricks और hardware knowledge चाहिए, और उनमें से काफी कुछ documented नहीं है

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

1 टिप्पणियां

 
GN⁺ 2023-11-29
Hacker News की राय

  • portable SIMD को सच में इस्तेमाल होते देखना रोचक था, और Zen 3 सिस्टम पर benchmark दोहराकर देखा तो वही speedup मिला
    M1 MacBook Pro पर input length 110 bytes होने पर performance gain 1.4x से शुरू होकर धीरे-धीरे 2x तक पहुँचा; x86_64 से कम है, लेकिन लगता है लक्ष्य हासिल हो गया
    हालांकि code देखकर मेरे इस अनुभव की पुष्टि होती है कि Rust में SIMD और pointer से जुड़े कामों, और व्यापक रूप से performance engineering के लिए ergonomics काफ़ी खराब हैं

    • Rust engineer के नज़रिए से कुछ हद तक सहमत हूँ, लेकिन pointers और raw memory operations पर safety की वजह से जानबूझकर काफ़ी constraints हैं, और भाषा आपको सच में सोचने पर मजबूर करती है कि वह क्या कर रही है
      फिर भी Rust का portable SIMD, C++ की तुलना में अभी कोई बहुत अच्छी कहानी नहीं है, और raw byte regions, pointers, buffers manipulation तक उतरना हो तो Pin, MaybeUninit वगैरह से परिचित होना पड़ता है
      portable_simd और allocator_api कई सालों से unstable हैं, entry barrier भी ऊँचा है और वे ज़्यादा awkward हैं, मगर इसका अधिकतर हिस्सा intentional design है
      हालांकि अपने program के भीतर इस्तेमाल आसान करने वाले abstractions खुद बनाने या third-party crates इस्तेमाल करने से कोई नहीं रोकता
    • ergonomics खराब हैं, इससे मैं सहमत नहीं हूँ
      C++ SSE intrinsic में underscores भी भद्दे लगते हैं और नाम याद रखना भी मुश्किल है, वह कहीं ज़्यादा खराब है

  • classic C++ में अपनी तरफ़ से best implementation करने के बाद, जब कोई SIMD version बनाकर उसे 10 गुना से भी ज़्यादा तेज़ कर देता है, तो कभी-कभी सचमुच हैरानी होती है
    बदले में यह code कम portable होता है
    काश compiler की auto-vectorization और बेहतर हो, और language level पर कुछ annotations जैसा support भी हो जो local स्तर पर कुछ operations reordering की अनुमति दे

    • अच्छा SIMD code data memory में कैसे laid out है, इस पर बहुत बारीकी से ध्यान चाहता है
      compiler बहुत local context से बाहर data को आपकी तरफ़ से बदल नहीं सकता, इसलिए auto-vectorization सच में कठिन हो जाती है
    • compiler अगर perfectly optimize कर भी सके, तब भी कई unavoidable serial guarantees होती हैं
      उदाहरण के लिए for(double v: vec) sum+=v में floating-point addition associative नहीं होता, इसलिए values को क्रम से जोड़ना और SIMD तरीके से 8-8 के gap में जोड़कर बाकी को merge करना समान नहीं है
      compiler के नज़रिए से यह obvious optimization लग सकता है, लेकिन जब तक आप उसे किसी खास guarantee को relax करने के लिए न बताएं, वह optimization से पहले serial semantics guarantee को प्राथमिकता देता है
      इसलिए चीज़ें गड़बड़ हो जाती हैं, और janwas के कहे अनुसार hot paths के लिए libraries, खासकर Google Highway या Intel ISPC जैसी चीज़ें इस्तेमाल करना बेहतर लगता है
    • यही C++ जैसी systems programming language का एक point है
      जितना हो सके portable तरीके से efficient रहने की कोशिश करते हुए भी, ज़रूरत पड़ने पर target-specific programming आसान बनाना
      auto-vectorization में FORTRAN compilers निश्चित तौर पर बेहतर हैं, क्योंकि aliasing allowed नहीं होती
      C++ C के memory model को follow करने के कारण अटक जाता है
    • बस CUDA भी इस्तेमाल कर सकते हैं
      CUDA आज की ultimate SIMD machine, यानी GPU, के लिए design किया गया C++ है, और ROCm असल में AMD के लिए CUDA जैसा ही है
      निजी तौर पर मुझे Microsoft का C++AMP पसंद था; मुझे लगता है वह शुरू करने के लिए सबसे आसान था
      लेकिन आखिरकार वह जम नहीं पाया, यह अफ़सोस की बात है
    • मेरे अनुभव में ऐसा अक्सर होता है
      साथ ही SIMD wrapper library इस्तेमाल करने पर असल में इसे काफ़ी portable बनाया जा सकता है

  • छोटी-सी note के तौर पर, compiler उस popcount implementation को single instruction में optimize नहीं कर पाया, लेकिन दूसरी implementation में यह संभव है
    बेशक, यह काफ़ी tricky है: https://godbolt.org/z/T69KxWWW8

  • _mm256_cvtps_epu32 के बारे में कहा गया कि यह किसी specific instruction set का low-level operation दर्शाता है और इसे AVX2 का float-to-int cast बताया गया, लेकिन वह instruction AVX-512 में आती है
    AVX2 में float-to-int cast नहीं है, और AVX1 में integer result signed होता है तथा instruction _mm256_cvtps_epi32 है

  • fastbase64[0] से तुलना कैसी होगी, यह जानने की उत्सुकता है
    लेख बढ़िया है और ऐसी चीज़ें online देखना अच्छा लगता है, लेकिन portable SIMD library को लेकर लेखक जितने optimistic हैं, उतना मैं साझा नहीं कर पाता
    [0]: https://github.com/lemire/fastbase64

  • SIMD को C++ या Rust में जोड़ने से बेहतर मुझे ISPC ही लगता है
    यह dynamic dispatch भी support करता है, जिसे खुद implement करना दर्दनाक feature है

    • अगर कोई tool लोगों से SIMD का ज़्यादा इस्तेमाल करवाता है तो आम तौर पर अच्छी बात है, लेकिन निजी तौर पर मैं चाहूँगा कि SIMD उसी toolchain में integrated हो
      ताकि C++ में वापस inline calls भेज सकें, SIMD code में templates और classes इस्तेमाल कर सकें, और कई SIMD code regions को साथ में inline भी कर सकें
      dynamic dispatch implement करना मुश्किल है, इससे सहमत हूँ, लेकिन Highway वह हिस्सा संभाल देता है
    • सोच रहा हूँ कि article जैसी छोटी subroutine में C++ या Rust से ISPC call करना आसान है या नहीं

  • शानदार लेख है, और यह एहसास बहुत ज़ोर से रह जाता है कि “मैं कभी इतना smart नहीं हो पाऊँगा”

    • बस यह आपका work domain नहीं है
      कुछ वैसा ही जैसे आम लोग software engineer या physicist नहीं होते
      कुछ महीनों तक focus करके पढ़ें तो आप similar level तक कर पाएँगे
    • अगर ऐसे employer या project से मिलने का मौका मिले जहाँ इसकी ज़रूरत हो, तो शायद आप “इतने smart” हो सकते हैं
      आखिरकार यह interest और need का मामला है
      मैं भी personal projects में performance optimization या systems के करीब bare-metal engineering में आता-जाता रहता हूँ, लेकिन काश काम में इसकी ज़रूरत ज़्यादा पड़ती
      हालांकि industry के ज़्यादातर कामों में इसकी demand नहीं होती
    • AoC '23 को APL/j/k, BQN, Python/numpy, CUDA आदि में करके देखना अच्छा रहेगा
      idiomatic Python नहीं, बल्कि सब कुछ numpy से हल करने जैसा
      यह मज़ेदार है और इस तरह की cleverness सीखी जा सकती है; लेख के कई हिस्से उन भाषाओं में समस्याएँ हल करने की सोच के हिसाब से बहुत natural लगते हैं
      समय के साथ आप समस्याओं को उसी रूप में देखने लगते हैं
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • दिलचस्प लेख है
    शुरुआत के पहले उदाहरण में कहा गया है कि non-vectorized popcnt implementation “ईमानदारी से कहें तो हास्यास्पद रूप से खराब code” बनाता है, लेकिन release mode में native target CPU इस्तेमाल करने पर वह function काफी ठीक-ठाक vectorize होता दिखता है
    https://godbolt.org/z/WE1Eq65jY

    • नीचे वाला code समान output बनाना चाहिए
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      यह popcnt eax, edi; ret में compile होता है
      बड़े bit vectors में AVX2 implementation POPCNT से तेज़ हो सकता है
      “Faster Population Counts Using AVX2 Instructions” देखें: https://academic.oup.com/comjnl/article/61/1/111/3852071
      32-bit पर्याप्त बड़ा नहीं है, और Rust जो code generate करता है वह सच में हास्यास्पद रूप से खराब है
    • आदर्श रूप से लगता है कि इसे popcnt instruction में lower होना चाहिए
    • auto-vectorization कभी होती है और कभी नहीं
      हाल ही में मैंने ऐसा code लिखा था जिसमें vector operation के result mask में bits की संख्या count करनी थी, और यह अच्छी तरह popcnt में बदल गया
      https://godbolt.org/z/zT9Whcnco

  • “यह तो trap question जैसा है… बस add नहीं है क्या?” जैसे हिस्सों की वजह से आम तौर पर मन करता है कि intermediate vector representation को target किया जाए और details compiler पर छोड़ दी जाएँ
    उदाहरण के लिए Haswell chips में प्रति core कई floating-point execution units थे, और CPU एक साथ दो या उससे अधिक pipelined floating-point operations execute कर सकता था, लेकिन उनमें से केवल एक add instruction हो सकती थी
    अगर पिछले result पर निर्भर न होने वाले बहुत सारे additions हों और latency से बचा जा सकता हो, तो multiplier term 1 वाले fused multiply-add instructions भी साथ भेजकर addition throughput को दोगुना किया जा सकता था
    वह instruction सामान्य vector floating-point addition के साथ-साथ execute हो सकती थी