Suốt sê-ri này, malloc/free xuất hiện như một chi phí ẩn ở khắp nơi — mỗi node linked list, mỗi chuỗi dài, mỗi shared_ptr đều trả nó. Nhưng malloc/free không phải cách cấp phát duy nhất. Khi bạn cấp nhiều đối tượng có cùng vòng đời, có một kỹ thuật đơn giản mà nhanh gấp nhiều lần: arena allocator (còn gọi bump allocator hoặc region allocator). Nó cấp phát bằng cách chỉ tăng một con trỏ và giải phóng cả lô một lần. Tôi đo nó so với malloc/free trong container gcc:13, và con số cho thấy vì sao game engine, trình biên dịch, và web server dùng nó ở đường nóng.
Tăng con trỏ, và giải phóng cả lô
malloc/free rất linh hoạt: cấp và giải phóng bất kỳ đối tượng nào, bất kỳ lúc nào. Nhưng sự linh hoạt đó có giá — mỗi malloc phải quản lý một danh sách khối trống: tìm khối vừa, cắt nó, ghi header quản lý (~5–11 ns như phần 10 đo); mỗi free trả khối về và có thể gộp với khối lân cận.
Arena allocator bỏ hết sự linh hoạt đó để đổi lấy tốc độ: cấp một khối lớn trước, rồi phát ra bằng cách chỉ tăng một con trỏ offset (cộng căn lề). Cấp một đối tượng = vài phép tính, ~1 ns, không bookkeeping. Và giải phóng = reset offset về 0 — O(1) cho tất cả đối tượng cùng lúc, không free từng cái.
Điều này cho hai lợi thế: cấp phát nhanh hơn nhiều lần (bump so với quản lý free list), và giải phóng cả lô trong một thao tác O(1). Cộng thêm bonus: các đối tượng nằm liền mạch trong arena nên thân thiện cache. Cái giá: không free lẻ được — chỉ giải phóng cả lô.
Đo: cấp nhanh 10 lần, free cả lô O(1)
10 triệu đối tượng Node (24 byte), g++ -O2:
A. CẤP PHÁT:
malloc mỗi cái : 10,1 ns/đối tượng (quản lý free list)
arena bump : 0,98 ns/đối tượng (chỉ tăng con trỏ + căn lề)
-> arena nhanh hơn ~10 lần
B. GIẢI PHÓNG:
malloc free N lần : 4,4 ns/đối tượng (= 44 ms cho 10 triệu)
arena reset con trỏ : O(1) cho TẤT CẢ (~0 ns tổng)
-> arena tức thời
C. DUYỆT (cache locality):
arena / malloc : 0,6 ns/duyệt (~ngang nhau ở đây)
Nhìn A: cấp một đối tượng bằng malloc tốn 10,1 ns (phải quản lý free list), còn arena chỉ 0,98 ns (tăng con trỏ) — nhanh hơn ~10 lần. B còn ấn tượng hơn: free 10 triệu đối tượng từng cái mất 4,4 ns × 10 triệu = 44 mili-giây, còn arena chỉ reset một con trỏ — O(1), gần như 0 nano-giây cho tất cả. Tổng lại, xử lý 10 triệu đối tượng bằng malloc+free mất ~145 ms, còn arena chỉ ~10 ms cấp + tức thời giải phóng.
C là chỗ tôi báo trung thực: duyệt các đối tượng arena (liền mạch) và malloc (rải rác) đo được ngang nhau (0,6 ns) ở đây. Vì khi cấp một loạt đối tượng liên tiếp không xen free, malloc của glibc cũng đặt chúng liền mạch trong heap — nên không có khác biệt cache. Lợi thế cache của arena chỉ lộ ra khi bộ nhớ bị phân mảnh (cấp xen kẽ với free, hoặc lẫn với các cấp phát khác) — trong một loạt cấp phát sạch, malloc cũng liền mạch. Con số dramatic là tốc độ cấp phát và giải phóng, không phải cache trong workload này.
Một lần tôi đo hớ: "malloc là cách duy nhất" và "arena luôn tốt hơn"
Tôi vào đo với niềm tin ngầm: "cấp phát thì phải malloc/free, đó là cách duy nhất, chi phí không tránh được". Đo phá tan: arena cấp bằng cách tăng con trỏ nhanh gấp 10 lần, và giải phóng cả lô bằng một reset O(1) thay vì free 10 triệu lần (44 ms). Với các đối tượng cùng vòng đời, malloc/free không phải lựa chọn tối ưu. Còn niềm tin ngược "vậy arena luôn tốt hơn, dùng khắp nơi" cũng sai: arena không free lẻ được — nó chỉ giải phóng cả lô. 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; bạn cần malloc/free. Arena chỉ hợp khi các đối tượng chết cùng lúc.
Bài học đo lường: arena/bump allocator cấp phát bằng cách chỉ TĂNG con trỏ (0,98 ns vs malloc 10,1 ns = ~10x) và giải phóng cả lô bằng reset con trỏ O(1) (vs free N lần, 44 ms cho 10 triệu); nhưng KHÔNG free lẻ được — chỉ hợp khi các đối tượng có VÒNG ĐỜI đồng nhất (chết cùng lúc): per-frame (game), per-request (server), per-phase (trình biên dịch). Vòng đời rời rạc thì cần malloc/free. Nếu tôi tin "malloc là cách duy nhất" tôi bỏ lỡ một tối ưu 10 lần cho đường nóng; nếu tôi tin "arena luôn tốt" tôi dùng nó cho dữ liệu vòng-đời-rời-rạc và không giải phóng được từng cái.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi bạn cấp nhiều đối tượng cùng vòng đời, dùng arena. Mẫu điển hình: mọi thứ cấp trong một khung hình game (giải phóng cuối khung), một request server (giải phóng khi trả lời xong), một giai đoạn của trình biên dịch (giải phóng khi sang giai đoạn sau). Cấp một arena đầu giai đoạn, bump-allocate mọi đối tượng, reset ở cuối. Nhanh hơn nhiều malloc/free, và không bao giờ rò rỉ (reset xóa hết). Nhiều ngôn ngữ/thư viện có sẵn: std::pmr::monotonic_buffer_resource (C++17), arena của Rust, bump allocator của các game engine.
Hệ quả thứ hai: pool allocator cho đối tượng cùng kích thước có free lẻ. Nếu bạn cần free lẻ nhưng vẫn muốn nhanh, một pool allocator (giữ một free list riêng cho các khối cùng kích thước) cho phép cấp/free O(1) mỗi cái mà không tìm kiếm — trung gian giữa arena (nhanh nhất, không free lẻ) và malloc (linh hoạt nhất, chậm). Đây là cách các allocator tùy chỉnh cân bằng tốc độ và linh hoạt.
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, không phải hằng số của ngôn ngữ. Con số mang theo: arena/bump allocator: cấp bằng tăng con trỏ 0,98 ns (vs malloc 10,1 ns = ~10x), giải phóng cả lô bằng reset con trỏ O(1) (vs free N lần = 44 ms cho 10 triệu); đối tượng liền mạch (cache tốt khi phân mảnh). Cái giá: KHÔNG free lẻ — chỉ giải phóng cả lô, hợp cho vòng đời đồng nhất (per-frame, per-request, per-phase). Vòng đời rời rạc -> malloc/free; cần free lẻ nhanh -> pool allocator. Chọn allocator theo vòng đời của đối tượng, không mặc định malloc.
Thử ba mươi giây
Tự cài một arena đơn giản: malloc một khối lớn, giữ một offset, và alloc(n) chỉ trả buf + offset rồi offset += n (nhớ căn lề). Cấp vài triệu đối tượng nhỏ bằng nó so với malloc từng cái, và bấm giờ — arena nhanh hơn nhiều lần vì không quản lý free list. Rồi "giải phóng": với arena, chỉ đặt offset = 0 (một dòng, O(1) cho tất cả); với malloc, bạn phải free từng cái, mất thời gian tỷ lệ với số đối tượng. Cuối cùng, thử "free một đối tượng riêng ở giữa" — với arena bạn không làm được, và đó chính là đánh đổi. Ba mươi giây đó cho bạn thấy điều mà "cấp phát thì phải malloc" giấu đi: khi các đối tượng cùng sinh cùng tử, một arena cấp bằng cách tăng con trỏ và giải phóng cả lô nhanh hơn hàng chục lần — miễn là bạn chấp nhận không free lẻ được.
