Ai cũng biết trình biên dịch tính sẵn 2 + 3 thành 5 — chẳng ai để CPU cộng hai số biết trước lúc chạy. Nhưng tối ưu này, gọi là gấp hằng số (constant folding), đi xa hơn nhiều so với những phép cộng hiển nhiên. Kết hợp với người anh em lan truyền hằng (constant propagation), nó có thể lấy cả một hàm phức tạp và, nếu đầu vào là hằng số, biến toàn bộ thành một con số nạp sẵn — tính toán biến mất khỏi lúc chạy. Bài này đo cái biến mất đó bằng đồng hồ và mã máy.
Gấp hằng và lan truyền: hai bước đi cùng
Gấp hằng số là việc trình biên dịch tính mọi biểu thức chỉ gồm hằng số ngay lúc biên dịch, thay bằng kết quả. Viết 3600 * 24 * 365 thì mã máy chứa thẳng 31536000, không có phép nhân nào lúc chạy — bạn được viết công thức cho dễ đọc mà không trả giá tốc độ.
Lan truyền hằng là bước đi kèm, và là chỗ nó trở nên mạnh. Nếu trình biên dịch biết chắc một biến mang giá trị hằng — bạn gán int k = 100, hay một tham số được truyền hằng số vào một hàm đã inline — nó thay mọi lần dùng k bằng 100. Mà khi k đã thành 100, các biểu thức chứa k giờ toàn hằng, nên gấp hằng lại nhảy vào tính tiếp. Hai bước lặp qua lại: lan truyền tạo ra hằng mới, gấp hằng tính chúng, lộ ra hằng mới hơn nữa, lan truyền tiếp... cho tới khi không còn gì để gấp. Kết quả có thể ngoạn mục hơn nhiều so với 2 + 3.
Đo: một hàm phức tạp rút thành một con số
Tôi viết một hàm f(k) làm việc thật: ba phép nhân 64-bit, vài phép xor và dịch bit trộn lẫn. Rồi tôi gọi nó hai cách. Cách thứ nhất, all_const(), gọi f(100) — k là hằng số 100 viết thẳng trong mã. Cách thứ hai, runtime_val(), gọi f(*pv) với pv trỏ tới một biến volatile — giá trị chỉ biết lúc chạy. Nhìn mã máy hai hàm:
Cùng hàm f() (3 phép nhân + xor + dịch), gcc -O2, mã máy:
all_const (k = 100 hằng) : 5 lệnh, 0 phép nhân
runtime_val (k từ volatile) : 22 lệnh, 3 phép nhân
Hàm all_const chỉ còn 5 lệnh và không một phép nhân nào. Mở nó ra, toàn bộ thân hàm là bốn lệnh mov/movk nạp một số 64-bit rồi ret — trình biên dịch đã lan truyền k = 100 xuyên qua cả hàm, gấp hết ba phép nhân và mọi phép trộn, tính ra kết quả cuối cùng lúc biên dịch, và nhét nó vào mã dưới dạng một hằng số literal. Còn runtime_val giữ nguyên 22 lệnh với 3 phép nhân — vì k đến từ volatile, trình biên dịch không biết giá trị của nó, buộc phải sinh mã tính đủ f() mỗi lần gọi. Và thời gian:
Thời gian mỗi lời gọi:
all_const (k = 100 hằng) : 0,000 ns
runtime_val (k từ volatile) : 0,992 ns
Bản hằng số chạy 0 nano giây — không phải vì nó nhanh, mà vì không còn gì để chạy: kết quả đã có sẵn dưới dạng một literal. Bản runtime tốn ~1 ns thật để làm ba phép nhân mỗi lần. Cùng một hàm, cùng một trình biên dịch, khác biệt duy nhất là đầu vào có phải hằng số biết trước lúc biên dịch hay không.
Một lần tôi đo hớ: lan truyền hằng đi xa hơn tôi tưởng
Định kiến của tôi là "trình biên dịch chỉ gấp những biểu thức hằng hiển nhiên như 2 + 3 hay 3600 * 24". Con số bác bỏ điều đó: nó lan truyền hằng rất xa — đẩy giá trị 100 xuyên qua một hàm với ba phép nhân, xor, dịch bit, tính sẵn toàn bộ thành một literal duy nhất. Đây không phải "gấp một biểu thức", mà là "thực thi cả một đoạn chương trình lúc biên dịch". Trình biên dịch, khi biết đủ, có thể chạy giúp bạn phần tính toán ngay khi dịch, để lúc chạy chỉ còn việc đọc kết quả.
Nhưng — và đây là mặt còn lại của bài học — phép màu này dừng ngay khi chạm một giá trị "chạy mới biết". Chỉ cần k đến từ một nguồn mà trình biên dịch không thể biết trước — đọc từ file, từ argv, từ mạng, hay từ một biến volatile như trong đo của tôi — thì cả chuỗi lan truyền sụp đổ: không có hằng số nào để đẩy đi, không có gì để gấp, và toàn bộ tính toán phải sinh ra để chạy thật (22 lệnh, 3 phép nhân, ~1 ns). Ranh giới giữa "0 ns" và "tính đủ" không nằm ở độ phức tạp của phép tính, mà ở một câu hỏi duy nhất: trình biên dịch có biết giá trị này lúc dịch không?
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, rất thực dụng: viết hằng số dưới dạng biểu thức dễ đọc, đừng tự "tối ưu" bằng tay. 60 * 60 * 24 rõ ràng hơn 86400, và trình biên dịch gấp nó thành cùng một literal — bạn được cả sự rõ ràng lẫn tốc độ. Tự tính sẵn 86400 chỉ làm code khó đọc mà không nhanh hơn một nano giây nào. Cùng vậy với các hằng cấu hình: khai báo const int BUFSIZE = 4096; ... BUFSIZE * 8 và để trình biên dịch lo phần số học.
Hệ quả thứ hai giải thích vì sao inline và hằng số là cặp bài trùng. Như bài inline đã đo, lợi lớn của inline không phải bỏ lệnh call mà là mở khóa tối ưu xuyên biên — và tối ưu xuyên biên số một chính là lan truyền hằng. Khi bạn gọi một hàm với đối số hằng (một cờ, một kích thước, một chế độ), inline đưa hằng đó vào thân hàm, lan truyền hằng chuyên biệt hóa thân hàm cho đúng chỗ gọi, gấp hằng và khử mã chết dọn phần thừa. Đó là lý do một hàm tổng quát gọi với tham số hằng thường sinh ra mã ngắn gọn đến bất ngờ.
Hệ quả thứ ba là bài học đo lường của bài: ranh giới compile-time / runtime quyết định cái gì được tính miễn phí. Con số mang theo: cùng một hàm với ba phép nhân, khi đầu vào là hằng số gcc gấp toàn bộ thành một literal 64-bit (5 lệnh, 0 phép nhân, 0 ns); khi đầu vào đến từ volatile thì phải tính đủ (22 lệnh, 3 phép nhân, 0,99 ns) — tính toán dời sang lúc biên dịch chỉ khi giá trị thật sự là hằng lúc biên dịch. Muốn tận dụng điều này, hãy để những gì biết trước thành hằng số hay constexpr (bài sau sẽ đo), và đừng vô tình che giấu một hằng số sau một lớp volatile hay một lời gọi mà trình biên dịch không thấy xuyên qua. Cái gì trình biên dịch biết, nó tính giúp bạn — miễn phí.
Thử ba mươi giây
Viết một hàm nhỏ tính một biểu thức phức tạp từ tham số, uint64_t f(uint64_t k){ return k*k*k + k*7 - 3; }, và một hàm gọi nó với hằng số: uint64_t g(){ return f(1000); }. Biên dịch gcc -O2 -S -o out.s file.c rồi tìm hàm g trong out.s: bạn sẽ thấy nó không có phép nhân nào, chỉ nạp một con số — trình biên dịch đã tính 1000³ + 7000 - 3 giúp bạn. Giờ đổi g thành nhận tham số g(uint64_t k){ return f(k); } và xem lại: phép nhân xuất hiện, vì k không còn là hằng. Ba mươi giây đó cho bạn thấy ranh giới compile-time/runtime bằng mắt — và vì sao "cái gì biết trước thì để trình biên dịch tính".
