Bonne journée à tous.
Récemment, un article est paru sur Habr Winning With vingt lignes de Haskell: nous écrivons notre wc à partir de @ 0xd34df00d . L'auteur, connu pour sa sympathie pour la programmation fonctionnelle, a implémenté un analogue de l'utilitaire wc sur Haskell , et l'a soumis à l'optimisation, résultant en une option qui fonctionne plus de 7 fois plus rapidement que l'utilitaire Unix standard.
Être un référent consciencieux, 0xd34df00dÀ la fin de l'article, il a indiqué que sa version fonctionne avec un savoir-faire considérablement simplifié par rapport à l'original (par exemple, Unicode a été ignoré), et donc sa supériorité dans les performances ne signifie rien en fait. Mais il est clair que malgré cela, le format de l'article a suscité beaucoup de controverse dans les commentaires (et souvent je ne lis pas plus loin que le titre moi-même, ce qui n'est pas un secret). Sous l'articleyleoIl a cité les résultats du test d'une solution triviale écrite par lui en C (dans une condition simplifiée), montrant que même une implémentation C naïve contourne la version optimisée de Haskell. Après cela, les messieurs ont commencé à se jeter l'un sur l'autrekacommentaires, dans lesquels ils ont trouvé à redire à de petites différences dans les possibilités de leurs options (c'est exclusivement ma vision personnelle de la situation).
Après un certain temps, un article a été publié camarade chapuza, qui a introduit la mise en œuvre de wc simplifié sur Elixir, qui fonctionne également plus rapidement que le standard. La discussion s'est poursuivie dans les commentaires du premier post, bien qu'à mon avis l'ancien fusible ait été perdu.
Dans cet article, nous n'essaierons pas de vaincre un paradigme de langage / programmation avec un autre / un autre. Je pense qu'une personne impartiale comprend que C est beaucoup plus flexible en termes d'optimisation manuelle que Haskell et la plupart des autres langages de programmation, et donc le code C, bien qu'il puisse être plus lent que Haskell, peut également être beaucoup plus rapide - tout dépend de qui écrit ce code. D'un autre côté, je vois personnellement beaucoup de possibilités du paradigme fonctionnel qui n'ont pas encore été découvertes, et je n'exclus pas la possibilité qu'un jour le code fonctionnel soit optimisé si cool que l'écriture d'un tel analogique en C serait trop cher. Mais même ainsi, ce temps n'est pas encore venu.
, , ( ) , 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 .
En tout cas, j'espère que l'article était intéressant et que quelqu'un pourrait apprendre quelque chose de nouveau par lui-même.
Joyeux Holivars!