关于wc的另一篇文章

祝大家有美好的一天。

最近，有一篇文章发表在Habrell的《 Habrell Winning with二十行》上：我们从@ 0xd34df00d 编写了wc。作者以对函数式编程的同情而闻名，他在Haskell上实现了wc实用程序的类似物并对其进行了优化，从而使该选项的运行速度比标准Unix实用程序快7倍以上。

作为一个认真的基准测试者， 0xd34df00d在文章末尾，他表示与原始版本相比，其版本使用了大大简化的TK（例如，忽略了Unicode），因此，其性能优越实际上并不意味着任何意义。但是很明显，尽管如此，文章的格式还是在评论中引起了很多争议（而且我经常阅读的内容不超过标题本人，这是一个隐藏的罪过）。下条音阶他列举了测试他用C语言编写的一个简单解决方案的结果（在简化条件下），表明即使是单纯的C实现也会绕过优化的Haskell版本。在那之后，先生们开始互相攻击K a评论，他们发现自己的选择可能存在微小差异（这完全是我个人对情况的看法）。

一段时间后，同志发表了一篇文章 Chapuza，它介绍了在Elixir上实现简化的wc的方法，该方法的工作速度也比标准方法快。在第一篇文章的评论中，讨论继续进行，尽管在我看来，前者的保险丝已经消失了。

在本文中，我们不会尝试用另一种/另一种语言来击败一种语言/编程范例。我认为没有偏见的人知道C在手动优化方面比Haskell和大多数其他编程语言要灵活得多，因此C代码虽然可能比Haskell慢，但也可以更快-这都取决于谁编写这段代码。另一方面，我个人看到了尚未发现的功能范式的许多可能性，并且我不排除有一天某天功能代码将被优化得如此酷，以至于用C编写这样的模拟将太昂贵了。但是即使这样，这个时候还没有到。

同时，作为一个热衷于优化（甚至毫无意义）的人，我非常狂热，我立即对琐碎的C选项可以优化多少感兴趣。这就是我们要做的。我认为在前几篇文章之后，这将很有趣，此外，0xd34df00d 在他对文章的评论中，他表示有兴趣使用“模拟魔术”对单词进行计数。

试验台

因此，首先，我们将提出考虑单词的条件。

#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 .

无论如何，我希望这篇文章很有趣，并且有人可以自己学到一些新东西。

祝大家好运！