Phân tích protobuf ở tốc độ hơn 2GB/s: vì sao tôi bắt đầu yêu tail calls trong C (2021)

• Tail Call: lời gọi hàm được thực hiện ngay trước khi hàm hiện tại trả về. Khi tối ưu hóa Tail Call xảy ra, lệnh jmp sẽ được dùng để giảm ngăn xếp lời gọi.
• Ưu điểm:
  • Giảm mức sử dụng bộ nhớ stack từ O(n) xuống O(1).
  • Loại bỏ overhead hiệu năng của lời gọi hàm, nhờ đó có thể dùng như một cấu trúc điều khiển lặp hiệu quả.

Vấn đề của vòng lặp thông dịch

• Vấn đề:
  • Khi hàm trở nên lớn hơn và luồng điều khiển phức tạp hơn, sẽ khó giữ dữ liệu quan trọng trong thanh ghi.
  • Nếu đường đi nhanh và đường đi chậm bị trộn lẫn, chất lượng mã sẽ suy giảm.

Cải thiện vòng lặp thông dịch bằng Tail Call

• Giải pháp: dùng Tail Call để tách mỗi tác vụ thành các hàm nhỏ, và mỗi hàm gọi tác vụ kế tiếp bằng Tail Call.
• Ưu điểm:
  • Có thể kiểm soát việc cấp phát thanh ghi.
  • Tách riêng đường đi nhanh và đường đi chậm để duy trì chất lượng mã.
  • Có thể tối ưu các chuỗi lệnh độc lập.

Giới hạn

• Vấn đề khi tồn tại non-tail call: nếu có non-tail call, stack frame sẽ được tạo ra và dữ liệu được lưu vào stack, làm giảm hiệu năng.
• Xử lý ngoại lệ phức tạp: khi xử lý ngoại lệ phức tạp, mã bị lặp lại và độ phức tạp tăng lên.
• Vấn đề tính di động: thuộc tính musttail không phải là tiêu chuẩn, nên không được mọi trình biên dịch hỗ trợ.

Tóm tắt của GN⁺

• Tối ưu hóa Tail Call đóng vai trò quan trọng trong việc cải thiện hiệu năng, đặc biệt cho phân tích Protobuf.
• Kỹ thuật này cũng có thể áp dụng cho các trình thông dịch ngôn ngữ lớn được viết bằng C (Python, Ruby, PHP, Lua, v.v.).
• Vấn đề tính di động của thuộc tính musttail là một thách thức cần được giải quyết.
• Các dự án cung cấp tính năng tương tự gồm có LuaJIT, trình thông dịch WebAssembly wasm3, v.v.

[GN⁺]

Ý kiến trên Hacker News

• Bản đề xuất tiêu chuẩn C có bao gồm tail call dưới dạng return goto (expression);

  • So với việc chuẩn hóa [[musttail]], cách này đảm bảo vòng đời của đối tượng cục bộ và không cần phân tích escape trên diện rộng

• Với những người yêu thích Rust, đã từng có một RFC cũ đề xuất thêm từ khóa become

  • Nó đã bị hoãn để tập trung vào mục tiêu của bản 2018 edition, nhưng gần đây lại được đem ra thảo luận
  • Có khả năng nó sẽ quay trở lại

• Trong C++, cách các trình thông dịch tăng tốc chủ yếu là dùng computed goto

  • Có thể tránh được các vấn đề về calling convention
  • Dùng kiểu computed goto hoặc kiểu tail call có thể làm giảm áp lực lên bộ dự đoán nhánh

• Vấn đề chuyển đổi ngữ cảnh bằng tail call đòi hỏi các hàm dùng calling convention

  • Điều này làm lãng phí thanh ghi để khôi phục trạng thái khi hàm kết thúc
  • Blog remake của luajit đưa ra các phương án thay thế và phân tích

• Hy vọng thuộc tính [[musttail]] sẽ được phổ biến sang GCC, Visual C++ và các trình biên dịch phổ biến khác

  • Thuộc tính [[musttail]] đang trong quá trình được thêm vào GCC

• Có đề cập đến hỗ trợ C++, đồng thời chỉ ra rằng trong C++ hầu như không có tail call

  • Ví dụ, trả về một đối tượng của lớp có destructor thì không phải là tail call

• Có người thắc mắc điều gì xảy ra nếu ném ngoại lệ trong hàm C++ [[musttail]]

  • Họ đặt câu hỏi liệu ngăn xếp ngoại lệ có bị tách rời hoàn toàn hay không

• Có nhắc rằng với các ví dụ đơn giản thì không cần __attribute__((musttail)) để sinh mã tốt

  • Họ có lẽ sẽ không quá bận tâm đến tốc độ gọi hàm xử lý lỗi
  • Một số cấu trúc cụ thể có thể tạo ra jump table đáng tin cậy

• Có người tò mò về tốc độ của cách dùng trampoline để gọi con trỏ hàm được trả về trong một vòng lặp bên ngoài

  • Cách này có ưu điểm là C thuần có tính di động

• Có yêu cầu làm rõ ví dụ về đường đi ngoại lệ được bọc bằng [[musttail]]

  • Giải thích rằng [[musttail]] ngăn việc dựng stack frame và register spilling
  • Việc dựng stack frame và register spilling chỉ xảy ra khi đường đi ngoại lệ thực sự được gọi
  • Vì đường đi ngoại lệ hiếm khi được gọi nên nó không ảnh hưởng nhiều đến hiệu năng
  • Do hiệu ứng dự đoán nhánh, khả năng phải làm thêm việc có thể khiến đường đi nhanh bị chậm lại