Karakter harus dikodekan menjadi bit dengan cara tertentu. Sebagian besar string di Internet, termasuk postingan di Habré ini, dikodekan dalam UTF-8. Format UTF-8 mewakili "karakter" dalam satu, dua, tiga, atau empat byte. Ini adalah generalisasi untuk standar ASCII, yang hanya menggunakan satu byte per karakter. Artinya, string ASCII juga merupakan string UTF-8.
Ini sebenarnya sedikit lebih rumit, karena secara teknis UTF-8 mendeskripsikan poin kode. Karakter yang terlihat seperti emoji dapat terdiri dari beberapa titik kode ... tetapi sebagian besar pemrogram tidak memerlukan kata-kata yang berlebihan ini.
Ada standar lain juga. Beberapa bahasa pemrograman lama seperti C # dan Java mengandalkan UTF-16. Ini menggunakan dua atau empat byte per karakter. Sepertinya ide yang bagus pada saat itu, tetapi sekarang konsensus bergerak menuju penggunaan UTF-8 kapan saja, di mana saja.
Kebanyakan encoding memiliki batasan yang dapat diberlakukan. Dengan kata lain, tidak setiap urutan bit acak bisa masuk ke UTF-8. Jadi, Anda perlu memvalidasi string - periksa apakah itu benar-benar UTF-8.
Apa bedanya? Bagus. Misalnya, server web Microsoft memiliki kerentanan seperti itu: ia menerima URI yang tampaknya valid dan aman, tetapi setelah diinterpretasikan oleh server, ia memberi penyerang akses jarak jauh ke disk. Bahkan mengesampingkan masalah keamanan, Anda hampir pasti tidak ingin menyimpan baris yang tidak valid di database Anda.
Dengan demikian, bahasa pemrograman, server web, browser, dan mesin database terus-menerus memvalidasi UTF-8.
Jika string Anda sebagian besar hanya ASCII, maka pemeriksaannya cukup cepat dan pemeriksaan UTF-8 tidak menjadi masalah. Lewatlah sudah hari-hari ketika sebagian besar string dikodekan ASCII. Kita hidup di dunia emoji dan banyak huruf nasional.
Di tahun 2018 lalu, saya bertanya pada diri sendiri:Seberapa cepat string UTF-8 dapat divalidasi ? Saat itu, saya menemukan opsi validasi dengan beberapa siklus CPU per simbol. Seseorang dapat menenangkan diri dalam hal ini, tetapi jawaban ini tidak memuaskan saya.
Pengerjaannya memakan waktu bertahun-tahun, tetapi tampaknya sekarang kami mendapatkan versi yang mendekati ideal. Algoritme baru adalah urutan besarnya lebih cepat daripada opsi pencarian cepat lainnya. Kami telah menyiapkan kertas putih: "Validasi UTF-8 dalam Kurang dari Satu Instruksi Per Byte" (akan diterbitkan dalam Perangkat Lunak: Praktik dan Pengalaman ), dan juga menerbitkan utilitas pembandingan .
Semua detail dijelaskan dalam artikel ilmiah, jadi kami tidak akan membahas detailnya di sini, tetapi hanya mempertimbangkan secara singkat esensinya. Bagian utama dari validasi UTF-8 dilakukan dengan mencari pasangan byte yang berurutan. Setelah memeriksa semua pasangan byte dan mengidentifikasi kemungkinan pelanggaran yang dapat ditemukan dari informasi ini, relatif sedikit yang harus dilakukan.
Semua prosesor memiliki instruksi SIMD cepat. Mereka bekerja dengan register lebar (128 bit, 256 bit, dll.). Kebanyakan set memiliki instruksi "vectorized lookup" yang mengambil, katakanlah, nilai 16-byte (berkisar dari 0 hingga 16) dan mencarinya dalam tabel 16-byte. Di prosesor Intel dan AMD, deskripsi ini sesuai dengan instruksi
pshufb... Nilai antara 0 dan 16 terkadang disebut nibble dan mencakup 4 bit. Byte terdiri dari dua nibble (rendah dan tinggi).
Dalam algoritme pencarian kami, instruksi pencarian vektorisasi dipanggil tiga kali: sekali untuk nibble rendah, sekali untuk nibble tinggi, dan sekali untuk nibble tinggi untuk byte berikutnya. Kami memiliki tiga tabel lookup 16-byte yang sesuai. Jika dipilih dengan benar, bitwise AND dari tiga pencarian akan menemukan kesalahan.
Lihat artikel ilmiah untuk lebih jelasnya , tetapi pada akhirnya validasi UTF-8 yang hampir lengkap dilakukan hanya dengan lima baris kode C ++ cepat tanpa cabang apa pun ... dan kelima baris tersebut memeriksa blok hingga 32 byte sekaligus ...
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}Meskipun tidak segera terlihat, validasi ini cukup dan 100% aman. Sungguh . Hanya ada beberapa langkah teknis tambahan yang tidak mahal yang tersisa.
Akibatnya, pada prosesor Intel / AMD terbaru, dibutuhkan kurang dari satu instruksi per byte untuk memeriksa data input acak yang paling sampah sekalipun. Karena kodenya sangat dioptimalkan, Anda dapat naik hingga tiga instruksi per siklus, dan bahkan lebih. Artinya, kami menggunakan sebagian kecil dari siklus (kurang dari sepertiga) per byte input pada CPU modern. Dengan demikian, kecepatan pemrosesan dipertahankan secara andal pada lebih dari 12 GB / dtk.
Pelajarannya adalah bahwa tabel pemeta biasa berguna, tetapi tabel vektorisasi adalah blok bangunan fundamental untuk algoritme kecepatan tinggi.
Jika Anda perlu menggunakan fitur validasi UTF-8 cepat dalam produksi, kami merekomendasikan library simdjson (versi 0.5 atau lebih tinggi). Ini telah diuji dengan baik dan memiliki fitur built-in yang berguna seperti pengiriman runtime. Meskipun pustaka dirancang untuk mengurai JSON, Anda dapat menggunakannya murni untuk validasi UTF-8, meskipun tidak ada JSON sama sekali. Ini mendukung prosesor ARM 64-bit dan x64, dan juga memiliki pemrosesan cadangan untuk CPU lain. Kami mengemasnya menjadi satu file header bersama dengan satu file sumber; jadi Anda bisa memasukkannya ke dalam proyek C ++ Anda.
Pekerjaan sebelumnya... Keunggulan utama dalam mempopulerkan metode klasifikasi vektor, yang merupakan kunci dari algoritma pencarian, adalah milik Mula. Sejauh yang saya tahu, Keizer adalah orang pertama yang mengusulkan strategi pencarian rangkap tiga kami. Algoritma validasi UTF-8 berbasis SIMD praktis pertama dibuat oleh K. Willets. Beberapa orang, termasuk Z. Wegner, melakukan perbaikan di dalamnya. Travis Downs muncul dengan ide-ide cerdas tentang cara mempercepat algoritme konvensional.
Bacaan lebih lanjut . Jika Anda menikmati pekerjaan ini, Anda mungkin menyukai artikel lain tentang topik terkait: "Encoding dan Decoding Base64 dengan Kecepatan Hampir Menyalin-dalam-Memori" (Software: Practice and Experience, 50 (2), 2020) dan "Parsing Gigabytes of JSON Per Second" ( VLDB Journal, 28 (6), 2019).