Hari baik untuk semua
Baru-baru ini sebuah artikel muncul di Habr Winning Dengan dua puluh baris Haskell: kami menulis wc kami dari @ 0xd34df00d . Penulis, yang dikenal karena simpatinya untuk pemrograman fungsional, mengimplementasikan analog utilitas wc pada Haskell dan menjadikannya optimasi, menghasilkan opsi yang bekerja lebih dari 7 kali lebih cepat daripada utilitas Unix standar.
Menjadi pembanding yang teliti, 0xd34df00dPada akhir artikel, ia menunjukkan bahwa versinya bekerja dengan TK yang sangat disederhanakan dibandingkan dengan aslinya (misalnya, Unicode diabaikan), dan karena itu keunggulan dalam kinerjanya tidak berarti apa-apa pada kenyataannya. Tetapi jelas bahwa terlepas dari ini, format artikel menghasilkan banyak kontroversi dalam komentar (dan saya sendiri sering tidak membaca lebih jauh daripada judulnya sendiri, yang merupakan dosa yang disembunyikan). Di bawah artikelyleoDia mengutip hasil pengujian solusi sepele yang ditulis olehnya dalam C (di bawah kondisi yang disederhanakan), menunjukkan bahwa bahkan implementasi C yang naif mem-bypass versi Haskell yang dioptimalkan. Setelah itu, tuan-tuan mulai saling melemparkan dirikakomentar, di mana mereka menemukan kesalahan dengan perbedaan kecil dalam kemungkinan pilihan mereka (ini adalah visi pribadi saya tentang situasi).
Setelah beberapa waktu, sebuah artikel diterbitkan kawan chapuza, yang memperkenalkan implementasi wc yang disederhanakan pada Elixir, yang juga bekerja lebih cepat dari yang standar. Diskusi berlanjut dalam komentar dari posting pertama, meskipun menurut saya bekas sekering hilang.
Dalam artikel ini kami tidak akan mencoba untuk mengalahkan satu bahasa / paradigma pemrograman dengan yang lain / yang lain. Saya pikir orang yang tidak bias memahami bahwa C jauh lebih fleksibel dalam hal optimasi manual daripada Haskell dan sebagian besar bahasa pemrograman lainnya, dan karena itu kode C, walaupun mungkin lebih lambat dari Haskell, juga bisa jauh lebih cepat - itu semua tergantung pada siapa yang menulis kode ini. Di sisi lain, saya pribadi melihat banyak kemungkinan paradigma fungsional yang belum ditemukan, dan saya tidak mengecualikan kemungkinan bahwa suatu hari nanti kode fungsional akan dioptimalkan dengan sangat keren sehingga penulisan analog semacam itu dalam C akan terlalu mahal. Namun meski begitu, saat ini belum datang.
, , ( ) , 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 .
Bagaimanapun, saya harap artikel itu menarik, dan seseorang dapat belajar sesuatu yang baru untuk diri mereka sendiri.
Selamat holivarov!