AVX-512 kullanan `tolower()` fonksiyonu

 (dotat.at)
1 puan yazan GN⁺ 2024-07-30 | 1 yorum | WhatsApp'ta paylaş

  • Birkaç yıl önce, SWAR numaralarını kullanarak tolower() işlemini hızlandırma yöntemi hakkında yazmıştım. Birkaç gün önce, Olivier Giniaux'nun yazısında SIMD komutlarıyla küçük dizeleri işleme optimizasyonu hakkında ilginç bir yaklaşımla karşılaştım. Bu yöntem, Rust ile yazılmış hızlı bir hash fonksiyonunda kullanılıyor.

  • SIMD komutları kısa dizeleri kolayca işleyebiliyor, ancak bellek ile vektör kayıtları arasındaki aktarımın zor olması her zaman can sıkıcıydı. Olivier'nin yazısı bu soruna eğlenceli bir çözüm sunuyor.

Umut verici işaretler

  • Bazı SIMD komut setleri, dize işleme için kullanışlı maskeli yükleme ve saklama özellikleri sunuyor. Bunlar bayt düzeyinde çalışıyor.

    • ARM SVE: Amazon Graviton gibi yeni büyük ARM Neoverse çekirdeklerinde kullanılabiliyor. Ancak Apple Silicon'da kullanılamıyor.
    • AVX-512-BW: Yeni AMD Zen işlemcilerinde kullanılabiliyor. AVX-512 karmaşık bir genişletme seti ve Intel tarafında desteği düzensiz.

  • Elimde bir AMD Zen 4 kutusu olduğu için AVX-512-BW'yi denemeye karar verdim.

tolower64()

  • Intel intrinsics rehberini kullanarak, bir seferde 64 baytı işleyebilen temel bir tolower() fonksiyonu yazdım.
    • Bayt düzeyindeki AVX-512 fonksiyonlarını bulmak için * joker karakterini kullanıp mm512*epi8 araması yaptım.
    • Birkaç yazmacı 64 kullanışlı baytla doldurdum.
    • Büyük harfleri küçük harflere dönüştürmek için gereken sayıları ayarladım.
    • Girdi karakterlerini A ve Z ile karşılaştırarak büyük harf olup olmadıklarını kontrol ettim.
    • Büyük harf olanları küçük harfe dönüştürmek için maske kullandım.

Toplu yükleme ve saklama

  • tolower64() çekirdeğini daha kullanışlı bir fonksiyonla sarmalamak gerekiyor. Örneğin, dizeleri kopyalarken aynı anda küçük harfe çeviren bir fonksiyon.
    • Uzun dizelerde hizasız vektör yükleme ve saklama komutları kullanılıyor.

Maskeli yükleme ve saklama

  • Küçük dizeler ve uzun dizelerin son kısımları için maskeli hizasız yükleme ve saklama kullanılıyor.
    • Maskede ilk len bit ayarlanıyor.
    • Yükleme ve saklama, maske eklenmiş tam genişlikli sürümlere benziyor.

Karşılaştırmalı performans testi

  • Birbirine benzeyen birkaç fonksiyonun performansı karşılaştırıldı.

    • Clang 16 ile derlenip AMD Ryzen 9 7950X üzerinde çalıştırıldı.
    • Her fonksiyon, inline etkileşimi ve kod taşınmasını önlemek için ayrı ayrı derlendi.

  • Sonuçlar:

    • tolower64, test edilen tüm fonksiyonlar arasında en hızlısı.
    • copybytes64, tolower64 ile benzer şekilde AVX-512 kullanıyor ama belirgin biçimde daha hızlı değil.
    • copybytes1, bayt düzeyinde memcpy yapıyor ve Clang 11'in otomatik vektörleştirmesinin görece zayıf olduğunu gösteriyor.
    • Standart tolower() en yavaşı.
    • tolower1, Clang 16 ile derlenmiş bayt düzeyinde bir tolower() ve otomatik vektörleştirme iyileşmiş olsa da hâlâ yavaş.
    • tolower8, önceki blog yazısında tanıtılan SWAR tolower(); Clang otomatik vektörleştirmeyi denese de sonuç iyi değil.
    • memcpy, başta hızlı ama sonra copybytes64 hızının yarısına düşüyor.

Sonuç

  • AVX-512-BW, özellikle kısa dizeleri işlerken çok faydalı.

  • Zen 4 üzerinde çok hızlı ve intrinsics'leri kullanmak kolay.

  • AVX-512-BW'nin performansı oldukça akıcı.

  • ARM SVE destekli bir sistemim olmadığı için ayrıntılı inceleyemedim, ama SVE'nin kısa dizelerde ne kadar iyi çalıştığını merak ediyorum.

  • Bu tür komut seti genişletmelerinin daha yaygın kullanılmasını umuyorum. Dize işleme performansını büyük ölçüde artıracaktır.

  • Bu blog yazısındaki kodu kendi web sitemde görebilirsiniz.

GN⁺ Özeti

  • Bu yazı, SIMD komutları kullanarak kısa dizeleri verimli biçimde işlemenin nasıl yapılacağını anlatıyor.
  • AVX-512-BW ve ARM SVE komut setlerinin dize işleme için ne kadar yararlı olduğunu gösteriyor.
  • Karşılaştırmalı testler, AVX-512-BW'nin özellikle kısa dizelerde üstün performans sunduğunu ortaya koyuyor.
  • Yazı, performans optimizasyonuyla ilgilenen geliştiriciler için faydalı olacaktır.

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-30
Hacker News görüşleri

  • Rust ve LLVM bellek modelinde "unsafe read beyond of death" hilesi tanımsız davranış olarak kabul ediliyor

    • Derleyici, optimizasyon için böyle bir davranışın gerçekleşmediğini varsayabilir
    • Bundan kaçınmak için satır içi assembly kullanmak gerekiyor

  • AMD'nin AVX512 uygulaması ile Intel'in AVX10 rekabeti hakkında merak uyandırıyor

    • AVX10, Intel'in P ve E çekirdek sorununun çözümü için var
    • AMD, duruma göre Zen5'in tam genişliğini veya Zen4 ile Zen5 mobile'daki 256 bit double-pump yaklaşımını kullanıyor
    • Büyük performans artışı Zen4 çekirdeklerinde gerçekleşiyor

  • SWAR optimizasyonu yalnızca 8 bayt adresine hizalanmış dizeler için yararlı

    • Hizalanmamış dizelere uygulanırsa özgün algoritmadan daha yavaş oluyor
    • Algoritmayı üç parçaya bölmek daha fazla komut gerektiriyor

  • Maske ekleme temiz görünüyor

    • .NET yerleşik özelliklerinde AVX512'nin maske yazmaçlarını doğrudan manipüle etmenin bir yolu olsaydı iyi olurdu

  • Clang kullanılırsa daha iyi sonuç alınabiliyor

    • Daha iyi komut seçimi ve iyi açılmış sonuçlar sunuyor

  • Kısa uzunluktaki dizeler için çekirdek döngü bir komut daha az içeriyor

    • Kısa dizeleri hızlı işlemek önemli

  • ASCII'yi UTF-8 olarak büyük/küçük harf dönüştüren benzer bir uygulama C# ile yazılmış

    • Kısa dizeler çoğu kod tabanına hakim olduğu için bunları hızlı işlemek önemli

  • AVX512 kullanarak metni uwu'ya dönüştüren bir SIMD kullanım örneği var

  • Unicode karakter dönüşümü de hesaba katılsa daha etkileyici olurdu

    • Programcıların çoğu yalnızca ASCII'yi önemsiyor, ancak standart karakter kümesinin dışında da koca bir dünya var

  • Geçmişte, tampon SIMD sorunlarını önlemek için görsellerin etrafına siyah kenarlık ekleme deneyimi olmuş

    • Girdiyi her zaman tamamen kontrol etmek mümkün olmuyor