SIMD के लिए उपयुक्त substring search algorithm (2018)

 (0x80.pl)
1 पॉइंट द्वारा GN⁺ 2025-06-15 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • यह SIMD-अनुकूल substring search algorithm पर आधारित विषय है
  • इसमें तेज़ string search के लिए तकनीकी approach प्रस्तुत की गई है
  • parallel processing का उपयोग करके मौजूदा तरीकों की तुलना में efficiency बेहतर करने की दिशा दिखाई गई है
  • डेवलपर्स और IT professionals के लिए उपयोगी performance tip के रूप में इस पर ध्यान दिया जाता है
  • यह algorithm modern hardware optimization से जुड़ा हुआ है

परिचय

  • यह दस्तावेज़ SIMD (Single Instruction, Multiple Data) instruction set के लिए optimized substring search algorithm का परिचय देता है
  • आज के IT environment में, जहाँ string processing speed महत्वपूर्ण हो गई है, यह पारंपरिक sequential search की सीमाओं को पूरा करने के लिए parallel processing approach पर चर्चा करता है
  • SIMD का उपयोग करने पर एक साथ कई data points की तुलना की जा सकती है, इसलिए बड़े पैमाने पर string search में महत्वपूर्ण performance improvement की उम्मीद की जा सकती है

मुख्य बिंदु

  • SIMD algorithm input string को कई हिस्सों में बाँटकर एक ही instruction से कई bytes की एक साथ तुलना करता है
  • इस तरीके से, पारंपरिक loop-आधारित comparison की तुलना में ज़्यादा तेज़ और efficient search संभव होती है
  • इसका प्रभावी उपयोग text search, log analysis, DNA sequencing जैसे high-speed large-scale data processing वाले क्षेत्रों में किया जाता है

डेवलपर्स और इंजीनियरों के लिए फायदे

  • SIMD-अनुकूल algorithm लागू करने पर, बहुत कम code changes के साथ modern CPU की क्षमता को अधिकतम करने की संभावना मिलती है
  • यह मौजूदा search logic की तुलना में speed और efficiency के लिहाज़ से लाभ देता है
  • multi-core environment में इसकी performance scalability भी उत्कृष्ट है

निष्कर्ष

  • जिन IT services, data analysis, और real-time search engine क्षेत्रों में substring search performance महत्वपूर्ण है, वहाँ SIMD-आधारित algorithm अपनाने से व्यावहारिक performance improvement मिल सकता है
  • यह आधुनिक hardware environment का लाभ उठाने के लिए आवश्यक optimization strategy है

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

1 टिप्पणियां

 
GN⁺ 2025-06-15
Hacker News राय

  • यह बताया गया कि ripgrep का acceleration तरीका Rust के regex crate का इस्तेमाल करने वाला AVX2 (generic) approach है। उदाहरण के लिए, \w+\s+Sherlock\s+\w+ जैसे regular expression में भी सिर्फ Sherlock को अलग निकालकर तेज़ी से खोजा जा सकता है, इस पर ज़ोर दिया गया। वास्तविक implementation यहाँ देखा जा सकता है। इस लेख के algorithm से मुख्य अंतर यह बताया गया कि needle के पहले/आखिरी byte की बजाय, background distribution का उपयोग करके कम बार आने वाले 2-byte पर search optimize करने वाली heuristic इस्तेमाल की जाती है। benchmark नतीजों के अनुसार यह साधारण Two-Way तरीके या GNU libc के memmem से काफ़ी तेज़ है। prebuilt benchmark में यह API सीमा भी रेखांकित की गई कि memmem जैसी routines को needle हर बार fixed होने पर state बार-बार rebuild करनी पड़ती है, इसलिए उनकी efficiency घटती है

    • यह सवाल उठाया गया कि bytes का background distribution पता कैसे चलता है; अगर haystack में उस distribution को अलग से scan करना पड़े, तो क्या उससे performance उलटे ख़राब नहीं होगी

  • Wasm/WASI libc के SIMD optimization की कोशिश करते समय इस तरह का string search algorithm लागू करने का अनुभव साझा किया गया। यह राय भी दी गई कि जब haystack की लंबाई तय हो और needle काफ़ी बड़ा हो, तब Quick Search के साथ इसका संयोजन उपयोगी होता है। साथ में संबंधित code और algorithm explanation link भी दी गई

  • यह भी साझा किया गया कि C# में IndexOf पर भी SIMD लागू होता है, और अधिक विवरण यहाँ देखा जा सकता है

  • एक व्यक्ति ने बताया कि उन्होंने भी SIMD तरीका इस्तेमाल करके string search और split के लिए कई algorithms खुद implement किए हैं। tamgu का conversion.cxx source साझा किया गया। यह भी स्पष्ट किया गया कि उन्होंने मुख्य लेख में बताए गए तरीके से अलग algorithm इस्तेमाल किया था

    • उनके algorithm का संक्षिप्त सार देने का अनुरोध किया गया। उदाहरण के तौर पर यह स्पष्टीकरण जोड़ा गया कि मूल लेख का पहला algorithm पहले/आखिरी character को देखता है, जबकि दूसरा algorithm शुरुआती 4 characters को एक साथ compare करके कई candidate positions जाँचता है

    • यह भी साझा किया गया कि कुछ साल पहले Zig के generic SIMD का उपयोग करके LZ77 window search के लिए modified version implement करने की कोशिश की थी। संबंधित चर्चा यहाँ देखी जा सकती है

  • तेज़ HTTP parsing के लिए SIMD algorithms इस्तेमाल करने वाले hparse project की याद आने की बात कही गई

  • यह उल्लेख किया गया कि swar algorithm, 1-byte aligned data को 8-byte unit में cast करता है, जिससे UB (undefined behavior) होता है। unaligned load की वजह से performance issue भी हो सकता है, ऐसा संकेत दिया गया

    • इस पर राय दी गई कि ऐसे code को अक्सर आदर्श algorithm या readability के लिए pseudocode की तरह स्वीकार किया गया है। memcpy का उपयोग नहीं किया गया, और boundary checks भी सटीक नहीं हैं। जैसे haystack की लंबाई 8 के multiple होने की धारणा, या needle खाली होने पर unsigned integer overflow के कारण out-of-bounds होना—ऐसे कुल 3 UB मौजूद हैं। यह अनुभव भी साझा किया गया कि वास्तविक SIMD demo code में अक्सर vector उपयोग का दिलचस्प तरीका दिखाया जाता है, लेकिन boundary conditions छोड़ दी जाती हैं

  • libc का strstr धीमा होना पहले से ज्ञात बात है, लेकिन musl तेज़ है और modern algorithm इस्तेमाल करता है, इस पर ज़ोर दिया गया। अब सिर्फ नाम तय हो जाए तो इसे smart shootout में जोड़ा जा सकता है। साथ ही यह जिज्ञासा भी जताई गई कि सबसे अच्छे SIMD algorithms की तुलना में इसका प्रदर्शन कैसा रहेगा

    • संदर्भ benchmark के रूप में musl के Two-Way और साझा किए गए SIMD-optimized libc algorithm के comparison results बताए गए। benchmark method संबंधित code पर आधारित है। SIMD उपयोग से हुए improvements इस table में देखे जा सकते हैं। ईमानदारी से आकलन किया गया कि यह असाधारण नहीं, बल्कि काफ़ी ठीक-ठाक स्तर का सुधार है। यह भी कहा गया कि musl fixed-length strings (memmem) में विशेष रूप से अच्छा है, जबकि Wasm environment में unknown-length strings (strstr) के लिए कई optimizations आज़माने की ज़्यादा आज़ादी थी। NUL-terminated strings की वजह से कई अच्छे algorithms को दिक्कत होती है

    • यह निजी इच्छा भी साझा की गई कि smart में और SIMD algorithms शामिल होने चाहिए, और समय मिलने पर इसे खुद आज़माना चाहेंगे

  • यह प्रश्न पूछा गया कि string search के SIMD comparison में 2018 version छूट तो नहीं गया

  • यह सवाल भी उठा कि string size के आधार पर SIMD approach वास्तव में किस सीमा से प्रभावी होती है। सामान्य तौर पर छोटे strings में SIMD setup overhead (alignment, length calculation आदि) की वजह से यह साधारण byte-based search से भी धीमा हो सकता है। साथ ही यह भी रेखांकित किया गया कि hardware architecture के अनुसार यह काफ़ी बदल सकता है

    • इसके जवाब में कहा गया कि अपने अनुभव में मामला उलटा है। ऐसे algorithms में लगभग कोई बेकार setup नहीं होता और वे brute force के काफ़ी क़रीब होते हैं, इसलिए लंबे और repetitive needle पर उनकी time complexity खराब हो जाती है। इसके विपरीत, quadratic समस्या से बचाने वाले या sublinear execution देने वाले उन्नत string search algorithms को needle की संरचना में गहराई से देखने वाला महँगा setup चाहिए होता है

  • यह इच्छा जताई गई कि Python में दूसरी language को call किए बिना सीधे SIMD इस्तेमाल करना अच्छा होता

    • Austin के ब्लॉग और vowel detection पर उनके संकलन (link) का उल्लेख करते हुए यह पूछा गया कि “किसी दूसरी language को call किए बिना सीधे SIMD इस्तेमाल करना” से उनका मतलब क्या है। हल्के मज़ाक में कहा गया कि assembly भी आख़िर एक “दूसरी language” ही है। Python और SIMD ecosystem में PeachPy (Python से x86 assembly लिखना), Mojo (नई Python-style language), और CPython bindings वाली पतली SIMD libraries जैसे काफ़ी विविध विकल्प मौजूद हैं। यह पूछा गया कि वे किस तरह का तरीका चाहते हैं, और यदि target ASCII है तो StringZilla का find_first_of (code) function भी सुझाया गया

    • यह भी सवाल किया गया कि आख़िर Python में सीधे ऐसा करने की ज़रूरत क्यों है। अगर चिंता performance limit की है, तो सिर्फ language बदलने से ही 20~50 गुना या उससे अधिक speedup मिल सकता है, ऐसी सलाह दी गई