C’den {n} kat daha hızlı

 (owen.cafe)
1 puan yazan GN⁺ 2023-07-07 | 1 yorum | WhatsApp'ta paylaş
  • Küçük bir C döngüsünde bile derleyici çıktısı her zaman en iyisi olmadığından, x86_64 assembly elle ayarlandığında koşullu dallanmayı kaldıran sürüm clang çıktısından 6,73 kat daha hızlı oldu
  • Hedef fonksiyon, bir dizgede 's' için +1, 'p' için -1, '\0' için sonlandırma uygular; clang 16 çıktısı bu akışı 3 koşullu dallanmaya böler
  • Dallanma sırasını değiştirme, temel blokları yeniden yerleştirme ve atlamaları aritmetikle değiştirme sonucunda çalışma süresi 3,23 saniyeden 2,87 saniyeye düştü; bu aşamada GCC 12 ile aynı hıza ulaştı
  • En hızlı sürüm, cmove ile her karakter için eklenecek değeri 0, 1, -1 arasından seçip her zaman add çalıştırarak 0,48 saniye ve 1,94GiB/s işleme hızı kaydetti
  • Benchmark, AMD Ryzen 5 5625U ve Linux 6.1.33 üzerinde 1 milyon rastgele 'p'/'s' karakterinden oluşan listeyi 1000 kez işledi; birden fazla çalıştırma içindeki en iyi sonuç kullanıldı

Deney konusu fonksiyon ve derleyici çıktısı

  • Hedef fonksiyon, dizge işaretçisini teker teker artırırken karaktere göre res tamsayısını günceller
    • 's': res += 1
    • 'p': res -= 1
    • '\0': res döndürülür
    • Diğer karakterler: değişiklik yok
  • Fonksiyon küçük olduğu için gcc veya clang’in bunu oldukça iyi, hatta belki de en iyi şekilde optimize edebileceği beklentisiyle yola çıkıldı
  • clang’in ürettiği ilk assembly, dört durumu üç koşullu dallanmaya (je, je, jne) ayırıyor
    • res = 0 ile başlıyor
    • Karakteri okuyup önce '\0' olup olmadığını kontrol ediyor
    • Ardından 'p' ve 's' ile karşılaştırıyor
  • İlk clang sonucu
    • Çalışma süresi: 3,23 saniye
    • İşleme hızı: 295,26MiB/s
  • GCC biraz daha fazla kod üretti ancak az da olsa daha hızlıydı

Nadir sonlandırma koşulundan önce yaygın karakterleri kontrol etmek

  • Döngü yalnızca null sonlandırma karakteri '\0' ile karşılaştığında biter ve bu fonksiyonda null sonlandırma karakteri en fazla bir kez görünür
  • clang çıktısı önce '\0' kontrolü yaptığı için her 'p' ve 's' karakterinde önce sonlandırma koşulunu kontrol eden bir yapı oluşur
  • İlk manuel değişiklik, karşılaştırma sırasını değiştirip önce 'p' ve 's' karakterlerini kontrol etmek oldu
  • Sonuç
    • Çalışma süresi: 3,10 saniye
    • Hız artışı: 1,04 kat
    • İşleme hızı: 307,64MiB/s

Temel blokları yeniden yerleştirme ve atlamaları azaltma

  • Yaygın iki durum olan 'p' ve 's' ikisi de döngü başına geri atladığından, bloklardan biri döngünün üstüne yerleştirilerek dallanma azaltılabilir
  • 's' bloğu döngünün hemen önüne konursa, 's' işlendikten sonra ayrı bir atlama olmadan akış döngüye düşer
  • Buna karşılık fonksiyon başlangıcında 's' bloğunu atlamak için döngüye bir kez atlamak gerekir
    • Fonksiyon başlangıcındaki atlama yalnızca bir kez gerçekleşir
    • 's' karakteri birçok kez karşılaşılabileceğinden bu kabul edilebilir bir takas olarak ele alındı
  • Sonuç
    • Çalışma süresi: 2,98 saniye
    • Toplam hız artışı: 1,08 kat
    • İşleme hızı: 320,02MiB/s

Aritmetik ile bir koşulsuz atlamayı kaldırmak

  • p: bloğundan döngüye dönen koşulsuz jmp komutunu kaldırmak için aritmetik kullanıldı
  • Bir kez azaltma, sub eax, 2 ardından inc eax ile aynı etkiyi verebildiğinden, 'p' işlendiğinde akışın 's' bloğuna düşmesi sağlandı
  • Bu yöntemle bir dallanma komutu daha kaldırıldı
  • Sonuç
    • Çalışma süresi: 2,87 saniye
    • Toplam hız artışı: 1,12 kat
    • İşleme hızı: 332,29MiB/s
  • Bu noktadaki performans, GCC 12’nin ürettiği kodla aynıydı
    • GCC 12 kodu da 2,87 saniyede çalıştı
    • Elle yazılan sürüm 13 komuttan oluşuyordu
    • GCC çıktısı 19 komuttu
    • GCC kodu döngüyü unroll etmiş ve case bloklarını bir ölçüde yeniden kullanmış gibi görünüyor

Koşullu dallanmayı cmove ile değiştirmek

  • Darboğaz koşullu dallanmalarsa, dallanma tahminleyicisine güvenmek yerine koşullu dallanmanın kendisi kaldırılabilir
  • En hızlı sürüm cmove, yani eşitlik koşullu taşıma kullandı
  • Çalışma kuralı basit
    • Varsayılan değer 0
    • Geçerli karakter 's' ise 1
    • Geçerli karakter 'p' ise -1
    • Her yinelemede seçilen değer her zaman res değerine eklenir
  • Bu yöntem kontrol akışı grafiğindeki birçok oku kaldırır
  • Sonuç
    • Çalışma süresi: 0,48 saniye
    • Toplam hız artışı: 6,73 kat
    • İşleme hızı: 1,94GiB/s
  • Elle yazılmış yoğun bir C döngüsü assembly’sinde, derleyicinin otomatikleştirmediği optimizasyonla 6 katın üzerinde hız artışı mümkün oldu

Register tasarrufu denemesi ve başarısız ek deneyler

  • x86_64’teki sete kullanılarak 1 baytlık register’ı koşula bağlı olarak 0 veya 1’e ayarlayan bir sürüm de denendi
  • Bu sürüm r8d kullanımını kaldırıyor, ancak yalnızca cmov kullanan sürümden daha yavaştı
  • Sonuç
    • Çalışma süresi: 0,51 saniye
    • Toplam hız artışı: 6,33 kat
    • İşleme hızı: 1,83GiB/s
  • Daha az register kullanmak veya 32 bit işlemler yerine 8 bit işlemler kullanmak daha hızlı hale getirmedi
  • Ek denemeler de performansı düşürdü
    • En iyi sürümde döngü unroll: yavaşladı
    • Döngü başlangıcını 16 bayt sınırına hizalama: yavaşladı
    • GNU assembler’da etiketin önüne .align <bytes> koymak nop ekleyebilir

Benchmark ortamı ve kod

  • Kod listesi GitHub üzerinde bulunuyor
  • Benchmark ortamı
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • CPU family 25, 6 çekirdek, çekirdek başına 2 thread, 1 soket
    • clang: 16.0.1
    • gcc: 12.2.0
  • C sürümü -march=native ile derlenerek belirli CPU’ya uygun kod üretmesi sağlandı
  • Benchmark, rastgele 'p' ve 's' karakterlerinden oluşan 1 milyon karakterlik bir listeyi hedef alıyor
    • Her fonksiyon sürümü bu listeyi 1000 kez işler
    • Her sürüm birden fazla kez çalıştırıldı ve en iyi sonuç seçildi
  • Devam yazısı olarak part two bağlantılı

İlgili okumalar

1 yorum

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

  • Doğru sonuç elle yazılmış assembly C'den 6 kat daha hızlıdır değil, daha çok dallanma koşullu aritmetikten çok daha yavaş olabilir olmalı
    C'de de switch kullanmayıp bir iki if ile işlenirse aynı etki kolayca elde edilebilir. C fonksiyonu s ise artır, p ise azalt, \0 ise bitir şeklinde değiştirildiğinde 5.5 kat hızlandı; örnek çalıştırmada da 3.58 saniyeden 0.65 saniyeye düştü

    • Güzel. 2. bölümde C yeniden yazılarak 12 kat hızlanma elde edildi: https://owen.cafe/posts/the-same-speed-as-c/
      Başkalarının da dediği gibi, girdi düzenlendikten sonra algoritma vektörize de edilebilir. Bunu eğitsel bir alıştırma olarak gördüm ve gerçekten iyi bir gerekçe olmadan assembly seviyesine inilmemesini içtenlikle umuyorum
    • Dallanma koşullu aritmetikten daha yavaştır sözü, dallanma tahmin edilemez olduğunda doğrudur. Dallanma tahmin edilebiliyorsa daha hızlıdır
      Linus da zamanında öngörülebilir dallanmalarda cmovun faydalı olmadığını uzun uzun yazmıştı: https://yarchive.net/comp/linux/cmov.html
    • Hangi GCC sürümünün kullanıldığını merak ediyorum. Ubuntu ve Windows'ta ikisinde de aynı performans çıktı; gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 ile lone ve ltwo ikisi de yaklaşık 3.58 saniyeydi
    • switchi birkaç if ile değiştirmenin her zaman daha hızlı olup olmadığını merak ediyorum. Hangi durum sayısından sonra switchin daha hızlı olduğunu da merak ediyorum ve eğer tutarlıysa bunun derleyici optimizasyonuna girmesi gerekir gibi görünüyor
    • Derleyicinin de bu düzeyde bir dönüşümü yapabilmesi gerekmez mi?

  • Bence özgün kod derleyici dostu yazılmamış. result += *s == 's'; result -= *s == 'p'; gibi yazılırsa derleyici uygun dallanmayan sete/cmov kodu üretir ve yazıdaki optimize assembly ile neredeyse aynı hıza ulaşır
    Yine de döngü açma veya vektörizasyon yapmaz. Dize boyutu ayrı verilerek size biliniyorsa derleyici döngü boyutunu bildiği için açma yapar ve mümkünse AVX-512 komutlarını da kullanır. Büyük girdilerde çok daha hızlıdır ama kendim benchmark yapmakla uğraşmak istemiyorum. Dize uzunluğunu takip etmeyen C programcıları canı ne isterse yapsın ama bence gerçekten yapmamalılar: https://godbolt.org/z/rde51zMd8

    • Derleyici dostu sürüm 2. bölümde var: https://owen.cafe/posts/the-same-speed-as-c/
      O sürüm 3.88GiB/s değerine ulaşıyor. Bilerek vektörizasyona kadar gitmedim; problemin kapsamını küçük tutup yazıdaki assembly ipuçları ve hilelerini göstermek istedim. Sonradan girdi dizesini padding yapıp algoritmayı vektörize etmeye dair bir yazı için alan var
    • Kodda önemli bir satır eksik: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • Nim'de de şu şekilde tetikleniyor gibi görünüyor: {.overflowChecks:off.} açılıyor ve input üzerinde dolaşırken 's' == c ise artırılıp 'p' == c ise azaltılıyor
      Apple M1'de yaklaşık 5 kat hızlanma görüldü; taşma kontrolleri açıkken ise temel C sürümüne göre yalnızca yaklaşık 2 kat daha hızlıydı. SIMD optimizasyonunu tetikleyen iyi desenleri bilmek her zaman faydalıdır
    • “Gerçekten yapmamalılar” ile kastedilen, dize uzunluğunu takip etmemek mi?

  • Optimizasyon uzmanına yakın bir bakış açısından ben bu problemi tamamen farklı çözerdim. Benim makinemde ilk C sürümü saniyede 389MB idi ve yazıdaki assembly aynı 6.2 kat artışı veriyorsa bu saniyede yaklaşık 2.4GB eder
    Uzun tamponlarda bu C++ sürümü benim makinemde saniyede 24GB'ı aşıyor: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    Assembly olmadan, AVX2 intrinsic tabanlı olarak özgün sürüme göre 61 kat hızlanıyor

    • İlginç. Sayacı ymm yazmaçlarında tutmak yerine movemask ve popcnt ile prologu vektörize etmek mümkün olabilir gibi görünüyor
      Henüz test edilmemiş bir kod, yani benchmark gerekir; ama s, p, \0 maskeleri oluşturup dizenin sonuna kadarki bitleri tzcnt ve bzhi ile sayma yaklaşımı mümkün görünüyor
    • Meraktan soruyorum, bunun std::experimental::simd ile de yapılıp yapılamayacağını bilmek isterim: https://en.cppreference.com/w/cpp/experimental/simd
    • Bunun @414owen deposuyla uyumlu bir biçimde yeniden yazılması iyi olabilir
    • AVX öğrenmek ve pratik yapmak için iyi kaynakları merak ediyorum

  • Bu kod SIMD için gerçekten çok uygun görünüyor. Prototip açık uzunluk alacak şekilde değiştirilebilirse 16 baytlık bloklar halinde okumak ve işlemek kolay olur
    Karşılaştırma sonuçları doğrudan toplanıp çıkarılabilir; fonksiyon başında strlen() çağırıp açık uzunluğu almak bile muhtemelen buna değer

  • Hızlıca bir RISC-V vektörize uygulaması yaptım. rvv ile dize okunuyor, \0 konumu bulunuyor, ardından s ve p sayıları vcpop ile sayılıyor
    Mangopi MQ Pro'da (C906, rv64gc + rvv 0.7.1, 128 bit vektör uzunluğu) switch 0.19 Bytes/Cycle, tablo tabanlı C uygulaması 0.17 Bytes/Cycle, rvv ise 1.57 Bytes/Cycle verdi ve yaklaşık 30KiB sonrasında 1.35'e düştü. İşaretçiyi sayfa hizalı yapıp vl değerini sayfa boyutundan büyük olmayacak şekilde tutarsanız 2/1.7 Bytes/Cycle da mümkün oluyor

    • Tamamen doğru olması için yüklemenin fault-only-first load olması gerekir. rvv bunu destekliyor; aksi halde null baytı ayrılmış belleğin sonundan hemen önceyse başarısız olabilir

  • Bu, x86 mimarisine özgü bir özellik gibi görünüyor. Dallanma yapmamanın maliyeti o kadar ucuz ki, dallanma görece pahalıymış gibi görünüyor: https://wordsandbuttons.online/challenge_your_performance_in...
    Ama diğer işlemcilerde durum böyle olmayabilir: https://wordsandbuttons.online/using_logical_operators_for_l...
    Daha büyük soru, genel olarak neden C'ye ihtiyaç duyulduğu. Eğer belirli bir donanımda en iyi çalışacak şekilde elle ayarlama yapacaksanız, C yanlış araçtır; assembly ve iyi bir makro sistemi gerekir. C'nin asıl hedefi, sistem seviyesindeki kodu bir platformdan diğerine taşımayı kolaylaştırmaktı ve bu süreçte verimlilik kaybı beklenen bir şeydi. Bu, Hintçe bir şiiri Urduca'ya çevirmek yerine Esperanto ile yazıp istenen dillere otomatik çeviri yapmak gibi. Ortaya iki harika şiir çıkmaz, ama iki düşük kaliteli çeviriyi hızlıca elde edersiniz; C'nin rolü de budur

  • FDO/PGO ile derlerseniz, dallanma ve blok yeniden düzenleme kesinlikle yapılabilir. FDO olmadan derleyici her dalın ne kadar sık seçileceğini bilemez. Bazı durumlarda FDO, cmov'u da etkinleştirebilir
    Yine de cmov'un sıradan test/jump'tan daha etkili olup olmadığı büyük ölçüde dallanmanın ne kadar öngörülebilir olduğuna bağlıdır ve genelde dallanma çok öngörülemez olduğunda cmov daha iyi çalışır. cmov ile 6 kat hızlandıysa, test girdisinin neredeyse tamamen s ve p'den oluşan rastgele dizeler olduğunu tahmin ediyorum. Bu yanlış değil ama yazı, verinin açıkça belirtilmemiş özelliklerini benchmark'a özel olarak kullanmış olduğu için biraz yanıltıcı olabilir

    • Test kodu burada: https://github.com/414owen/blog-code/blob/master/02-the-same...
      Rastgele 's' veya 'p' seçiliyor ve karakter olarak 's', 'p' ve sonlandırıcı null dışında başka bir şey gelemiyor. Bu girdi özelliğini biliyorsanız, result += (1 | *s++) - 'r'; gibi aşırı kurnaz bir optimizasyon bile mümkün. Fazla akıllı bir kod ama verinin özelliklerinden yararlanma fikrini mükemmel biçimde gösteriyor
    • Bir dize içinde '\0', fonksiyon geri döndüğü için en fazla bir kez görülebilir, ama diğer karakterler birden çok kez görülebilir. Bu bilgi, PGO olmadan da derleyicinin erişebileceği bir bilgi gibi görünüyor
      Elbette PGO yardımcı oluyor ve benim bilgisayarımda 2.80 saniye verdi; bu da Rearranging blocks bölümünün sonundaki koddn daha iyiydi. Girdi, Benchmarking setup bölümünde açıklanmış ve depoda da bulunuyor: https://github.com/414owen/blog-code/blob/master/01-six-time...
      Yazının sonunda bağlantısı verilen 2. bölümde, C kodunu olabildiğince hızlandırıp bu yazıdaki tüm assembly'leri geçiyor. Assembly yazmanın mutlaka iyi bir fikir olduğunu hiç söylemedim; optimizasyonu ve derleyici çıktısını çözümlemeyi ilginç bir meydan okuma ve iyi bir öğrenme fırsatı olarak görüyorum

  • Bunu, yazıdan ve devam yazısından daha hızlı yapmış gibi görünüyorum. Ama bunun bedeli, yalnızca 's' ve 'p''den oluşan dizelere özel hale gelmiş olması
    Benchmark da sadece 's' ve 'p''den oluşan dizeleri test ettiği için bunu adil buluyorum. Ana fikir şu: sonraki karakter s olduğunda res'i 1 artırmak istiyoruz, ama res += c - 'r' ifadesi s için 1 iken p için -2 oluyor ve başarısız oluyor. Ancak 'p' - 'r' işaretsiz tamsayı olarak ele alınırsa underflow oluşur ve carry flag ayarlanır; x64'te adc, iki register'ı ve carry flag'i birlikte toplar. Böylece iki cmp, cmov bir sub, adc ile değiştirilebilir. Bu sürüm, devam yazısındaki C sürümünden 1.08 kat, mevcut x64-7'den ise 1.66 kat daha hızlıydı. Elbette SWAR/SIMD ile daha da iyileştirilebilir

    • İlginç bir yaklaşım. 02-the-same-speed-as-c/loop-5.x64.s içindeki nispeten basit assembly'nin elimdeki en hızlı sürüm olduğunu açıkça belirtmem gerekirdi
      Benim bilgisayarımda loop-5.x64.s 0.244 saniye, yukarıdaki uygulama ise 0.422 saniye veriyor. Bu farkın nedenini tam bilmiyorum; görünüşte yukarıdaki uygulama daha hızlı olmalı. O yüzden her zaman gerçekten çalıştıracağınız donanım üzerinde benchmark yapmak gerekir
    • Daha basit bir yöntem olarak, dizideki tüm elemanları toplayıp en sonda 'p' * len çıkartabilir ve ('s' - 'p') ile bölerek s sayısını bulabilirsiniz. p sayısı da len - s_count olur
      İlk toplama işlemi de kolayca vektörleştirilebilir. Hata yapmadıysam çalışır; tek sorun biriken toplamın overflow ihtimali. Bunu bizzat benchmark etme motivasyonum yok. Düzeltme: s görüldüğünde azalan kısmı atlamışım, dolayısıyla nihai sonuç p_count - s_count

  • strlen() muhtemelen oldukça hızlı uygulanmıştır ve tampon boyutunu biliyorsanız derleyici iç döngüyü otomatik vektörleştirebilir
    Nitekim len = strlen(buf) sonrasında for döngüsünde (buf[i] == 's') - (buf[i] == 'p') toplamak otomatik vektörleştiriliyor: https://gcc.godbolt.org/z/qYfadPYoq

  • Bir zamanlar SBCL hedefleyerek Common Lisp UTF-8 decoder yazmıştım. Zaten yerleşik decoder vardı; bu daha çok egzersiz içindi
    Bariz kolay optimizasyonlar dışında, neredeyse tüm performans artışı derleyicinin dallanma yerine cmov* komutları üretmesini sağlayacak şekilde kodu yapılandırmaktan geldi

    • Kodu nasıl değiştirdiğinize dair bir örnek merak ediyorum. Ayrıca doğru komutların kullanıldığını görmek için fonksiyonun disassembly'sine tekrar tekrar baktınız mı, yoksa gerçek iyileşmeyi benchmark ile mi doğruladınız, onu da merak ediyorum
    • Eğer dallanma doğru tahmin ediliyorsa, koşullu taşıma komutundan daha hızlı olması muhtemeldir. Çünkü dallanma kritik yol uzunluğunu artırmaz
      UTF-8 decoder'lar genelde tamamen ASCII olan girdilerde çok çalıştırılır. Hangi girdilerle benchmark yaptığınızı merak ediyorum