AMD64'te 16 bayttan büyük struct'lar geçirmeyin

• Neat'in related_post_gen benchmark sıralamasındaki yükselişi, yüksek seviyeli bir optimizasyondan değil, dizileri 24 baytlık bir struct yerine 3 pointer argümanı olarak geçiren küçük bir ABI değişikliğinden geldi
• Neat dizileri, referans sayımı nedeniyle başlangıç ve bitiş pointer'larına ek olarak dizi nesnesi tabanlı bir pointer'a ihtiyaç duyuyor; bu yüzden D dilindeki 16 baytlık dizilerden farklı olarak SystemV AMD64 ABI'nin bellekten geçirme yoluna giriyor
• 16 baytı aşan belirli aggregate türleri, çağrı sırasında değeri stack'e kopyalayıp ardından pointer ile geçirilir; bu da register ile geçirme avantajını kaybettirir ve stack shuffle maliyetini artırır
• Örnek benchmark'ta struct Vector { double x, y, z; } struct'ını doğrudan geçirmek, 1 milyar çalıştırmada 12.3 saniye sürerken, alanları ayrı argümanlar olarak geçirmek bunu 5.3 saniyeye düşürüyor
• C API'leri C ABI'ye uymalıdır; ancak dil çalışma zamanı içindeki array, tuple, sumtype gibi türler 16 baytı aştığında alanlara ayrılmış geçirme yaklaşımını benchmark etmeye değer

---

Neat'te ortaya çıkan darboğaz

• Neat, related_post_gen benchmark'ında birkaç basamak yükseldi
• Performans artışı, yeni bir yüksek seviyeli optimizasyon pass'inden değil, dizi geçirme biçimini değiştirmekten kaynaklandı
  • Önceki: 3 pointer içeren struct argümanı
  • Sonraki: 3 pointer'ı ayrı ayrı argüman olarak geçirmek
• Neat, D ile karşılaştırıldığında beklenenden daha yavaştı ve profiler'da fonksiyon çağrıları için stack'in büyük bölümlerinin taşındığı görülüyordu
• Darboğaz, hesabın kendisinden çok çağrı anındaki stack yeniden düzenleme maliyetine yakındı

Neat dizileri neden 24 bayt oluyor

• D dizilerinden farklı olarak Neat, referans sayımı kullanıyor
• Neat dizisi şu 3 pointer'ı içeriyor
  • başlangıç pointer'ı
  • bitiş pointer'ı
  • referans sayısının tutulduğu dizi nesnesi tabanlı pointer
• 3 pointer 24 bayt ettiğinden, 2 pointer'lı 16 baytlık dizilerden farklı bir AMD64 argüman geçirme yoluna giriyor
• D dizilerinin hızlı, Neat dizilerinin yavaş olmasının nedeni, 24 bayta çıkıp 16 bayt sınırını aşmalarıydı

SystemV AMD64 ABI'deki 16 bayt sınırı

• SystemV AMD64 ABI specification, belirli aggregate boyutları iki adet eightbyte'ı aşarsa tüm argümanın bellek üzerinden geçirilmesini şart koşuyor
• Bir struct'ı bellek üzerinden geçirmek için çağıran tarafta şu işlemler gerekir
  • stack üzerinde struct boyutu kadar yer ayırmak
  • bu alanı geçirilecek değerle doldurmak
  • fonksiyona bu struct konumunun pointer'ını vermek
• Bu durumda değer mutlaka stack üzerinde bulunmak zorundadır; bu da LLVM'nin optimizasyon alanını daraltır
• Değer register'lardan stack'e kopyalanmalıdır; ayrıca stack'in hangi kısmının kullanımda olduğu ve hangi kısmının yeniden kullanılabileceği de takip edilmelidir
• LLVM özellikle bu stack yeniden kullanım takibinde iyi bir performans göstermedi

3 double vektör benchmark'ı

• Benchmark, struct Vector { TYPE x, y, z; }; biçiminde 3 alanlı bir vektör kullanıyor
• TYPE, double olarak tanımlanıyor
• İki fonksiyon aynı toplama işlemini yapıyor, ancak argüman geçirme biçimleri farklı
  • vector_add_struct(struct Vector left, struct Vector right) büyük struct'ları argüman olarak alıyor
  • vector_add_fields(...) ise left_x, left_y, left_z, right_x, right_y, right_z değerlerini ayrı ayrı argüman olarak alıyor
• mode ve çalışma süresi komut satırı argümanlarıyla alınıyor; böylece optimizer tüm hesabı constant folding ile sadeleştiremiyor
• impl.c, inlining'i önlemek için ayrı derleniyor

clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000

• Sonuçlar, struct geçirme sürümünde 12.3 saniye, alanları ayrı geçirme sürümünde ise 5.3 saniye oldu

Assembly'de görülen fark

• Struct geçirme sürümü birçok komutu stack shuffle için harcıyor
• Alan bazlı sürüm, parametrelerin fonksiyona girerken zaten SSE register'larında bulunması sayesinde avantajlı
• Struct geçirme sürümünde değerlerin her seferinde stack'ten yüklenmesi gerekiyor
• SystemV ABI, değerleri mümkün olduğunca register üzerinden geçirmeyi amaçlıyor; ancak bu örnekte 16 baytı aşan struct nedeniyle bu avantaj ortadan kalkıyor
• AMD64'te kullanılabilir register sayısı düşünüldüğünde, 16 baytı aşan türlerde de değerle geçirme yararlı olabilirdi

cdecl'e benzer hale gelen durum

• Alanları stack'e yazıp pointer geçirmek, sonuçta her şeyi stack üzerinden geçiren eski x86 cdecl ABI'sine benziyor
• cdecl'in yavaş olduğu biliniyordu ve bunu hızlandırmak için çeşitli çağrı kuralları ortaya çıktı
• Sorun, AMD64 System V ABI'nin struct boyutu yüzünden bu durumda eski stack geçirme yöntemine benzer davranması

Inlining ve LTO istisnası

• Gerçek kodda bu tür fonksiyonların tamamı inline edilebilir
• gcc'de LTO açıldığında iki sürüm arasındaki performans farkı kayboluyor
• clang'de ise aynı sonuç elde edilmiyor
• Her fonksiyonun inline edilebilmesi ya da edilmesi gerekmez

Dil geliştiricileri ve API optimizasyonu için öneri

• C API çağrılarında C ABI izlenmelidir
• Ancak C dışı dillerin içindeki yüksek seviyeli türlerin, backend'e struct gibi görünseler bile mutlaka tek bir struct olarak temsil edilmeleri gerekmez
• Dil geliştiricileri, array, tuple, sumtype gibi yapıların nasıl geçirileceğine kendileri karar verebilir
• Neat'te 16 baytı aşan bu türlerin ayrı alanlar halinde geçirilmesi seçildi ve benchmark'ta faydası görüldü
• AMD64 üzerinde dil implementasyonu yapıyor ya da bir API'yi mikro düzeyde optimize ediyorsanız, 16 baytı aşan struct'ları elle bölmenin işe yarayıp yaramadığını benchmark etmeniz gerekir
• Özellikle iç döngülerde performans farkı beklenenden büyük olabilir

Ek: double struct'ı ve SSE

• Soru şu: double teknik olarak SSE sınıfında ise neden struct SSE register'larıyla geçirilmiyor?
• Cevap ise şu: nedeni bilinmiyor, ama pratikte gerçekten böyle geçirilmiyor

[GN⁺]

Hacker News yorumları

• Buradaki sorun SysV amd64 ABI. Dilin dahili ABI’si olarak SysV kullanmak zorunda değilsiniz. SysV C çağıranlarına açılmıyorsa istediğiniz çağrı kuralını kullanabilirsiniz.
  https://llvm.org/docs/LangRef.html#calling-conventions
  Merak edenler için neatlang’deki ilgili değişiklik burada: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
  Yalnızca LLVM çağrı kuralı çıktısını değiştirmekten çok daha karmaşık görünüyor. Muhtemelen yazar bu tipleri C programlarına deterministik bir çağrı kuralıyla açmak istemiş.

  • Aslında genel olarak ABI’lerin tamamı için böyle denebilir. Assembly programcısıysanız bilirsiniz; bu, derleyiciyi kolayca yenebileceğiniz alçakta duran meyvelerden biridir.
    Gelenekleri körü körüne izlemek yerine, belirli durumda en mantıklı olan yöntemi seçmek yeterli.
  • Aklıma gelen ilk sorunun yanıtı zaten varmış. Uzun zaman önce oluşturulmuş ABI gibi şeylere pek çok şeyin uyması ilginç.
    Özellikle ABI’ler çoğu zaman daha eski CPU’larla uyumluluğa eğilimlidir; daha yeni CPU’larda ise genişletilmiş register’lar gibi özellikler kullanılarak yapı boyutunu küçültmeden de iyileştirme alanı olabilir. Belirli donanım veya nesle göre ayarlanmış yazılım bazı makinelerde kullanılamayacağı için pek cazip olmayabilir; ama kendi sisteminizin donanım özelliklerine göre kodu aşırı optimize etmek istediğinizde böyle çıktı üretebilen bir derleyici harika olurdu.

• Argüman aktarma maliyeti çoğu zaman iyi anlaşılmıyor; bu yüzden böyle yazılar sevindirici. Google gibi yerlerde bile 24 baytlık nesnelerin değer olarak geçirilmesi yaygın ve bunun maliyeti tüm fonksiyonlara genişçe yayıldığı için profiler’da pek görünmüyor.

  • Değerle geçirme ve referansla geçirme fiilen ABI/API’yi etkilediğinden epey büyük bir bilişsel yük oluşturur. Zig bunu dayatmamaya çalışıyor; bu yüzden “değer olarak geçirseniz” bile derleyici gerçekte referansla geçirmeye karar verebilir.
    Ancak bu tür pürüzler de ortaya çıkıyor: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
  • “Google gibi yerler” derken, bizzat yaşadığın bir şey mi? Eski bir Googler olarak net söyleyebilirim: ilkel tip olmayan şeylerin pointer veya referansla geçirilmesi yönünde bir kılavuz var.
    Aklıma gelen tek istisna string_view civarı.
  • Çağrı kuralına gömülüymüş gibi geniş biçimde dağılmış overhead’in profiling ile neredeyse bulunamamasına dikkat çekmesi iyi.
  • 24 baytlık bir nesneyi bunun yerine pointer ile geçirirseniz, o nesneyi gerçekten kullanmanız gerektiğinde pointer’ı dereference etmeniz gerekir; bu da bir trade-off. Üstelik nesnenin yakında olduğunun garantisi yok.
    Şanssızsanız cache miss oluşur ve ana bellekten 24 baytlık nesnenin getirilmesini yaklaşık 100 nanosaniye bekleyebilirsiniz. Aynı nesne doğrudan geçirilirse stack’te olacağından cache’te olma ihtimali yüksektir.
  • C++ ABI’nin de her çağrıda 24 baytlık nesneleri stack’e döküp dökmediğini merak ediyorum. std::string veya std::function parametrelerinin hızlı olmasını beklemem ama yine de şaşırtıcı.

• x64’e ilk geçtiğimizde grafiklerdeki vec3 nesnesinin (3 float) sizeof()=12 değil de 16 bayta büyümesinden endişelenip grafik motorunu epey benchmark ettim.
  Şaşırtıcı olmayan şekilde, 8 baytlık okuma hizalaması sayesinde 16 bayt 12 bayttan daha hızlıydı. Hem dahili olarak hem de GPU’da böyleydi. Bu yüzden vec3 sessizce vec4 oldu; ayrıca ayrı bir vec4 de hâlâ var. Her zamanki gibi yerel benchmark değil, bütüncül bakış açısıyla benchmark yapmak gerekir.

  • SSE boyutuyla da iyi örtüşen çok güzel bir yan etkisi var. Böylece _mm_load_ps doğrudan kullanılabiliyor, kod daha temiz hale geliyor ve vektörleştirme de çok kolaylaşıyor.
  • Muhtemelen çok daha hızlı değildir. Ayrıca bu veriyle ne yaptığınızdan bağımsız olarak CPU’ya da çok bağlı değil mi diye düşünüyorum.
    16 bayt olduğunda birçok erişimin 3x4 bayt yerine hizalanmış 2x8 bayt veya 1x16 bayt olabileceğini anlıyorum. Ama başka erişimlerde bu daha az geçerli olabilir ve cache baskısının artması sorunu da var.
  • x64 ABI, x86 ABI’den de epey daha iyi.

• Sağduyuya göre, register’larda geçirilen değerler spekülatif yürütme sayesinde önceden yüklenebildiği için stack yazmaktan daha hızlıdır; stack manipülasyonu da heap allocation’dan hızlıdır.
  Bu yüzden bolca global değişken içeren dağınık spaghetti code inanılmaz hızlıdır; zarif recursive fonksiyonlar veya tuple/struct/list argümanları ise inanılması güç derecede yavaştır. İlki sıkı assembly döngülerine optimize etmek için çok daha kolaydır.

  • Elbette o spaghetti code’un zarif kodla aynı algoritmayı uyguladığı varsayımı gerekir.
    Zarif kod O(n), spaghetti code O(n^2) ise farkı hissedebilirsiniz. Bakım yapılabilirliği de hesaba katmak gerekir. Bir anlamda derleyiciler, bizim zarif çözümlerimizi spaghetti code’a dönüştürmek için vardır.
  • “Parametreleri stack yerine register ile geçir” sağduyuya yakındır; ama “16 bayttan büyük parametreler her zaman stack üzerinden geçirilir” bunun kadar açık değildir.
  • Günümüzde bazı CPU’lar bellek yeniden adlandırması yapabildiği için stack’e dökmenin maliyeti daha ucuz olabilir.
    Global nesneler derleyici optimizasyonlarını da engeller.

• Referans olarak, MSVC’de struct’lar stack üzerinden geçirilmeden önceki eşik boyut 8 bayttır. Bu bir ABI ayrıntısıdır; taşınabilir kodda buna güvenmemek gerekir.
  Ama sık çağrılmayan bir fonksiyonsa fazla stres yapmaya gerek yok. Örnekteki gibi sık çağrılan küçük bir fonksiyonsa, LTO gibi yöntemlerle derleyicinin kodu inline edebilmesini sağlayın. Böylece argümanları register’dan geçirmekten çok daha faydalı optimizasyonların önü açılır.

• Bu tür yazıları “baş belası olmaya tam yetecek kadar bilgi” kategorisine koyuyorum. Talimatlara uyup ayrı derleyerek derleyiciyi ABI üzerinden çağrılabilir bir fonksiyon üretmeye zorlasanız bile, LTO bu hatayı geri alabilir.
  Bu program LTO ile derlendiğinde, LTO’suz programın herhangi bir moduna kıyasla her iki modda da dramatik biçimde hızlanıyor. Performansa duyarlı bir programsa profil çıkarıp, darboğazı sonuna kadar optimize ettikten sonra ancak yapıları argümanlara parçalama gibi işleri commit etmek gerekir.

  • İyi bir tavsiye ama bu tür şeyleri görünür kılan bir derleyiciye henüz rastlamadım. Öncelikle bu etki kod tabanının geneline dağılmış durumda; şans eseri bir hot spot haline gelmedikçe etkisini gösteren bir profiler da görmedim.
    Bu, neredeyse tüm derleyici üretimi kodlar için geçerli. Valgrind ölçebilir ama örneklemeli profiler muhtemelen ölçemez; dağınık kod üretimi sorunlarını öne çıkaran bir araç da yok.
  • Üstelik performansın mutlak öneminden bahsederken referans sayımı kullanıyorlar.

• Windows’un varsayılan cdecl çağrı kuralında, 8 bayttan büyük yapılar register üzerinden geçirilmez [1]
  [1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

• amd64 üzerinde SysV amd64 ABI kullansanız bile 16 bayttan büyük yapıları değer olarak geçirmek ve döndürmek tamamen mümkündür. Sadece yavaştır.
  Yine de kodu daha anlaşılır kılmak için değerle aktarmanın çoğu zaman değdiği durumlar vardır. Elbette bu örnekte değil; ama loeg’in işaret ettiği gibi, kendi dilinizin içinde C++ derleyicileri, Go, OCaml ve SBCL gibi kullanıcı tanımlı ABI kullanabilirsiniz.

• Verilen örnekte, çağıran tarafı etkilemeden parametre tipini “struct Vector”dan “const struct Vector &”a değiştirip referansla geçirme yaparak düzeltmek mümkün.
  İşaretçi hataları olan pek çok C++ kodunun gereksiz yere işaretçi kullandığını; oysa referansla geçirmenin yeterli olup daha kolay ve güvenli kullanılabileceğini çok gördüm.

  • Hayır. Aslında burada asıl mesele tam da bu. ABI sayesinde derleyici pratikte tam olarak bunu yapıyor.
    ABI, değerin işaretçiyle geçirilmesini söylediği için, işaretçiyi elde etmek üzere değeri bir yere kaydetmek gerekiyor; const-ref olarak açıkça yazdığınızda olanla aynı şey yaşanıyor. Yapı değerini ayrı argümanlara çevirirseniz argümanları register üzerinden geçirebilirsiniz.
  • Bu sorunu fark ettiğimde, byval için işaretçi geçirmek üzere yirmi otuz tane alloca içeren bir koddu. Her fonksiyon, çağrıya geçirilen her parametre için ayrı bir alloca ile başlıyordu.
    LLVM’in bu tür şeyleri iyi temizleyeceğini hep bir ölçüde varsaymıştım; meğer öyle değilmiş.
  • Yine de yapı işaretçisini çağrılan fonksiyona geçirmek için derleyicinin üç register’ı stack’e serileştirmesi gerekir.
    Anlatılan avantaj, register’dan stack’e serileştirmeyi tamamen önlemek; referansla geçirme bunu önleyemiyor gibi görünüyor.
  • Bu bir C++ örneği değil, C99 örneğiydi. Pek çok ortamda, asgari düzeydeki atalet yüzünden araçları istediğiniz gibi değiştiremezsiniz.
    C++’a izin verirseniz kopyalamayı azaltmaya yönelik move argümanları gibi daha fazla seçeneğiniz olur.

• C++’ta hep duyduğum temel kural şu: ilkel tip olmayan şeyleri, değer olarak geçirmek için iyi bir neden yoksa referansla; gerçekten gerekiyorsa işaretçiyle geçirin.
  Bu hem ABI yüzünden, hem de kopya oluşturucuları veya move oluşturucuları önlemek içindir. Sıkıcı düşük seviye ayrıntılar ama C++’ta en yüksek performansı istiyorsanız önemsemeniz gereken şeyler. Açık olmak gerekirse bu yalnızca bir performans optimizasyonudur; yapı geçiren kod doğru çalışır, sadece daha az hızlıdır.