हर डेवलपर को SIMD क्यों जानना चाहिए

 (mitchellh.com)
1 पॉइंट द्वारा GN⁺ 2 시간 전 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • SIMD सिर्फ हाई-परफॉर्मेंस सॉफ्टवेयर के लिए कोई जटिल तकनीक नहीं है, बल्कि लगातार डेटा को कई वैल्यूज़ के समूहों में प्रोसेस करके सामान्य loops को तेज करने वाला रोज़मर्रा का optimization तरीका है
  • आम SIMD code आमतौर पर 5-स्टेप structure फॉलो करता है: constant broadcast, vector-width traversal, parallel operations, result reduction/storage, और scalar tail handling
  • Ghostty का codepoint search loop एक बार में 4, 8, या 16 u32 की तुलना करता है, जिससे theoretical throughput ARM NEON पर अधिकतम 4x, AVX2 पर 8x, और AVX-512 पर 16x तक बढ़ सकता है
  • AVX2 Intel desktop पर terminal की overall throughput करीब 5x तेज हुई, और अगर supported vector width न हो या input बच जाए, तो पुराना scalar loop पूरा input या बचा हुआ हिस्सा प्रोसेस करता है
  • Compiler की auto-vectorization simple loops में भी मौके चूक सकती है, इसलिए पहले optimized output जांचें; लेकिन अहम hot loops में explicit SIMD से behavior और performance को predictable रखा जा सकता है

SIMD क्या करता है

  • SIMD CPU को एक instruction से कई values parallel में प्रोसेस करने देता है
    • bytes को एक-एक करके compare करने के बजाय, एक बार में 4, 8 या उससे ज्यादा compare किए जा सकते हैं
    • for (byte in bytes), for (character in string), for (value in array) जैसे loops को vector-width processing में बदलने का मौका हो सकता है
  • अगर data सैकड़ों, हजारों या लाखों bytes का है, तो parallel width के हिसाब से 4x, 8x या उससे ज्यादा local speedup मिल सकता है
  • अगर data सिर्फ कुछ या दर्जनों items का है, तो SIMD लागू करना worthwhile नहीं है
  • simdutf और simdjson complex SIMD techniques इस्तेमाल करते हैं, लेकिन रोज़मर्रा के SIMD को इतना complex होना जरूरी नहीं है
  • उदाहरण Zig का इस्तेमाल करते हैं, लेकिन 5-step structure दूसरी languages पर भी लागू होता है, और हर language में SIMD instructions support करने का तरीका अलग होता है

दोहराया जाने वाला 5-step structure

  1. जरूरी constants को सभी lanes में broadcast करें, और जरूरत हो तो vector accumulator initialize करें
  2. input को एक बार में vector width size जितना traverse करें
  3. सभी lanes पर comparison या arithmetic operations parallel में चलाएं
  4. algorithm के हिसाब से vector results को reduce या store करें
  5. जो बाकी items complete vector में नहीं आते, उन्हें पुराने loop यानी scalar tail से handle करें
  • इस structure की आदत हो जाए तो सामान्य loops को इन्हीं 5 steps में तोड़ा जा सकता है, जिससे SIMD लिखना scalar loop जितना simple हो जाता है
  • अगर कोई logic इस structure में आसानी से express नहीं होता, तो फिलहाल SIMD लागू करना छोड़ देना बेहतर है

Ghostty का real search loop

  • Ghostty decoded codepoints की array में data तब तक consume करता है जब तक 0xF या उससे कम value न मिल जाए
    • terminal data का ज्यादातर हिस्सा print करने योग्य सामान्य characters होता है, इसलिए इन्हें batches में process किया जाता है
    • loop अगले printable region का end जितनी जल्दी हो सके ढूंढता है
  • original scalar implementation codepoints को एक-एक करके check करता है
while (end < cps.len and cps[end] > 0xF) end += 1;
  • vector implementation CPU-specific intrinsics के बिना general vectors का इस्तेमाल करता है, और scalar implementation से code सिर्फ 12 lines ज्यादा है
  • expected throughput improvement vector lanes की संख्या से match करता है
    • ARM NEON और Apple Silicon: अधिकतम 4x
    • ज्यादातर modern x86 CPUs में supported AVX2: अधिकतम 8x
    • कुछ Intel CPUs और AMD Zen 4 या उससे ऊपर में supported AVX-512: अधिकतम 16x
  • AVX2 Intel desktop पर terminal program input से final terminal state तक measure की गई overall throughput करीब 5x तेज हुई
    • SIMD के आसपास के कामों की वजह से पूरा theoretical speedup नहीं मिलता
  • C0 control characters 0xF के बाद भी मौजूद होते हैं, लेकिन 0xF इस Ghostty code path में इस्तेमाल होने वाला criterion है
    • ESC और दूसरी control sequences अलग path में handle होती हैं

Step 1: Constant broadcast

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • Ghostty का simd.lanes(u32) target CPU द्वारा एक साथ process किए जा सकने वाले u32 values की संख्या लौटाता है
    • हर value को lane कहा जाता है
    • ARM 4, AVX2 8, और AVX-512 16 लौटाता है
    • अगर usable vector size न हो तो null लौटाकर SIMD code skip करता है
  • @Vector(lanes, u32) उतने lanes वाला vector type बनाता है
    • अगर lanes 8 है, तो एक V में parallel process किए जा सकने वाले 8 u32 होते हैं
  • vector comparison में दोनों sides vector चाहिए, इसलिए @splat(0xF) 0xF को सभी lanes में replicate करता है
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • इस algorithm में vector accumulator की जरूरत नहीं है, लेकिन दूसरे algorithms इस step में accumulator initialize कर सकते हैं

Step 2: एक-एक vector traverse करना

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • अगर lanes 8 है, तो loop में तभी enter किया जाता है जब कम से कम 8 values बची हों, और 8 values values में load होती हैं
  • हर iteration के अंत में end को 1 नहीं, बल्कि lanes की संख्या से increment किया जाता है
  • complete vector load हो सकना चाहिए, इसलिए अगर सिर्फ 5 values बची हैं तो 8-lane vector नहीं पढ़ा जाता
  • vector में न आने वाली values step 5 का scalar tail handle करता है

Step 3: सभी lanes की parallel comparison

const greater_than_threshold = values > threshold;
  • values और threshold दोनों vectors हैं, इसलिए > corresponding lanes को एक vector operation के रूप में compare करता है
  • 8 lanes होने पर cps[end] > 0xF जैसी 8 comparisons parallel में होती हैं
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • कोई explicit inner loop नहीं है, और result lane-wise booleans वाला vector है
  • comparison के अलावा addition, multiplication, minimum, maximum जैसे vector type द्वारा supported operations पर भी वही structure लागू किया जा सकता है
  • comparison खुद एक vector operation है, लेकिन vector load, result reduction, और failed lane search के लिए extra instructions चाहिए

Step 4: Vector result reduction

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...) सभी booleans को and से combine करके single boolean बनाता है
  • अगर सभी lanes true हैं, तो अगले vector पर जाता है; अगर एक भी false है, तो failed exact position ढूंढता है
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast boolean vector को हर lane के लिए 1 bit वाले integer mask में convert करता है
    • 1 का मतलब value 0xF से बड़ी है
    • 0 का मतलब comparison fail हुआ
  • mask invert करने पर failed comparison 1 बन जाता है, और @ctz पहले 1 से पहले के 0 bits की संख्या गिनता है
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • इस example में @ctz(~mask) 3 लौटाता है, और end को पहले control character 0x0A वाली lane 3 पर ले जाता है
  • result reduction 5 steps में algorithm के हिसाब से सबसे ज्यादा बदलने वाला हिस्सा है
    • sum vector accumulator को single number में reduce कर सकता है
    • transform पूरा vector output buffer में store कर सकता है
    • यह search bit mask बनाकर किसी specific lane की position ढूंढता है

Step 5: Scalar tail handling

while (end < cps.len and cps[end] > 0xF) end += 1;
  • अगर input length vector width का exact multiple नहीं है, तो original scalar loop बाकी हिस्से को handle करता है
  • 8-lane vector loop के बाद 0 से 7 values बच सकती हैं
  • जिन CPUs पर simd.lanes(u32) null है, वहां SIMD section skip होता है और scalar loop पूरा input process करता है
  • original implementation remainder handling और compatibility fallback दोनों का काम करता है
  • general vectors CPU-specific syntax हटाते हैं, लेकिन CPU-specific code generation नहीं हटाते
    • Zig target पर active instruction set के हिसाब से vector operations को translate करता है

Auto-vectorization क्या miss करती है

  • Compiler simple code को auto-vectorize कर सकता है, जैसे complex control flow के बिना regular arithmetic loops
  • manual SIMD लिखने से पहले scalar version को optimization options के साथ compile करके generated code check करना चाहिए
  • production compilers अक्सर vectorization opportunities miss करते हैं, और auto-vectorization पर दशकों से research हुई है, लेकिन recent research भी इसी problem से शुरू होती है
  • अगर किसी loop के लिए 5x speedup मायने रखता है, तो vectorization explicitly लिखकर behavior predictable रखा जा सकता है
    • unrelated code changes या compiler updates की वजह से vector loop चुपचाप scalar loop में वापस बदल जाने की स्थिति से बचा जा सकता है

Developers को SIMD कितना सीखना चाहिए

  • जब बड़ी मात्रा में contiguous data को search, compare, count या transform करने वाला hot loop मिले, तो vector-width processing पर विचार करना आना चाहिए
  • everyday SIMD constants तैयार करना, vector load, parallel operation, result reduction, और scalar tail जैसे regular form को follow करता है
  • अगर language SIMD को अच्छे से support करती है, तो assembly या CPU-specific details सीधे जाने बिना भी performance improve की जा सकती है
  • हर developer के लिए जरूरी level complex simdutf/simdjson-style techniques नहीं, बल्कि SIMD लागू करने के अवसर पहचानना और common structure का उपयोग कर पाना है

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

1 टिप्पणियां

 
GN⁺ 2 시간 전
Hacker News की राय

  • लेख अच्छा है, लेकिन SIMD को समझना आसान है और उसे for loop जितना आसान लिखा जा सकता है कहकर शुरू करना, और फिर पहले ही उदाहरण में scalar code की एक लाइन को 12 लाइनों में बदल देना, काफ़ी कमज़ोर तर्क लगता है
    इसके बजाय ईमानदारी से कहना बेहतर होगा कि SIMD मुश्किल है, लेकिन नतीजे उसके लायक हैं। अगर यह शुरुआती लोगों के लिए है, तो चरण 1 से ही broadcast जैसे SIMD-विशेष शब्द बिना समझाए नहीं इस्तेमाल करने चाहिए, और scalar tail handling समझाने वाला चरण 5 अच्छी संरचना है

    • SIMD और पहला उदाहरण मुश्किल से ज़्यादा झंझट वाला काम लगता है
      हार्डवेयर एक बार में कितने items संभाल सकता है यह पता करना, उसी आकार में काम को बाँटना, फिर नतीजों को खोलना, बचे हुए items को अलग संभालना, और constants को भी duplicated vector में बनाना पड़ता है। इनमें से कुछ भी बहुत कठिन नहीं है, लेकिन काम बढ़ाकर इसे झंझटपूर्ण बना देता है
    • मैंने 1990 के आसपास Transputer उछाल के दौर में बनी Parallel-C सीखी थी, जो C में parallel programming features जोड़ने वाली भाषा थी
      उसका मेरा पसंदीदा feature par(; ; ) था, जिसमें कुछ boundary conditions के तहत compiler for loop को अपने-आप parallelize कर देता था
    • मैं लगभग ठीक वही target reader हूँ, इसलिए इसे दिलचस्पी से पढ़ा, लेकिन कठिनाई बहुत तेज़ी से बढ़ती है और यह बदनाम owl drawing meme जैसा लगा
    • SIMD खुद में सरल है; अटपटा हिस्सा scalar language में data-parallel operations का इस्तेमाल है
    • तकनीकी शिक्षा की सबसे बड़ी गलतियों में से एक यह है कि विषय का डर हटाने के नाम पर उसे सरल घोषित कर दिया जाए। सरल है यह मत कहो, सच में दिखाओ
      अगर विषय वास्तव में जटिल है, तो उसे छोटे और सरल हिस्सों में बाँटना चाहिए, फिर सीखने की तीखी चढ़ाई चढ़ने लायक क्रम बनाना चाहिए और यह भरोसा दिलाना चाहिए कि यह मेहनत क़ीमती है

  • इससे बेहतर सलाह यह है कि सभी को array programming जाननी चाहिए। SIMD optimization के लिए आम तौर पर वही सोच चाहिए होती है, और सिर्फ packed SIMD के लिए विशेष techniques उम्मीद से कम मिलती हैं
    array programming compiler के लिए auto-vectorization आसान बना देती है, इसलिए SIMD सीधे न लिखने पर भी ज़्यादातर अच्छा performance मिल जाता है

    • पहले सारी comparisons करना और बाद में पहली failure ढूँढना, ऐसी array programming छोटे execution span में बहुत मददगार नहीं होती। इसमें अपने-आप early exit नहीं मिलता, इसलिए अनावश्यक comparisons पर काफ़ी समय लग सकता है
    • मुझे closed-source languages पसंद नहीं हैं और MATLAB में भी कई कमियाँ हैं, लेकिन university में numerical simulation के लिए vectorized code कुशलता से लिखना बहुत स्वाभाविक लगा
      मेरा अनुभव ज़्यादा नहीं है, लेकिन Julia इसी तरह की vectorization क्षमता वाली, ज़्यादा आधुनिक और expressive language के सबसे क़रीब लगती है

  • पिछले कुछ दिनों में मैंने एक bioinformatics project की matrix operations को AVX-512 से optimize किया, और नतीजों से बहुत खुश हूँ
    ज़्यादातर applications में bottleneck memory से बड़े datasets पढ़ना होता है, इसलिए कई operations के लिए बार-बार पढ़ने के बजाय AVX registers और fused kernels के साथ सब कुछ एक बार में किया जा सकता है। 5x speedup आम बात है, और मैंने intrinsics सीधे इस्तेमाल किए, लेकिन wide crate से सामान्य operations बहुत आसान हो जाते हैं: https://docs.rs/wide/latest/wide/

  • भारी बहुमत वाले developers को SIMD सीखने की बिल्कुल ज़रूरत नहीं है। यह गलतफ़हमी क्यों पैदा की जाती है कि सभी developers को यह आना चाहिए, तभी वे सच में developer माने जाएँगे?

    • कम-से-कम SIMD के अस्तित्व और उसकी संभावनाओं के बारे में जानना ठीक है। एक developer ने कभी न कभी simple values को जोड़ने या compare करने वाले hot loops लिखे होंगे, और compiler target CPU architecture के हिसाब से उन्हें optimize कर सकता है—यह जानकारी कई स्थितियों में काम आती है

  • शीर्षक को बदलकर “सभी को यह जानना चाहिए कि SIMD कब लागू नहीं होता” करना बेहतर होगा
    आधुनिक compilers vectorization बहुत अच्छे से करते हैं, लेकिन एक assumption या data-dependent branch की वजह से अचानक scalar code पर लौट जाते हैं। SIMD लिखने के तरीके से ज़्यादा क़ीमती शायद यह सीखना हो कि compiler की optimization reports कैसे देखी जाएँ

    • खराब auto-vectorization का समाधान तो खुद SIMD code लिखना है, ऐसे में optimization reports देखना क्या सच में उससे ज़्यादा क़ीमती है, इस पर शक है
      अगर आप सिर्फ समस्या पहचान सकते हैं, तो अंत में बस “अफ़सोस” ही बचेगा
    • सचमुच अभी हाल में ऐसा ही हुआ था: https://xcancel.com/mitchellh/status/2079672171321081908#m

  • पिछले साल audio synthesizer बनाते समय मैंने x86 और ARM SIMD सीखना शुरू किया: https://github.com/seclorum/SIMDSynth
    multi-timbre और polyphonic synthesizer architecture में एक ही processing कई data flows पर लागू होती है, इसलिए SIMD के सिद्धांत सीखने के लिए यह बहुत उपयुक्त था। लेकिन debugging काफ़ी मुश्किल निकली, इसलिए हर processing pipe की स्थिति समझा सकने वाला simulator बहुत ज़रूरी लगा, और SIMD tools को ठीक से खंगालने के लिए शायद फिर से बड़ा निवेश करना पड़ेगा

  • लेख अच्छा है, और अच्छा होगा अगर और भाषाएँ SIMD को support करें, लेकिन जब सबसे लोकप्रिय दो भाषाएँ ही SIMD को native तौर पर support नहीं करतीं, तब “हर programmer को यह जानना चाहिए” कहना थोड़ा अजीब लगता है

    • यह मान लेना मुश्किल है कि सबसे लोकप्रिय languages ही इस तरह के लेख के target software engineers द्वारा सबसे ज़्यादा इस्तेमाल की जाने वाली भाषाएँ हैं

  • अगर आप खुद SIMD नहीं लिखते, या AI से लिखवाने वाले हैं, तब भी यह समझना ज़रूरी है कि किस तरह का काम किस hardware पर SIMD से तेज़ हो सकता है। तभी आप algorithm और code structure को इस तरह design कर पाएँगे कि SIMD लागू किया जा सके
    data dependency का असर, vector element width बढ़ाने की लागत और उससे बचने के तरीके, conditions और branches को masks में बदलना, और “division instruction होती ही नहीं” जैसी बातें, SIMD को थोड़ा भी हाथ से आज़माने पर कहीं ज़्यादा आसानी से समझ आती हैं

    • SIMD कब तेज़ होता है, इस पर काफ़ी कम बात होती है
      बड़े continuous data को एक बार में inspect या transform करना हो तो यह अच्छा काम करता है, लेकिन अगर input के हर कुछ bytes पर decision लेना पड़े, तो यह scalar तरीके जितना ही या उससे धीमा भी हो सकता है। SIMD कोई जादुई speedup button नहीं है

  • The Witness dev team ने असली performance problem को SIMD से कैसे हल किया, यह Casey Muratori का एक उपयोगी वीडियो है: https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • शानदार प्रस्तुति है, लेकिन दूसरों को recommend करने के लिए वीडियो बहुत लंबा है; अच्छा होता अगर इसका कोई लेख संस्करण होता जो सीधे मुख्य बात पर आता
      performance के लिए vertical integration का यह अच्छा उदाहरण है: यह दिखाता है कि सामान्य abstractions क्यों मौजूद हैं और उन्हें generic क्यों होना चाहिए, और फिर किसी specific use case में problem definition से लेकर SIMD तक vertical integration करके बड़ा लाभ कैसे लिया जा सकता है

  • SIMD जैसी सूक्ष्म optimization में जाने से पहले data structures और access patterns की गंभीरता से समीक्षा करनी चाहिए
    पहले मैंने पुराने Zig कोड पर SIMD लागू किया था, लेकिन data structure model optimization के बिल्कुल उलट था, यानी टूटी हुई इंजन वाली कबाड़ गाड़ी पर high-performance racing tires लगाने जैसा। यह performance को मापे बिना और memory allocation कहाँ हो रही है यह सोचे बिना की गई एक क्लासिक जल्दबाज़ optimization थी
    अब मैं data को SQL table की तरह देखता हूँ और संभावित primary keys तथा access patterns के आधार पर structure डिज़ाइन करता हूँ। पहले मैं ऐसे tree इस्तेमाल करता था जो heap में मौजूद दूसरे structs की ओर इशारा करते थे, और इस वजह से linked list जैसी कमियाँ, कई heap vectors की fragmentation, और धीमी creation·deallocation cost सब साथ में झेलनी पड़ती थीं, यहाँ तक कि सिर्फ Drop में ही runtime का बड़ा हिस्सा खर्च हो जाता था
    tree को कभी भी linearize किया जा सकता है, इसलिए मैं access·insertion patterns, क्या वह वास्तव में tree है या कोई दूसरा graph, और उसे Vec या कई Vec के struct के रूप में store करना चाहिए या नहीं, यह सब देखता हूँ। नतीजे में कोड ज़्यादा तेज़ और सरल हो गया, data homogeneous arrays में इकट्ठा होने लगा जिससे compiler की SIMD optimizations और L1 cache का फायदा उठाना आसान हुआ, और ज़रूरत पड़ने पर सीधे branchless SIMD code भी लिखा जा सकता है
    संबंधित सामग्री: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • hot loop को SIMD से तेज़ बनाना हो तो data layout और cache-friendly structure सबसे अहम हैं
      असली bottleneck सेक्शनों में memory allocation, virtual function table lookup, और ज़रूरत से ज़्यादा indirect references से बचना चाहिए। अगर C++ का vector अनपेक्षित allocation trigger कर सकता है, तो वह भी हमेशा सबसे अच्छा विकल्प नहीं है
    • performance engineer के रूप में मैं हमेशा इसी समस्या से जूझता हूँ। performance की शुरुआत architecture से होती है, और जहाँ hot path में data layout खराब हो, वहाँ निकाली जा सकने वाली performance की सीमा होती है
      इसके उलट, data-oriented code लगभग हमेशा threading और SIMD को आसानी से support करता है
    • उससे भी बुनियादी बात है कि memory access patterns महत्वपूर्ण हैं
      दिलचस्प बात यह है कि CPU code भी आखिरकार GPU-style में लिखा जाने लगता है, और objects की array की जगह Parquet-शैली की array of structs का उपयोग एक तरीका हो सकता है
    • table एक सामान्य-purpose graph को कुशलतापूर्वक implement करने का तरीका है, और जब तक graph को विशेषीकृत नहीं किया जा सकता, यह मेरे हिसाब से सबसे अच्छा representation है