Geekly articles weekly

Cara mempercepat pembongkaran LZ4 di ClickHouse

Saat menjalankan kueri di ClickHouse, Anda dapat melihat bahwa di profiler, di salah satu tempat pertama, fungsi LZ_decompress_fast sering terlihat. Mengapa ini terjadi? Pertanyaan ini menjadi alasan bagi keseluruhan penelitian untuk memilih algoritma dekompresi terbaik. Di sini saya menerbitkan seluruh penelitian, dan versi singkat dapat ditemukan di laporan saya di HighLoad ++ Siberia.

Data ClickHouse disimpan dalam bentuk terkompresi. Dan selama eksekusi permintaan ClickHouse mencoba melakukan hampir tidak ada - menggunakan sumber daya CPU minimum. Itu terjadi bahwa semua perhitungan yang bisa memakan waktu cukup lama sudah dioptimalkan dengan baik, dan permintaan ditulis dengan baik oleh pengguna. Kemudian tetap melakukan rilis.



Pertanyaannya adalah - mengapa pembongkaran LZ4 bisa menjadi hambatan? Tampaknya LZ4 adalah algoritma yang sangat ringan : tingkat kompresi, tergantung pada data, biasanya berkisar antara 1 hingga 3 GB / s per inti prosesor. Ini secara signifikan lebih dari kecepatan subsistem disk. Selain itu, kami menggunakan semua kernel yang tersedia, dan skala ekspansi secara linear di semua kernel fisik.

Tetapi ada dua hal yang perlu diingat. Pertama, data terkompresi dibaca dari disk, dan tingkat kompresi diberikan dalam jumlah data yang tidak terkompresi. Jika rasio kompresi cukup besar, maka hampir tidak ada yang perlu dibaca dari disk. Tetapi pada saat yang sama, banyak data terkompresi dihasilkan, dan tentu saja, ini mempengaruhi konsumsi CPU: jumlah pekerjaan kompresi data dalam kasus LZ4 hampir sebanding dengan volume data terkompresi itu sendiri.

Kedua, membaca data dari disk mungkin tidak diperlukan sama sekali jika data ada dalam cache. Untuk melakukan ini, Anda bisa mengandalkan cache halaman atau menggunakan cache Anda sendiri. Dalam database kolom, menggunakan cache lebih efisien karena faktanya tidak semua kolom termasuk di dalamnya, tetapi hanya yang sering digunakan. Inilah sebabnya mengapa LZ4, dalam hal beban CPU, sering menjadi hambatan.

Karena itu dua pertanyaan lagi. Jika kompresi data "melambat", maka mungkin mereka tidak boleh dikompresi sama sekali? Namun dalam praktiknya, anggapan ini tidak ada artinya. Baru-baru ini di ClickHouse hanya dimungkinkan untuk mengkonfigurasi dua opsi kompresi data - LZ4 dan Zstandard . Standarnya adalah LZ4. Dengan beralih ke Zstandard, Anda dapat membuat kompresi lebih kuat dan lebih lambat. Tetapi tidak mungkin untuk sepenuhnya menonaktifkan kompresi hingga saat ini - LZ4 dianggap sebagai minimum yang wajar, yang selalu dapat digunakan. Itu sebabnya saya sangat suka LZ4. :)

Namun baru-baru ini, seorang asing muncul di obrolan berbahasa Inggris ClickHouse, yang mengatakan bahwa ia memiliki subsistem disk yang sangat cepat (NVMe SSD) dan semuanya tergantung pada kompresi - alangkah baiknya untuk dapat mematikannya. Saya menjawab bahwa tidak ada kemungkinan seperti itu, tetapi mudah untuk ditambahkan. Beberapa hari kemudian kami menerima permintaan kumpulan , yang menerapkan metode none kompresi. Saya meminta hasilnya - seberapa banyak ini membantu, seberapa cepat permintaan. Orang itu mengatakan bahwa fitur baru ini ternyata tidak berguna dalam praktik, karena data tanpa kompresi mulai memakan terlalu banyak ruang.

Pertanyaan kedua yang muncul adalah: jika ada cache, mengapa tidak menyimpan data yang sudah terkompresi di dalamnya? Ini diperbolehkan - dalam banyak kasus akan mungkin untuk menghilangkan kebutuhan untuk dekompresi. Dan di ClickHouse ada cache seperti itu - cache dari blok yang diperluas . Namun sayang untuk menghabiskan banyak RAM di sana karena efisiensinya yang rendah. Itu membenarkan dirinya hanya pada permintaan kecil, berturut-turut yang menggunakan data yang hampir sama.

Pertimbangan umum: data harus dikompresi, sebaiknya selalu. Selalu bakar mereka ke disk yang dikompresi. Mengirimkan melalui jaringan juga dengan kompresi. Menurut pendapat saya, kompresi default harus dianggap dibenarkan bahkan ketika mentransfer ke jaringan 10-gigabit tanpa kelebihan langganan dalam pusat data, dan mentransfer data tanpa kompresi antara pusat data umumnya tidak dapat diterima.

Mengapa LZ4?


Mengapa LZ4 digunakan? Apakah mungkin untuk memilih sesuatu yang lebih mudah? Pada prinsipnya, itu mungkin, dan itu benar dan bermanfaat. Tapi mari kita lihat dulu kelas algoritma apa yang dimiliki LZ4.

Pertama, itu tidak tergantung pada tipe data. Misalnya, jika Anda tahu sebelumnya bahwa Anda akan memiliki array bilangan bulat, maka Anda dapat menggunakan salah satu dari banyak varian algoritma VarInt - itu akan lebih efisien pada CPU. Kedua, LZ4 tidak terlalu bergantung pada asumsi yang diperlukan pada model data. Misalkan Anda memiliki serangkaian waktu pembacaan sensor - array dengan jumlah tipe float. Kemudian Anda dapat menghitung delta dan kemudian kompres lebih lanjut, dan ini akan lebih efisien dalam hal rasio kompresi.

Artinya, LZ4 dapat digunakan tanpa masalah untuk setiap byte array - untuk file apa pun. Tentu saja, ia memiliki spesialisasi sendiri (lebih lanjut tentang itu di bawah), dan dalam beberapa kasus penggunaannya tidak ada artinya. Tetapi jika Anda menyebutnya algoritma tujuan umum, ini akan menjadi kesalahan kecil. Dan perhatikan bahwa, berkat perangkat internal, LZ4 secara otomatis mengimplementasikan algoritma RLE sebagai kasus khusus.

Pertanyaan lain: apakah LZ4 algoritma yang paling optimal dari kelas ini untuk kombinasi kecepatan dan gaya kompresi? Algoritma semacam ini disebut pareto frontier - ini berarti bahwa tidak ada algoritma lain yang benar-benar lebih baik dalam satu indikator dan tidak lebih buruk pada yang lain (dan bahkan pada berbagai dataset). Ada algoritma yang lebih cepat, tetapi memberikan rasio kompresi yang lebih rendah, dan ada yang kompres lebih banyak, tetapi pada saat yang sama kompres atau dekompresi lebih lambat.

Faktanya, LZ4 bukan perbatasan pareto. Ada opsi yang sedikit lebih baik. Misalnya, ini adalah LZTURBO dari powturbo tertentu. Tidak ada keraguan dalam keandalan hasil berkat komunitas di encode.ru (forum terbesar dan kira-kira satu-satunya untuk kompresi data). Tetapi pengembang tidak mendistribusikan kode sumber atau binari, tetapi hanya memberikannya kepada lingkaran orang terbatas untuk pengujian atau untuk banyak uang (seperti belum ada yang membayar sejauh ini). Juga patut diperhatikan Lizard (sebelumnya LZ5) dan Density . Mereka dapat bekerja sedikit lebih baik daripada LZ4 ketika memilih beberapa level kompresi. Perhatikan juga LZSSE - hal yang sangat menarik. Namun, lebih baik melihatnya setelah membaca artikel ini.

Bagaimana cara kerja LZ4?


Mari kita lihat bagaimana LZ4 bekerja secara umum. Ini adalah salah satu implementasi dari algoritma LZ77: L dan Z menunjukkan nama-nama penulis (Lempel dan Ziv), dan 77 - pada tahun 1977, ketika algoritma tersebut dipublikasikan. Ini memiliki banyak implementasi lain: QuickLZ, FastLZ, BriefLZ, LZF, LZO, serta gzip dan zip saat menggunakan level kompresi rendah.

Blok data yang dikompres menggunakan LZ4 berisi urutan catatan (perintah, instruksi) dari dua jenis:

  1. Literal: "ambil N byte berikutnya apa adanya dan salin ke hasilnya."
  2. Match (pertandingan): "ambil N byte yang sudah didekompresi oleh offset offset dari posisi saat ini."

Sebuah contoh Sebelum kompresi:
Hello world Hello

Setelah kompresi:
literals 12 "Hello world " match 5 12

Jika kita mengambil blok terkompresi dan melewatinya dengan kursor, menjalankan perintah ini, maka kita akan mendapatkan data awal yang tidak terkompresi sebagai hasilnya.

Kami secara kasar melihat bagaimana data tersebut didekompresi. Intinya juga jelas: untuk melakukan kompresi, algoritma mengkodekan urutan byte berulang menggunakan kecocokan.

Hapus dan beberapa properti. Algoritma ini berorientasi byte - tidak membedah byte individual, tetapi hanya menyalinnya secara keseluruhan. Di sinilah letak perbedaan, misalnya, dari pengkodean entropi. Sebagai contoh, zstd adalah komposisi LZ77 dan pengkodean entropi.

Perhatikan bahwa ukuran blok terkompresi tidak dipilih terlalu besar sehingga tidak menghabiskan banyak RAM selama pembongkaran; agar tidak memperlambat akses acak dalam file terkompresi (yang terdiri dari banyak blok terkompresi); dan kadang-kadang agar blok cocok dengan beberapa cache CPU. Misalnya, Anda dapat memilih 64 KB - jadi buffer untuk data terkompresi dan tidak terkompresi akan muat dalam cache L2 dan setengahnya akan tetap.

Jika kita perlu mengompres file yang lebih besar, kita hanya akan menggabungkan blok terkompresi. Pada saat yang sama, di sebelah setiap blok terkompresi, lebih nyaman untuk menempatkan data tambahan - ukuran, jumlah cek.

Offset maksimum untuk pertandingan terbatas, dalam LZ4 - 64 kilobyte. Nilai ini disebut jendela geser. Memang, ini berarti bahwa ketika kursor bergerak maju, kecocokan bisa berada dalam jendela berukuran 64 kilobyte dengan kursor, yang bergerak dengan kursor.

Sekarang mari kita lihat bagaimana mengompres data - dengan kata lain, bagaimana menemukan urutan yang cocok dalam suatu file. Tentu saja, Anda dapat menggunakan sufiks trie (hebat jika Anda pernah mendengarnya). Ada beberapa opsi di mana urutan pencocokan terpanjang dijamin berada di antara byte sebelumnya dalam proses kompresi. Ini disebut penguraian optimal dan memberikan rasio kompresi yang hampir lebih baik untuk format blok terkompresi tetap. Tetapi ada opsi yang lebih efektif - ketika kami menemukan kecocokan yang cukup baik dalam data, tetapi belum tentu yang terpanjang. Cara paling efisien untuk menemukannya adalah dengan menggunakan tabel hash.

Untuk melakukan ini, kita pergi melalui blok data sumber dengan kursor dan mengambil beberapa byte setelah kursor. Misalnya, 4 byte. Hash mereka dan letakkan di tabel hash offset dari awal blok - di mana 4 byte ini bertemu. Nilai 4 disebut min-match - dengan bantuan tabel hash seperti itu kita dapat menemukan kecocokan setidaknya 4 byte.

Jika kita melihat tabel hash, dan sudah ada catatan di sana, dan jika offset tidak melebihi jendela geser, maka kita memeriksa berapa banyak byte yang cocok setelah empat byte ini. Mungkin ada lebih banyak yang bertepatan. Mungkin juga tabrakan telah terjadi di tabel hash dan tidak ada yang cocok. Ini normal - Anda cukup mengganti nilai di tabel hash dengan yang baru. Tabrakan di tabel hash hanya akan menghasilkan rasio kompresi yang lebih rendah karena ada lebih sedikit kecocokan. Omong-omong, tabel hash semacam ini (dengan ukuran tetap dan tanpa resolusi tabrakan) disebut tabel cache, tabel cache. Ini juga logis - jika terjadi tabrakan, tabel cache hanya lupa tentang catatan lama.
Tugas untuk pembaca yang penuh perhatian. Biarkan data menjadi array angka seperti UInt32 dalam format endian kecil, yang merupakan bagian dari urutan bilangan asli: 0, 1, 2 ... Jelaskan mengapa ketika menggunakan LZ4 data ini tidak dikompresi (jumlah data terkompresi tidak kurang dari jumlah data yang tidak terkompresi).

Cara mempercepat


Jadi, saya ingin mempercepat pembongkaran LZ4. Mari kita lihat seperti apa siklus bongkar muat itu. Inilah loop dalam pseudocode:

  sementara (...)
 {
     baca (input_pos, literal_length, match_length);

     salin (output_pos, input_pos, literal_length);
     output_pos + = literal_length;

     baca (input_pos, match_offset);

     salin (output_pos, output_pos - match_offset,
         match_length);
     output_pos + = match_length;
 }

Format LZ4 dirancang sehingga literal dan cocok berganti dalam file terkompresi. Dan tentu saja, literal selalu didahulukan (karena sejak awal pertandingan tidak memiliki tempat untuk mendapatkan dari). Oleh karena itu, panjangnya dikodekan bersama.

Faktanya, semuanya sedikit lebih rumit. Satu byte dibaca dari file, dan dua nibble diambil darinya, di mana angka 0 hingga 15 dikodekan.Jika angka yang sesuai tidak sama dengan 15, maka itu dianggap sebagai panjang literal dan cocok, masing-masing. Dan jika 15, maka panjangnya lebih panjang dan dikodekan dalam byte berikut. Kemudian byte selanjutnya dibaca, dan nilainya ditambahkan ke panjangnya. Selanjutnya, jika itu sama dengan 255, maka kita melanjutkan - kita membaca byte berikutnya dengan cara yang sama.

Perhatikan bahwa rasio kompresi maksimum untuk format LZ4 tidak mencapai 255. Dan pengamatan kedua (tidak berguna): jika data Anda sangat berlebihan, maka menggunakan LZ4 akan menggandakan rasio kompresi yang meningkat dua kali lipat.

Ketika kita membaca panjang literal (dan kemudian juga panjang korek api dan offset korek api), untuk mengosongkannya cukup dengan menyalin dua keping memori saja.

Cara menyalin sepotong memori


Tampaknya Anda dapat menggunakan fungsi memcpy , yang hanya dirancang untuk menyalin keping memori. Tetapi ini tidak optimal dan masih salah.

Mengapa penggunaan fungsi memcpy suboptimal? Karena dia:

  1. biasanya terletak di perpustakaan libc (dan perpustakaan libc biasanya terhubung secara dinamis, dan panggilan memcpy akan masuk secara tidak langsung, melalui PLT),
  2. tidak sejalan dengan argumen ukuran yang tidak diketahui dalam waktu kompilasi,
  3. membuat banyak upaya untuk dengan benar memproses "ekor" dari fragmen memori yang tidak kelipatan dari ukuran kata mesin atau register.

Poin terakhir adalah yang paling penting. Misalkan kita meminta fungsi memcpy untuk menyalin tepat 5 byte. Akan sangat bagus untuk menyalin 8 byte sekaligus, menggunakan dua instruksi movq untuk ini.

Hello world Hello wo ...
^^^^^ ^^^ - src
^^^^^ ^^^ - dst

Tapi kemudian kita akan menyalin tiga byte tambahan - yaitu, kita akan menulis di luar negeri buffer yang ditransfer. Fungsi memcpy tidak memiliki hak untuk melakukan ini - memang, karena kami akan menimpa beberapa data dalam program kami, akan ada "bagian" dari memori. Dan jika kita menulis di alamat yang tidak selaras, maka byte tambahan ini dapat ditemukan pada halaman memori virtual yang tidak terisi atau pada halaman tanpa akses tulis. Lalu kita mendapatkan segfault (itu bagus).

Tetapi dalam kasus kami, kami hampir selalu dapat menulis byte tambahan. Kita dapat membaca byte tambahan di buffer input selama byte tambahan terletak di dalamnya sepenuhnya. Dalam kondisi yang sama, kita dapat menulis byte tambahan ke buffer output - karena pada iterasi selanjutnya kita akan menimpanya.

Optimasi ini sudah dalam implementasi LZ4 asli:

  inline void copy8 (UInt8 * dst, const UInt8 * src)
 {
     memcpy (dst, src, 8);  /// Sebenarnya, memcpy tidak dipanggil di sini.
 }

 inline void wildCopy8 (UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
 {
     lakukan
     {
         copy8 (dst, src);
         dst + = 8;
         src + = 8;
     } while (dst <dst_end);
 }

Untuk memanfaatkan optimisasi ini, Anda hanya perlu memverifikasi bahwa kami cukup jauh dari batas buffer. Ini harus gratis, karena kami sudah memeriksa bahwa batas buffer terlampaui. Dan pemrosesan beberapa byte terakhir - "ekor" dari data - dapat dilakukan setelah loop utama.

Namun, masih ada beberapa kehalusan. Ada dua salinan dalam siklus - literal dan kecocokan. Tetapi ketika menggunakan fungsi LZ4_decompress_fast (bukan LZ4_decompress_safe), pemeriksaan dilakukan sekali - ketika kita perlu menyalin literal. Saat menyalin pertandingan, pemeriksaan tidak dilakukan, tetapi dalam spesifikasi format LZ4 ada beberapa kondisi yang memungkinkannya untuk dihindari:

5 byte terakhir selalu literal
Pertandingan terakhir harus dimulai setidaknya 12 byte sebelum akhir blok.
Akibatnya, sebuah blok dengan kurang dari 13 byte tidak dapat dikompres.

Data input yang dipilih secara khusus dapat menyebabkan drive memori. Jika Anda menggunakan fungsi LZ4_decompress_fast, Anda perlu perlindungan terhadap data yang buruk. Data yang dikompresi harus setidaknya merupakan jumlah pemeriksaan. Dan jika Anda membutuhkan perlindungan terhadap penyerang, maka gunakan fungsi LZ4_decompress_safe. Pilihan lain: mengambil fungsi hash kriptografi sebagai jumlah cek, tetapi hampir pasti akan membunuh semua kinerja; baik mengalokasikan lebih banyak memori untuk buffer; baik mengalokasikan memori untuk buffer dengan panggilan terpisah ke mmap dan membuat halaman penjaga.

Ketika saya melihat kode yang menyalin data 8 byte, saya langsung bertanya - mengapa tepatnya 8 byte? Anda dapat menyalin 16 byte menggunakan register SSE:

  inline void copy16 (UInt8 * dst, const UInt8 * src)
 {
 #jika __SSE2__
     _mm_storeu_si128 (reinterpret_cast <__ m128i *> (dst),
         _mm_loadu_si128 (reinterpret_cast <const __m128i *> (src)));
 #else
     memcpy (dst, src, 16);
 #endif
 }

 inline void wildCopy16 (UInt8 * dst, const UInt8 * src, UInt8 * dst_end)
 {
     lakukan
     {
         copy16 (dst, src);
         dst + = 16;
         src + = 16;
     } while (dst <dst_end);
 }

Menyalin 32 byte untuk AVX dan 64 byte untuk AVX-512 bekerja dengan cara yang sama. Selain itu, Anda dapat memperluas siklus beberapa kali. Jika Anda pernah melihat bagaimana memcpy diimplementasikan, maka inilah pendekatan yang tepat. (Omong-omong, kompiler dalam kasus ini tidak akan memperluas atau membuat vektor loop, ini akan membutuhkan penyisipan pemeriksaan rumit.)

Mengapa ini tidak dilakukan dalam implementasi LZ4 asli? Pertama, tidak jelas apakah ini lebih baik atau lebih buruk. Hasilnya tergantung pada ukuran fragmen yang perlu disalin. Tiba-tiba mereka semua pendek dan kerja ekstra akan sia-sia? Dan kedua, itu menghancurkan kondisi tersebut dalam format LZ4 yang memungkinkan Anda untuk menghindari brunch yang tidak perlu di loop dalam.

Namun demikian, kami akan tetap mengingat opsi ini untuk saat ini.

Salinan rumit


Kembali ke pertanyaan - apakah selalu mungkin untuk menyalin data dengan cara ini? Misalkan kita perlu menyalin kecocokan - yaitu, menyalin sepotong memori dari buffer output yang diimbangi di belakang kursor ke posisi kursor ini.

Bayangkan kasing sederhana - Anda perlu menyalin 5 byte pada offset 12:

Hello world ...........
^^^^^ - src
^^^^^ - dst

Hello world Hello wo ...
^^^^^ - src
^^^^^ - dst

Tetapi ada kasus yang lebih rumit - ketika kita perlu menyalin sepotong memori yang panjangnya lebih besar dari offset. Yaitu, sebagian mengindikasikan data yang belum ditulis ke buffer output.

Salin 10 byte pada offset 3:

abc .............
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

abc abcabcabca ...
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

Dalam proses kompresi, kami memiliki semua data, dan kecocokan tersebut dapat ditemukan. Fungsi memcpy tidak cocok untuk menyalinnya: ia tidak mendukung kasing ketika rentang fragmen memori berpotongan. By the way, fungsi memmove juga tidak cocok, karena fragmen memori dari mana untuk mendapatkan data belum sepenuhnya diinisialisasi. Anda perlu menyalin seolah-olah kami menyalin dengan byte.

  op [0] = cocok [0];
 op [1] = cocok [1];
 op [2] = cocok [2];
 op [3] = cocok [3];
 ...


Begini cara kerjanya:

a bc a ............
^ - src
^ - dst

a b ca b ...........
^ - src
^ - dst

ab c ab c ..........
^ - src
^ - dst

abc a bc a .........
^ - src
^ - dst

abca b ca b ........
^ - src
^ - dst

Artinya, kita harus membuat urutan yang berulang. Dalam implementasi LZ4 asli, kode yang sangat tidak dapat dimengerti ditulis untuk ini:

  const unsigned dec32table [] = {0, 1, 2, 1, 4, 4, 4, 4};
 dec64tabel kon int [] = {0, 0, 0, -1, 0, 1, 2, 3};

 const int dec64 = dec64table [offset];
 op [0] = cocok [0];
 op [1] = cocok [1];
 op [2] = cocok [2];
 op [3] = cocok [3];
 match + = dec32table [offset];
 memcpy (op + 4, match, 4);
 cocok - = dec64;

Kami menyalin 4 byte pertama byte-demi-bit, bergeser dengan beberapa angka ajaib, menyalin 4 byte berikutnya secara keseluruhan, menggeser pointer untuk mencocokkan dengan angka ajaib lainnya. Penulis kode ( Jan Collet ), untuk beberapa alasan konyol, lupa untuk meninggalkan komentar tentang apa artinya ini. Selain itu, nama variabel membingungkan. Keduanya disebut tabel dec ..., tetapi kami menambahkan satu dan mengurangi yang lain. Selain itu, yang lain tidak ditandatangani, dan yang lainnya adalah int. Namun, ada baiknya membayar upeti: baru-baru ini, penulis memperbaiki tempat ini dalam kode.

Begini cara kerjanya. Salin 4 byte pertama byte:

abc abca .........
^^^^ - src
^^^^ - dst

Sekarang Anda dapat menyalin 4 byte sekaligus:

abcabca bcab .....
^^^^ - src
^^^^ - dst

Anda dapat melanjutkan seperti biasa dengan menyalin 8 byte sekaligus:

abcabcabcab cabcabca .....
^^^^^^^^ - src
^^^^^^^^ - dst

, — . :

 inline void copyOverlap8(UInt8 * op, const UInt8 *& match, const size_t offset)
{
    /// 4 % n.
    /// Or if 4 % n is zero, we use n.
    /// It gives equivalent result, but is better CPU friendly for unknown reason.
    static constexpr int shift1[] = { 0, 1, 2, 1, 4, 4, 4, 4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[] = { 0, 0, 0, 1, 0, -1, -2, -3 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
}

, , . , , — 16 .

« » , ( offset < 16 , offset < 8 ). () 16- :

 inline void copyOverlap16(UInt8 * op, const UInt8 *& match, const size_t offset)
{
    /// 4 % n.
    static constexpr int shift1[]
        = { 0, 1, 2, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[]
        = { 0, 0, 0, 1, 0, -1, -2, -3, -4, 4, 4, 4, 4, 4, 4, 4 };

    /// 16 % n - 8 % n
    static constexpr int shift3[]
        = { 0, 0, 0, -1, 0, -2, 2, 1, 8, -1, -2, -3, -4, -5, -6, -7 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
    memcpy(op + 8, match, 8);
    match += shift3[offset];
}

? , SIMD-, 16 , ( 1 15). , , .

— pshufb ( packed shuffle bytes) SSSE3 ( S). 16- . . — «»: 0 15 — , . , 127 — .

Berikut ini sebuah contoh:

 xmm0: abc.............
xmm1: 0120120120120120

pshufb %xmm1, %xmm0

xmm0: abcabcabcabcabca

— ! :

 inline void copyOverlap16Shuffle(UInt8 * op, const UInt8 *& match, const size_t offset)
{
#ifdef __SSSE3__

    static constexpr UInt8 __attribute__((__aligned__(16))) masks[] =
    {
        0, 1, 2, 1, 4, 1, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, /* offset = 0, not used as mask, but for shift amount instead */
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* offset = 1 */
        0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
        0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,
        0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,
        0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1,
        0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 1,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0,
    };

    _mm_storeu_si128(reinterpret_cast<__m128i *>(op),
        _mm_shuffle_epi8(
            _mm_loadu_si128(reinterpret_cast<const __m128i *>(match)),
            _mm_load_si128(reinterpret_cast<const __m128i *>(masks) + offset)));

    match += masks[offset];

#else
    copyOverlap16(op, match, offset);
#endif
}

_mm_shuffle_epi8 — intrinsic , pshufb .

, ? SSSE3 — , 2006 . AVX2 , 32 , 16- . packed shuffle bytes, vector permute bytes — , . AVX-512 VBMI , 64 , . ARM NEON — vtbl (vector table lookup), 8 .

, pshufb 64- MMX-, 8 . . , , 16 ( ).

Highload++ Siberia , 8 ( ) — !

if


, , 16 . ?

, . , , , . , .

, . , , , 65 536 . 65 536 . , , 65 551 . , , 96 128 — . , «» mmap ( madvice). - page faults. , .

?


, , :

  1. 16 8.
  2. shuffle- offset < 16 .
  3. if.

.

Contoh 1:
Xeon E2650v2, ., AppVersion.
reference: 1.67 GB/sec.
16 bytes, shuffle: 2.94 GB/sec ( 76% ).

Contoh 2:
Xeon E2650v2, ., ShowsSumPosition.
reference: 2.30 GB/sec.
16 bytes, shuffle: 1.91 GB/sec ( 20% ).

, . , . - , . , . — 16 . : , , .

, C++ : 8- 16- ; shuffle-.

 template <size_t copy_amount, bool use_shuffle>
void NO_INLINE decompressImpl(
     const char * const source,
     char * const dest,
     size_t dest_size)

, shuffle . , :

 sudo echo 'performance' | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
kill -STOP $(pidof firefox) $(pidof chromium)

«» (c Xeon E5645), , . , , . , shuffle-, , 16- .

:

 sudo kill -STOP $(pidof python) $(pidof perl) $(pgrep -u skynet) $(pidof cqudp-client)

. thermal throttling power capping.


, , . , , . . , , . : ClickHouse , , . , ( — ?). .

, , . « » . , , , .

, . . - . — ClickHouse 64 . ( .)

, « », , . , , , - . . , , . .

, , . «» , . , . Thompson Sampling.

, , . — : , . . , . , C++. — , - , ; .

? , . . -, , . -, , , «» .

, , Thompson Sampling — ( , ). , , - , , . , .

, «» . , , «», . — . , , .

, , , , «»:

 /// For better convergence, we don't use proper estimate of stddev.
/// We want to eventually separate between two algorithms even in case
/// when there is no statistical significant difference between them.
double sigma() const
{
    return mean() / sqrt(adjustedCount());
}

double sample(pcg64 & rng) const
{
     ...
    return std::normal_distribution<>(mean(), sigma())(rng);
}

, — memory latencies.

, , — LZ4 .

, :
— reference (baseline): LZ4 ;
— variant 0: 8 , shuffle;
— variant 1: 8 , shuffle;
— variant 2: 16 , shuffle;
— variant 3: 16 , shuffle;
— «» , .

CPU


CPU, , . , CPU ?

ClickHouse , 256 100 ( 256 ). , CPU , . CPU:
— Intel® Xeon® CPU E5-2650 v2 @ 2.60GHz
— Intel® Xeon® CPU E5-2660 v4 @ 2.00GHz
— Intel® Xeon® CPU E5-2660 0 @ 2.20GHz
— Intel® Xeon® CPU E5645 @ 2.40GHz
— Intel Xeon E312xx (Sandy Bridge)
— AMD Opteron(TM) Processor 6274
— AMD Opteron(tm) Processor 6380
— Intel® Xeon® CPU E5-2683 v4 @ 2.10GHz
— Intel® Xeon® CPU E5530 @ 2.40GHz
— Intel® Xeon® CPU E5440 @ 2.83GHz
— Intel® Xeon® CPU E5-2667 v2 @ 3.30GHz

— , R&D:
— AMD EPYC 7351 16-Core Processor — AMD.
— Cavium ThunderX2 — x86, AArch64. SIMD- . 224 56 .

13 , 256 6 (reference, 0, 1, 2, 3, adaptive), 10 , . 199 680 , .

, CPU . : LZ4 ( — ). , Cavium . ClickHouse, «» Xeon E5-2650 v2 , , ClickHouse x86.

 ┌─cpu───────────────────┬──ref─┬─adapt─┬──max─┬─best─┬─adapt_boost─┬─max_boost─┬─adapt_over_max─┐
│ E5-2667 v2 @ 3.30GHz │ 2.81 │ 3.19 │ 3.15 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2650 v2 @ 2.60GHz │ 2.5 │ 2.84 │ 2.81 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2683 v4 @ 2.10GHz │ 2.26 │ 2.63 │ 2.59 │ 3 │ 1.16 │ 1.15 │ 1.02 │
│ E5-2660 v4 @ 2.00GHz │ 2.15 │ 2.49 │ 2.46 │ 3 │ 1.16 │ 1.14 │ 1.01 │
│ AMD EPYC 7351 │ 2.03 │ 2.44 │ 2.35 │ 3 │ 1.20 │ 1.16 │ 1.04 │
│ E5-2660 0 @ 2.20GHz │ 2.13 │ 2.39 │ 2.37 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E312xx (Sandy Bridge) │ 1.97 │ 2.2 │ 2.18 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E5530 @ 2.40GHz │ 1.65 │ 1.93 │ 1.94 │ 3 │ 1.17 │ 1.18 │ 0.99 │
│ E5645 @ 2.40GHz │ 1.65 │ 1.92 │ 1.94 │ 3 │ 1.16 │ 1.18 │ 0.99 │
│ AMD Opteron 6380 │ 1.47 │ 1.58 │ 1.56 │ 1 │ 1.07 │ 1.06 │ 1.01 │
│ AMD Opteron 6274 │ 1.15 │ 1.35 │ 1.35 │ 1 │ 1.17 │ 1.17 │ 1 │
│ E5440 @ 2.83GHz │ 1.35 │ 1.33 │ 1.42 │ 1 │ 0.99 │ 1.05 │ 0.94 │
│ Cavium ThunderX2 │ 0.84 │ 0.87 │ 0.87 │ 0 │ 1.04 │ 1.04 │ 1 │
└───────────────────────┴──────┴───────┴──────┴──────┴─────────────┴───────────┴────────────────┘

ref, adapt, max — (, ). best — , 0 3. adapt_boost — baseline. max_boost — baseline. adapt_over_max — .

, x86 12–20%. ARM 4%, , . , «» Intel.

Kesimpulan


. , LZ4 12–20%, . . , .

, , «» , ZStandard level 1 LZ4: IO .

— , . , .

: . LZ4 , Lizard, Density LZSSE , . , LZ4 LZSSE ClickHouse.

LZ4 : . : , . . , inc- dec- . , 12–15% 32 , 16, . 32 — , .

, , page cache userspace ( mmap, O_DIRECT userspace page cache — ), - ( CityHash128 CRC32-C, HighwayHash, FARSH XXH3). , .

, master, . HighLoad++ Siberia, .

Source: https://habr.com/ru/post/id452778/

More articles:


All Articles