Heap và cấp phát động — dữ liệu sống lâu hơn hàm

TL;DR: Khi bạn không biết trước kích thước dữ liệu, hoặc cần dữ liệu sống lâu hơn hàm tạo ra nó, bạn cấp phát trên heap — một vùng nhớ lớn, linh hoạt, quản lý bởi một allocator (như malloc trong C, new trong Java). Khác stack (push/pop theo LIFO, tự dọn), heap cho cấp phát và giải phóng theo bất kỳ thứ tự nào, nên allocator phải theo dõi vùng nào trống, vùng nào đang dùng. Sự tự do đó có giá: cấp phát heap chậm hơn stack hàng chục tới hàng trăm lần, và sau nhiều lần cấp/giải phóng kích thước khác nhau, heap bị fragmentation — bộ nhớ trống nhưng vỡ vụn, không gom được thành khối lớn. Hiểu heap giải thích vì sao new tốn kém, vì sao cấp phát nhiều object nhỏ gây áp lực bộ nhớ, và vì sao tái dùng object đôi khi đáng giá.

Bạn đọc một file kích thước chưa biết vào một ArrayList, nó tự lớn dần. Bạn tạo một object trong hàm rồi return nó, và nó vẫn sống sau khi hàm kết thúc. Cả hai chỉ có thể nhờ heap — vùng nhớ không bị ràng buộc vào vòng đời của một lời gọi hàm. Nhưng heap không miễn phí: nó cần một bộ máy quản lý phức tạp mà stack không cần.

Bài này giải thích vì sao heap tồn tại, allocator cấp phát và giải phóng thế nào, fragmentation phát sinh ra sao, và những quyết định code rút ra từ chi phí của heap.

1. Analogy — bãi đỗ xe so với chồng đĩa

Stack giống chồng đĩa (bài 02): chỉ thêm/lấy ở đỉnh, thứ tự cứng nhắc LIFO. Heap giống một bãi đỗ xe lớn: xe (object) đến và đi bất kỳ lúc nào, bất kỳ thứ tự nào. Người quản lý bãi (allocator) phải ghi sổ chỗ nào trống, chỗ nào có xe, và tìm chỗ đủ rộng khi một xe tải lớn (object lớn) tới.

Vấn đề nảy sinh: sau một ngày xe ra vào lộn xộn, bãi có thể còn 20 chỗ trống nhưng rải rác — không có 5 chỗ liền nhau cho một xe buýt. Bãi "còn chỗ" nhưng "không nhận được xe buýt". Đó là fragmentation.

2. Cơ chế — allocator làm gì khi bạn gọi new

Khi chương trình khởi động, OS cấp cho heap một vùng địa chỉ liên tục lớn. Allocator (một thư viện như malloc của glibc, hoặc bộ cấp phát của JVM) quản lý vùng này. Nó giữ một free list — danh sách các khối trống và kích thước.

Khi bạn gọi malloc(size) hoặc new:

1. Allocator duyệt free list tìm một khối trống đủ lớn (≥ size).
2. Cắt khối đó: phần size byte giao cho bạn, phần dư (nếu có) trả lại free list.
3. Đánh dấu khối đã giao là "đang dùng" và trả về địa chỉ đầu khối.

Khi bạn free(ptr) (C) hoặc GC xác định object chết (Java):

1. Khối được đánh dấu trống, đưa lại free list.
2. Nếu khối kề một khối trống khác, allocator gộp (coalesce) chúng thành khối lớn hơn để chống fragmentation.

flowchart TD
  A["new MyObject()"] --> B{"Free list co khoi<br/>du lon khong?"}
  B -->|Co| C["Cat khoi, danh dau dang dung"]
  B -->|Khong| D["Xin them tu OS (sbrk/mmap)<br/>hoac chay GC"]
  C --> E["Tra ve dia chi object"]
  D --> C

Khác biệt cốt lõi với stack: stack cấp phát bằng một phép dịch stack pointer (1 lệnh); heap cấp phát bằng duyệt và cập nhật cấu trúc dữ liệu (hàng chục–trăm lệnh, có thể phải khoá để an toàn đa luồng). Đây là lý do cấp phát heap chậm hơn stack đáng kể.

Heap sau vai lan cap phat/giai phong:

[#### A ####][ trong ][## B ##][ trong ][###### C ######][  trong  ]
             ^4KB              ^2KB                       ^6KB trong
Tong trong = 12KB, nhung khoi lien tuc lon nhat = 6KB
-> mot object 8KB KHONG cap phat duoc du "con 12KB" -> fragmentation

3. Fragmentation — vì sao "còn bộ nhớ" mà vẫn hết

Có hai loại fragmentation:

• External fragmentation: bộ nhớ trống bị chia thành nhiều khối nhỏ rải rác (như bãi đỗ xe ở trên). Tổng trống đủ, nhưng không khối liền nào đủ lớn cho yêu cầu mới. Đây là loại gây OutOfMemoryError dù "còn chỗ".
• Internal fragmentation: allocator làm tròn kích thước lên (ví dụ luôn cấp bội số của 16 byte để căn chỉnh). Bạn xin 20 byte, nhận 32 byte — 12 byte dư bên trong khối bị lãng phí.

Allocator hiện đại chống fragmentation bằng nhiều kỹ thuật: phân loại khối theo kích thước (size classes), gộp khối kề nhau, hoặc — trong các runtime có GC như JVM — nén (compaction): di chuyển các object còn sống về sát nhau, dồn vùng trống thành một khối lớn liền mạch.

flowchart LR
  subgraph before["Truoc compaction"]
    direction LR
    X1["A"] --- G1[" "] --- X2["B"] --- G2[" "] --- X3["C"]
  end
  subgraph after["Sau compaction"]
    direction LR
    Y1["A"] --- Y2["B"] --- Y3["C"] --- G3["vung trong lien tuc"]
  end
  before --> after

4. Áp dụng vào code của bạn

Hiểu chi phí heap dẫn tới vài quyết định thực tế về tốc độ và áp lực bộ nhớ.

Tránh cấp phát trong vòng lặp nóng. Mỗi new là một lần gọi allocator. Cấp phát object tạm trong vòng lặp chạy triệu lần tạo áp lực lớn lên allocator và GC:

// SAI: tao mot StringBuilder moi moi vong lap
for (int i = 0; i < 1_000_000; i++) {
    StringBuilder sb = new StringBuilder(); // 1 trieu lan cap phat
    sb.append(prefix).append(i);
    results.add(sb.toString());
}

// TOT HON: tai dung, clear thay vi cap phat lai
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1_000_000; i++) {
    sb.setLength(0);              // reset, khong cap phat moi
    sb.append(prefix).append(i);
    results.add(sb.toString());
}

Cấp phát sẵn dung lượng (pre-size) cho collection. ArrayList lớn dần bằng cách cấp một mảng mới lớn hơn rồi copy — mỗi lần grow là một lần cấp phát + copy. Nếu biết trước kích thước, cấp sẵn:

// SAI: list grow nhieu lan, moi lan cap phat + copy mang
List<Item> items = new ArrayList<>();
for (int i = 0; i < 100_000; i++) items.add(load(i));

// TOT: cap san dung luong -> 1 lan cap phat
List<Item> items = new ArrayList<>(100_000);
for (int i = 0; i < 100_000; i++) items.add(load(i));

Object pool cho object đắt. Khi object tốn kém để tạo (kết nối DB, buffer lớn), tái dùng qua pool thay vì cấp phát/giải phóng liên tục — đây là lý do connection pool tồn tại. Nhưng đừng lạm dụng: với object rẻ, pool phức tạp hoá code mà GC hiện đại (cấp phát object non rất nhanh) thường xử lý tốt hơn.

5. Đào sâu (tuỳ chọn)

6. Liên hệ các bài khác

• Bài 02 — Stack và stack frame: đối lập trực tiếp với heap — stack nhanh, tự dọn, LIFO; heap linh hoạt nhưng tốn kém. Dữ liệu thoát khỏi hàm phải lên heap.
• Bài 04 — Stack vs heap vs static: tổng hợp ba vùng và quy tắc chọn vùng nào cho dữ liệu nào.
• Module 4 — Quản lý bộ nhớ ngôn ngữ bậc cao: ai giải phóng object heap (bạn hay GC), và GC compaction chống fragmentation thế nào.

7. Tóm tắt

• Heap là vùng nhớ lớn, linh hoạt, cho cấp phát kích thước tuỳ ý lúc chạy và sống lâu hơn hàm tạo ra nó.
• Cấp phát heap do allocator quản lý: duyệt free list, cắt khối, đánh dấu đang dùng — tốn nhiều lệnh hơn stack hàng chục tới hàng trăm lần.
• Fragmentation phát sinh khi cấp/giải phóng kích thước khác nhau: external (trống rải rác, không khối lớn liền) và internal (làm tròn kích thước, dư bên trong).
• Allocator chống fragmentation bằng size class, gộp khối kề; runtime có GC còn nén (compaction) — di chuyển object còn sống về sát nhau, điều C không làm được.
• Quyết định thực tế: tránh cấp phát trong vòng lặp nóng, pre-size collection, pool object đắt — nhưng luôn đo trước, vì GC hiện đại cấp phát object non gần như miễn phí.

8. Tự kiểm tra

Bài tiếp theo: Stack vs heap vs static