Ngăn xếp và heap

Khi chương trình cần một mẩu bộ nhớ, nó có hai chỗ để lấy: ngăn xếp (stack) — nơi biến cục bộ sống — hay heap, qua malloc. Ai cũng "biết" stack nhanh còn malloc chậm, nhưng nhanh/chậm cụ thể bao nhiêu, và cái giá của mỗi lựa chọn là gì? Bài này đo trực tiếp chi phí cấp phát trên stack so với heap — và phát hiện phép đo đầu tiên của tôi che mất chính con số cần tìm, vì một sai lầm quen thuộc.

Hai nơi cấp phát

Ngăn xếp là vùng bộ nhớ cho biến cục bộ của mỗi lời gọi hàm. Cấp phát trên đó gần như miễn phí: trình biên dịch chỉ dời con trỏ ngăn xếp xuống một đoạn — một lệnh máy duy nhất, bất kể bạn xin 8 byte hay 8 KB. Và nó tự giải phóng khi hàm trả về (con trỏ dời lại lên). Nhưng ngăn xếp có hai cái giá: nó nhỏ (giới hạn mặc định ~8 MB), và khi tràn thì chương trình crash thẳng cẳng (SIGSEGV), không báo trước, không có cơ hội xử lý lỗi.

Heap là vùng bộ nhớ lớn mà malloc/free quản lý. Cấp phát ở đây tốn công thật: bộ cấp phát phải tìm một khối trống đủ lớn, cập nhật sổ sách của nó, đảm bảo an toàn luồng (khóa, vì nhiều luồng có thể cùng malloc), và đôi khi phải xin thêm bộ nhớ từ nhân (brk/mmap). Đổi lại, heap lớn (tới hàng GB) và khi hết chỗ nó trả về NULL để bạn xử lý, chứ không crash. Tôi muốn đo khoảng cách chi phí giữa hai bên.

Đo: và một vòng đo che mất kết quả

Phép đo đầu tiên của tôi cho một kết quả đáng ngờ nên tôi phải kể trước. Tôi viết một hàm cấp phát buffer (stack hay heap), chạm vào toàn bộ nó (ghi rồi cộng từng byte) để trình biên dịch khỏi xóa mất phần cấp phát, rồi đo. Kết quả ở kích cỡ 64 KB:

N=64 KB: stack 618 ns ≈ heap 614 ns

Stack và heap tốn như nhau? Điều đó mâu thuẫn với mọi hiểu biết rằng stack chỉ là một lệnh dời con trỏ. Số đo bất khả nghĩa là tôi đang đo nhầm: cái vòng chạm toàn bộ 64 KB (ghi 1024 byte, đọc 1024 byte) tốn tới ~600 ns, và nó nuốt trọn chi phí cấp phát vốn chỉ vài nano giây, làm hai bên trông bằng nhau. Chính dụng cụ đo của tôi — vòng chạm — là thứ tôi đang đo, không phải phép cấp phát.

Sửa lại bằng cách chạm tối thiểu (chỉ ghi/đọc byte đầu và byte cuối, đủ để chống tối ưu), chi phí cấp phát thuần mới lộ ra:

Giờ sự thật rõ ràng: stack tốn ~1 nano giây cho mọi kích cỡ — từ 64 byte tới 1 MB đều như nhau, đúng như lý thuyết "chỉ dời một con trỏ", O(1) theo kích cỡ. Còn heap chậm hơn 6 đến 14 lần vì phải làm sổ sách. Cấp phát stack không chỉ nhanh, mà nhanh một cách bất biến theo kích cỡ, còn malloc thì luôn phải trả cái giá quản lý.

Và để thấy đánh đổi, tôi thử vượt giới hạn. RLIMIT_STACK là 8 MB; cấp 16 MB trên stack (alloca) khiến chương trình SIGSEGV, mã thoát 139 — crash không một lời cảnh báo. Cùng 16 MB đó trên heap (malloc) thì thành công bình thường (và nếu hết bộ nhớ thật, nó trả NULL chứ không giết chương trình).

Một lần tôi đo hớ: vòng đo nuốt mất thứ cần đo

Cái sai của tôi đã lặp lại một chủ đề xuyên suốt sê-ri, lần này ở dạng tinh vi hơn. Tôi muốn đo chi phí cấp phát, nhưng để phép đo "thật" (chống trình biên dịch xóa phần cấp phát), tôi cho nó chạm toàn bộ buffer. Ở buffer nhỏ điều đó vô hại; nhưng ở 64 KB, cái vòng chạm ~600 ns nuốt trọn chi phí cấp phát vài ns, khiến stack và heap trông bằng nhau, và tôi suýt kết luận "với buffer lớn, cấp phát stack và heap tốn như nhau" — một điều hoàn toàn sai.

Bài học đo lường: vòng đo và việc chạm dữ liệu là một biến ẩn, và nó có thể nuốt mất chính đại lượng bạn muốn đo. Đây là họ hàng của cái bẫy ở bài mmap (vòng cộng byte thành nút thắt che mất khác biệt read-vs-mmap) và bài fork (trình biên dịch xóa mất memcpy). Để đo chi phí của một thao tác nhỏ (cấp phát ~ns), mọi thứ khác trong vòng đo phải nhỏ hơn nữa, nếu không bạn đo cái vòng chứ không đo thao tác. Chạm tối thiểu — vừa đủ chống tối ưu, không hơn — là cách tách biến. Một lần nữa, công cụ đo tự dựng chính là thứ dễ nói dối nhất.

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

Hệ quả đầu tiên là ưu tiên stack cho dữ liệu nhỏ, ngắn hạn. Biến cục bộ, buffer tạm nhỏ, struct nhỏ — để trên stack thì cấp phát gần như miễn phí (~1 ns), tự dọn, và không gây phân mảnh heap. Tránh malloc cho những mẩu bé xíu dùng-rồi-bỏ trong một hàm: bạn trả 6-14 lần chi phí cấp phát cộng chi phí free, cho một thứ stack làm gần như không mất gì. Đây là lý do các đường nóng (hot path) hiệu năng cao cố giữ mọi thứ trên stack.

Hệ quả thứ hai là dùng heap cho dữ liệu lớn, sống lâu, hay kích cỡ chạy mới biết. Buffer lớn (vài trăm KB trở lên), cấu trúc phải sống qua nhiều lời gọi hàm, hay mảng có kích cỡ chỉ biết lúc chạy — phải đi heap, vì stack quá nhỏ và tràn thì crash chết người. Đặc biệt cảnh giác với buffer lớn khai trên stack (char buf[1024*1024]) hay đệ quy quá sâu: cả hai âm thầm ăn stack và một ngày đẹp trời cho bạn một SIGSEGV không rõ nguyên nhân. Nếu kích cỡ do người dùng nhập, luôn dùng heap và kiểm NULL — đừng bao giờ alloca một kích cỡ không kiểm soát (đó còn là lỗ hổng bảo mật).

Hệ quả thứ ba, về đo lường: để đo một thao tác nhỏ, mọi thứ quanh nó phải nhỏ hơn. Con số mang theo: cấp phát trên stack tốn ~1 ns cho mọi kích cỡ (chỉ dời con trỏ, O(1)), malloc/free chậm hơn 6-14 lần vì làm sổ sách và khóa; nhưng stack giới hạn ~8 MB và tràn thì CRASH (SIGSEGV) không báo, còn heap lớn và trả NULL — nên dữ liệu nhỏ ngắn hạn đi stack, dữ liệu lớn/lâu/động đi heap. Và cẩn thận: một vòng chạm nặng trong phép đo có thể nuốt mất chính chi phí cấp phát bạn muốn thấy.

Thử ba mươi giây

Xem giới hạn ngăn xếp của bạn: ulimit -s (đơn vị KB; thường 8192 = 8 MB). Muốn thấy tràn stack tận mắt, viết một hàm đệ quy vô hạn hoặc khai một mảng cục bộ khổng lồ (char buf[100*1024*1024]; buf[0]=1;) rồi chạy — nó sẽ crash với "Segmentation fault" ngay, không lời giải thích. Đổi cùng thứ đó sang malloc(100*1024*1024) và kiểm giá trị trả về: nó chạy được (hoặc trả NULL để bạn xử lý). Trong code của bạn, để ý các mảng cục bộ lớn và độ sâu đệ quy — đó là những quả bom stack overflow chờ nổ; chuyển sang heap khi dữ liệu lớn hay kích cỡ không đoán trước được, đúng cái ranh giới bài này đo.