Guten Tag allerseits.
Kürzlich erschien ein Artikel über Habr Winning mit zwanzig Zeilen Haskell: Wir schreiben unser WC von @ 0xd34df00d . Der Autor, bekannt für seine Sympathie für funktionale Programmierung, implementierte ein Analogon des Dienstprogramms wc auf Haskell und unterzog es einer Optimierung, was zu einer Option führte, die mehr als siebenmal schneller als das Standarddienstprogramm von Unix funktioniert.
Als gewissenhafter Benchmarker 0xd34df00dAm Ende des Artikels wies er darauf hin, dass seine Version mit einer im Vergleich zum Original stark vereinfachten TK arbeitet (beispielsweise wurde Unicode ignoriert), und daher bedeutet ihre Überlegenheit in der Leistung tatsächlich nichts. Trotzdem ist klar, dass das Format des Artikels in den Kommentaren viele Kontroversen ausgelöst hat (und ich lese oft nicht weiter als die Überschrift selbst, was kein Geheimnis ist). Unter ArtikelyleoEr zitierte die Ergebnisse des Testens einer von ihm in C geschriebenen trivialen Lösung (unter einer vereinfachten Bedingung) und zeigte, dass selbst eine naive C-Implementierung die optimierte Haskell-Version umgeht. Danach begannen sich die Herren gegenseitig zu bewerfenkaKommentare, in denen sie kleine Unterschiede in den Möglichkeiten ihrer Optionen beanstandeten (dies ist ausschließlich meine persönliche Vision der Situation).
Nach einiger Zeit wurde ein Artikel Kamerad veröffentlicht Chapuza, mit dem die Implementierung von vereinfachtem WC auf Elixir eingeführt wurde, das auch schneller als das Standard- WC funktioniert. Die Diskussion wurde in den Kommentaren des ersten Beitrags fortgesetzt, obwohl meiner Meinung nach die frühere Sicherung verloren gegangen ist.
In diesem Artikel werden wir nicht versuchen, ein Sprach- / Programmierparadigma mit einem anderen zu besiegen. Ich denke, eine unvoreingenommene Person versteht, dass C in Bezug auf die manuelle Optimierung viel flexibler ist als Haskell und die meisten anderen Programmiersprachen, und daher kann C-Code, obwohl er langsamer als Haskell sein kann, auch viel schneller sein - alles hängt davon ab Wer schreibt diesen Code. Andererseits sehe ich persönlich viele Möglichkeiten des Funktionsparadigmas, die noch nicht entdeckt wurden, und ich schließe die Möglichkeit nicht aus, dass der Funktionscode eines Tages so cool optimiert wird, dass das Schreiben eines solchen Analogons in C zu teuer wäre. Aber trotzdem ist diese Zeit noch nicht gekommen.
, , ( ) , 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 .
Auf jeden Fall hoffe ich, dass der Artikel interessant war und jemand etwas Neues für sich lernen konnte.
Glückliche Holivars!