مقال آخر عن مرحاض

يوم جيد للجميع.

في الآونة الأخيرة ظهرت مقالة على Habr Winning مع عشرين سطرًا من Haskell: نكتب مرحاضنا من @ 0xd34df00d . قام المؤلف ، المعروف بتعاطفه مع البرمجة الوظيفية ، بتنفيذ تمثيلي لأداة wc المساعدة على Haskell ، وأخضعها للتحسين ، مما أدى إلى خيار يعمل بشكل أسرع بأكثر من 7 مرات من الأداة المساعدة Unix القياسية.

كونك مقياس أداء واعي ، 0xd34df00dفي نهاية المقال ، أشار إلى أن نسخته تعمل مع المعارف التقليدية المبسطة إلى حد كبير مقارنة بالأصل (على سبيل المثال ، تم تجاهل Unicode) ، وبالتالي فإن تفوقها في الأداء لا يعني أي شيء في الواقع. ولكن من الواضح أنه على الرغم من ذلك ، فإن تنسيق المقالة أثار الكثير من الجدل في التعليقات (وأنا غالبًا لا أقرأ أكثر من العنوان بنفسي ، وهو خطيئة أخفيها). تحت المادةيليوواستشهد بنتائج اختبار حل تافه كتبه في C (تحت حالة مبسطة) ، يظهر أنه حتى التنفيذ الساذج يتجاوز نسخة Haskell المحسنة. بعد ذلك ، بدأ السادة في إلقاء أنفسهم على بعضهم البعضكاالتعليقات ، التي وجدوا فيها خطأًا مع اختلافات بسيطة في إمكانيات خياراتهم (هذه هي حصري رؤيتي الشخصية للوضع).

بعد مرور بعض الوقت ، تم نشر مقال الرفيق تشابوزاوالذي أدخل تطبيق Wc المبسط على Elixir ، والذي يعمل أيضًا بشكل أسرع من القياسي. استمر النقاش في التعليقات من المنشور الأول ، على الرغم من أن الفتيل السابق فقد في رأيي.

في هذه المقالة ، لن نحاول هزيمة نموذج لغة / برمجة بأخرى / أخرى. أعتقد أن شخصًا غير متحيز يدرك أن لغة C أكثر مرونة من حيث التحسين اليدوي من لغة Haskell ومعظم لغات البرمجة الأخرى ، وبالتالي فإن كود C ، على الرغم من أنه قد يكون أبطأ من لغة Haskell ، يمكن أن يكون أيضًا أسرع بكثير - كل هذا يتوقف على الذي يكتب هذا الرمز. من ناحية أخرى ، أرى شخصيًا الكثير من الاحتمالات للنموذج الوظيفي الذي لم يتم اكتشافه بعد ، ولا أستبعد إمكانية تحسين الشفرة الوظيفية في يوم من الأيام بشكل رائع لدرجة أن كتابة مثل هذا التناظرية في C ستكون باهظة الثمن. ولكن مع ذلك ، لم يحن الوقت بعد.

في الوقت نفسه ، لكوني شخصًا أعتبر حبه للتحسين (حتى بلا معنى) متعصبًا ، أصبحت مهتمًا على الفور إلى أي مدى يمكن تحسين خيار 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 .

على أي حال ، آمل أن يكون المقال مثيرًا للاهتمام ، وأن يتمكن شخص ما من تعلم شيء جديد لأنفسهم.

هوليفارس سعيد!