Đệ quy xuất hiện suốt sê-ri này — quicksort, merge sort, cây tìm kiếm, tất cả đều là hàm tự gọi chính nó. Và hai lần, ở quicksort và cây tìm kiếm nhị phân, tôi ghi nhận một cái chết lạ trên đầu vào đã sắp: không phải chậm, mà là tràn ngăn xếp — chương trình sập hẳn. Bài này đo thẳng vào cơ chế đằng sau: đệ quy thật sự tốn gì, và tôi mang theo hai lầm tưởng phổ biến để đối chất với đồng hồ. Cả hai đều sai, và cái sai chỉ đúng chỗ nguy hiểm thật của đệ quy nằm ở đâu.
Mỗi lời gọi hàm đẩy một khung lên ngăn xếp
Khi một hàm gọi một hàm khác (kể cả gọi chính nó), máy đẩy một khung (stack frame) lên ngăn xếp lời gọi: khung đó chứa biến cục bộ của lời gọi, tham số, và địa chỉ để quay về sau khi hàm xong. Đệ quy sâu n tầng nghĩa là n khung chồng lên nhau cùng lúc, và chúng chỉ được gỡ ra khi các lời gọi lần lượt trả về. Đây là điểm mấu chốt: đệ quy đổi độ sâu tính toán lấy không gian ngăn xếp, và ngăn xếp lời gọi là một tài nguyên hệ điều hành có giới hạn cứng — mặc định thường chỉ 8 MB. Vòng lặp thì không dùng ngăn xếp lời gọi; nó ở nguyên một khung. Sự khác biệt tưởng nhỏ đó là toàn bộ câu chuyện, và tôi đo nó.
Đo: trần cứng ở 655 nghìn lần gọi
Lầm tưởng thứ nhất tôi mang vào: độ sâu đệ quy là chuyện tùy ý, muốn sâu bao nhiêu cũng được. Để đo trần thật, tôi viết một hàm đệ quy đơn giản rồi cho nó chạy trong một tiến trình con (fork), tăng dần độ sâu và bắt tín hiệu SIGSEGV để biết đúng chỗ nó sập — làm trong tiến trình con để tiến trình đo không chết theo. Tìm nhị phân ra biên:
đệ quy sâu ~654 000 lần gọi : SỐNG
đệ quy sâu ~655 600 lần gọi : TRÀN NGĂN XẾP (segfault)
Trần cứng nằm quanh 655 000 lần gọi. Con số này khớp với số học: ngăn xếp 8 MB chia cho kích thước một khung (đo được ~13 byte cho hàm nhỏ này) ra đúng cỡ đó. Đây là điều đầu tiên đáng nhớ: độ sâu đệ quy không hề tùy ý — nó có một trần cứng đo được, và một hàm đệ quy hoàn toàn đúng về logic vẫn sẽ chết trên đầu vào đủ lớn. Đây chính xác là cái đã xảy ra ở quicksort và cây tìm kiếm khi khóa đã sắp: cây đệ quy suy biến thành n tầng, và với n vài trăm nghìn, nó đâm thủng trần này. Không phải bug logic — là hết ngăn xếp. Và nó chết im lặng: không ngoại lệ bắt được, chỉ một segmentation fault cụt lủn. Với hàm có khung lớn hơn (nhiều biến cục bộ), trần còn thấp hơn nữa.
Một lần tôi đo hớ: lặp không hề nhanh hơn
Lầm tưởng thứ hai của tôi tưởng chắc thắng: "đệ quy chậm hơn lặp vì tốn chi phí gọi hàm — đẩy tham số, nhảy, lưu địa chỉ trả về, quay lui." Tôi định đo để xác nhận lặp nhanh hơn rồi khuyên đổi đệ quy sang lặp vì tốc độ. Đo ra ngược với mong đợi. Tính tổng một mảng 100 nghìn số ngẫu nhiên (đọc thật từ bộ nhớ để trình biên dịch không rút gọn thành công thức):
đệ quy (một lời gọi hàm mỗi phần tử) : 22,8 micro giây
lặp (một vòng for) : 22,7 micro giây
Bằng nhau — chênh trong khoảng nhiễu. Chi phí gọi hàm có thật, nhưng nó nhỏ và bị che khuất: mỗi lời gọi còn làm một việc thật (đọc một phần tử mảng, cộng), và CPU hiện đại pipeline phần gọi/trả song song với phần việc đó, nên nó gần như biến mất. Tôi đã sai về lý do nên tránh đệ quy sâu. Bài học đo lường: cái đắt của đệ quy không phải đồng hồ, mà là cái trần ngăn xếp. Nếu bạn đổi đệ quy sang lặp, hãy đổi vì độ bền (bỏ được trần độ sâu), không phải vì kỳ vọng nhanh hơn — vì với công việc thực mỗi lời gọi, tốc độ gần như không đổi. Hai con số 22,7 và 22,8 nói rõ: đừng tối ưu đệ quy vì tốc độ; hãy sửa nó vì nó có thể sập.
Cách chữa: ngăn xếp tường minh trên heap
Nếu vấn đề là ngăn xếp OS quá nhỏ, cách chữa tự nhiên là đừng dùng ngăn xếp OS — dựng ngăn xếp của riêng bạn trên heap, nơi rộng hơn nhiều. Tôi cấp phát một mảng làm ngăn xếp 10 triệu ô (76 MB) — gấp gần 10 lần giới hạn 8 MB của ngăn xếp lời gọi — và dùng nó mô phỏng một đệ quy sâu 10 triệu tầng: đẩy vào, lấy ra, cho kết quả đúng, ở độ sâu mà đệ quy thật đã segfault từ lâu ở mốc 655 nghìn. Đây là kỹ thuật chuẩn để chữa tràn ngăn xếp mà giữ nguyên thuật toán: chuyển một hàm đệ quy thành một vòng lặp cầm một ngăn xếp tường minh, tự bạn đẩy và lấy các "khung" (chỉ gồm đúng trạng thái bạn cần nhớ) trên heap. Bạn không đổi ý tưởng thuật toán, chỉ dời chỗ cất trạng thái từ ngăn xếp OS chật sang heap rộng. Với đệ quy đuôi (tail recursion) còn có cách gọn hơn nữa mà một bài sau sẽ đo.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, rất thực tế: một hàm đệ quy đúng logic vẫn có thể là một quả bom hẹn giờ trên đầu vào lớn. Nếu độ sâu đệ quy tỉ lệ với kích thước dữ liệu (duyệt một cây có thể rất sâu, một danh sách liên kết dài, một cấu trúc lồng nhau từ người dùng), thì nó sẽ chạy tốt trên mọi test nhỏ rồi sập trên dữ liệu thật. Khi viết hàm đệ quy, hãy hỏi: độ sâu tối đa có thể là bao nhiêu, và nó có vượt vài trăm nghìn không? Nếu có, bạn cần một ngăn xếp tường minh hoặc một vòng lặp.
Hệ quả thứ hai, về cách quyết định: chọn đệ quy hay lặp theo độ bền và độ rõ ràng, không theo tốc độ. Đệ quy thường diễn đạt một thuật toán gọn và dễ đọc hơn (cây, chia để trị), và nó không chậm hơn đáng kể — nên với độ sâu nông và có kiểm soát, cứ dùng đệ quy cho sáng sủa. Chỉ chuyển sang ngăn xếp tường minh khi độ sâu có thể lớn tới mức đe dọa trần. Đây là quyết định về rủi ro tràn, không phải về vài micro giây.
Hệ quả thứ ba là con số mang theo: ngăn xếp lời gọi của OS mặc định chỉ 8 MB, mỗi khung ~13 byte, nên đệ quy có trần cứng đo được ~655 000 lần gọi rồi segfault im lặng; và đệ quy KHÔNG chậm hơn lặp (22,8 so với 22,7 micro giây) — cái đắt của nó là trần ngăn xếp, không phải tốc độ; cách chữa là ngăn xếp tường minh trên heap (76 MB, gấp ~10 lần) hoặc chuyển sang lặp. Đừng sợ đệ quy vì chậm (nó không chậm); hãy tôn trọng nó vì nó có một giới hạn độ sâu rất thật mà bạn phải đo trước khi đầu vào của người dùng đo giúp bạn.
Thử ba mươi giây
Lấy một hàm đệ quy bất kỳ trong code của bạn và hỏi một câu: độ sâu tối đa nó có thể đạt là bao nhiêu? Nếu câu trả lời tỉ lệ với kích thước dữ liệu — duyệt một cấu trúc có thể sâu, xử lý một danh sách dài, phân tích dữ liệu lồng nhau từ bên ngoài — thì bạn có một trần tiềm ẩn. Thử nhanh cho vui: viết một hàm đệ quy tầm thường (đếm ngược từ n về 0) rồi gọi với n = 1 triệu, và xem nó có sập không. Nó sẽ sập, và đó là bài học trực quan rằng ngăn xếp lời gọi là hữu hạn. Rồi nhớ hai điều đo được hôm nay: đổi sang lặp hay ngăn xếp tường minh không làm code nhanh hơn đáng kể, nhưng nó gỡ bỏ cái trần khiến chương trình chết im lặng — và trên đầu vào thật, đó mới là điều quan trọng.
