malloc và free là hai lời gọi ta viết mà gần như không nghĩ ngợi — xin bộ nhớ khi cần, trả lại khi xong, cứ như chúng là thao tác trong suốt và miễn phí. Ở bài merge sort tôi đã thoáng thấy một malloc trong vòng lặp làm chậm mọi thứ, nhưng chưa đào tới cùng. Bài này đo thẳng cái giá của việc cấp phát bộ nhớ đa dụng — ba cái giá ẩn mà "malloc gần như O(1)" che đi — và đo một cách cấp phát thay thế nhanh hơn nhiều: arena.
malloc làm nhiều việc hơn bạn nghĩ
malloc là một bộ cấp phát đa dụng: nó phải phục vụ mọi kích thước, cho phép giải phóng theo bất kỳ thứ tự nào, và (trong chương trình đa luồng) an toàn khi nhiều luồng cùng xin. Để làm được vậy, mỗi lần malloc phải tìm một khối trống đủ lớn trong cấu trúc quản lý heap, ghi lại thông tin về khối vừa cấp (để free sau này biết đường), và thường phải khoá để tránh đua tranh. Mỗi khối cấp ra còn mang theo một header ẩn (metadata) ngay trước vùng bạn dùng, và bị căn lề lên bội số nào đó — nên một yêu cầu 16 byte thực tế chiếm nhiều hơn 16 byte trên heap.
Và có một cái giá thứ ba, tinh vi hơn: phân mảnh. Khi bạn cấp rồi giải nhiều khối kích thước khác nhau theo thứ tự lộn xộn, các vùng trống còn lại nằm rải rác xen kẽ các vùng đang dùng. Tổng bộ nhớ trống có thể lớn, nhưng không có một mảnh liền nào đủ cho một yêu cầu lớn — "đủ mà không đủ". Ba cái giá này — thời gian, không gian, phân mảnh — là thứ "O(1) miễn phí" giấu đi. Tôi đo từng cái.
Đo: arena nhanh gấp 8 lần và gọn gấp 2,4 lần
Cách thay thế là arena (còn gọi pool, bump allocator): thay vì xin từng khối nhỏ, bạn xin một khối lớn rồi tự phát dần bằng cách đẩy (bump) một con trỏ về phía trước cho mỗi object; khi xong toàn bộ, giải phóng một lần cả khối. Không ghi sổ mỗi object, không header mỗi object, không phân mảnh. Tôi so hai cách trên ba triệu object nhỏ 16 byte:
cấp + giải
malloc từng object 47 ms
arena (bump con trỏ) 6,2 ms -> nhanh hơn 8 lần
Arena nhanh hơn 8 lần — vì mỗi malloc/free trả giá cho việc ghi sổ và khoá, còn arena chỉ đẩy một con trỏ (vài lệnh máy) và giải phóng cả khối trong một lời gọi. Đây chính là cái đã cắn merge sort ở bài 12: malloc trong một vòng nóng không phải "gần như miễn phí" mà là một khoản phí cộng dồn khổng lồ.
Cái giá không gian cũng đo được rõ. Tôi cấp một triệu object 16 byte — lẽ ra tốn 16 MB — và đo bộ nhớ thật (RSS) mà tiến trình chiếm:
RSS thật (cần 16 MB lý thuyết)
malloc từng object 38,6 MB (2,4 lần)
arena (một khối) 15,6 MB (khít)
malloc ngốn 38,6 MB — gấp 2,4 lần con số lý thuyết — vì mỗi object nhỏ gánh một header và bị căn lề: một yêu cầu 16 byte thực tế chiếm khoảng 32 byte chunk trong glibc, cộng thêm mảng con trỏ để giữ chúng. Arena gói một triệu object khít trong 15,6 MB, không một byte metadata mỗi object. Với object càng nhỏ và càng nhiều, tỉ lệ phí này càng đau.
Một lần tôi đo hớ: "tôi đã free" không có nghĩa "OS đã lấy lại"
Cú hớ thứ hai của tôi tinh tế hơn, và tôi chỉ thấy khi đo. Tôi vẫn ngầm tin: cấp bộ nhớ làm tiến trình phình ra, free làm nó co lại. Tôi cấp hai triệu object 64 byte (RSS đỉnh 168 MB), rồi free tất cả, rồi đo lại RSS:
cấp 2 triệu object 64B -> RSS đỉnh 168 MB
sau khi free HẾT -> RSS vẫn 168 MB
Bộ nhớ không trả về hệ điều hành. free chỉ trả khối về cho bộ cấp phát của thư viện (glibc) để tái dùng cho lần malloc sau, chứ glibc thường không trả ngay về OS — nên tiến trình vẫn giữ nguyên 168 MB nhìn từ bên ngoài. Bài học đo lường: "tôi đã free" không đồng nghĩa "hệ điều hành đã lấy lại bộ nhớ"; đỉnh bộ nhớ mà chương trình từng chạm tới có xu hướng ở lại với tiến trình. Đây là lý do một chương trình có thể "phình rồi không xẹp" dù đã giải phóng đúng — không phải rò rỉ (leak), mà là bộ cấp phát giữ lại. Và nó nhấn mạnh cái đẹp của arena: giải phóng cả khối một lần là O(1) và dứt khoát, thay vì free từng object rồi vẫn không co lại.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, rất cụ thể: đừng gọi malloc lắt nhắt trong một vòng nóng. Nếu bạn cấp phát hàng triệu object nhỏ có cùng đời sống — các node của một cây bạn sẽ vứt cùng lúc, các phần tử tạm của một thuật toán, các bản ghi của một lô xử lý — hãy gom chúng vào một arena: xin một khối lớn, bump con trỏ, và giải cả khối khi xong. Bạn được tốc độ (đo 8 lần), bộ nhớ gọn (2,4 lần), và giải phóng tức thì. Đây là một trong những tối ưu đơn giản mà hiệu quả nhất cho code cấp phát nhiều.
Hệ quả thứ hai: hiểu rằng bộ nhớ có chi phí quản lý, không chỉ có dung lượng. Một object không chỉ tốn kích thước của nó; nó tốn thêm metadata, căn lề, và một phần thời gian CPU để cấp và giải. Khi bạn thấy một chương trình dùng nhiều bộ nhớ hơn "tổng kích thước dữ liệu" đáng ra phải có, thủ phạm thường là chi phí mỗi-object này — và cách chữa là cấp phát theo lô (arena) hoặc gói dữ liệu chặt hơn thay vì rải thành nghìn khối nhỏ.
Hệ quả thứ ba là con số mang theo: malloc không "miễn phí O(1)" — cấp/giải 3 triệu object nhỏ tốn 47ms còn arena chỉ 6,2ms (nhanh 8 lần), 1 triệu object 16 byte tốn 38,6MB thay vì 16MB (metadata + căn lề mỗi object), và free hết rồi RSS vẫn 168MB (glibc giữ lại, không trả OS ngay); gom object cùng đời sống vào arena là cách chữa cả ba. Cấp phát bộ nhớ là một thao tác có giá thật; đối xử với nó như miễn phí là cách chắc chắn để một vòng lặp cấp phát âm thầm ngốn cả thời gian lẫn bộ nhớ.
Thử ba mươi giây
Nhìn vào vòng lặp nóng nhất trong code của bạn và đếm: có bao nhiêu lời gọi cấp phát (malloc, new, hay tương đương) chạy mỗi vòng? Nếu có object nhỏ được cấp và giải trong vòng lặp, thử một thí nghiệm: cấp một mảng lớn trước vòng lặp và tự phát từ đó (một arena thủ công), rồi bấm giờ trước và sau. Với cấp phát nhiều object nhỏ, bạn sẽ thấy khác biệt vài lần — đúng con số 8 lần trong bài. Và nếu bạn từng thắc mắc vì sao một tiến trình dùng nhiều RAM hơn dữ liệu của nó, hoặc phình lên rồi không xẹp, giờ bạn có hai lời giải thích đo được: chi phí metadata mỗi object, và việc free không trả bộ nhớ về hệ điều hành ngay. Bộ nhớ không bao giờ thật sự miễn phí; nó chỉ trông có vẻ vậy cho tới khi bạn đo.
