Algoritme pencarian substring yang cocok untuk SIMD (2018)

• Membahas algoritme pencarian substring yang ramah SIMD
• Menyajikan pendekatan teknis untuk pencarian string cepat
• Mengarah pada peningkatan efisiensi dibanding metode lama dengan memanfaatkan pemrosesan paralel
• Disorot sebagai tip performa yang berguna bagi pengembang dan profesional TI
• Algoritme tersebut berkaitan dengan optimisasi perangkat keras modern

---

Gambaran umum

• Dokumen ini memperkenalkan algoritme pencarian substring yang dioptimalkan untuk himpunan instruksi SIMD (Single Instruction, Multiple Data)
• Dalam lingkungan TI saat ini, ketika kecepatan pemrosesan string menjadi semakin penting, dokumen ini membahas metode pemrosesan paralel untuk melengkapi keterbatasan pendekatan pencarian sekuensial yang ada
• Dengan memanfaatkan SIMD, beberapa data dapat dibandingkan secara bersamaan dalam satu waktu, sehingga dapat diharapkan efek peningkatan performa yang signifikan dalam pencarian string berukuran besar

Poin utama

• Algoritme SIMD membagi string masukan menjadi beberapa bagian, lalu membandingkan beberapa byte sekaligus dengan instruksi yang sama
• Melalui pendekatan ini, pencarian yang lebih cepat dan efisien dimungkinkan dibanding perbandingan berbasis perulangan yang ada
• Ini digunakan secara efektif terutama di bidang yang membutuhkan pemrosesan data berkecepatan tinggi dalam volume besar, seperti pencarian teks, analisis log, dan DNA sequencing

Manfaat bagi pengembang dan insinyur

• Dengan menerapkan algoritme yang ramah SIMD, dimungkinkan untuk memaksimalkan potensi CPU modern hanya dengan perubahan kode yang minimal
• Memberikan keunggulan dari sisi kecepatan dan efisiensi dibanding logika pencarian yang ada
• Skalabilitas performa di lingkungan multi-core juga sangat baik

Kesimpulan

• Di bidang layanan TI, analisis data, dan mesin pencari real-time yang sangat bergantung pada performa pencarian substring, penerapan algoritme berbasis SIMD dapat menghasilkan peningkatan performa yang nyata
• Ini merupakan strategi optimisasi yang esensial untuk memanfaatkan lingkungan perangkat keras terbaru

[GN⁺]

Komentar Hacker News

• Dijelaskan bahwa metode akselerasi ripgrep adalah pendekatan AVX2 (generik) yang memanfaatkan crate Rust regex. Misalnya, untuk regex seperti \w+\s+Sherlock\s+\w+, ditekankan bahwa pencarian cepat tetap bisa dilakukan dengan mengekstrak Sherlock saja. Implementasi nyatanya bisa dilihat di sini. Disebutkan bahwa perbedaan utama dengan algoritme dalam artikel ini adalah penggunaan heuristik yang mengoptimalkan pencarian berdasarkan 2 byte yang lebih jarang muncul dengan memanfaatkan distribusi latar, alih-alih byte pertama/terakhir dari needle. Hasil benchmark juga menunjukkan performa yang jauh lebih cepat dibanding pendekatan Two-Way sederhana atau memmem GNU libc. Pada benchmark prebuilt, juga ditekankan adanya keterbatasan API karena rutin jenis memmem harus berulang kali membangun ulang state setiap kali needle tetap ditetapkan, sehingga efisiensinya menurun

  • Ada yang mempertanyakan bagaimana distribusi latar byte itu diketahui, dan apakah harus memindai distribusi tersebut satu per satu dari haystack justru akan berdampak buruk pada performa

• Berbagi pengalaman saat mencoba optimasi SIMD pada Wasm/WASI libc dan mengimplementasikan algoritme pencarian string semacam ini. Menurutnya, bila panjang haystack sudah diketahui dan needle cukup besar, menggabungkannya dengan Quick Search akan berguna. Ia juga membagikan kode terkait dan tautan penjelasan algoritme

• Dibagikan juga bahwa di C#, SIMD diterapkan pada IndexOf, dan detailnya bisa dilihat di sini

• Ada juga yang memperkenalkan pengalaman pribadi menerapkan pendekatan SMID untuk pencarian string dan split, dengan mengimplementasikan sendiri berbagai algoritme. Ia membuka source conversion.cxx milik tamgu. Ia menjelaskan bahwa algoritme yang dipakainya berbeda lagi dari yang disebut di artikel utama

  • Ada permintaan agar algoritmenya diringkas secara singkat. Sebagai contoh, dijelaskan bahwa algoritme nomor 1 di artikel asli membandingkan karakter pertama/terakhir, sedangkan algoritme nomor 2 membandingkan 4 karakter awal sekaligus sambil memeriksa banyak posisi kandidat

  • Ada yang berbagi pengalaman beberapa tahun lalu mencoba mengimplementasikan versi yang dimodifikasi untuk pencarian window LZ77 menggunakan generic SIMD milik Zig. Detail terkait bisa dilihat di sini

• Ada komentar bahwa ini mengingatkannya pada proyek hparse yang memakai algoritme SIMD untuk parsing HTTP cepat

• Disebutkan bahwa algoritme swar menimbulkan UB (undefined behavior) karena melakukan cast data yang disejajarkan 1 byte menjadi unit 8 byte. Ada juga catatan bahwa unaligned load bisa memunculkan isu performa

  • Menurut salah satu komentar, kode seperti ini sering dianggap sebagai algoritme ideal atau pseudocode demi keterbacaan. Ia juga menunjukkan bahwa kode tersebut tidak memakai mempcy dan pemeriksaan batasnya pun tidak akurat. Misalnya, ia mengasumsikan panjang haystack kelipatan 8, atau bila needle kosong maka unsigned integer overflow dapat menyebabkan out-of-bounds, sehingga total ada tiga UB. Ia juga berbagi pengalaman bahwa dalam banyak kode demo SIMD, yang sering ditampilkan memang hanya cara pemanfaatan vektornya yang menarik, sementara kondisi batas dihilangkan

• Bahwa strstr di libc lambat memang sudah dikenal, tetapi ditekankan bahwa musl cepat dan memakai algoritme modern. Tinggal diberi nama saja lalu bisa dimasukkan ke smart shootout. Ada rasa penasaran bagaimana hasilnya jika dibandingkan dengan algoritme SIMD terbaik

  • Sebagai benchmark referensi, dibagikan hasil perbandingan antara Two-Way milik musl dan algoritme libc dengan optimasi SIMD yang ia bagikan. Metode benchmark didasarkan pada kode terkait. Peningkatan dari pemanfaatan SIMD bisa dilihat di tabel ini. Ia menilai hasilnya bukan luar biasa, tetapi cukup bagus. Musl lebih terspesialisasi untuk string panjang tetap (memmem), sementara ia di lingkungan Wasm bisa lebih bebas mencoba berbagai optimasi untuk string panjang tak diketahui (strstr). String yang diakhiri NUL membuat banyak algoritme bagus mengalami kesulitan

  • Ia berharap lebih banyak algoritme SIMD dimasukkan ke smart, dan kalau ada waktu ingin mencoba bereksperimen sendiri

• Ada pertanyaan apakah versi 2018 tidak dimasukkan dalam perbandingan SIMD pencarian string

• Ada pertanyaan tentang batas ukuran string di mana pendekatan SIMD benar-benar efisien. Ditekankan bahwa pada string kecil, overhead penyiapan SIMD (alignment, perhitungan panjang, dan sebagainya) justru bisa membuatnya lebih lambat daripada pencarian berbasis byte yang sederhana. Ini juga bisa sangat berbeda tergantung arsitektur hardware

  • Berdasarkan pengalamannya justru kebalikannya. Algoritme seperti ini hampir seperti brute force dan nyaris tanpa setup yang tidak perlu, sehingga pada needle yang panjang dan repetitif kompleksitas waktunya memburuk. Sebaliknya, algoritme pencarian string yang lebih canggih—yang mencegah masalah quadratic atau mencapai performa sublinear—memerlukan setup berbiaya tinggi karena harus menelusuri struktur needle lebih dalam

• Ada harapan bahwa di Python kita bisa memakai SIMD secara langsung tanpa memanggil bahasa lain

  • Seseorang menyebut blog Austin dan kumpulan tulisannya (story on vowels detection tautan), lalu bertanya lebih spesifik apa yang dimaksud dengan “memakai SIMD langsung tanpa memanggil bahasa lain”. Secara teknis assembly pun adalah “bahasa lain”, selorohnya. Ia lalu menjelaskan bahwa ekosistem Python dan SIMD sangat beragam, dari PeachPy (menulis assembly x86 dari Python), Mojo (bahasa baru bergaya Python), hingga library SIMD dengan binding CPython yang tipis. Ia menanyakan pendekatan seperti apa yang sebenarnya diinginkan, dan jika targetnya ASCII maka ia juga merekomendasikan fungsi find_first_of milik StringZilla (kode)

  • Ada pula yang mempertanyakan mengapa harus dilakukan langsung di Python. Jika masalahnya adalah batas performa, ia menyarankan bahwa hanya dengan mengganti bahasanya saja peningkatan performa 20~50 kali atau lebih sudah mungkin dicapai