Algoritme Pencarian Substring yang Cocok untuk SIMD (2018)

• API seperti strstr dan std::string::find mengasumsikan pencarian substring sekali jalan, tetapi pada CPU modern biaya perbandingan string pendek dan vektor rendah, sehingga pendekatan SIMD bisa menguntungkan
• Ide intinya adalah mengganti kondisi hash lemah Karp-Rabin dengan predikat vektor, lalu melakukan perbandingan substring yang presisi hanya pada posisi kandidat
• Algoritme SIMD generik mengurangi kandidat dengan membandingkan karakter pertama dan karakter terakhir needle secara paralel, lalu memverifikasi hanya posisi yang mungkin cocok dengan memcmp
• Pendekatan SSE4.1 MPSADBW dan SSE4.2 PCMPESTRM juga dibandingkan, tetapi hasil pengukuran menunjukkan SIMD generik lebih stabil dan cepat, sementara PCMPESTRM cenderung lebih lambat bahkan dibanding MPSADBW
• SIMD generik lebih cepat daripada C strstr di semua platform, tetapi karena dapat membaca di luar string input, ia tidak aman, dan kondisi perbandingannya juga tidak sepenuhnya sama karena menerima informasi panjang lebih dulu

---

Asumsi biaya yang berubah dalam pencarian string

• API seperti strstr di C, std::string::find di C++, serta pos dan index pada string Python dirancang untuk pencarian sekali jalan atas substring dalam string yang diberikan
• Algoritme lama secara garis besar terbagi menjadi dua kelompok
  • Pendekatan berbasis deterministic finite automata seperti Knuth-Morris-Pratt dan Boyer Moore
  • Pendekatan berbasis perbandingan sederhana seperti Karp-Rabin
• Algoritme standar mengasumsikan bahwa membandingkan sepasang karakter, melihat tabel bantu, dan percabangan bersyarat itu murah, sedangkan membandingkan dua substring itu mahal
• Pada CPU desktop modern, asumsi ini mungkin tidak lagi sesuai
  • Pada CPU 64-bit, tidak ada perbedaan biaya untuk perbandingan 1, 2, 4, dan 8 byte
  • Jika mendukung instruksi SIMD, perbandingan vektor 16, 32, atau 64 byte bisa sama murahnya dengan perbandingan satu byte
  • Lookup tabel memerlukan biaya akses memori setingkat perjalanan pulang-pergi cache L1, dan pembacaan per karakter juga memiliki biaya serupa
  • Branch yang salah diprediksi dapat menimbulkan penalti sekitar 10–20 siklus
  • Rantai dependensi pendek dari membaca karakter, membandingkan, hingga percabangan bersyarat menyulitkan pemanfaatan eksekusi out-of-order CPU

Pendekatan: menggunakan predikat vektor sebagai pengganti hash lemah

• Karp-Rabin melakukan perbandingan presisi hanya ketika hash lemah substring target pencarian sama dengan hash segmen string saat ini
• Pendekatan SIMD mengganti kondisi hash ini dengan predikat vektor
  • Predikat dihitung secara paralel
  • Perbandingan substring yang presisi dilakukan hanya untuk setiap posisi yang bernilai benar dalam vektor predikat
• Spesialisasi berdasarkan panjang juga digunakan untuk meningkatkan performa
  • Implementasi umum memanggil fungsi seperti memcmp untuk perbandingan substring
  • Jika panjang substring yang dicari diketahui, pemanggilan fungsi dapat diganti dengan beberapa instruksi CPU yang disesuaikan dengan panjang tertentu, atau dalam beberapa kasus satu instruksi saja
  • Cara ini mengurangi biaya pemanggilan fungsi dan biaya internal memcmp

Algoritme 1: SIMD generik

• Algoritme SIMD generik dapat diterapkan pada berbagai set instruksi SIMD dan pendekatan SWAR
• Predikat dasarnya adalah memeriksa apakah karakter pertama dan karakter terakhir needle sama-sama cocok
  • Isi register F dengan karakter pertama
  • Isi register L dengan karakter terakhir
  • Pada setiap iterasi, baca chunk A dari offset haystack saat ini i, dan baca chunk B dari i + k - 1
  • Hitung F == A dan B == L, lalu gabungkan kedua hasilnya untuk membuat mask posisi kandidat
  • Perbandingan substring yang presisi dilakukan hanya pada posisi yang benar di mask
• Dalam contoh mencari "cat" pada "a_cat_tries", satu-satunya posisi tempat karakter pertama c dan karakter terakhir t sama-sama cocok adalah indeks 2, sehingga perbandingan presisi juga hanya dilakukan sekali
• Memilih karakter pertama dan terakhir tidak selalu baik
  • Jika string input sebagian besar berisi 'A' dan needle adalah "AjohndoeA", banyak kandidat dapat muncul
  • Implementasi dapat memilih karakter terjauh yang berbeda dari karakter pertama sebagai pengganti karakter terakhir
  • Jika semua karakter dalam needle sama, prosedur khusus untuk pola seperti "AAAAA" dapat digunakan

Perbedaan antarimplementasi

• Implementasi SSE dan AVX2 memiliki struktur yang hampir sama dan menggunakan jumlah instruksi minimum
  • Karena sudah diketahui bahwa karakter pertama dan terakhir cocok, memcmp tidak perlu membandingkan lagi karakter-karakter ini
• Pendekatan SWAR memanfaatkan fakta bahwa byte sama jika hasil XOR adalah 0
  • Alih-alih melakukan AND pada hasil parsial seperti SSE/AVX2, pendekatan ini menggunakan OR
  • Proses menemukan posisi byte 0 memerlukan lebih banyak pekerjaan
  • Implementasi C++ untuk vektor 64-bit menghitung mask byte yang presisi
• AVX512F tidak memiliki operasi byte dan item vektor terkecilnya adalah word 32-bit, sehingga diperlukan teknik SWAR
  • Dua XOR dan satu OR dihitung dengan instruksi AVX512F
  • Elemen 32-bit yang mengandung byte 0 dicari
  • Untuk setiap elemen 32-bit tersebut, 4 kandidat substring diperiksa
• Implementasi ARM Neon 32-bit menggunakan register SIMD 128-bit
  • Perjalanan pulang-pergi yang panjang dari unit Neon kembali ke CPU menjadi bottleneck
  • Hasil perbandingan disimpan ke memori sebagai word 64-bit untuk diproses
  • Meng-unroll 2 loop internal membuatnya sekitar 1,2 kali lebih cepat
• Implementasi AArch64 hampir sama dengan prosedur ARM Neon, tetapi operasi membaca lane register SIMD secara langsung lebih cepat

Algoritme 2: SSE4.1 MPSADBW

• MPSADBW pada SSE4.1 dan AVX2 menghitung Manhattan distance antara subvektor 4 byte dari satu register dan 8 subvektor 4 byte berurutan dari register lain
• Jika dua subvektor sama, jarak L1 menjadi 0, sehingga ini digunakan untuk mencari posisi kandidat
  • Pendekatan ini menggunakan kesamaan 4 karakter pertama sebagai predikat
• Karena membandingkan 4 karakter pertama, tampaknya lebih kuat daripada perbandingan karakter pertama dan terakhir, tetapi dalam kasus terburuk tidak dapat menghindari kompleksitas kuadratik
  • Jika haystack penuh dengan "a" dan needle adalah "aaaabcde", predikat akan benar untuk setiap karakter input
• Pendekatan MPSADBW memiliki beberapa batasan
  • Pada dasarnya tidak cocok untuk substring dengan panjang kurang dari 4
  • Penanganan panjang 3 dimungkinkan, tetapi membutuhkan kode tambahan
  • SSE MPSADBW hanya memproses 8 byte dalam satu waktu
  • AVX2 MPSADBW bekerja per lane 128-bit, bukan pada keseluruhan 256-bit, sehingga memerlukan kode loading tambahan
  • Latency instruksinya tinggi, 5–7 siklus tergantung CPU, tetapi throughput-nya 1–2 siklus sehingga latency dapat disembunyikan dengan loop unrolling
• AVX512F tidak memiliki MPSADBW, tetapi karena elemen 32-bit didukung secara native, predikat kesamaan prefix 4 byte dapat ditiru
  • Pada setiap iterasi, dibuat 4 vektor AVX512 yang berisi prefix 4 byte yang mungkin
  • Penyusunan setiap vektor memerlukan 2 shift dan 1 OR
  • Loop perbandingan menjadi rumit, dan untuk mengisi elemen terakhir diperlukan 4 byte di luar vektor

Algoritme 3: SSE4.2 PCMPESTRM

• SSE4.2 memperkenalkan set instruksi STNI yang ditujukan sebagai building block untuk operasi string
• Intel pada dasarnya menghentikan STNI pada prosesor-prosesor berikutnya dan tidak memperkenalkan versi AVX2, sementara instruksi-instruksi ini sangat lambat
  • Latency 11 siklus dinilai sulit diterima
• Instruksi PCMPxSTRx memiliki empat varian bergantung pada cara menentukan panjang string dan cara menyimpan hasil
  • Panjang dapat diberikan secara eksplisit, atau byte 0 pertama dapat dianggap sebagai akhir seperti string C tradisional
  • Hasil dapat disimpan sebagai mask bit/byte atau sebagai nomor bit pertama/terakhir yang disetel dalam mask
• Di sini digunakan mode perbandingan range ordered
  • Meski namanya demikian, mode ini mencari substring atau prefix-nya jika melampaui lebar register
  • Dalam contoh mencari "ABCD" pada "ABCD_ABC_ABCD_AB", suffix "AB" juga dapat diperlakukan sebagai kecocokan
  • Karena itu, yang dapat diasumsikan dengan aman hanyalah kecocokan karakter pertama, sedangkan sisanya harus diperiksa dengan memcmp

Lingkungan pengukuran performa

• Performa beberapa implementasi SIMD diukur, termasuk spesialisasi runtime untuk substring pendek
• C strstr disertakan sebagai pembanding, tetapi karena bug performa std::string::find pada GNU libc, ia dikecualikan dari tabel x64
• Pengujian menjalankan setiap program tiga kali
• Lingkungan pengujian x64
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• Lingkungan pengujian ARM
  • ARMv7 Raspberry Pi 3, kode 32-bit, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, kode 64-bit, Clang 3.8.0

Hasil x64

• Implementasi SIMD umum menunjukkan peningkatan kecepatan terbesar dibanding strstr pada x64
  • Di Westmere, SSE2 generic mencatat 0,74589 detik, sedangkan strstr 0,82246 detik
  • Di Haswell, AVX2 generic mencatat 0,38653 detik, sedangkan strstr 0,52786 detik
  • Di Skylake, AVX2 generic mencatat 0,36309 detik, sedangkan strstr 0,66148 detik
  • Di KNL, AVX512F generic mencatat 1,14057 detik, sedangkan strstr 4,94606 detik
• Peningkatan kecepatan maksimum adalah 1,10 kali di Westmere, 1,37 kali di Haswell, 1,82 kali di Skylake, dan 4,33 kali di KNL
• Performa strstr pada Bulldozer adalah 9,37792 detik, sangat buruk sehingga sulit digunakan sebagai patokan
• Pendekatan MPSADBW secara umum kurang baik kecuali di Skylake, dan sangat buruk di KNL
• Pendekatan PCMPESTRM menunjukkan hasil yang lebih lambat daripada MPSADBW

Hasil ARM

• Di ARMv7, std::strstr mencatat 7,30405 detik, sedangkan std::string::find 4,17131 detik
• Di ARMv7, ARM Neon 32-bit generic mencatat 1,29861 detik, hingga 3,1 kali lebih cepat dibanding std::string::find
• Di ARMv8, std::strstr mencatat 3,37546 detik, sedangkan std::string::find 1,81368 detik
• Di ARMv8, AArch64 64-bit generic mencatat 0,27897 detik, hingga 6,5 kali lebih cepat dibanding std::string::find
• Di ARMv8, SWAR 64-bit generic mencatat 0,46269 detik, dengan performa yang mendekati prosedur SIMD 32-bit

Kesimpulan dan batasan

• Algoritme SIMD umum lebih cepat daripada C strstr di semua platform
• Implementasi sebaiknya memilih versi SIMD tertinggi yang tersedia pada CPU tertentu
• MPSADBW tidak berkinerja baik kecuali pengecualian di Skylake, dan sangat buruk di Knights Landing
• PCMPESTRM berkinerja lebih rendah daripada MPSADBW
• Performa ARM Neon baik, termasuk implementasi SWAR
  • Versi SWAR 1,7 kali lebih cepat daripada string::find
  • Versi SIMD 3,1 kali lebih cepat daripada string::find
• Perbandingan dengan strstr mungkin tidak sepenuhnya adil
  • strstr memproses string tanpa mengetahui panjangnya
  • Implementasi ini menerima panjang sebagai argumen dan memanfaatkannya
• Implementasinya tidak aman
  • Dapat membaca data di luar string input
  • Jika string berada tepat sebelum memori yang tidak dipetakan, pelanggaran akses dapat terjadi
  • Address sanitizer juga dapat melaporkan masalah
  • Membuatnya aman itu mungkin, tetapi bukan tujuan pekerjaan ini
• Semua implementasi dan program pengujian tersedia di GitHub