Fungsi `tolower()` yang menggunakan AVX-512

• Beberapa tahun lalu, saya pernah menulis tentang cara mempercepat tolower() menggunakan trik SWAR. Beberapa hari lalu, saya tertarik pada tulisan Olivier Giniaux tentang cara mengoptimalkan pemrosesan string kecil dengan instruksi SIMD. Metode ini digunakan dalam fungsi hash cepat yang ditulis dengan Rust.

• Instruksi SIMD dapat menangani string pendek dengan mudah, tetapi saya selalu merasa repot karena transfer antara memori dan register vektor itu sulit. Tulisan Olivier menunjukkan cara menarik untuk mengatasi masalah ini.

Tanda-tanda harapan

• Beberapa set instruksi SIMD menyediakan fitur mask load dan store yang berguna untuk pemrosesan string. Fitur ini bekerja per byte.

  • ARM SVE: tersedia pada core ARM Neoverse besar yang lebih baru, misalnya Amazon Graviton. Namun, tidak tersedia di Apple Silicon.
  • AVX-512-BW: tersedia pada prosesor AMD Zen terbaru. AVX-512 adalah set ekstensi yang kompleks, dan dukungannya di Intel tidak konsisten.

• Karena saya memiliki mesin berbasis AMD Zen 4, saya memutuskan untuk mencoba AVX-512-BW.

tolower64()

• Dengan menggunakan panduan intrinsics Intel, saya menulis fungsi dasar tolower() yang dapat memproses 64 byte sekaligus.
  • Gunakan * sebagai wildcard untuk mencari mm512*epi8 dan menemukan fungsi AVX-512 tingkat byte.
  • Isi beberapa register dengan 64 byte yang berguna.
  • Tetapkan nilai yang diperlukan untuk mengubah huruf besar menjadi huruf kecil.
  • Bandingkan karakter input dengan A dan Z untuk memeriksa apakah itu huruf besar.
  • Gunakan mask untuk mengubahnya menjadi huruf kecil jika memang huruf besar.

Load dan store massal

• Kernel tolower64() perlu dibungkus dengan fungsi yang lebih praktis. Misalnya, fungsi yang menyalin string sambil mengubahnya menjadi huruf kecil.
  • Untuk string panjang, digunakan instruksi vector load dan store tak selaras.

Mask load dan store

• Untuk string kecil dan bagian akhir string panjang, digunakan load dan store tak selaras yang dimask.
  • Mask disetel pada len bit pertama.
  • Operasi load dan store mirip dengan versi lebar penuh yang ditambahkan mask.

Benchmark

• Kinerja beberapa fungsi serupa di-benchmark.

  • Dikompilasi dengan Clang 16 dan dijalankan pada AMD Ryzen 9 7950X.
  • Setiap fungsi dikompilasi secara terpisah untuk menghindari gangguan dari inlining dan perpindahan kode.

• Hasilnya:

  • tolower64 adalah yang tercepat dari semua fungsi yang diuji.
  • copybytes64 juga menggunakan AVX-512 dengan cara yang mirip tolower64, tetapi tidak jauh lebih cepat.
  • copybytes1 melakukan memcpy per byte dan menunjukkan bahwa auto-vectorization di Clang 11 relatif kurang baik.
  • tolower() standar adalah yang paling lambat.
  • tolower1 adalah tolower() per byte yang dikompilasi dengan Clang 16; auto-vectorization sudah membaik tetapi tetap lambat.
  • tolower8 adalah tolower() SWAR yang diperkenalkan dalam posting blog sebelumnya; Clang mencoba melakukan auto-vectorization, tetapi hasilnya tidak bagus.
  • memcpy awalnya cepat, tetapi kemudian turun menjadi setengah kecepatan copybytes64.

Kesimpulan

• AVX-512-BW sangat berguna, terutama saat menangani string pendek.

• Sangat cepat di Zen 4, dan fungsi bawaannya mudah digunakan.

• Performa AVX-512-BW sangat mulus.

• Saya tidak bisa menyelidikinya lebih jauh karena tidak punya mesin dengan dukungan ARM SVE, tetapi saya penasaran seberapa baik SVE bekerja untuk string pendek.

• Saya berharap ekstensi set instruksi seperti ini bisa digunakan lebih luas. Ini akan sangat meningkatkan performa pemrosesan string.

• Kode dari posting blog ini dapat dilihat di situs web saya.

Ringkasan GN⁺

• Tulisan ini menjelaskan cara memproses string pendek secara efisien menggunakan instruksi SIMD.
• Menunjukkan bahwa set instruksi AVX-512-BW dan ARM SVE berguna untuk pemrosesan string.
• Hasil benchmark menunjukkan bahwa AVX-512-BW memberikan performa yang sangat baik, terutama untuk string pendek.
• Tulisan ini akan bermanfaat bagi developer yang tertarik pada optimasi performa.

[GN⁺]

Komentar Hacker News

• Dalam model memori Rust dan LLVM, trik "unsafe read beyond of death" dianggap sebagai perilaku tak terdefinisi

  • Kompiler dapat mengasumsikan bahwa perilaku seperti ini tidak terjadi demi optimisasi
  • Untuk menghindarinya, perlu menggunakan assembly inline

• Muncul rasa penasaran tentang implementasi AVX512 milik AMD dan persaingannya dengan AVX10 dari Intel

  • AVX10 dibuat untuk menyelesaikan masalah inti P vs E milik Intel
  • AMD menggunakan lebar penuh Zen5 atau mode double-pump 256-bit pada Zen4 dan Zen5 mobile, sesuai situasi
  • Peningkatan performa besar terjadi pada inti Zen4

• Optimisasi SWAR hanya berguna untuk string yang disejajarkan ke alamat 8 byte

  • Jika diterapkan pada string yang tidak sejajar, hasilnya lebih lambat daripada algoritme asli
  • Jika algoritmenya dibagi menjadi tiga bagian, akan dibutuhkan lebih banyak instruksi

• Penambahan mask terlihat rapi

  • Akan menyenangkan jika ada cara untuk memanipulasi register mask AVX512 secara langsung di fitur bawaan .NET

• Dengan menggunakan Clang, hasil yang didapat bisa lebih baik

  • Memberikan pemilihan instruksi yang lebih baik dan hasil akhir yang tersusun rapi

• Core loop untuk string pendek memiliki satu instruksi lebih sedikit

  • Penting untuk memproses string pendek dengan cepat

• Ada implementasi serupa dalam C# untuk konversi huruf besar/kecil ASCII ke UTF-8

  • Karena string pendek mendominasi sebagian besar codebase, penting untuk menanganinya dengan cepat

• Ada contoh penggunaan SIMD yang memakai AVX512 untuk mengubah teks menjadi uwu

• Akan lebih mengesankan jika konversi karakter Unicode juga dipertimbangkan

  • Sebagian besar programmer hanya peduli pada ASCII, tetapi ada dunia yang luas di luar set karakter standar

• Pernah ada pengalaman menghindari masalah SIMD pada buffer dengan menambahkan bingkai hitam di sekitar gambar

  • Ada kalanya input tidak bisa dikendalikan sepenuhnya