2GB/s'nin üzerindeki hızlarda protobuf ayrıştırma: C dilinde tail call'ları sevmemin nedeni (2021)

• Tail Call: Bir fonksiyonun dönmeden hemen önce yaptığı fonksiyon çağrısı. Tail Call optimizasyonu gerçekleştiğinde jmp komutu kullanılır ve çağrı yığını küçülür.
• Avantajları:
  • Yığın belleği kullanımını O(n)'den O(1)'e düşürür.
  • Fonksiyon çağrısının performans ek yükünü ortadan kaldırarak verimli bir yineleme kontrol yapısı olarak kullanılabilir.

Yorumlayıcı döngüsünün sorunları

• Sorunlar:
  • Fonksiyon büyüdükçe ve kontrol akışı karmaşıklaştıkça önemli verileri register'larda tutmak zorlaşır.
  • Hızlı yol ile yavaş yol karıştığında kod kalitesi düşer.

Tail Call kullanarak yorumlayıcı döngüsünü iyileştirme

• Çözüm: Tail Call kullanarak her işi küçük fonksiyonlara ayırmak ve her fonksiyonun bir sonraki işi Tail Call ile çağırmasını sağlamak.
• Avantajları:
  • Register atamasını kontrol edebilirsiniz.
  • Hızlı yol ile yavaş yolu ayırarak kod kalitesi korunur.
  • Bağımsız komut dizileri optimize edilebilir.

Sınırlamalar

• Tail Call olmayan çağrılar varsa sorun: Tail Call olmayan çağrılar varsa stack frame oluşturulur ve veriler yığına yazılır; bu da performansı düşürür.
• Karmaşık exception handling: Exception handling karmaşık olduğunda kod tekrarı ve karmaşıklık artar.
• Taşınabilirlik sorunu: musttail özniteliği standart olmadığından tüm derleyiciler tarafından desteklenmez.

GN⁺ Özeti

• Tail Call optimizasyonu performans artışında önemli rol oynar ve özellikle Protobuf ayrıştırmada büyük başarı sağlar.
• Bu teknik, C ile yazılmış başlıca dil yorumlayıcılarına da uygulanabilir (Python, Ruby, PHP, Lua vb.).
• musttail özniteliğinin taşınabilirlik sorunu çözülmesi gereken bir konu.
• Benzer işlev sunan projeler arasında LuaJIT ve wasm3 WebAssembly yorumlayıcısı bulunur.

[GN⁺]

Hacker News görüşleri

• C standart önerisi, return goto (expression); biçiminde tail call içeriyor

  • [[musttail]] özelliğini standartlaştırmaya kıyasla, yerel nesnelerin ömrü garanti edildiği için kapsamlı escape analysis gerektirmiyor

• Rust meraklıları için become anahtar sözcüğünü ekleyen eski bir RFC vardı

  • 2018 edition hedeflerine odaklanmak için ertelenmişti ancak son dönemde yeniden tartışılıyor
  • Yeniden ortaya çıkma ihtimali var

• C++'ta yorumlayıcıların hız kazanma yöntemi çoğunlukla computed goto kullanmak

  • Calling convention sorunlarından kaçınılabiliyor
  • Computed goto tarzı ya da tail-call tarzı kullanıldığında branch predictor üzerindeki baskı azaltılabiliyor

• Tail call kullanarak context switch yapma sorunu, calling convention kullanan bir fonksiyon gerektiriyor

  • Fonksiyon çıkışında durumu geri yüklemek için register harcanıyor
  • luajit remake blogu alternatifler ve analiz sunuyor

• [[musttail]] özniteliğinin GCC, Visual C++ ve diğer popüler derleyicilere yayılacağı umuluyor

  • [[musttail]] özniteliği GCC'ye eklenme sürecinde

• C++ desteğinden söz edilirken, C++'ta tail call'ın neredeyse hiç olmadığına dikkat çekiliyor

  • Örneğin destructor'ı olan bir sınıfın nesnesi döndürülüyorsa bu bir tail call değil

• C++ [[musttail]] fonksiyonunda exception fırlatılırsa ne olacağı merak ediliyor

  • Exception stack'inin tamamen ayrılıp ayrılmadığı soruluyor

• Basit örneklerde iyi code generation için __attribute__((musttail)) gerekmediği belirtiliyor

  • Hata işleme fonksiyonu çağrısının hızının çok da önemsenmeyeceği söyleniyor
  • Belirli bir yapının güvenilir bir jump table ürettiği ifade ediliyor

• Trampoline kullanarak dönen function pointer'ı dış döngüde çağırma yaklaşımının ne kadar hızlı olduğu merak ediliyor

  • Bu yaklaşım, taşınabilir C avantajı sunuyor

• [[musttail]] ile sarmalanmış exception path örneğinin netleştirilmesi isteniyor

  • [[musttail]] özelliğinin stack frame kurulumu ve register spilling'i neden engellediği açıklanıyor
  • Stack frame kurulumu ve register spilling yalnızca exception path gerçekten çağrıldığında ortaya çıkıyor
  • Exception path nadiren çağrıldığı için performansa büyük etkisi olmuyor
  • Branch prediction etkisi nedeniyle ek iş olasılığı fast path'i yavaşlatabiliyor