Ở bài về gộp biểu thức chung, tôi vấp phải một hàm kết thúc bằng lời gọi đuôi b g thay vì ret — và nó làm hỏng công cụ đếm của tôi. Bài này nhìn thẳng vào chính hiện tượng đó: gọi đuôi (tail call). Khi việc cuối cùng một hàm làm là một lời gọi, trình biên dịch có thể tái dùng khung ngăn xếp hiện tại thay vì đẩy một khung mới — và với đệ quy đuôi, điều đó biến đệ quy thành vòng lặp, ngăn xếp không phình. Tôi đo trong container xem nó thật đến đâu, và phát hiện gcc làm nhiều hơn tôi tưởng, còn cái tôi tưởng chắc chắn thì lại mong manh.
Vị trí đuôi là gì
Một lời gọi ở vị trí đuôi khi nó là hành động cuối cùng của hàm — không còn việc gì làm với kết quả của nó ngoài việc return thẳng. return f(x); là gọi đuôi; return f(x) + 1; thì không, vì còn phép +1 sau khi f trả về. Khi lời gọi ở vị trí đuôi, khung ngăn xếp của hàm hiện tại chẳng còn gì để làm sau lời gọi, nên trình biên dịch tái dùng luôn khung đó cho hàm được gọi thay vì chồng thêm khung mới. Với một hàm gọi đệ quy chính nó ở đuôi, điều này biến chuỗi đệ quy — vốn chồng một khung mỗi tầng — thành một vòng lặp dùng đúng một khung, chạy hằng bộ nhớ ngăn xếp dù đệ quy triệu tầng.
Điều mấu chốt, sẽ quay lại ở phần đo hớ: trong C, đây là một tối ưu trình biên dịch có thể làm ở -O2, chứ không phải một bảo đảm của ngôn ngữ.
Đo: cùng mã, tràn ở -O0, chạy ở -O2
Tôi viết một hàm tính tổng đệ quy đuôi với biến tích lũy:
long sum_tail(long n, long acc){ if(n==0) return acc; return sum_tail(n-1, acc+n); }
Đọc assembly, đếm lời gọi đệ quy bl <sum_tail>:
-O0: bl <sum_tail> = 1 (đệ quy thật, chồng khung mỗi tầng)
-O2: bl <sum_tail> = 0 (không còn lời gọi — thành một vòng lặp)
Ở -O0, hàm gọi chính nó thật; ở -O2, lời gọi đệ quy biến mất, thay bằng một nhánh nhảy lùi — nó đã thành vòng lặp. Để thấy hệ quả, tôi chạy sum_tail(50000000) với ngăn xếp giới hạn 2 MB (ulimit -s 2048):
| Bản | Kết quả |
|---|---|
-O0 (đệ quy thật) |
exit 139 — SIGSEGV, tràn ngăn xếp |
-O2 (thành vòng) |
exit 0, ra 1250000025000000, chạy gọn |
Cùng một dòng mã sum_tail. Ở -O0 nó đệ quy 50 triệu tầng, chồng 50 triệu khung, blow ngăn xếp 2 MB và chết vì SIGSEGV. Ở -O2 nó là một vòng lặp dùng một khung, chạy ngon và ra đáp án đúng. Sự khác biệt giữa "chương trình chạy" và "chương trình sập" ở đây hoàn toàn nằm ở mức tối ưu.
Một lần tôi đo hớ: gcc khử nhiều hơn tôi tưởng
Tôi định dựng một ví dụ phản chứng cho gọn: một hàm trông giống đệ quy nhưng không ở vị trí đuôi, để cho thấy nó không được tối ưu. Tôi chọn:
long sum_body(long n){ if(n==0) return 0; return n + sum_body(n-1); }
Lập luận của tôi: return n + sum_body(n-1) còn một phép cộng n + sau khi lời gọi trả về, nên lời gọi không ở vị trí đuôi, nên gcc phải giữ đệ quy, nên nó sẽ tràn ngăn xếp y như -O0. Tôi đã chắc đến mức suýt viết thẳng vào bài.
Đọc assembly thì bất ngờ: ở -O2, bl <sum_body> = 0. gcc đã khử luôn đệ quy của sum_body, biến nó thành vòng lặp. Cách nó làm: tự thêm một biến tích lũy — nhận ra phép cộng là kết hợp được, gcc viết lại n + sum_body(n-1) thành một vòng cộng dồn, đúng như thể tôi đã viết sum_tail ngay từ đầu. Tôi đoán sai về giới hạn của trình biên dịch: nó không chỉ tối ưu lời gọi ở đúng vị trí đuôi cú pháp, mà còn biến đổi các đệ quy có hậu xử lý kết hợp được thành dạng đuôi rồi tối ưu. Lại một lần "đọc assembly, đừng đoán" cứu tôi khỏi một khẳng định sai.
Vậy cái gì thật sự không khử được? Tôi phải làm cho kết quả đệ quy đi qua một hàm mờ:
long not_tail(long n){ if(n==0) return 0; return opaque(not_tail(n-1)); }
Ở đây kết quả not_tail(n-1) bị đưa vào opaque() — một hàm ở file khác mà gcc không thấy thân — nên lời gọi đệ quy not_tail(n-1) thật sự không ở vị trí đuôi (việc cuối là gọi opaque, không phải gọi not_tail), và gcc không có phép biến đổi kết hợp nào để cứu. Đo: -O2 giữ bl <not_tail> = 1, và not_tail(50000000) tràn ngăn xếp (SIGSEGV) ngay cả ở -O2.
Nhưng bài học lớn hơn nằm ở phép đo đầu: TCO là tối ưu, không phải bảo đảm. Cùng một hàm đệ quy đuôi tràn ở -O0 và chạy ở -O2 — nghĩa là tính "không tràn" của nó không phải thuộc tính của mã, mà của cờ biên dịch. Đây đúng là cái dấu hiệu "kết quả đổi theo mức -O" mà bài về hành vi không xác định cảnh báo: một sự phụ thuộc mong manh. Trong Scheme hay các ngôn ngữ hàm, TCO được chuẩn ngôn ngữ bảo đảm, nên viết đệ quy đuôi sâu là an toàn. Trong C thì không — trình biên dịch có thể làm hoặc không, tùy mức tối ưu, tùy hình dạng hàm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng dựa vào TCO để đệ quy sâu trong C. Nếu thuật toán của bạn có thể đệ quy hàng trăm nghìn tầng (duyệt một danh sách liên kết dài, một cây lệch), đừng tin rằng "nó là đệ quy đuôi nên không tràn". Ở -O2 có thể đúng; nhưng một bản debug -O0, một trình biên dịch khác, hoặc chỉ một thay đổi nhỏ khiến lời gọi rời vị trí đuôi (thêm một dòng dọn dẹp sau nó, một biến cục bộ có destructor trong C++), là ngăn xếp tràn trở lại. Muốn chắc chắn không tràn, tự viết thành vòng lặp — biến cái đệ quy thành while với một biến tích lũy của chính bạn, đừng phó mặc cho -O.
Hệ quả thứ hai: hiểu vị trí đuôi để viết mã tối ưu được. Nếu bạn muốn trình biên dịch biến đệ quy thành vòng, hãy đặt lời gọi đệ quy ở đúng vị trí đuôi: mang trạng thái tích lũy xuống qua tham số (kiểu acc) thay vì xử lý kết quả sau khi gọi. return f(n-1, acc+n) tối ưu được; return combine(x, f(n-1)) với combine mờ thì không. Biết ranh giới này cho bạn viết đệ quy vừa sạch vừa an toàn ngăn xếp — khi trình biên dịch hợp tác.
Hệ quả thứ ba là bài học đo lường mang theo: một hành vi tái lập được ở một cấu hình không có nghĩa là nó được bảo đảm. Con số mang theo: -O2 biến đệ quy đuôi thành vòng lặp (bl-tự-gọi từ 1 xuống 0), nên sum_tail(50 triệu) tràn ngăn xếp ở -O0 nhưng chạy gọn ở -O2 — và gcc còn tự thêm biến tích lũy để khử cả n + f(n-1), nhưng bó tay khi kết quả đệ quy phải qua một hàm mờ; TCO là tối ưu, không phải bảo đảm của C, nên đừng dựa vào nó cho đệ quy sâu. Đo ở -O2 thấy chạy tốt là một chuyện; tin rằng nó luôn chạy tốt lại là chuyện khác — và cách phân biệt là hỏi "điều này được bảo đảm, hay chỉ tình cờ đúng ở cấu hình tôi đo?".
Thử ba mươi giây
Viết một hàm đệ quy đuôi đơn giản — long f(long n, long acc){ return n==0 ? acc : f(n-1, acc+n); } — và biên dịch hai lần: gcc -O0 -S và gcc -O2 -S. Đọc assembly quanh hàm: bản -O0 có một lệnh bl <f> (nó gọi chính mình); bản -O2 không có lệnh gọi nào, chỉ có một nhánh nhảy lùi — nó đã thành vòng. Rồi chạy f với n cỡ chục triệu sau khi đặt ulimit -s 2048 (2 MB ngăn xếp): bản -O0 sẽ Segmentation fault, bản -O2 chạy gọn và in ra kết quả. Bạn vừa thấy tận mắt một chương trình sập hay sống chỉ vì đổi mức tối ưu — và hiểu vì sao không nên dựa vào TCO trong C.
