👌🏾 👩‍👧 🚎 Wc के बारे में एक अन्य लेख 📻 🅰️ 👨🏾‍🚒

सबके लिए दिन अच्छा हो।

हाल ही में हेब्रा विनिंग विथ हास्केल की बीस पंक्तियों पर एक लेख छपा : हम @ 0xd34df00d से अपना wc लिखते हैं । लेखक, कार्यात्मक प्रोग्रामिंग के लिए उनकी सहानुभूति के लिए जाना जाता है, हास्केल पर wc उपयोगिता का एक एनालॉग लागू किया और इसे अनुकूलन के अधीन किया, जिसके परिणामस्वरूप एक विकल्प है जो मानक यूनिक्स उपयोगिता की तुलना में 7 गुना अधिक तेजी से काम करता है।

एक ईमानदार बेंचमार्कर होने के नाते, 0xd34df00dलेख के अंत में, उन्होंने संकेत दिया कि उनका संस्करण मूल की तुलना में बहुत सरल टीके के साथ काम करता है (उदाहरण के लिए, यूनिकोड को अनदेखा किया गया था), और इसलिए प्रदर्शन में इसकी श्रेष्ठता का वास्तव में कुछ भी मतलब नहीं है। लेकिन यह स्पष्ट है कि इसके बावजूद, लेख के प्रारूप ने टिप्पणियों में बहुत विवाद उत्पन्न किया (और मैं अक्सर खुद को शीर्षक से आगे नहीं पढ़ता हूं, जो छिपाने के लिए एक पाप है)। लेख के तहतyleoउन्होंने सी में उनके द्वारा लिखित एक तुच्छ समाधान के परीक्षण के परिणामों का हवाला दिया (एक सरलीकृत स्थिति के तहत), यह दिखाते हुए कि एक भोली सी-कार्यान्वयन अनुकूलित हस्केल-संस्करण को भी बायपास करता है। उसके बाद, सज्जनों ने खुद को एक दूसरे पर फेंकना शुरू कर दियाkaटिप्पणियाँ, जिसमें उन्होंने अपने विकल्पों की संभावनाओं में छोटे अंतर के साथ गलती पाई (यह विशेष रूप से स्थिति की मेरी व्यक्तिगत दृष्टि है)।

कुछ समय बाद, एक लेख कॉमरेड प्रकाशित हुआ chapuza, जिसने एलिक्सिर पर सरलीकृत डब्ल्यूसी के कार्यान्वयन की शुरुआत की , जो मानक एक से भी तेज काम करता है। पहली पोस्ट से टिप्पणियों में चर्चा जारी रही, हालांकि मेरी राय में पूर्व फ्यूज खो गया था।

इस लेख में हम एक भाषा / प्रोग्रामिंग प्रतिमान को दूसरे / दूसरे के साथ पराजित करने की कोशिश नहीं करेंगे। मुझे लगता है कि एक निष्पक्ष व्यक्ति समझता है कि सी, हास्केल और अन्य अन्य प्रोग्रामिंग भाषाओं की तुलना में मैनुअल अनुकूलन के मामले में बहुत अधिक लचीला है, और इसलिए सी कोड, हालांकि यह हास्केल की तुलना में धीमा हो सकता है, यह बहुत तेज भी हो सकता है - यह सब निर्भर करता है इस कोड को कौन लिखता है। दूसरी ओर, मैं व्यक्तिगत रूप से कार्यात्मक प्रतिमान की बहुत सारी संभावनाएं देखता हूं जो अभी तक खोजा नहीं गया है, और मैं इस संभावना को बाहर नहीं करता हूं कि किसी दिन कार्यात्मक कोड को इतना अच्छा अनुकूलित किया जाएगा कि सी में इस तरह का एनालॉग लिखना बहुत महंगा होगा। लेकिन फिर भी, यह समय अभी तक नहीं आया है।

, , ( ) , C-. . , , , 0xd34df00d "simd-".

, , .

#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <Windows.h>
#include <intrin.h>

using namespace std;

struct stats
{
    uint32_t char_count;
    uint32_t line_count;
    uint32_t word_count;
};

void word_count( unsigned char* const str, uint32_t size, stats& result );

int main( )
{
    FILE* f;
    fopen_s( &f, "input.txt", "rb" );
    fseek( f, 0, SEEK_END );
    long size = ftell( f );
    rewind( f );

    long alloc_size = size + 63 - ( size + 63 ) % 64;
    unsigned char* const data = (unsigned char*)_aligned_malloc( alloc_size, 64 );
    fread( data, 1, size, f );
    fclose( f );

    LARGE_INTEGER fr, t0, t1;
    QueryPerformanceFrequency( &fr );
    QueryPerformanceCounter( &t0 );

    stats result;
    word_count2( data, size, result );

    QueryPerformanceCounter( &t1 );

    _aligned_free( data );

    double const time = (double)( t1.QuadPart - t0.QuadPart ) / (double)fr.QuadPart;
    printf(
        "Words: %d; lines: %d; chars: %d\nElapsed time: %lfms\n",
        result.word_count, result.line_count, result.char_count, time * 1000.0
    );
    system( "pause" );
}

— , Windows Visual Studio. , Linux' , Linux- . , — VS.

, . , . 64 64 — SIMD-, . , . ( , , , .) , .

, Unicode, 32. , . , , .

Ryzen 5 3600 c 2x8 Gb 3200 MHz. , , .

void word_count( unsigned char* const str, uint32_t size, stats& result )
{
    uint32_t lines = 1;
    uint32_t words = 0;

    bool was_space = false;

    for ( uint32_t i = 0; i < size; ++i )
    {
        unsigned char const c = str[i];
        bool const is_space = c <= ' ';
        lines += ( c == '\n' ) ? 1 : 0;
        words += ( is_space && !was_space ) ? 1 : 0;
        was_space = is_space;
    }

    words += !was_space ? 1 : 0;

    result.char_count = size;
    result.line_count = lines;
    result.word_count = words;
}

0xd34df00d. :

Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 1825.704800ms

(SIMD- )

, ? , (, , ). 16 SSE-?

SSE:

void word_count_sse( unsigned char* const str, uint32_t size, stats& result )
{
    uint32_t lines = 1;
    uint32_t words = 0;

    bool was_space = false;

    for ( uint32_t i = 0; i < size; i += 16 )
    {
        __m128i const c = _mm_load_si128( (__m128i*)( str + i ) );
        uint32_t is_newline_mask = _mm_movemask_epi8(
            _mm_cmpeq_epi8( c, _mm_set1_epi8( '\n' ) )
        );

        uint32_t is_space_mask = _mm_movemask_epi8(
            _mm_andnot_si128( c, _mm_cmplt_epi8( c, _mm_set1_epi8( ' ' + 1 ) ) )
        );
        uint32_t was_space_mask = ( was_space ? 1 : 0 ) | ( is_space_mask << 1 );

        lines += __popcnt( is_newline_mask );
        words += __popcnt( is_space_mask & ~was_space_mask );
        was_space = is_space_mask & 0x8000;
    }

    words += !was_space ? 1 : 0;

    result.char_count = size;
    result.line_count = lines;
    result.word_count = words;
}

. was_space, . , 16 , 15- , .

_mm_load_si128 __m128i ( 128- XMM-).

. — 16- , 128- . SSE- XMM-, 16- _mm_movemask_epi8. — 128- , 16 , 16- , XMM-.

_mm_cmpeq_epi8, 128- , 0, , 255 . 128- , ( _mm_set1_epi8).

. , / SSE . _mm_cmplt_epi8 — , _mm_cmpeq_epi8. , , 128 , . _mm_andnot_si128. 128- "" . _mm_cmplt_epi8 . 128 , — , movemask'.

. was_space_mask, is_space_mask was_space, , __popcnt , . was_space , .

SIMD- x86 .

Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 165.704300ms

11 ! .

SIMD-

, , SSE AVX . 32 AVX/AVX2:

void word_count_avx( unsigned char* const str, uint32_t size, stats& result )
{
    uint32_t lines = 1;
    uint32_t words = 0;

    bool was_space = false;

    for ( uint32_t i = 0; i < size; i += 32 )
    {
        _mm_prefetch( (char*)str + i + 32 * 64, _MM_HINT_NTA );

        __m256i const c = _mm256_load_si256( (__m256i*)( str + i ) );
        uint32_t is_newline_mask = _mm256_movemask_epi8(
            _mm256_cmpeq_epi8( c, _mm256_set1_epi8( '\n' ) )
        );

        uint32_t is_space_mask = _mm256_movemask_epi8(
            _mm256_andnot_si256( c, _mm256_sub_epi8( c, _mm256_set1_epi8( ' ' + 1 ) ) )
        );
        uint32_t was_space_mask = ( was_space ? 1 : 0 ) | ( is_space_mask << 1 );

        lines += __popcnt( is_newline_mask );
        words += __popcnt( is_space_mask & ~was_space_mask );
        was_space = is_space_mask & 0x80000000;
    }

    words += !was_space ? 1 : 0;

    result.char_count = size;
    result.line_count = lines;
    result.word_count = words;
}

, SSE- . AVX/AVX2, , . 16, 32, 32-.

Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 109.606000ms

Prefetch

, , , , , _mm_prefetch. , , (, , ). AVX-:

void word_count2( unsigned char* const str, uint32_t size, stats& result )
{
    // ..............

    for ( uint32_t i = 0; i < size; i += 32 )
    {
        _mm_prefetch( (char*)str + i + 32 * 64, _MM_HINT_NTA );

        // ..............
    }

    // ..............
}

Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 73.564900ms

, 64 . , ; .

, RAM. — , 70ms. ~~( )~~.

, , . , , , 1.8 Gb 10 .

किसी भी मामले में, मुझे आशा है कि लेख दिलचस्प था, और कोई व्यक्ति खुद के लिए कुछ नया सीख सकता है।

होली की शुभकामनाएँ!

Wc के बारे में एक अन्य लेख

(SIMD- )

SIMD-

Prefetch

More articles: