SuaraSekitar Terkini Kumpulan Berita dan Informasi dari berbagai sumber yang terpercaya
Daftar Isi
Masalah ¶
Saat berurusan dengan file besar, misalnya file yang tidak muat di RAM, membagi file menjadi beberapa bagian adalah suatu keharusan.
Beberapa format data seperti NDJSON dapat dipisah secara sepele, karena semua n byte adalah pemisah baris. Namun, CSV dapat memiliki baris baru dalam tanda kutip, yang tidak menunjukkan baris baru, tetapi baris baru di bidang baris.
Di sana adalah dua jenis solusi untuk masalah menemukan titik pemisahan dalam file CSV:
- Membacanya. Dengan hanya membaca file, kita dapat membedakan antara n byte yang berada dalam tanda kutip dan yang tidak. t, dan itu adalah titik di mana kita dapat membagi CSV. Dengan pengkodean yang mempertahankan kode ASCII, seperti UTF-8, untuk karakter khusus, kami dapat menghindari status dan kode tambahan.
- Solusi statistik. Dengan langsung menuju ke titik di mana kita ingin membagi file, dan dengan membaca beberapa byte di sekitarnya, kita dapat menebak titik pemisahan yang baik. Solusi ini secara alami lebih cepat, karena Anda perlu memproses lebih sedikit byte, tetapi juga dapat mengembalikan titik pemisahan yang salah.
Kami memutuskan untuk menggunakan pendekatan pertama untuk mengutamakan ketepatan daripada kecepatan. Namun, kecepatan sangat penting bagi kami, seberapa cepat kami dapat melakukannya?
Kecepatan menang
Implementasi pertama kami adalah pengurai berbasis python. Kami menguji perilakunya yang benar, tetapi kami tentu saja melihat bahwa kinerja dengan pendekatan ini tidak dapat digunakan.
Halo, C
Kinerja python bisa sangat membatasi, tetapi hal yang baik tentang Python adalah bahwa kode C dapat diintegrasikan dengan mudah pada masalah sederhana seperti ini.
Kami mem-porting implementasi Python ke C dan menyebutnya menggunakan CFFI. Pengoptimalan tunggal ini, tanpa peningkatan lainnya, meningkatkan kinerja hingga dua kali lipat, sekarang mencapai penghalang 1 GB/dtk.
Sederhana lebih cepat
Kami cukup senang dengan implementasi awal 1GB/s, tetapi kami tahu bahwa kami dapat melakukan yang lebih baik. Kami mulai mengoptimalkan algoritme. Versi pertama didasarkan pada satu loop kompleks. Versi yang dioptimalkan lebih sederhana, dan memiliki loop bersarang untuk menangani bidang yang dikutip.
Implementasi awal.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
ketika ( pos ukuran buffer) { jika (buffer_text_encoded
== escapechar) { next_special_char_found = escapechar; } kalau tidak jika (buffer_text_encoded == garis baru) { next_special_char_found = garis baru; } kalau tidak jika (buffer_text_encoded == quotechar) { next_special_char_found = quotechar; } kalau tidak { next_special_char_found = 0
; } jika (parsing_state == estate_normal && next_special_char_found == 0) { pos = pos + 1
; melanjutkan; } jika (next_special_char_found == escapechar || next_special_char_found == quotechar) { jika (parsing_state != estate_possible_escape_found) { state_previous_to_escape_char_found = parsing_state; parsing_state = estate_possible_escape_found; pos = pos + 1; melanjutkan; } kalau tidak { parsing_state = state_previous_to_escape_char_found; pos = pos + 1; melanjutkan; } } jika (
parsing_state == estate_possible_escape_found) { jika (state_previous_to_escape_char_found == estate_normal) { parsing_state = estate_quoted_text; } kalau tidak {
parsing_state = estate_normal; } } jika ( parsing_state == estate_normal && next_special_char_found == garis baru) { last_unescaped_new_line_found = pos; pos = pos + 1; melanjutkan ;
} pos = pos + 1;
Penerapan yang dioptimalkan.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0; Saya ukuran buffer; Saya++){
jika (B[
i] == escapechar){ Saya++; melanjutkan ; } jika (B[i] ==
quotechar){
melakukan
{ Saya++; } ketika (((B [i] != quotechar) || (B[i] == quotechar && B[i-1] == escapechar)) && Saya ukuran buffer); melanjutkan; } jika (B[i] == 'n') { baris terakhir_baru = Saya; } }
SIMD
Implementasi ini cukup cepat, tapi kami masih berpikir kami bisa melangkah lebih jauh. Versi yang dioptimalkan ini tampaknya sangat sulit untuk ditingkatkan, karena hanya melakukan tiga perbandingan cepat per byte di jalur bahagia.
Meningkatkan waktu dibutuhkan untuk memproses setiap byte tampaknya hampir mustahil, dan sebenarnya, kami tidak melakukannya. Sebagai gantinya, kami memproses beberapa byte per iterasi.
Semua CPU x86 modern menyertakan instruksi SIMD seperti SSE dan AVX. Instruksi ini memungkinkan prosesor untuk bekerja pada beberapa register secara paralel, meningkatkan throughput.
Inilah tampilan versi terakhir kami:
} kalau tidak jika (masker == mask_baris baru) { // satu-satunya karakter khusus adalah baris baru jika (negara == NORMAL) { // dan kami berada di luar kutipan // bit terakhir yang disetel ke ‘1’ di topeng menunjukkan di mana baris terakhir ditemukan last_new_line_found = Saya + (31 – __builtin_clz(masker))); } } kalau tidak { // ada kompleks kombinasi karakter khusus // namun, kita dapat memajukan `i` dengan jumlah bit awal pada topeng yang disetel // ke ‘0’ Saya += __builtin_ctz(masker); merusak; } } } jika (penyangga[i] == quotechar){ negara = !negara; } kalau tidak jika (negara
__m128i
sse_newline
= _mm_set1_epi8( 'n'); __m128i sse_quotechar = _mm_set1_epi8(quotechar);
__m128i sse_escapechar = _mm_set1_epi8(escapechar ); int max_simd = ukuran buffer - 16; // hindari membaca melewati buffer berakhir karena SIMD untuk (; Saya ukuran buffer;
Saya++){ untuk (; Saya max_simd; Saya += 16){ // Muat 16 byte CSV di register SSE __m128i *sse_p
= (__m128i *)&penyangga[i]; __m128i sse_a = _mm_loadu_si128(sse_p ); // bandingkan 16 byte dengan quotechar, dan padatkan hasilnya dalam 16 bit pertama mask_quoted int mask_quoted = _mm_movemask_epi8(_mm_cmpeq_epi8(sse_quotechar , sse_a)); / / bandingkan dengan baris baru
int mask_newline = _mm_movemask_epi8(_mm_cmpeq_epi8(sse_newline, sse_a)); int masker = mask_quoted | mask_newline; jika (escapechar){
// bandingkan dengan escapechar masker |= _mm_movemask_epi8(_mm_cmpeq_epi8( sse_escapechar, sse_a)); } jika (masker != 0){ // setidaknya ada satu karakter khusus dalam 16 byte jika (masker == mask_quoted){ // satu-satunya karakter khusus adalah tanda kutip // kita cukup menghitung jumlah kutipan // status kutipanakan berubah jika hitungan ini adalah bilangan ganjil int kutipan = __builtin_popcount( mask_quoted); negara = (
negara + kutipan) % 2;
== NORMAL && penyangga[i] == ‘n’) {
last_new_line_found = Saya; } kalau tidak
jika (
penyangga[i] == escapechar) {Saya++; } }
Instrinsik kompiler yang digunakan:
__m128i _mm_set1_epi8(unsigned char c). Mengembalikan grup register SSE 16-byte dengan semua byte yang diisi dengan c. __m128i _mm_loadu_si128(__m128i constmem_addr). Mengembalikan grup register SSE 16-byte dengan byte yang disalin dari
mem_addr. __m128i _mm_cmpeq_epi8 (__m128i a, __m128i b). Mengembalikan grup register SSE 16-byte, membandingkan kesetaraan byte a dan B. Setiap byte yang dikembalikan diatur ke 0xFF jika byte yang sesuai dari a dan b adalah sama, 0 sebaliknya.
- int _mm_movemask_epi8 (__m128i a). Memadatkan 16 byte a dengan mengambil bit paling signifikan dan setiap byte dalam
-
int __builtin_popcount(unsigned int x). Menghitung jumlah bit dalam x yang disetel ke 1 .
a, mengembalikan topeng berukuran 16-bit.
int __builtin_clz(unsigned int x). Mengembalikan jumlah 0-bit terdepan dalam x, mulai dari posisi bit paling signifikan. Jika x adalah 0, hasilnya tidak terdefinisi. int __builtin_ctz (tidak ditandatangani int x). Mengembalikan jumlah trailing 0-bit dalam x, mulai dari posisi bit paling tidak signifikan. Jika x adalah 0, hasilnya tidak terdefinisi.
Lihat juga dokumen Intel dan gcc.
Ini tentu saja merupakan versi yang lebih kompleks, tetapi berkat SSE, ini bekerja pada 3GB/s!
Ingin membantu kami memecahkan masalah ini? Bergabunglah dengan kami!