Tối ưu xuyên file

Ở bài về đơn vị dịch ta thấy mỗi file .c được biên dịch độc lập thành một .o, và trình biên dịch không hề nhìn thấy nội dung các file khác. Hệ quả: một hàm nhỏ, nóng, định nghĩa ở file này mà được gọi từ file kia thì không nội tuyến được — vì lúc dịch file gọi, trình biên dịch chưa biết thân hàm trông ra sao. Tối ưu xuyên file (link-time optimization, LTO) sinh ra để phá đúng rào này. Bài này biên dịch một chương trình hai file, đo -flto giúp nhanh bao nhiêu, đọc assembly để biết vì sao — và phát hiện cái lợi thật không nằm ở chỗ tôi tưởng.

LTO dời tối ưu tới lúc link

Bình thường, gcc -O2 -c hot.c -o hot.o sinh ra mã máy hoàn chỉnh cho hot.c; lúc này mọi lời gọi tới hàm ở file khác đã đóng băng thành lệnh gọi thật (bl trên aarch64). Trình liên kết (linker) sau đó chỉ nối các .o lại và điền địa chỉ — nó không tối ưu gì.

-flto thay đổi luật chơi: khi biên dịch mỗi .c, trình biên dịch không sinh mã máy cuối cùng mà nhét một biểu diễn trung gian (bytecode nội bộ) vào .o. Tối ưu thật sự bị hoãn tới lúc link, khi trình liên kết đã có biểu diễn của toàn bộ chương trình trong tay. Lúc đó nó thấy thân của mọi hàm ở mọi file, nên có thể nội tuyến một hàm từ sq.c thẳng vào vòng lặp ở hot.c, truyền hằng số xuyên file, loại mã chết xuyên file — những việc bất khả khi mỗi file bị nhìn riêng lẻ.

Đo: nhanh gần ba lần

Tôi dựng hai file. sq.c định nghĩa long sq(long x){ return x*x; }. hot.c có một vòng lặp cộng dồn sq(a[i]) trên mảng 20 triệu phần tử, và chỉ khai báo sq chứ không định nghĩa — thân hàm nằm ở file kia. Tôi biên dịch theo hai cách, ghim vào một lõi bằng taskset -c 0, đo năm lần lấy nhỏ nhất:

Nhanh 2,9 lần, và kết quả tính ra y hệt (tôi in một giá trị kiểm tra, hai bên khớp nhau). Chỉ thêm một cờ -flto mà một vòng lặp gọi hàm xuyên file rút gần một phần ba thời gian. Câu hỏi thú vị hơn con số: nhanh nhờ đâu?

Đọc assembly: hàm gọi biến mất, và còn hơn thế

Bản không LTO, đọc objdump -d vòng compute:

ldr  x0, [x19], #8      ; nạp a[i]
bl   4008d0 <sq>        ; GỌI sq — xuyên file, không nội tuyến được
add  x20, x20, x0       ; s += kết quả
cmp  x19, x21
b.ne ...                ; lặp

Đúng như dự đoán: một lời gọi bl <sq> thật, mỗi vòng một lần, xử lý từng phần tử một — một vòng lặp vô hướng (scalar).

Bản có LTO, tôi tìm lời gọi và cả ký hiệu hàm:

bl tới <sq>   : 0
ký hiệu <sq>  : 0   (hàm biến mất khỏi binary)
vòng nóng     : ldr q1, [x0, ...]   (nạp thanh ghi vector 128-bit)

Hai điều xảy ra. Thứ nhất, sq được nội tuyến tới mức nó không còn tồn tại như một hàm riêng — trình liên kết thấy cả chương trình, biết sq chỉ được dùng nội tuyến, nên xóa hẳn bản độc lập (loại mã chết xuyên file). Thứ hai — và đây mới là điều đáng chú ý — vòng nóng giờ dùng ldr q1, một lệnh nạp vào thanh ghi vector 128-bit: vòng lặp đã được vector hóa, xử lý nhiều phần tử cùng một nhịp.

Một lần tôi đo hớ: quy cái nhanh cho nhầm thứ

Khi thấy bản LTO bỏ được lệnh bl <sq>, phản xạ của tôi là kết luận gọn: "nhanh nhờ tiết kiệm phí gọi hàm — 20 triệu lời gọi biến mất, mỗi lời gọi tốn ít chu kỳ, cộng lại thành 11 mili giây". Nghe hợp lý, và tôi suýt viết cả bài quanh câu đó.

Nhưng phép tính không khớp. Một lời gọi hàm đã được dự đoán nhánh đúng — mà lời gọi trong một vòng lặp chặt thì luôn được dự đoán đúng — chỉ tốn cỡ một tới hai chu kỳ. Ở ~3 GHz, 20 triệu lời gọi như thế cộng lại chừng vài mili giây là cùng, không đủ để giải thích khoảng cách 11 mili giây, càng không phải mức nhanh 2,9 lần. Hai con số mâu thuẫn nhau — phí gọi thì bé, mà cái nhanh thì lớn — và như cả sê-ri này lặp đi lặp lại: hai số mâu thuẫn nghĩa là tôi đang đo nhầm đại lượng.

Cái đúng nằm ở lệnh ldr q1. Bản không-LTO chạy vô hướng không phải vì nó "muốn" chậm, mà vì một lời gọi hàm mờ nằm giữa vòng lặp là một rào chặn vector hóa: trình biên dịch không thể gói bốn phép x*x vào một lệnh vector khi giữa chúng có một lời gọi mà nó không nhìn thấu (hàm đó có thể làm bất cứ gì). Khi LTO nội tuyến sq, lời gọi biến mất, trình biên dịch nhìn thấy vòng lặp thực chất chỉ là "cộng dồn bình phương", và vector hóa được cả vòng. Cái nhanh 2,9 lần chủ yếu đến từ vector hóa, không phải từ việc bỏ vài lệnh bl. Lời gọi không đắt vì bản thân nó; nó đắt vì nó là rào cản ngăn một tối ưu lớn hơn nhiều.

Nếu tôi tin cái kết luận đầu tiên và không đọc ldr q1, tôi đã dạy người đọc một cơ chế sai: rằng LTO nhanh nhờ "gọi hàm tốn kém". Sự thật tinh tế hơn và hữu ích hơn: LTO nhanh vì nội tuyến mở khóa những tối ưu mà ranh giới lời gọi vốn chặn lại — và bạn chỉ biết điều đó khi đọc assembly, chứ không phải khi đếm lệnh bl rồi đoán.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên: LTO đáng giá nhất cho các hàm nhỏ, nóng, gọi xuyên file. Nếu bạn chia mã ra nhiều file cho gọn (điều nên làm), thì đúng những hàm tiện ích bé xíu — một phép biến đổi, một getter, một hàm toán học — lại là thứ chịu thiệt nhất khi không có LTO, vì chúng quá nhỏ để đáng một lời gọi mà lại quá "xuyên file" để được nội tuyến. Bật -flto cho bản build phát hành thường là một trong những cải thiện hiệu năng rẻ nhất về công sức: một cờ, không đổi một dòng mã.

Hệ quả thứ hai, và là bài học tư duy: một lời gọi hàm không chỉ tốn phí gọi, nó còn là một bức tường mờ đối với trình tối ưu. Trình biên dịch phải giả định hàm được gọi có thể đọc/ghi bộ nhớ bất kỳ, nên nó chặn vector hóa, chặn gộp biểu thức chung (như bài trước đã đo), chặn giữ giá trị trong thanh ghi qua lời gọi. Đây là lý do nội tuyến — dù bằng static inline trong header, hay bằng LTO xuyên file — thường mang lại lợi ích gấp bội cái phí gọi mà nó tiết kiệm: nó phá bức tường và cho các tối ưu khác tràn qua. Khi bạn thấy một hàm nhỏ trong vòng nóng, giá trị của việc nội tuyến nó hiếm khi là "bỏ lệnh bl"; nó là những gì trình biên dịch làm được sau khi bức tường biến mất.

Hệ quả thứ ba là cái giá phải cân: LTO không miễn phí ở khâu build. Vì tối ưu dời tới lúc link, bước link trở nên chậm hơn và ngốn RAM hơn hẳn — với dự án lớn, thời gian link có thể tăng đáng kể. Ngoài ra, LTO nhìn cả chương trình nên nó cũng là lúc các lỗi ẩn giữa các đơn vị dịch (hai file khai cùng một hàm với chữ ký lệch nhau) lộ ra, đôi khi thành cảnh báo hoặc hành vi lạ. Nên LTO hợp cho bản phát hành, còn vòng lặp phát triển hằng ngày thường để không. Con số mang theo: -flto cho phép nội tuyến qua ranh giới file, và cái nội tuyến đó rút một vòng lặp gọi hàm xuyên file từ 16,4 xuống 5,6 ms — nhưng cái nhanh 2,9 lần đến chủ yếu từ vector hóa được mở khóa, không phải từ phí gọi tiết kiệm được. Bật LTO cho bản phát hành, và khi muốn biết nó thật sự làm gì, hãy đọc assembly thay vì đoán theo lệnh nào biến mất.

Thử ba mươi giây

Lấy một chương trình hai file của bạn, trong đó một vòng lặp nóng ở file này gọi một hàm nhỏ ở file kia. Build hai lần — gcc -O2 *.c và gcc -O2 -flto *.c — rồi đo thời gian chạy (nhớ ghim một lõi và lấy trung vị nhiều lần cho đỡ nhiễu). Nếu vòng lặp đủ nóng và hàm đủ nhỏ, bạn sẽ thấy bản LTO nhanh hơn rõ. Muốn biết vì sao, chạy objdump -d cả hai và tìm lời gọi bl <tên_hàm>: bản không-LTO còn nó, bản LTO không — và nếu bạn thấy thanh ghi vector (tên q0–q31 trên ARM, xmm/ymm trên x86) xuất hiện trong vòng của bản LTO, thì cái nhanh của bạn cũng đến từ vector hóa được mở khóa, không phải chỉ từ lời gọi biến mất.