SIMD के लिए उपयुक्त substring खोज एल्गोरिद्म (2018)

• strstr, std::string::find जैसे API को एक-बार वाले substring search के लिए डिज़ाइन किया गया मान लिया जाता है, लेकिन आधुनिक CPU पर छोटे string और vector compare की लागत कम होने से SIMD तरीका फायदेमंद हो सकता है
• मुख्य विचार यह है कि Karp-Rabin की weak hash condition को vector predicate में बदला जाए, और केवल candidate positions पर ही सटीक substring comparison किया जाए
• generic SIMD एल्गोरिद्म needle के पहले अक्षर और आख़िरी अक्षर की parallel तुलना करके candidates घटाता है, और सिर्फ़ match की संभावना वाली positions को memcmp से verify करता है
• SSE4.1 MPSADBW और SSE4.2 PCMPESTRM तरीकों की भी तुलना की गई, लेकिन मापे गए परिणामों में generic SIMD ज़्यादा स्थिर रूप से तेज़ रहा और PCMPESTRM, MPSADBW से भी धीमा निकला
• generic SIMD हर प्लेटफ़ॉर्म पर C strstr से तेज़ था, लेकिन यह input string के बाहर तक पढ़ सकता है, इसलिए सुरक्षित नहीं है, और यह पहले से length information भी लेता है, इसलिए तुलना की शर्तें भी पूरी तरह समान नहीं हैं

---

string search में बदली हुई cost assumptions

• C का strstr, C++ std::string::find, Python string के pos, index जैसे API दिए गए string में substring खोजने की एक-बार वाली search के लिए बने हैं
• पारंपरिक एल्गोरिद्म मोटे तौर पर दो वर्गों में बँटते हैं
  • Knuth-Morris-Pratt, Boyer Moore जैसे deterministic finite automata आधारित तरीके
  • Karp-Rabin जैसे सरल comparison-आधारित तरीके
• standard एल्गोरिद्म यह मानते हैं कि एक character pair की तुलना, auxiliary table lookup, और conditional branch सस्ते हैं, जबकि दो substrings की तुलना महँगी है
• आधुनिक desktop CPU पर यह मान्यता सही न भी हो सकती है
  • 64-bit CPU पर 1, 2, 4, 8-byte compare की लागत में खास अंतर नहीं होता
  • SIMD instructions होने पर 16, 32, 64-byte vector compare भी single-byte compare जितना सस्ता हो सकता है
  • table lookup में L1 cache round-trip स्तर की memory access लागत लग सकती है, और character-level reads की लागत भी मिलती-जुलती होती है
  • गलत branch prediction लगभग 10~20 cycles की penalty दे सकती है
  • character read, compare, और conditional branch से बनी छोटी dependency chain CPU के out-of-order execution का लाभ उठाना कठिन बनाती है

तरीका: weak hash की जगह vector predicate

• Karp-Rabin केवल तब exact comparison करता है जब target substring की weak hash और current string segment की hash समान हो
• SIMD तरीका इस hash condition को vector predicate से बदल देता है
  • predicate को parallel में compute किया जाता है
  • predicate vector में जिन positions पर true आता है, केवल उन्हीं पर exact substring comparison किया जाता है
• length-based specialization भी performance सुधारने में काम आती है
  • सामान्य implementation substring comparison के लिए memcmp जैसी function call करती है
  • अगर खोजी जाने वाली substring की length पता हो, तो उस length के लिए function call को कुछ CPU instructions, और कभी-कभी सिर्फ़ एक instruction से बदला जा सकता है
  • इससे function call overhead और memcmp के अंदर की लागत घटती है

एल्गोरिद्म 1: generic SIMD

• generic SIMD एल्गोरिद्म पूरे SIMD instruction set परिवार और SWAR तरीके पर लागू किया जा सकता है
• मूल predicate यह जाँचता है कि needle का पहला अक्षर और आख़िरी अक्षर दोनों match करते हैं या नहीं
  • पहले अक्षर को register F में भरा जाता है
  • आख़िरी अक्षर को register L में भरा जाता है
  • हर iteration में haystack के current offset i से chunk A पढ़ा जाता है और i + k - 1 से chunk B पढ़ा जाता है
  • F == A और B == L की गणना करके दोनों परिणामों को मिलाकर candidate position mask बनाया जाता है
  • mask जिन positions पर true हो, वहीं exact substring comparison किया जाता है
• "cat" को "a_cat_tries" में खोजने वाले उदाहरण में पहला अक्षर c और आख़िरी अक्षर t दोनों सिर्फ़ index 2 पर match करते हैं, इसलिए exact comparison भी केवल एक बार होता है
• पहला और आख़िरी अक्षर चुनना हमेशा अच्छा नहीं होता
  • अगर input string ज़्यादातर 'A' है और needle "AjohndoeA" है, तो बहुत सारे candidates बन सकते हैं
  • implementation आख़िरी अक्षर की जगह पहले अक्षर से अलग सबसे दूर वाले अक्षर को चुन सकती है
  • अगर needle के सभी अक्षर समान हों, तो "AAAAA" जैसे pattern के लिए विशेष प्रक्रिया इस्तेमाल की जा सकती है

implementations के बीच अंतर

• SSE और AVX2 implementations की संरचना लगभग एक जैसी है और वे न्यूनतम instruction count का उपयोग करती हैं
  • क्योंकि पहले से पता है कि पहला और आख़िरी अक्षर match कर चुके हैं, memcmp में इन अक्षरों की दोबारा तुलना करने की ज़रूरत नहीं रहती
• SWAR तरीका इस तथ्य का उपयोग करता है कि XOR का परिणाम 0 हो तो bytes समान हैं
  • SSE/AVX2 की तरह partial results को AND करने के बजाय OR का उपयोग किया जाता है
  • 0-byte positions खोजने की प्रक्रिया में अधिक काम पड़ता है
  • 64-bit vector के लिए C++ implementation सटीक byte mask निकालती है
• AVX512F में byte operations नहीं हैं और सबसे छोटा vector element 32-bit word है, इसलिए SWAR technique की ज़रूरत पड़ती है
  • दो XOR और एक OR को AVX512F instructions से compute किया जाता है
  • उन 32-bit elements को खोजा जाता है जिनमें 0 byte शामिल हो
  • ऐसे हर 32-bit element के लिए 4 candidate substrings जाँची जाती हैं
• ARM Neon 32-bit implementation 128-bit SIMD registers का उपयोग करती है
  • Neon unit से CPU पर वापस आने वाला लंबा round-trip bottleneck बनता है
  • comparison result को 64-bit word के रूप में memory में store करके process किया जाता है
  • inner loop को 2 बार unroll करने पर लगभग 1.2x speedup मिलता है
• AArch64 implementation लगभग ARM Neon प्रक्रिया जैसी ही है, लेकिन SIMD register lane को सीधे पढ़ना तेज़ है

एल्गोरिद्म 2: SSE4.1 MPSADBW

• SSE4.1 और AVX2 का MPSADBW एक register के 4-byte subvector और दूसरे register के लगातार 8 4-byte subvectors के बीच Manhattan distance निकालता है
• अगर दो subvectors समान हों तो L1 distance 0 होती है, इसलिए इसे candidate position खोजने में इस्तेमाल किया जा सकता है
  • यह तरीका पहले 4 अक्षरों की समानता को predicate के रूप में उपयोग करता है
• पहले 4 अक्षरों की तुलना होने से यह पहले/आख़िरी अक्षर तुलना से अधिक शक्तिशाली लगता है, लेकिन worst case में quadratic complexity से नहीं बचता
  • अगर haystack "a" से भरा हो और needle "aaaabcde" हो, तो predicate हर input character पर true हो जाएगा
• MPSADBW तरीके की कुछ सीमाएँ हैं
  • 4 से छोटी length वाली substrings के लिए यह मूल रूप से उपयुक्त नहीं है
  • length 3 को संभाला जा सकता है, लेकिन अतिरिक्त code चाहिए
  • SSE MPSADBW एक बार में केवल 8 bytes process करता है
  • AVX2 MPSADBW पूरे 256-bit vector पर नहीं, बल्कि 128-bit lane इकाइयों में काम करता है, इसलिए अतिरिक्त loading code चाहिए
  • instruction latency CPU के अनुसार 5~7 cycles तक ऊँची है, लेकिन throughput 1~2 cycles है, इसलिए loop unrolling से latency छिपाई जा सकती है
• AVX512F में MPSADBW नहीं है, लेकिन 32-bit elements native रूप से समर्थित हैं, इसलिए 4-byte prefix equality predicate की नकल की जा सकती है
  • हर iteration में संभव 4-byte prefixes रखने वाले 4 AVX512 vectors बनाए जाते हैं
  • हर vector construction में 2 shift और 1 OR चाहिए
  • comparison loop जटिल हो जाता है, और आख़िरी element भरने के लिए vector के बाहर के 4 bytes भी चाहिए होते हैं

एल्गोरिद्म 3: SSE4.2 PCMPESTRM

• SSE4.2 ने string operations के building block के रूप में STNI instruction set पेश किया
• Intel ने बाद के processors में STNI को लगभग छोड़ दिया, AVX2 version भी नहीं लाया, और ये instructions बहुत धीमे हैं
  • 11 cycles की latency को स्वीकार करना कठिन माना गया
• PCMPxSTRx instructions के चार variants हैं, जो string length तय करने के तरीके और result store करने के तरीके पर निर्भर करते हैं
  • length को explicit दिया जा सकता है, या पारंपरिक C string की तरह पहले 0 byte को अंत माना जा सकता है
  • result को bit/byte mask या mask के first/last set bit number के रूप में store किया जा सकता है
• यहाँ range ordered comparison mode का उपयोग किया गया है
  • नाम के विपरीत, substring या register width से आगे जाने पर यह उसके prefix को ढूँढता है
  • उदाहरण में "ABCD" को "ABCD_ABC_ABCD_AB" में खोजने पर suffix "AB" को भी match माना जा सकता है
  • इसलिए सुरक्षित रूप से केवल पहले अक्षर का match मान सकते हैं, बाकी को memcmp से verify करना पड़ता है

performance measurement environment

• कई SIMD implementations की performance मापी गई, और छोटी substrings के लिए runtime specialization भी शामिल की गई
• C strstr को comparison target में रखा गया, लेकिन GNU libc के std::string::find performance bug की वजह से x64 तालिका में इसे शामिल नहीं किया गया
• हर program को तीन बार चलाकर test किया गया
• x64 test environment
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• ARM test environment
  • ARMv7 Raspberry Pi 3, 32-bit code, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, 64-bit code, Clang 3.8.0

x64 results

• generic SIMD implementation ने x64 पर strstr की तुलना में सबसे बड़ा speedup दिखाया
  • Westmere पर SSE2 generic 0.74589 सेकंड, strstr 0.82246 सेकंड
  • Haswell पर AVX2 generic 0.38653 सेकंड, strstr 0.52786 सेकंड
  • Skylake पर AVX2 generic 0.36309 सेकंड, strstr 0.66148 सेकंड
  • KNL पर AVX512F generic 1.14057 सेकंड, strstr 4.94606 सेकंड
• अधिकतम speedup Westmere पर 1.10x, Haswell पर 1.37x, Skylake पर 1.82x, और KNL पर 4.33x था
• Bulldozer का strstr performance 9.37792 सेकंड था, जो इतना खराब था कि उसे baseline बनाना कठिन था
• MPSADBW तरीका Skylake को छोड़कर कुल मिलाकर अच्छा नहीं रहा, और KNL पर विशेष रूप से खराब था
• PCMPESTRM तरीका MPSADBW से भी धीमा निकला

ARM results

• ARMv7 पर std::strstr 7.30405 सेकंड और std::string::find 4.17131 सेकंड था
• ARMv7 पर ARM Neon 32-bit generic 1.29861 सेकंड था, जो std::string::find से अधिकतम 3.1x तेज़ था
• ARMv8 पर std::strstr 3.37546 सेकंड और std::string::find 1.81368 सेकंड था
• ARMv8 पर AArch64 64-bit generic 0.27897 सेकंड था, जो std::string::find से अधिकतम 6.5x तेज़ था
• ARMv8 पर SWAR 64-bit generic 0.46269 सेकंड था, जो 32-bit SIMD प्रक्रिया के क़रीब performance दिखाता है

निष्कर्ष और सीमाएँ

• generic SIMD एल्गोरिद्म हर प्लेटफ़ॉर्म पर C strstr से तेज़ था
• implementation में किसी दिए गए CPU पर उपलब्ध सबसे ऊँचा SIMD version चुनना बेहतर है
• MPSADBW का performance Skylake को छोड़कर अच्छा नहीं था, और Knights Landing पर बहुत खराब था
• PCMPESTRM, MPSADBW से भी धीमा है
• ARM Neon का performance, SWAR implementation सहित, अच्छा रहा
  • SWAR version string::find से 1.7x तेज़ है
  • SIMD version string::find से 3.1x तेज़ है
• strstr के साथ तुलना पूरी तरह निष्पक्ष नहीं हो सकती
  • strstr ऐसी strings संभालता है जिनकी length ज्ञात नहीं होती
  • ये implementations length को argument के रूप में लेती हैं और उसका उपयोग करती हैं
• implementation सुरक्षित नहीं है
  • यह input string के बाहर का data पढ़ सकती है
  • अगर string किसी unmapped memory के ठीक पहले हो, तो access violation हो सकता है
  • address sanitizer भी समस्या report कर सकता है
  • इसे सुरक्षित बनाना संभव है, लेकिन यह इस काम का लक्ष्य नहीं था
• सभी implementations और test programs GitHub पर उपलब्ध हैं