Bom Dia a todos.
Recentemente, apareceu um artigo sobre Habr Winning With vinte linhas de Haskell: escrevemos nosso wc em @ 0xd34df00d . O autor, conhecido por sua simpatia pela programação funcional, implementou um análogo do utilitário wc no Haskell e o submeteu à otimização, resultando em uma opção que funciona mais de 7 vezes mais rápido que o utilitário Unix padrão.
Sendo um comparador consciente, 0xd34df00dNo final do artigo, ele indicou que sua versão funciona com um TK bastante simplificado em comparação com o original (por exemplo, o Unicode foi ignorado) e, portanto, sua superioridade no desempenho não significa nada de fato. Mas é claro que, apesar disso, o formato do artigo gerou muita controvérsia nos comentários (e muitas vezes eu não leio além do título, que é um pecado a esconder). ArtigoyleoEle citou os resultados do teste de uma solução trivial escrita por ele em C (sob uma condição simplificada), mostrando que mesmo uma implementação ingênua de C ignora a versão Haskell otimizada. Depois disso, os cavalheiros começaram a se atirar um no outrokacomentários, nos quais encontraram falhas em pequenas diferenças nas possibilidades de suas opções (esta é exclusivamente minha visão pessoal da situação).
Depois de algum tempo, um artigo foi publicado camarada chapuza, que introduziu a implementação do wc simplificado no Elixir, que também funciona mais rápido que o padrão. A discussão continuou nos comentários do primeiro post, embora, na minha opinião, o antigo fusível estivesse perdido.
Neste artigo, não tentaremos derrotar um paradigma de linguagem / programação com outro / outro. Eu acho que uma pessoa imparcial entende que C é muito mais flexível em termos de otimização manual do que Haskell e a maioria das outras linguagens de programação e, portanto, o código C, embora possa ser mais lento que Haskell, também pode ser muito mais rápido - tudo depende de quem escreve esse código. Por outro lado, eu pessoalmente vejo muitas possibilidades do paradigma funcional que ainda não foram descobertas e não excluo a possibilidade de algum dia o código funcional ser otimizado tão legal que escrever um analógico em C seria muito caro. Mas, mesmo assim, esse momento ainda não chegou.
, , ( ) , 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 .
De qualquer forma, espero que o artigo seja interessante e que alguém possa aprender algo novo por si.
Holivares felizes!