Phần trước đo một arena allocator: cấp bằng cách tăng con trỏ, nhanh gấp 10 lần malloc, giải phóng cả lô bằng một reset O(1). Nhưng arena có một cái giá lớn — không free lẻ được. Nếu các đối tượng của bạn chết rời rạc (cái này lúc này, cái kia lúc khác), arena bó tay. Câu hỏi tự nhiên: muốn free lẻ và vẫn nhanh, có phải quay lại malloc/free không? Câu trả lời là danh sách tự do (free list) / pool allocator: giữ các ô cùng kích thước, xâu những ô đã free vào một danh sách liên kết, cấp và free từng ô trong O(1). Tôi đo nó so với malloc/free trong container gcc:13, và con số cho thấy nó lấp đúng khoảng giữa arena và malloc.
Xâu ô trống thành danh sách: cấp và free O(1)
Ý tưởng của pool free list: cấp trước một khối lớn chia thành các ô cùng kích thước (ví dụ mỗi ô 24 byte cho một Node). Giữ một con trỏ freehead trỏ tới đầu một danh sách liên kết các ô đang trống. Hai thao tác đều O(1):
- Cấp (
alloc): lấy ô ở đầu free list (p = freehead; freehead = *(void**)freehead), hoặc nếu list rỗng thì bump một ô mới từ khối. Không tìm kiếm, không quản lý free list phức tạp nhưmalloc. - Free (
dealloc): đẩy ô vừa trả về đầu free list (*(void**)p = freehead; freehead = p). Cũng O(1), không gộp khối lân cận.
Khác với arena của phần trước, free list cho phép free lẻ và tái dùng ngay ô vừa free — nên bộ nhớ không phình lên dù bạn cấp/free hàng chục triệu lần. Đây là allocator mà nhiều thư viện dùng cho node cây, hạt (particle) game, kết nối mạng — những đối tượng cùng cỡ, sinh và tử liên tục.
Có một mẹo tinh tế trong "con trỏ next" của free list: nó được nhúng ngay trong chính ô trống. Một ô đang dùng chứa dữ liệu (Node); một ô đang trống thì không có dữ liệu gì, nên ta mượn luôn không gian đó để lưu con trỏ tới ô trống kế tiếp. Vì thế free list không tốn thêm một mảng con trỏ hay header nào — 0 byte thừa.
Đo: churn nhanh 5,7 lần, con trỏ next tốn 0 byte
Tôi giữ 1 triệu ô sống cùng lúc, rồi lặp 20 triệu lượt free một ô ngẫu nhiên và cấp lại một ô (đúng kiểu "churn" của một cache hay một tập đối tượng động). So pool free list tự cài với malloc/free:
Node 24 byte, g++ -O2:
A. CHURN (giữ 1 triệu ô sống, 20 triệu lượt free + cấp lại):
POOL free list : 6,96 ns/lượt (lấy/đẩy đầu list, TÁI DÙNG ô vừa free)
malloc/free : 39,66 ns/lượt (quản lý free list toàn cục mỗi lần)
-> pool nhanh hơn ~5,7 lần
B. BỘ NHỚ (con trỏ next):
next NHÚNG trong ô TRỐNG -> 0 byte thừa
1 triệu ô × 24 byte = 24 MB (= đúng dữ liệu thô, không phình)
Nhìn A: một lượt free-rồi-cấp qua pool free list mất 6,96 ns — chỉ vài phép gán con trỏ để đẩy/lấy đầu list. Cùng lượt đó qua malloc/free mất 39,66 ns, vì malloc phải quản lý một free list toàn cục nhiều cỡ khối (tìm khối vừa, có thể tách/gộp, ghi header quản lý), còn free có thể gộp với khối lân cận. Pool nhanh hơn ~5,7 lần — và toàn bộ khác biệt là chi phí bookkeeping mà pool bỏ đi được nhờ mọi ô cùng một cỡ: không cần chọn cỡ, không cần gộp, chỉ đẩy/lấy đầu một danh sách.
B kiểm chứng cái mẹo "con trỏ next nhúng trong ô trống": pool giữ 1 triệu ô × 24 byte = đúng 24 MB, bằng dữ liệu thô, không một byte nào cho danh sách liên kết các ô trống. Vì con trỏ next chỉ tồn tại khi ô đang trống — lúc đó ô không chứa Node nào, nên mượn 8 byte đầu của nó làm con trỏ là hoàn toàn miễn phí. Khi ô được cấp lại, 8 byte đó lập tức thành dữ liệu Node. Không chồng chéo, không lãng phí.
Ba mức đánh đổi: arena, free list, malloc
Gộp ba phần lại, ta có một phổ rõ ràng về cấp phát:
- Arena (phần trước): nhanh nhất để cấp (bump con trỏ ~1 ns), giải phóng cả lô O(1), nhưng không free lẻ — chỉ hợp khi các đối tượng chết cùng lúc (per-frame, per-request).
- Free list / pool: cấp và free từng ô O(1), churn nhanh ~5,7 lần malloc, tái dùng ô nên không phình — nhưng đòi các ô cùng kích thước.
malloc/free(phần 10): linh hoạt nhất (mọi cỡ, free lẻ bất kỳ lúc nào), nhưng chậm nhất vì phải quản lý free list toàn cục nhiều cỡ.
Đi từ trái sang phải là đổi tính linh hoạt lấy tốc độ: arena bỏ free lẻ để đạt tốc độ tối đa; free list lấy lại free lẻ nhưng đòi cùng cỡ; malloc cho mọi thứ nhưng trả giá đắt nhất mỗi thao tác.
Một lần tôi đo hớ: "muốn free lẻ thì phải malloc" và "free list tốn thêm bộ nhớ cho next"
Tôi vào đo với một suy luận nghe rất chặt: "arena không free lẻ được, vậy nếu cần free từng cái thì phải quay lại malloc/free, không có đường nào khác". Đo phá tan: một pool free list free lẻ O(1) (đẩy ô vào đầu list) và cấp lại O(1) (lấy đầu list, tái dùng chính ô vừa free) — churn 6,96 ns/lượt so với malloc/free 39,66 ns, nhanh gấp 5,7 lần, và còn chống phân mảnh vì luôn dùng lại đúng những ô cũ. "Cần free lẻ" không buộc phải dùng malloc; với các đối tượng cùng cỡ, một pool free list vừa free lẻ vừa nhanh hơn nhiều.
Còn một niềm tin ngược cũng sai: "free list thì phải tốn thêm bộ nhớ để lưu con trỏ next cho mỗi ô". Nghe hợp lý — một danh sách liên kết cần con trỏ mà. Nhưng đo cho thấy 1 triệu ô chỉ tốn đúng 24 MB, 0 byte thừa: con trỏ next được nhúng ngay trong ô đang trống. Ô đang dùng chứa dữ liệu; ô trống không có dữ liệu nên mượn không gian đó làm con trỏ — hai vai trò không bao giờ tồn tại cùng lúc trên một ô, nên không chồng chéo.
Bài học đo lường: pool free list cho đối tượng CÙNG KÍCH THƯỚC: free lẻ O(1) (đẩy ô vào đầu list) + cấp O(1) (lấy đầu list, TÁI DÙNG ô vừa free) — churn 6,96 ns/lượt vs malloc/free 39,66 ns = ~5,7x nhanh, chống phân mảnh vì dùng lại đúng ô cũ; con trỏ next NHÚNG trong ô TRỐNG nên 0 byte thừa (24 MB đúng bằng dữ liệu thô). "Cần free lẻ thì phải malloc" SAI; "free list tốn thêm cho next" cũng SAI. Nếu tôi tin cái thứ nhất, tôi bỏ lỡ một allocator nhanh 5,7 lần cho đúng loại workload đó; nếu tôi tin cái thứ hai, tôi tưởng free list lãng phí bộ nhớ trong khi nó không tốn gì thêm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi bạn cấp và free liên tục nhiều đối tượng CÙNG CỠ, dùng pool free list thay vì malloc/free. Node cây/danh sách, hạt trong game, khung kết nối mạng, ô trong một cache — chúng cùng kích thước và sinh-tử liên tục, đúng sân của free list. Cấp một khối lớn, chia ô, giữ một freehead; alloc lấy đầu list, dealloc đẩy vào đầu. Bạn được free lẻ và nhanh gấp mấy lần malloc, lại không phân mảnh. Nhiều thư viện chuẩn có sẵn: std::pmr::unsynchronized_pool_resource (C++17) chính là ý tưởng này.
Hệ quả thứ hai: chọn allocator theo vòng đời và tính đồng nhất của đối tượng, không mặc định malloc. Ba câu hỏi: các đối tượng có chết cùng lúc không? → arena. Chúng cùng cỡ và chết rời rạc không? → pool free list. Khác cỡ và cần tự do hoàn toàn? → malloc/free. malloc là mặc định tiện nhưng là điểm chậm nhất trong ba lựa chọn; khi một trong hai điều kiện đặc biệt kia đúng, bạn có một allocator nhanh hơn nhiều đang chờ.
Hệ quả thứ ba là tinh thần đo lường: cấp phát bộ nhớ là một chi phí có thể thiết kế lại, và có cả một phổ giữa "nhanh cứng nhắc" (arena) và "chậm linh hoạt" (malloc). Con số mang theo: pool free list (ô cùng cỡ): cấp/free lẻ O(1) bằng đẩy-lấy đầu một danh sách liên kết các ô trống — churn 6,96 ns/lượt vs malloc/free 39,66 ns = ~5,7x, tái dùng ô nên chống phân mảnh; con trỏ next nhúng trong ô trống = 0 byte thừa. Trung gian giữa arena (nhanh nhất, không free lẻ) và malloc (linh hoạt nhất, chậm nhất). Đừng để "malloc là cách duy nhất để free lẻ" giấu đi một tối ưu 5,7 lần.
Thử ba mươi giây
Tự cài một pool free list: malloc một khối lớn chia thành các ô cùng cỡ (mỗi ô ít nhất bằng sizeof(void*)), giữ một con trỏ freehead. alloc() trả freehead rồi cho freehead nhảy tới ô kế (freehead = *(void**)freehead), hoặc bump một ô mới nếu list rỗng. dealloc(p) làm ngược: *(void**)p = freehead; freehead = p. Rồi giữ vài triệu ô sống và lặp hàng chục triệu lượt free-một-ô-rồi-cấp-lại, so với malloc/free cùng vòng lặp — pool nhanh hơn nhiều lần vì mỗi thao tác chỉ là vài phép gán con trỏ, không quản lý free list toàn cục. Cuối cùng, để ý rằng bạn không khai một mảng con trỏ next nào cả — con trỏ nằm ngay trong ô trống, và khi ô được cấp lại, 8 byte đó lập tức thành dữ liệu. Ba mươi giây đó cho bạn thấy điều mà "muốn free lẻ thì phải malloc" giấu đi: với các đối tượng cùng cỡ, một danh sách liên kết các ô trống cho bạn free lẻ O(1), tái dùng ô, và tốc độ gấp mấy lần malloc — mà không tốn một byte bộ nhớ nào cho chính danh sách đó.
