Cấp phát nhanh gấp 10 lần malloc bằng một mẹo cũ: arena

Nghĩ về một tấm bảng trắng cạnh bàn làm việc. Suốt cả buổi họp bạn cứ viết thêm ý này ý kia xuống dưới, không bao giờ xóa lẻ một dòng — quá phiền. Đến cuối buổi, bạn cầm khăn lau một phát sạch cả bảng. Viết thì cực nhanh (chỉ hạ bút xuống chỗ trống kế tiếp), xóa cũng cực nhanh (một nhát lau cho tất cả). Cái giá duy nhất: bạn không thể xóa riêng dòng thứ ba mà giữ nguyên phần còn lại. Đó gần như đúng cách một arena allocator làm việc với bộ nhớ.

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. Đúng cái bảng trắng: hạ bút xuống chỗ trống kế tiếp, rồi cuối buổi lau một nhát.

Đ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 muốn nói thẳng cho sòng phẳng: 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ôi trường đo: container gcc:13 trên host ARM AArch64, glibc malloc, g++ -O2, mỗi số lấy MIN sau warmup chia số đối tượng. Con số đổi theo máy và allocator; cái cần nhìn là tỉ lệ ~10x cấp phát và reset O(1) so với free 44 ms.)

Hai niềm tin đối nghịch, cùng sai

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". Con số bác thẳng: 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.

Nhưng niềm tin ngược lại — "vậy arena luôn tốt hơn, dùng khắp nơi cho nhanh" — cũng sai, và sai theo cách dễ gây họa. 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 — đúng cái bảng trắng chỉ lau được cả bảng, không tẩy được một dòng.

Về đến code hằng ngày

Điều đầ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ữ và 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.

Điều thứ hai, nối với phần free list: cần free lẻ mà vẫn nhanh thì dùng pool allocator. Nếu các đối tượng cùng kích thước nhưng chết rời rạc, một pool (free list riêng cho khối cùng cỡ) cho 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 nhất). Tôi hay chọn allocator bằng đúng một câu hỏi: các đối tượng này chết cùng lúc hay rời rạc? Cùng lúc → arena; rời rạc mà cùng cỡ → pool; còn lại → malloc.

Chỗ này thú vị là các runtime "cao cấp" đã làm sẵn arena cho bạn mà bạn không để ý. Cấp một đối tượng mới trong Java hay Go rẻ giật mình — thường chỉ một phép bump con trỏ — chính vì mỗi luồng có một vùng nhớ bump riêng (TLAB trong JVM), y hệt arena trong bài này; khác biệt là việc thu hồi thì giao cho garbage collector thay vì reset thủ công. Go còn cho lập trình viên chạm thẳng vào ý tưởng arena qua gói arena thử nghiệm để cấp cả cụm đối tượng của một request rồi giải phóng một lần. Và các database thì dùng "memory context" (PostgreSQL gọi đúng tên đó): mỗi câu truy vấn cấp bộ nhớ trong một context riêng, xử lý xong thì hủy cả context một phát — đúng mô hình per-request, không cần lần theo từng mẩu để free. Cùng một ý tưởng bảng-trắng-lau-một-nhát, lặp lại ở mọi tầng.

Muốn tự thấy thì 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. Vài phút đó 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.