Mengurai protobuf dengan kecepatan lebih dari 2GB/s: alasan saya jadi menyukai tail call di bahasa C (2021)

• Tail Call: pemanggilan fungsi yang dilakukan tepat sebelum fungsi melakukan return. Jika optimasi Tail Call terjadi, instruksi jmp digunakan sehingga mengurangi call stack.
• Kelebihan:
  • Mengurangi penggunaan memori stack dari O(n) menjadi O(1).
  • Menghilangkan overhead kinerja dari pemanggilan fungsi sehingga bisa digunakan sebagai struktur kontrol perulangan yang efisien.

Masalah pada loop interpreter

• Masalah:
  • Semakin besar fungsi dan semakin kompleks alur kontrolnya, semakin sulit mempertahankan data penting di register.
  • Jika jalur cepat dan jalur lambat bercampur, kualitas kode menurun.

Peningkatan loop interpreter dengan memanfaatkan Tail Call

• Solusi: gunakan Tail Call untuk memisahkan setiap tugas menjadi fungsi-fungsi kecil, lalu setiap fungsi memanggil tugas berikutnya dengan Tail Call.
• Kelebihan:
  • Alokasi register dapat dikendalikan.
  • Jalur cepat dan jalur lambat dapat dipisahkan untuk menjaga kualitas kode.
  • Urutan instruksi yang independen dapat dioptimalkan.

Keterbatasan

• Masalah saat ada non-Tail Call: jika ada non-Tail Call, stack frame akan dibuat dan data disimpan ke stack sehingga kinerja menurun.
• Penanganan eksepsi yang kompleks: jika penanganan eksepsi rumit, duplikasi kode dan kompleksitas meningkat.
• Masalah portabilitas: atribut musttail bukan standar, sehingga tidak didukung oleh semua compiler.

Ringkasan GN⁺

• Optimasi Tail Call berperan penting dalam peningkatan kinerja, terutama menunjukkan hasil besar pada parsing Protobuf.
• Teknik ini juga dapat diterapkan pada interpreter bahasa utama yang ditulis dalam C (Python, Ruby, PHP, Lua, dll.).
• Masalah portabilitas atribut musttail adalah tantangan yang perlu diselesaikan.
• Proyek dengan fungsi serupa mencakup LuaJIT dan interpreter WebAssembly wasm3.

[GN⁺]

Komentar Hacker News

• Proposal standar C mencakup tail call dalam bentuk return goto (expression);

  • Dibanding menstandardkan [[musttail]], cara ini menjamin masa hidup objek lokal sehingga tidak memerlukan analisis escape yang luas

• Untuk para penggemar Rust, pernah ada RFC lama untuk menambahkan kata kunci become

  • Ditunda agar fokus pada target edisi 2018, tetapi belakangan kembali dibahas
  • Ada kemungkinan akan muncul lagi

• Di C++, cara interpreter meningkatkan kecepatan umumnya adalah dengan menggunakan computed goto

  • Bisa menghindari masalah calling convention
  • Menggunakan gaya computed goto atau gaya tail dapat mengurangi tekanan pada branch predictor

• Masalah berpindah konteks dengan menggunakan tail call memerlukan fungsi yang memakai calling convention

  • Ini memboroskan register untuk memulihkan status saat fungsi berakhir
  • Blog remake luajit memberikan alternatif dan analisis

• Berharap atribut [[musttail]] menyebar ke GCC, Visual C++, dan compiler populer lainnya

  • Atribut [[musttail]] sedang dalam proses ditambahkan ke GCC

• Menyebut dukungan C++, sambil menunjukkan bahwa di C++ hampir tidak ada tail call

  • Misalnya, mengembalikan objek dari kelas yang memiliki destruktor bukanlah tail call

• Bertanya-tanya apa yang terjadi jika melempar exception di fungsi C++ [[musttail]]

  • Menanyakan apakah stack exception menjadi sepenuhnya terpisah

• Menyebut bahwa contoh sederhana tidak memerlukan __attribute__((musttail)) untuk menghasilkan kode yang baik

  • Tidak akan terlalu peduli pada kecepatan pemanggilan fungsi penanganan error
  • Struktur tertentu menghasilkan jump table yang andal

• Penasaran dengan kecepatan pendekatan yang memakai trampolin, di mana function pointer yang dikembalikan dipanggil oleh loop eksternal

  • Pendekatan ini memiliki keunggulan berupa C yang portabel

• Ada permintaan untuk memperjelas contoh jalur exception yang dibungkus dengan [[musttail]]

  • Dijelaskan bahwa [[musttail]] mencegah pembentukan stack frame dan register spilling
  • Pembentukan stack frame dan register spilling hanya terjadi saat jalur exception benar-benar dipanggil
  • Karena jalur exception jarang dipanggil, dampaknya pada performa tidak besar
  • Karena efek branch prediction, kemungkinan adanya pekerjaan tambahan dapat memperlambat jalur cepat