AVX-512 का उपयोग करने वाला `tolower()` फ़ंक्शन

 (dotat.at)
1 पॉइंट द्वारा GN⁺ 2024-07-30 | 1 टिप्पणियां | WhatsApp पर शेयर करें

  • कुछ साल पहले, मैंने SWAR ट्रिक का उपयोग करके tolower() को तेज़ करने के तरीकों पर लिखा था। कुछ दिन पहले, Olivier Giniaux के लेख में SIMD निर्देशों का उपयोग करके छोटे strings को प्रोसेस करने के optimization तरीके देखकर मेरी रुचि जगी। यह तरीका Rust में लिखे गए तेज़ hash function में इस्तेमाल होता है.

  • SIMD निर्देश छोटे strings को आसानी से संभाल सकते हैं, लेकिन memory और vector register के बीच transfer हमेशा असुविधाजनक रहा है। Olivier के लेख ने इस समस्या का एक दिलचस्प समाधान दिखाया.

उम्मीद के संकेत

  • कुछ SIMD instruction sets string processing के लिए उपयोगी masked load और store सुविधाएँ देते हैं। ये byte स्तर पर काम करती हैं.

    • ARM SVE: हाल के बड़े ARM Neoverse cores में उपलब्ध, जैसे Amazon Graviton। लेकिन Apple Silicon पर उपलब्ध नहीं.
    • AVX-512-BW: हाल के AMD Zen processors में उपलब्ध। AVX-512 एक जटिल extension set है, और Intel में इसका support बेतरतीब है.

  • मेरे पास एक AMD Zen 4 box है, इसलिए मैंने AVX-512-BW को आज़माने का फैसला किया.

tolower64()

  • Intel intrinsics guide का उपयोग करके मैंने एक बेसिक tolower() फ़ंक्शन लिखा जो एक बार में 64 bytes प्रोसेस कर सकता है.
    • byte स्तर के AVX-512 functions खोजने के लिए * को wildcard की तरह इस्तेमाल कर mm512*epi8 खोजा.
    • कुछ registers को 64 उपयोगी bytes से भरा.
    • uppercase को lowercase में बदलने के लिए आवश्यक संख्याएँ सेट कीं.
    • input characters को A और Z से compare करके जाँचा कि वे uppercase हैं या नहीं.
    • mask का उपयोग करके uppercase होने पर उन्हें lowercase में बदला.

bulk load और store

  • tolower64() kernel को एक अधिक सुविधाजनक फ़ंक्शन में wrap करना पड़ता है। उदाहरण के लिए, ऐसा फ़ंक्शन जो string को copy करते हुए उसे lowercase में बदले.
    • लंबे strings के लिए unaligned vector load और store instructions का उपयोग किया जाता है.

masked load और store

  • छोटे strings और लंबे strings के अंत वाले हिस्से के लिए masked unaligned load और store का उपयोग किया जाता है.
    • mask में पहले len bits सेट होते हैं.
    • load और store, mask जुड़े full-width versions के समान होते हैं.

benchmarking

  • कई समान फ़ंक्शनों का performance benchmark किया गया.

    • Clang 16 से compile किया गया और AMD Ryzen 9 7950X पर चलाया गया.
    • inline और code motion के हस्तक्षेप से बचने के लिए हर फ़ंक्शन को अलग से compile किया गया.

  • नतीजे:

    • tolower64 परीक्षण किए गए सभी फ़ंक्शनों में सबसे तेज़ है.
    • copybytes64 भी tolower64 की तरह AVX-512 का उपयोग करता है, लेकिन बहुत अधिक तेज़ नहीं है.
    • copybytes1 byte स्तर पर memcpy करता है, जो दिखाता है कि Clang 11 की auto-vectorization अपेक्षाकृत अच्छी नहीं है.
    • मानक tolower() सबसे धीमा है.
    • tolower1 Clang 16 से compile किया गया byte-स्तरीय tolower() है, और auto-vectorization बेहतर हुई है, लेकिन यह अभी भी धीमा है.
    • tolower8 पिछले ब्लॉग पोस्ट में प्रस्तुत SWAR tolower() है, जिसमें Clang auto-vectorization की कोशिश करता है, लेकिन परिणाम अच्छे नहीं हैं.
    • memcpy शुरुआत में तेज़ है, लेकिन copybytes64 की आधी गति तक गिर जाता है.

निष्कर्ष

  • AVX-512-BW खासकर छोटे strings को प्रोसेस करते समय बहुत उपयोगी है.

  • Zen 4 पर यह बहुत तेज़ है, और built-in functions का उपयोग करना आसान है.

  • AVX-512-BW का performance बहुत smooth है.

  • मेरे पास ARM SVE support वाला box नहीं है, इसलिए मैं इसे विस्तार से जाँच नहीं सका, लेकिन यह जानने की जिज्ञासा है कि SVE छोटे strings पर कितना अच्छा काम करता है.

  • उम्मीद है कि ऐसे instruction set extensions और व्यापक रूप से इस्तेमाल होंगे। ये string processing performance को काफी बेहतर बना सकते हैं.

  • इस ब्लॉग पोस्ट का code मेरी वेबसाइट पर देखा जा सकता है.

GN⁺ का सार

  • यह लेख SIMD निर्देशों का उपयोग करके छोटे strings को कुशलता से प्रोसेस करने का तरीका समझाता है.
  • यह दिखाता है कि AVX-512-BW और ARM SVE instruction sets string processing के लिए उपयोगी हैं.
  • benchmarking के नतीजे बताते हैं कि AVX-512-BW खासकर छोटे strings में बेहतरीन performance देता है.
  • performance optimization में रुचि रखने वाले developers के लिए यह लेख उपयोगी होगा.

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

1 टिप्पणियां

 
GN⁺ 2024-07-30
Hacker News राय

  • Rust और LLVM memory model में "unsafe read beyond of death" ट्रिक को undefined behavior माना जाता है

    • compiler optimization के लिए यह मान सकता है कि ऐसा behavior होता ही नहीं है
    • इससे बचने के लिए inline assembly का इस्तेमाल करना चाहिए

  • AMD के AVX512 implementation और Intel के AVX10 competition को लेकर जिज्ञासा है

    • AVX10, Intel के P vs E core problem को हल करने के लिए है
    • AMD, स्थिति के अनुसार Zen5 की full width या Zen4, Zen5 mobile की 256-bit double pump का उपयोग करता है
    • बड़ा performance improvement Zen4 cores में होता है

  • SWAR optimization सिर्फ 8-byte address पर aligned string के लिए उपयोगी है

    • unaligned string पर लागू करने से यह मूल algorithm से भी धीमा हो जाता है
    • algorithm को तीन हिस्सों में बाँटने पर ज्यादा instructions की जरूरत पड़ती है

  • mask addition साफ-सुथरा लगता है

    • अच्छा होता अगर .NET built-ins में AVX512 के mask registers को सीधे manipulate करने का कोई तरीका होता

  • Clang का उपयोग करने पर बेहतर परिणाम मिल सकते हैं

    • यह बेहतर instruction selection और अच्छी तरह optimized result देता है

  • छोटी लंबाई की strings के लिए core loop में एक instruction कम है

    • छोटी strings को तेज़ी से process करना महत्वपूर्ण है

  • ASCII को UTF-8 में uppercase/lowercase बदलने का एक समान implementation C# में लिखा गया है

    • ज़्यादातर codebase में छोटी strings का दबदबा होता है, इसलिए उन्हें तेज़ी से process करना महत्वपूर्ण है

  • AVX512 का उपयोग करके text को uwu में बदलने का SIMD usage example भी है

  • Unicode character conversion को ध्यान में रखें तो यह और भी प्रभावशाली होगा

    • ज़्यादातर programmer सिर्फ ASCII की परवाह करते हैं, लेकिन standard character set के बाहर भी एक बहुत बड़ी दुनिया है

  • पहले image के चारों ओर काली border जोड़कर buffer SIMD problems से बचने का अनुभव रहा है

    • input को हमेशा पूरी तरह control नहीं किया जा सकता