Fungsi `tolower()` yang diimplementasikan dengan AVX-512

 (dotat.at)
1 poin oleh GN⁺ 2024-07-30 | 1 komentar | Bagikan ke WhatsApp
  • Ini adalah eksperimen untuk mengekstrak performa SIMD bahkan pada string kecil dengan memproses penyalinan string sambil mengubah huruf besar ASCII menjadi huruf kecil 64 byte sekaligus menggunakan AVX-512-BW
  • Inti implementasinya adalah membandingkan setiap byte apakah berada di antara 'A' dan 'Z', lalu melakukan operasi mask yang menambahkan 'a' - 'A' hanya pada posisi tersebut
  • Sisa ekor untuk string pendek dan bagian akhir string panjang ditangani dengan masked load/store, sehingga mengurangi biaya penanganan potongan kecil yang sering menjadi masalah pada kode SIMD
  • Hasil pengukuran penyalinan sekitar 1MiB dalam chunk 1 byte hingga 1KiB pada Clang 16, Debian 11, dan AMD Ryzen 9 7950X menunjukkan bahwa tolower64 secara konsisten termasuk yang lebih cepat di antara pembanding
  • Pada Zen 4, AVX-512-BW terlihat sangat cocok untuk pemrosesan string, tetapi ARM SVE dan ekstensi RISC-V Vector belum bisa diverifikasi langsung secara mendalam

Membuat tolower() 64 byte dengan AVX-512-BW

  • Tujuannya adalah mengimplementasikan kernel tolower() dengan SIMD yang menyalin string sambil mengubah karakter ASCII huruf besar menjadi huruf kecil
  • AVX-512-BW adalah ekstensi yang mendukung operasi satuan byte dan word, dan dapat digunakan pada prosesor AMD Zen terbaru
    • AVX-512 terbagi ke dalam beberapa ekstensi sehingga dukungan ketersediaannya cukup rumit
    • Dukungan di pihak Intel dinilai sangat tidak konsisten
  • ARM SVE juga menyediakan masked load/store satuan byte yang cocok untuk pemrosesan string
    • Tersedia pada core big-ARM Neoverse terbaru, misalnya Amazon Graviton
    • Tidak tersedia di Apple Silicon
  • Ekstensi RISC-V Vector juga memiliki gaya yang mirip dengan ARM SVE, dan tersedia pada berbagai komputer papan tunggal kecil

Cara kerja tolower64()

  • tolower64() adalah kernel berbasis AVX-512 yang memproses 64 byte sekaligus
  • Pertama, nilai acuan diisikan ke register vektor yang memuat 64 byte
    • 'A'
    • 'Z'
    • 'a' - 'A'
  • Vektor karakter input c dibandingkan dengan 'A' dan 'Z' untuk membuat masing-masing mask 64-bit
    • posisi dengan c >= 'A'
    • posisi dengan c <= 'Z'
  • Kedua mask digabungkan dengan _kand_mask64() untuk membuat mask is_upper yang hanya menandai posisi huruf besar
  • Terakhir, _mm512_mask_add_epi8() diterapkan
    • Byte dengan is_upper false mempertahankan c asli
    • Byte dengan is_upper true menjadi c + ('a' - 'A')

Menangani string panjang dan string pendek

  • Sebagian besar string panjang diproses dengan vector load/store tak terjajar biasa
    • _mm512_loadu_epi8()
    • tolower64()
    • _mm512_storeu_epi8()
  • Untuk string pendek dan potongan sisa terakhir dari string panjang, digunakan masked unaligned load/store
  • Mask dibuat dalam bentuk hanya len bit bagian bawah yang menyala
    • uint64_t len_bits = (~0ULL) >> (64 - len)
    • Dinaikkan ke register mask SIMD dengan _cvtu64_mask64(len_bits)
  • _mm512_maskz_loadu_epi8() mengisi register tujuan dengan 0 pada posisi saat mask mati
  • _mm512_mask_storeu_epi8() hanya menyimpan posisi saat mask menyala
  • Pendekatan ini adalah kunci untuk memproses potongan string kecil dengan cepat

Kondisi benchmark dan objek pembanding

  • Benchmark dijalankan pada Clang 16, Debian 11, dan AMD Ryzen 9 7950X
  • Yang diukur adalah penyalinan sekitar 1MiB, dengan panjang chunk diubah dari 1 byte hingga 1KiB
  • Untuk mencerminkan perbedaan alignment string sumber dan tujuan, beberapa byte disisipkan di antara masing-masing string, dan byte-byte ini tidak dimasukkan ke dalam total pengukuran 1MiB
  • Cache L2 Ryzen 9 7950X adalah 1MiB per core, sehingga tiap eksekusi pengujian diperkirakan akan melewati hingga cache L3
  • Setiap fungsi dikompilasi secara terpisah untuk menghindari interferensi dari inlining dan perpindahan kode
    • Pada kode nyata, kemungkinan besar inlining justru lebih dianjurkan daripada dicegah

Hasil: performa tolower64 yang mulus

  • tolower64 berwarna merah muda secara umum konsisten berada di kelompok tercepat di antara fungsi-fungsi yang diuji
    • Saat panjangnya 65 byte, performa sedikit turun ketika berpindah ke vektor kedua
    • Setelah itu cepat naik dan tidak memiliki lembah performa yang dalam, menunjukkan bahwa masked load/store efektif untuk menangani potongan string pendek
  • copybytes64 berwarna hijau adalah versi memcpy yang menggunakan AVX-512 dengan cara serupa
    • Tidak jauh lebih cepat daripada tolower64
    • Clang terbaru mengenali makna fungsi ini dan menulis ulang seluruhnya, sehingga dikompilasi dengan Clang 11
  • copybytes1 berwarna oranye adalah versi memcpy satuan byte
    • Dikompilasi dengan Clang 11
    • Menunjukkan bahwa heuristik auto-vectorization Clang 11 relatif kurang baik untuk potongan string di bawah 256 byte
  • tolower berwarna merah adalah baseline yang memanggil tolower() standar dari <ctype.h> dan sangat lambat
  • tolower1 berwarna ungu adalah tolower() satuan byte yang dikompilasi dengan Clang 16
    • Auto-vectorization Clang 16 jauh lebih baik daripada Clang 11
    • Tetap lebih lambat daripada versi tulis tangan dan menghasilkan kode yang jauh lebih rumit
    • Penanganan potongan string pendek tidak sebagus tolower64, sehingga grafik performanya bergetar tajam
  • tolower8 berwarna cokelat adalah tolower() SWAR dari tulisan sebelumnya
    • Clang mencoba melakukan auto-vectorization, tetapi hasilnya kurang baik karena fungsinya rumit
    • Meski dikompilasi dengan Clang 16, tetap muncul jurang performa 256 byte ala Clang 11
  • memcpy berwarna biru memanggil memcpy dari glibc
    • Pada awalnya cepat, tetapi ada rentang di mana kecepatannya turun hingga sekitar setengah dari copybytes64
    • Penyebabnya belum dapat dipastikan

Kesimpulan dan kode

  • AVX-512-BW sangat cocok untuk menangani string, terutama string pendek
  • Di Zen 4, performanya sangat cepat, dan fungsi intrinsic-nya juga relatif mudah digunakan
  • Karakteristik yang paling menonjol adalah performa yang mulus
    • Hampir tidak terlihat lembah performa saat auto-vectorization beralih ke kode skalar pada potongan string kecil
  • Karena tidak ada akses mudah ke perangkat yang mendukung ARM SVE atau ekstensi RISC-V Vector, kedua ekstensi itu belum bisa diteliti secara rinci
  • Kodenya dapat dilihat di repositori git situs web

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-30
Komentar Hacker News

  • Trik “unsafe read beyond of death” dianggap sebagai perilaku tak terdefinisi dalam model memori Rust dan LLVM, meskipun diizinkan oleh perangkat keras
    Seperti perilaku tak terdefinisi lainnya, compiler dapat berasumsi bahwa “hal seperti itu tidak terjadi” dalam proses optimisasi, sehingga bisa muncul hasil yang tidak terduga; untuk mengakalinya perlu memakai assembly inline
    https://github.com/ogxd/gxhash/issues/82

    • Akan bagus kalau ada opsi selain assembly untuk kasus seperti ini
      Load yang “membaca nilai di luar rentang alokasi sebagai elemen tak terspesifikasi, dan hanya menjadi perilaku tak terdefinisi ketika perangkat keras tidak menyukainya” tampaknya tidak sulit untuk didukung, dan cukup saja bila secara internal itu menjadi alias dari pemanggilan assembly tersebut
      Lebih jauh lagi, akan bagus jika setelah setiap alokasi seperti malloc, stack, konstanta, dan sebagainya dijamin ada setidaknya sekitar 64 byte alamat tanpa fault, tetapi itu jauh lebih rumit karena membutuhkan kerja sama banyak komponen
      Pada custom allocator itu hal sepele, tetapi dalam kasus tersebut kode SIMD sulit dipakai untuk data di luar heap kustom, dan kita jadi terikat pada kemungkinan segfault yang sangat kecil
      sanitizer atau Valgrind juga tetap berguna, karena nilai di luar rentang bisa dilacak sebagai nilai tak pasti dan dapat memunculkan error saat benar-benar digunakan
    • Saya ragu apakah itu benar bahkan di level perangkat keras
      Saya penasaran apa yang terjadi jika membaca page yang tidak dipetakan atau memori yang diproteksi, dan karena belum melihat kodenya saya tidak tahu apakah jaminan alignment menghindari hal ini
    • Penjelasan bahwa “jika itu perilaku tak terdefinisi, compiler dapat berasumsi hal seperti itu tidak ada” itu salah
      Perilaku tak terdefinisi adalah istilah teknis dalam standar C, jadi menggeneralisasikannya saja sudah aneh; ANSI C tidak secara eksplisit mengizinkan asumsi seperti itu, dan ISO C memang lebih terbuka, tetapi tidak secara spesifik membenarkan asumsi tersebut
      Menurut saya penjelasan seperti “UB = boleh diasumsikan tidak mungkin terjadi” cukup mendekati fearmongering yang tidak jujur

  • Melihat kode dalam tulisan itu yang rapi dan berkinerja bagus, saya jadi penasaran bagaimana implementasi AVX512 AMD akan bersaing dengan AVX10 yang direncanakan Intel
    Inti AVX10 tampaknya adalah menyelesaikan situasi P-core/E-core Intel, sedangkan AMD tampaknya memilih pendekatan yang lebih baik: tetap menjaga API mulus sambil memakai implementasi lebar penuh pada Zen5 atau metode pemrosesan 2 kali 256-bit pada Zen4 dan Zen5 mobile, tergantung situasinya
    Peningkatan kinerja besar dalam tulisan itu juga semuanya berasal dari core Zen4, dan karena AVX512 punya banyak keunggulan, terasa menjengkelkan bahwa Intel terlalu membatasinya untuk segmentasi pasar hingga secara praktis menghambat adopsinya dalam kode klien umum

    • Jika Intel benar-benar memasukkan AVX10/256 ke semua CPU yang akan mereka rilis ke depan, pada akhirnya mereka akan menang karena tingkat penyebarannya
      Pasar berulang kali menolak percabangan jalur kode per CPU, dan implementasi SIMD yang benar-benar penting adalah common denominator terendah
      AVX10.1/256 dan AVX512VL memiliki subset yang sama, jadi setelah waktu yang cukup berlalu dan sebagian besar CPU mendukungnya, orang-orang akan menargetkan bagian itu
      AMD akan terus mendapat kemenangan mudah pada beberapa aplikasi benchmark yang diperbarui untuk mendukung AVX512, tetapi jika Intel mempertahankan rencana AVX10, AMD kemungkinan pada akhirnya juga akan memakai pipeline SIMD 2 kali pemrosesan secara penuh agar bisa mendukung AVX10/256 secara efisien sambil mempertahankan kompatibilitas AVX512
      Intel membuat banyak pilihan buruk selama 10 tahun terakhir, tetapi memecah pasar lewat instruction set adalah salah satu yang terburuk. Mereka seperti membunuh sendiri momentum dan minat terhadap inovasi terbaru; fitur seperti operasi mask jauh lebih penting daripada lebarnya sendiri, jadi saya berharap mereka memasukkan AVX10/256 ke seluruh lini produk
    • Implementasi AVX512 Zen 4 bukan double-pumped, dan jurnalis teknologi seharusnya berhenti menyebutnya begitu
      Istilah itu punya makna tertentu, dan tidak cocok dengan cara kerjanya yang sebenarnya
      Zen 4 hanya mendecode operasi register ZMM menjadi beberapa micro-op lalu menjadwalkannya ke unit 256-bit yang kosong, sementara shuffle lebar penuh 512-bit ditangani secara khusus oleh hardware khusus untuk menghindari emulasi yang mahal
      Karena itu, Zen 4 dengan 4 unit SIMD 256-bit pun berperilaku seperti core 2×512-bit yang kuat, dan implementasi ini sama sekali bukan cara yang murah; mungkin ini bentuk terbaik yang sejauh ini ada di hardware konsumen
    • Saya tidak mengerti mengapa Intel tidak menyelesaikan masalah ini dengan memasukkan AVX512 double-pumped ke E-core. Atau buat saja CPU desktop yang hanya berisi P-core, seperti yang memang seharusnya
      Mereka sudah punya waktu bertahun-tahun untuk memperbaikinya, dan menyebalkan bahwa meski AMD mendukungnya, adopsi tidak terjadi karena pangsa pasar; sayangnya AVX10 sepertinya akan membuat Intel menahan dunia lebih lama lagi
      Di desktop, saya ingin melihat core yang lebih baik, lebih banyak core, dan instruction set yang distandardisasi dengan baik yang membuka fitur berguna seperti SIMD lebar, float16, dan gather/scatter; AMD melakukannya dengan cukup baik
      Sebaliknya Intel menempelkan core lemah di samping core yang bagus, membatasi core yang bagus agar sesuai dengan core yang lemah, merilis CPU dengan jumlah core yang sama selama beberapa generasi, membuat seolah-olah jumlah core banyak dengan core lemah, mengeluarkan terlalu banyak varian instruksi sehingga sulit terbentuk common set yang berguna, dan bahkan meninggalkan dukungan instruksi yang sebelumnya tampak mereka janjikan
      Preferensi produsen desktop dulu adalah Intel pada 90-an, AMD pada awal 2000-an, Intel pada akhir 2000-an dan 2010-an, dan sekarang kembali AMD. Saya penasaran apa yang akan dilakukan Intel untuk mendapatkan kembali pijakan selain menghambat lawannya, dan kompetisi harus terus berjalan agar salah satu pihak tidak terlalu terlena

  • Materi menarik untuk dilihat sekadar iseng: http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt

    • Ada juga yang seperti ini: jika ß dalam bahasa Jerman diubah menjadi huruf besar, panjang string ikut berubah
      Misalnya "straße".upper() menjadi 'STRASSE'
      Selain itu, jika locale tidak ditentukan, saat huruf i tanpa titik dalam bahasa-bahasa Turkik dikonversi bolak-balik ke huruf besar/kecil, 'ı'.upper().lower() menjadi 'i' sehingga rusak
    • Untungnya, kode ini berasal dari pekerjaan DNS, jadi karena khusus ASCII, kompleksitas seperti itu tidak perlu ditangani
      Ada beberapa protokol ASCII yang tidak membedakan huruf besar/kecil, dan ini sering muncul di hot path banyak server
    • String yang dipakai secara internal seperti ID berbeda dengan teks yang dimasukkan manusia
      Yang pertama biasanya cukup memakai ASCII murni dalam encoding 8-bit, tetapi yang kedua menjadi rumit
      Alamat DNS adalah contoh yang mudah: secara teknis dapat memuat hampir semua Unicode, tetapi untuk resolusi DNS yang sebenarnya dikonversi menjadi subset ASCII yang sangat terbatas, dan proses resolusi itu tidak membedakan huruf besar/kecil
      Tentu ada juga bahasa pemrograman yang mendukung semua sistem aksara Unicode tetapi identifier-nya tidak membedakan huruf besar/kecil. Jika Anda menangani hal semacam itu, turut berduka
    • Terkait contoh bahasa Jerman maße yang berubah menjadi MASSE, dalam bahasa Jerman juga ada ẞ, yaitu Eszett kapital
      Ini belum tersebar luas dan font yang mendukungnya masih sedikit, tetapi secara teori sekarang sudah ada

  • Rasanya penjelasan “penjumlahan mask” di artikel itu salah
    Bukankah seharusnya saat is_upper false dilakukan penjumlahan, dan saat true disalin apa adanya?

    • Ah, belakangan saya sadar bahwa nama variabel to_upper terbalik, jadi seharusnya disebut to_lower
      Terima kasih sudah menunjukkan bagian yang membingungkan; artikel dan kodenya sudah saya perbaiki
    • Operasi ini adalah tolower
      Huruf kapital A adalah 0x40, huruf kecil adalah 0x60, jadi menambahkan 0x20 harus terjadi saat is_upper bernilai true

  • Optimisasi SWAR seperti ini sering kali hanya berguna ketika string terselaraskan pada alamat 8 byte
    Jika algoritma SWAR diterapkan pada string yang tidak terselaraskan, sering kali hasilnya lebih lambat daripada algoritma aslinya
    Jika dipecah menjadi 3 tahap—memproses bagian awal hingga alamat terselaraskan, memproses badan yang terselaraskan, lalu memproses ekor kurang dari 8 byte—jumlah instruksi malah bertambah
    Contoh serupa dan benchmark terkait klaim keliru bahwa utf8.IsValid di Go lebih cepat ada di sini: https://github.com/sugawarayuuta/charcoal/pull/1

    • Operasi SIMD bermasker pada AVX-512 dan ARM SVE dibuat untuk mengatasi masalah itu
      Operasi memori selalu dibuat terselaraskan dan sebesar ukuran vektor penuh, tetapi mask dapat diterapkan hanya pada elemen yang valid
      Bahkan jika operasi memori vektor bermasker tidak terselaraskan dan melintasi halaman yang tidak dipetakan atau dilindungi, jika lane tersebut dimatikan oleh mask, fault tidak akan terjadi
      Untuk operasi yang panjangnya belum diketahui sebelumnya seperti strlen(), ada juga instruksi load khusus yang mengurangi panjang vektor tepat sebelum elemen pertama yang akan menimbulkan fault

  • Penjumlahan mask terlihat keren. Akan bagus kalau register mask AVX512 bisa dimanipulasi langsung dari intrinsic .NET, tetapi saat ini harus bergantung pada “idiom yang dikenali”
    Jika loop inti buatan penulis yang dihasilkan GCC dianalisis dengan uiCA(CQA/MAQAO) untuk Ice Lake, hasilnya sekitar 32B/cycle, dan jika dikonversi pada 3GHz menjadi hampir 96GiB/s dengan asumsi tidak ada bottleneck memori. Tentu saja, pada algoritma seperti ini akses memori selalu menjadi bottleneck
    Namun tampaknya belum benar-benar mendekati pemanfaatan optimal, dan jika memakai Clang, hasil unroll yang lebih terurai serta pemilihan instruksi yang lebih baik bisa mencapai 42,67B/cycle. Cache L2 pun tampaknya sulit mempertahankan throughput seperti itu, tetapi menarik bahwa konversi huruf besar/kecil untuk string berukuran menengah selesai kira-kira dalam waktu cahaya layar mencapai kornea
    Beberapa bulan lalu saya mengimplementasikan konversi huruf besar/kecil ASCII dalam UTF-8 yang mirip di C#: https://github.com/U8String/U8String/blob/main/Sources/U8Str...
    Karena string pendek mendominasi sebagian besar codebase, konversi yang di-unroll untuk panjang di bawah panjang vektorisasi itu penting, dan switch dikompilasi menjadi jump table serta fall-through branchless
    Saat ini hanya memakai hingga 256-bit, karena pada kasus seperti Zen 3 atau 4 yang hanya memiliki unit SIMD 256×4, itu sudah jenuh. Contoh perbandingan berdampingan dengan versi C ada di sini: https://godbolt.org/z/eTGYhTPan
    Di AVX512, sepertinya konversi dengan 3 instruksi menggunakan vpternlogd juga mungkin, dan ketika perangkat keras AVX512 bisa dipakai, .NET mengoptimalkannya seperti itu pada lebar 256-bit + AVX512VL, tetapi sekarang anehnya tidak bisa direproduksi pada lebar 512-bit
    Anda juga akan melihat percobaan SWAR yang gagal pada bagian dispatch switch; saya penasaran dengan lisensi tulisannya. Kalau lolos test suite, saya ingin memakainya

    • Clang dan GCC berbeda dalam cara menangani intrinsic, dan khususnya pada instruksi AVX-512, Clang lebih mungkin menyimpang dari opcode dan algoritma yang ditentukan panduan Intel dibanding GCC
      Kalau melihat struktur kedua compiler, ini bisa dipahami, tetapi hasilnya kadang membaik dan kadang merugikan
      Beberapa tahun lalu saat mengerjakan proyek yang sangat tervectorisasi dan harus bisa dikompilasi dengan keduanya, akhirnya saya menyimpan inline assembly khusus target tertentu dan file .S di repository, bersama versi referensi C
      Makefile jadi berantakan dan benchmark pun harus dimasukkan ke test suite, sehingga beban pemeliharaannya besar; karena itu saya menyimpulkan bahwa memakai intrinsic sebagai sarana low-level yang lebih baik daripada auto-vectorization harus dilakukan dengan sangat hati-hati
      Contoh: di https://godbolt.org/z/T4Pjhrz5d, output GCC sesuai dugaan, tetapi output Clang mengejutkan dan memang lebih lambat. Jika dijalankan sebagai loop, menurut uiCA hasilnya 7 cycle dibanding 4 cycle pada GCC, dan ini juga terlihat pada benchmark aplikasi nyata tempat fungsi ini dieksekusi miliaran kali dalam algoritma brute-force
      Saat melihat codebase LLVM, saya juga ingat melihat masalah bahwa Clang 16 mungkin sama sekali tidak mengeluarkan sebagian instruksi AVX-512 bermasker karena refactoring internal
    • Analisisnya sangat bermanfaat
      Tujuannya bukan mengejar performa setinggi mungkin; awalnya hanya ingin melihat apakah bisa berjalan, dan hasil percobaan pertama yang cukup bagus adalah bonus
      Perhatian utama saya adalah string yang lebih pendek daripada register vektor dan menghilangkan lembah pada grafik throughput
      Jika mengikuti tautan kode di akhir posting blog, ada informasi lisensinya; selain bagian MPL-2.0 yang awalnya ditulis untuk BIND, lisensinya 0BSD atau MIT-0
    • Kalau hanya melihat bongkahan assembly yang besar memang kurang terlihat, tetapi Clang menulis ulang (x >= 'a' && x <= 'z') menjadi bentuk (x - 'a') < ... sehingga mengurangi satu instruksi
      Karena encoding opcode yang aneh, kadang register load juga ikut berkurang

  • Saya tidak tahu apa itu swar

    • Itu singkatan dari “SIMD Within A Register”
      Biasanya berarti teknik memasukkan beberapa item ke dalam satu register secara packed sehingga secara efektif dipakai seperti SIMD, tanpa instruksi SIMD eksplisit
      Misalnya, jika memasukkan angka 31-bit dan 32-bit ke register 64-bit lalu menyisakan 1 bit untuk carry, satu penjumlahan 64-bit bisa melakukan dua penjumlahan
      Di game, nilai RGB(A) di-packing ke integer 32-bit untuk trik grafis seperti ini, dan ScummVM juga punya kode yang menginterpolasi 2 piksel RGB 16-bit di dalam nilai 32-bit, total 6 komponen: https://github.com/scummvm/scummvm/blob/master/graphics/scal...
    • Artinya SIMD di dalam register

  • Setelah Unicode muncul, konsep huruf besar dan huruf kecil menjadi rawa
    Untuk melakukannya dengan benar, dibutuhkan banyak data
    Jika Anda mengerjakan sesuatu yang keberhasilannya bergantung pada apakah ASCII tolower selesai tepat waktu, lebih baik mengubah permainan dan mengganti prasyaratnya

  • Dulu saya pernah menambahkan bingkai hitam di sekitar gambar untuk sepenuhnya menghindari masalah SIMD membaca melewati buffer
    Itu bekerja sangat baik dan dari sisi kecepatan bisa mengalahkan beberapa implementasi OpenCV, tetapi tidak selalu mungkin mengendalikan input sepenuhnya seperti itu

  • Saya penasaran apakah pernah mencoba cara seperti ini. Hasil auto-vectorization tampak cukup rapi
    https://godbolt.org/z/1c5joKK5n

    • Itu pada dasarnya sama dengan tolower1. Lihat bullet di bawah grafik