Hai phần trước đo hai allocator "gọn gàng": arena cấp bằng tăng con trỏ rồi giải phóng cả lô, và free list/pool cấp/free từng ô cùng cỡ O(1). Cả hai đều tránh được một vấn đề mà malloc/free thông thường phải sống chung: phân mảnh (fragmentation). Khi bạn cấp và free nhiều đối tượng khác cỡ xen kẽ nhau, heap vỡ thành nhiều hố trống rải rác không liền nhau — và điều đó tốn kém hơn "chỉ là lãng phí một chút bộ nhớ" rất nhiều. Tôi đo cái giá thật của phân mảnh trong container gcc:13 bằng cách đọc RSS thật của tiến trình, và con số cho thấy hai niềm tin phổ biến đều sai.
Free không trả về hệ điều hành, và hố nhỏ không lấp được request lớn
Có một mô hình tinh thần đơn giản mà nhiều người mang theo: "malloc xin bộ nhớ, free trả nó lại; free xong thì bộ nhớ về hệ điều hành, RSS giảm". Thực tế phức tạp hơn nhiều, và hai điểm sau là gốc của mọi chi phí phân mảnh:
freethường không trả bộ nhớ về hệ điều hành. Với các khối nhỏ, glibc cấp từ một vùng heap mở rộng bằngbrk. Khi bạnfree, nó chỉ đánh dấu khối là trống và giữ lại trong danh sách trống của chính nó để tái dùng — chứ không thu hẹp heap trả về nhân. Nên RSS (bộ nhớ thật tiến trình đang chiếm) không giảm dù dữ liệu sống của bạn tụt xuống.- Hố trống rời rạc không phải lúc nào cũng dùng lại được. Nếu các hố nhỏ và nằm rải rác giữa các khối còn sống, một request lớn hơn không lọt vào bất kỳ hố nào.
mallockhông thể gộp các hố không liền nhau thành một khối lớn, nên nó buộc phải xin thêm bộ nhớ — heap phình ra dù đang còn rất nhiều chỗ trống cộng lại.
Đây là external fragmentation (phân mảnh ngoài): tổng bộ nhớ trống thì nhiều, nhưng bị chia vụn thành những mảnh quá nhỏ để dùng cho việc cần. Nó khác với chuyện vector mọc lại hay căn lề — đây là hệ quả của lịch sử cấp/free, không phải của một cấu trúc đơn lẻ.
Đo: giữ gấp 12 lần, và cấp lại làm phình thêm 563 MB
Tôi dựng một mẫu cấp/free "loạn": cấp 4 triệu ô cỡ ngẫu nhiên 16–271 byte, chạm vào từng ô để nó thật sự vào RSS, rồi free ngẫu nhiên ~90% — để lại các hố nhỏ rải rác. Sau đó cấp lại 2 triệu ô 512 byte (lớn hơn phần lớn hố). Đọc RSS thật từ /proc/self/statm ở mỗi mốc:
RSS thật (/proc/self/statm), g++ -O2:
A. NHIỀU CỠ (16..271 byte, gây phân mảnh):
Pha 1 cấp 4tr ô : RSS 655 MB, sống 547 MB
Pha 2 free 90% ngẫu nhiên: RSS 655 MB, sống 55 MB -> RSS/sống = 12x
Pha 3 cấp lại 2tr ô 512B : RSS phình +563 MB (hố nhỏ không lấp được)
B. CÙNG CỠ 64 byte (tái dùng hố, không phân mảnh):
Pha 3 cấp lại 2tr ô 64B : RSS phình +0 MB (tái dùng đúng các hố vừa free)
Nhìn A pha 2 — đây là con số phá vỡ niềm tin thứ nhất: sau khi free 90% số ô, dữ liệu sống chỉ còn 55 MB, nhưng RSS vẫn giữ nguyên 655 MB. Tiến trình đang chiếm gấp 12 lần bộ nhớ nó thực sự cần. free đã chạy đủ 3,6 triệu lần, nhưng không một byte nào trả về hệ điều hành — glibc giữ hết trong heap để tái dùng sau. Nếu bạn nhìn top hay RES và tưởng "chương trình đang dùng 655 MB dữ liệu", bạn sai gấp 12 lần.
Nhìn A pha 3 — đây là con số phá vỡ niềm tin thứ hai. Ta vừa có 600 MB "trống" nằm trong heap (các hố 16–271 byte). Nhưng khi cấp 2 triệu ô 512 byte, chúng không lọt vào những hố nhỏ đó, và malloc không gộp được các hố rời rạc — nên heap phải phình thêm 563 MB. Bộ nhớ trống thì có thừa, nhưng sai kích thước và rời rạc, nên vô dụng. Phân mảnh không chỉ giữ bộ nhớ cũ; nó còn ép bạn xin bộ nhớ mới.
Nhìn B để thấy tương phản: làm đúng cùng chuỗi thao tác nhưng mọi ô đều 64 byte. Sau khi free 90% rồi cấp lại 2 triệu ô cùng 64 byte, heap phình +0 MB — vì mỗi ô mới lọt đúng vào một hố vừa free. Cùng kích thước nghĩa là mọi hố đều tái dùng được, nên không có phân mảnh ngoài. Đây chính là lý do pool free list của phần trước chống phân mảnh: nó ép mọi ô cùng cỡ.
(Một lưu ý trung thực: RSS tuyệt đối ở kịch bản B cao vì nó chạy sau A trong cùng tiến trình và thừa hưởng phần heap mà A đã giữ lại — thêm một bằng chứng nữa rằng bộ nhớ không được trả về. Con số có ý nghĩa ở B là mức phình +0 MB, so với +563 MB của A.)
Một lần tôi đo hớ: "free là trả về hệ điều hành ngay" và "phân mảnh chỉ là lãng phí bộ nhớ"
Tôi vào đo với một mô hình ngây thơ: "free(p) là trả p về hệ điều hành; free hết thì RSS về gần 0". Đo phá tan: sau khi free 90% của 4 triệu ô nhỏ, RSS vẫn giữ 655 MB trong khi dữ liệu sống chỉ 55 MB — glibc giữ lại các hố nhỏ trong heap brk để tái dùng, không trả về nhân. "Free xong là hết chiếm" là sai: một dịch vụ chạy lâu có thể phình RSS lên đỉnh rồi giữ nguyên mãi, dù tải đã giảm — người ta hay nhầm đó là "rò rỉ bộ nhớ" trong khi thực ra là phân mảnh/giữ lại.
Còn một niềm tin ngược cũng sai: "phân mảnh thì cũng chỉ là lãng phí một ít bộ nhớ thôi, không sao". Đo cho thấy nó tệ hơn thế: các hố nhỏ rời rạc không lấp được request lớn hơn, nên cấp lại 2 triệu ô 512B làm heap phình thêm 563 MB — phân mảnh không chỉ giữ bộ nhớ cũ mà còn ép xin bộ nhớ mới, và các đối tượng nằm rải rác khắp một heap lớn cũng làm cache tệ đi (như phần duyệt mảng vs danh sách). Nó là một chi phí kép: RAM và tốc độ.
Bài học đo lường: phân mảnh ngoài — cấp/free loạn nhiều CỠ khác nhau làm heap vỡ thành hố rời rạc: (1) free KHÔNG trả bộ nhớ về HĐH ngay (free 90% mà RSS giữ 655 MB vs sống 55 MB = 12x, glibc giữ hố trong heap brk); (2) hố nhỏ rời rạc KHÔNG lấp được request lớn hơn (cấp lại 512B -> heap phình +563 MB), trong khi CÙNG cỡ tái dùng đúng hố -> +0 MB. Phân mảnh = giữ RAM thừa + ép xin thêm + cache tệ. Nếu tôi tin "free là trả về ngay" tôi đọc sai RSS gấp 12 lần và chẩn nhầm phân mảnh thành rò rỉ; nếu tôi tin "chỉ lãng phí chút bộ nhớ" tôi bỏ qua chuyện nó làm cấp phát phình và cache chậm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: với dịch vụ chạy lâu cấp/free nhiều cỡ, đừng đọc RSS như "dữ liệu đang dùng". RSS phản ánh đỉnh bộ nhớ heap từng chạm cộng phần giữ lại, không phải dữ liệu sống hiện tại. Một tiến trình phình lên lúc tải cao rồi giữ nguyên RSS khi tải giảm thường là phân mảnh/giữ lại, không phải rò rỉ. Muốn phân biệt: đo dữ liệu sống thật của bạn và so với RSS — chênh nhiều lần và ổn định (không tăng vô hạn) là dấu hiệu phân mảnh, còn tăng mãi mới là rò rỉ.
Hệ quả thứ hai: khi bạn cấp/free nhiều đối tượng nhỏ cùng cỡ với tần suất cao, dùng pool/free list hoặc arena để cắt phân mảnh. Đây là chỗ ba phần nối vào nhau: cùng cỡ và chết rời rạc → pool free list (mọi hố tái dùng được, +0 MB như đo); chết cùng lúc → arena (bump rồi reset cả lô, không có hố nào). Cả hai ép một trật tự lên bộ nhớ mà malloc đa cỡ không có được. Nhiều runtime (game engine, database, allocator như jemalloc/tcmalloc) chia bộ nhớ thành các "size class" cùng cỡ chính vì lý do này.
Hệ quả thứ ba là tinh thần đo lường: "cấp rồi giải phóng" không phải một cặp đối xứng sạch — lịch sử cấp/free để lại dấu vết trong bộ nhớ. Con số mang theo: phân mảnh ngoài giữ RSS cao hơn dữ liệu sống nhiều lần (đo 12x sau khi free 90%) vì free không trả về HĐH, và hố nhỏ rời rạc ép heap phình khi gặp request lớn hơn (+563 MB); ép cùng cỡ (pool) hay cùng vòng đời (arena) thì hố luôn tái dùng được (+0 MB). Đọc RSS phải nhớ nó gồm cả phần giữ lại, không chỉ dữ liệu sống. Chọn allocator và cỡ đối tượng có tính đến cách chúng sinh và tử theo thời gian, không chỉ tổng bộ nhớ tức thời.
Thử ba mươi giây
Viết một vòng cấp 4 triệu khối cỡ ngẫu nhiên nhỏ (16–271 byte), chạm vào từng khối, rồi đọc RSS từ /proc/self/statm (số trang resident × kích thước trang). Ghi lại RSS và tổng byte sống. Giờ free ngẫu nhiên 90% số khối và đọc lại: bạn sẽ thấy dữ liệu sống tụt còn ~10%, nhưng RSS gần như không đổi — free không trả về hệ điều hành. Rồi cấp thêm vài triệu khối lớn hơn (512 byte) và xem RSS phình ra dù bạn vừa "giải phóng" hàng trăm MB — vì các hố quá nhỏ và rời rạc. Cuối cùng, lặp lại toàn bộ nhưng cho mọi khối cùng một cỡ: lần này cấp lại không làm phình gì, vì mỗi khối mới lọt đúng một hố cũ. Ba mươi giây đó cho bạn thấy điều mà "free là trả bộ nhớ về hệ điều hành" giấu đi: bộ nhớ đã cấp và free để lại một cái heap vỡ vụn, và chính hình dạng của những mảnh vỡ đó — chứ không phải tổng dung lượng — quyết định lần cấp sau nhanh hay chậm, gọn hay phình.
