Hình dung một cái kệ sách đầy dần. Có hai cách xử lý khi hết chỗ. Cách thứ nhất: mỗi lần thêm đúng một cuốn mà kệ đã đầy, bạn mua một cái kệ lớn hơn đúng một khe, rồi khuân toàn bộ sách sang — làm vậy mỗi lần thêm sách, và càng nhiều sách thì mỗi cú khuân càng nặng. Cách thứ hai: khi đầy, bạn mua một cái kệ lớn gấp đôi và khuân sang — chuyện khuân trở nên hiếm, và tuy thỉnh thoảng phải khuân cả một kệ to, tính trung bình mỗi cuốn sách chỉ tốn công khuân rất nhỏ. Cách thứ nhất là "grow-by-1", cách thứ hai là "nhân đôi" — và đó chính là bí mật khiến std::vector nhanh.

Mảng động — std::vector, ArrayList, list của Python — là cấu trúc dữ liệu bạn dùng nhiều nhất, và nó có một bí mật: mảng bên dưới cố định kích thước, nên khi bạn push_back mà nó đầy, nó phải cấp một buffer lớn hơn rồi copy toàn bộ dữ liệu cũ sang. Nghe như mỗi lần thêm phần tử phải copy cả mảng — chậm khủng khiếp? Hay nếu chỉ cấp thêm đúng một ô mỗi lần thì tiết kiệm bộ nhớ hơn? Cả hai suy nghĩ đều dẫn tới kết luận sai, và khác biệt là cả một bậc độ phức tạp. Tôi đo ba chiến lược mọc lại trong container gcc:13, và con số phân tách O(1) khỏi thảm họa O(N²).

Ba cách mọc, và phép màu amortize

Khi mảng động đầy, nó cấp buffer mới, copy dữ liệu cũ sang, giải phóng buffer cũ. (Với std::vector, đây là copy thật — gọi copy/move constructor cho từng phần tử — không dùng được realloc mở rộng tại chỗ.) Buffer này nằm trên heap, và mỗi lần cấp lớn dần chính là kiểu heap mọc dần mà sê-ri hệ điều hành đã đo. Câu hỏi là: buffer mới lớn hơn bao nhiêu?

  • Nhân đôi (×2) — như std::vector: khi đầy, tăng capacity gấp đôi. Copy chỉ xảy ra khi đầy (log N lần cho N phần tử). Chìa khóa: tổng công của tất cả các lần copy là 1 + 2 + 4 + ... + N, một chuỗi hình học bằng khoảng 2N — không phải N mỗi lần. Nên dù có những lần copy lớn, trung bình mỗi push_back chỉ tốn O(1). Đây gọi là amortize (khấu hao): chi phí đắt của vài lần copy được chia đều cho tất cả các lần push — mua kệ gấp đôi, khuân hiếm.

  • Grow-by-1 (+1): khi đầy, chỉ cấp thêm đúng một ô. Nghe "tiết kiệm bộ nhớ" (không dự phòng thừa), nhưng: mỗi push đều làm mảng đầy, nên mỗi push copy cả mảng. Tổng công là 1 + 2 + 3 + ... + N = N²/2 — O(N²), thảm họa bậc hai — khuân cả kệ mỗi lần thêm một cuốn.

  • Reserve: nếu biết trước N, cấp đủ ngay một lần — 0 lần mọc lại, nhanh nhất.

Tôi tự cài mảng động bằng malloc/memcpy để kiểm soát chiến lược, và đếm cả tổng số phần tử phải copy.

Đo: O(1) so với O(N²)

Xây mảng động bằng push (malloc buffer mới + memcpy khi mọc):
  NHÂN ĐÔI (×2)  N = 20.000.000 : 0,051 s | copy ~1,7N (33,5 triệu) | 2,57 ns/push (amortize O(1))
  RESERVE trước  N = 20.000.000 : 0,007 s | copy 0                  | 0,33 ns/push (0 mọc lại)
  GROW-BY-1 (+1) N =     50.000 : 0,161 s | copy ~N²/2 (1,25 TỶ!)  | 3.213 ns/push (O(N²))

Nhân đôi xây 20 triệu phần tử trong 0,051 giây — chỉ 2,57 ns mỗi push. Tổng số phần tử phải copy qua tất cả các lần mọc chỉ là ~33,5 triệu (~1,7N), bị chặn tuyến tính dù có lần copy 10 triệu phần tử. Đó là amortize làm việc: một vài lần copy lớn, nhưng chia cho 20 triệu push thì trung bình vẫn O(1). Reserve còn nhanh hơn (0,33 ns/push) vì không mọc lại lần nào.

Giờ nhìn grow-by-1: nó chỉ xây được 50 nghìn phần tử (ít hơn 400 lần) mà mất 0,161 giây — lâu gấp 3 lần thời gian nhân đôi xây 20 triệu. Mỗi push tốn 3.213 ns, chậm hơn nhân đôi ~1.250 lần. Vì tổng số phần tử phải copy là ~N²/2 = 1,25 tỷ — chỉ cho 50 nghìn phần tử! Nếu grow-by-1 xây 20 triệu như nhân đôi, nó sẽ mất (20M/50k)² × 0,161s ≈ 400² × 0,161 ≈ 25.760 giây ≈ 7 tiếng. Đó là O(N²): tăng dữ liệu 100 lần, chậm 10.000 lần.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, mỗi số lấy MIN sau warmup. Con số đổi theo máy; cái cần nhìn là amortize chặn tổng copy ở ~2N (O(1)/push) so với N²/2 của grow-by-1, và 7 giờ là suy ra từ tỉ lệ N², không phải chạy thật.)

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

Tôi vào đo với hai niềm tin trái nhau mà cùng lệch. Thứ nhất: "mỗi push_back phải copy cả mảng, nên vector chậm". Sai — nhân đôi amortize: copy chỉ xảy ra khi đầy (log N lần), và tổng công mọi lần copy là ~2N, nên trung bình mỗi push chỉ 2,57 ns = O(1). Vector không chậm; nó nhanh chính vì chiến lược mọc thông minh.

Thứ hai, ngược lại: "grow-by-1 tiết kiệm bộ nhớ (không dự phòng thừa) nên tốt hơn". Cũng sai — nó biến việc xây mảng thành O(N²), chậm thảm họa; "tiết kiệm" vài phần trăm RAM để trả giá gấp hàng nghìn lần thời gian. Toán học đằng sau rất gọn: chuỗi hình học 1+2+4+...+N ≈ 2N (tăng cấp số nhân → tổng tuyến tính) so với chuỗi cộng 1+2+...+N = N²/2 (tăng cấp số cộng → tổng bậc hai). Nhân đôi đổi một chút RAM dự phòng (tối đa ~2× lúc copy, trung bình lãng phí ~50% capacity) lấy push amortize O(1) — một món hời gần như luôn đáng.

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

Điều đầu tiên: tin tưởng push_back/append của vector — nó là O(1) amortize. Đừng tránh vector vì sợ "copy khi mọc"; chiến lược nhân đôi làm nó nhanh, và bố cục liền mạch của mảng còn cho bạn cache locality miễn phí khi duyệt. Nhưng đừng bao giờ tự cài mảng động mà cấp lại từng chút — đó là O(N²) ẩn. Nếu bạn thấy code realloc(p, n+1) trong một vòng lặp thêm phần tử, đó là quả bom bậc hai.

Điều thứ hai: nếu biết trước kích thước, reserve / cấp đủ ngay. Đo cho thấy reserve (0,33 ns/push) nhanh hơn cả nhân đôi (2,57 ns) — vì tránh được mọi lần copy và cấp lại. Khi bạn biết (hoặc đoán được) mình sẽ thêm bao nhiêu phần tử, vec.reserve(n) một lần loại bỏ toàn bộ chi phí mọc và cả phân mảnh. Đây là tối ưu rẻ nhất, dễ nhất cho vòng lặp xây dữ liệu lớn.

Chỗ này thú vị là mọi ngôn ngữ đều dùng đúng thủ thuật nhân đôi, chỉ khác growth factor, và biết con số đó đáng. Java ArrayList tăng ~1,5× (oldCap + oldCap>>1), Go append tăng gấp đôi cho slice nhỏ rồi giảm dần hệ số khi lớn, Python list tăng ~1,125× (over-allocate khiêm tốn), C++ std::vector thường ×2 (libstdc++) hoặc ×1,5 (MSVC). Vì sao khác nhau? Đây là đánh đổi RAM-vs-tốc-độ: factor lớn (×2) ít lần copy hơn nhưng lãng phí RAM nhiều hơn; factor nhỏ (×1,5) tiết kiệm RAM và còn dễ tái dùng các khối bộ nhớ đã giải phóng, đổi lại copy thường xuyên hơn. Tất cả đều là cấp số nhân nên vẫn O(1) amortize — chỉ hằng số khác nhau. Và tất cả đều cho bạn cách nạp sẵn (ArrayList(capacity), make([]T, 0, n), list từ generator biết độ dài) để né mọc lại, đúng bài học reserve.

Muốn tự thấy thì tự cài một mảng động đơn giản bằng malloc/realloc, thêm vài triệu phần tử, và bấm giờ hai phiên bản: một cái nhân đôi capacity khi đầy, một cái chỉ tăng +1 mỗi lần đầy. Phiên bản +1 sẽ chậm đến mức bạn phải giảm N xuống hàng chục nghìn mới chạy xong trong vài giây — trong khi phiên bản nhân đôi xử lý hàng triệu trong tích tắc. Rồi thêm một phiên bản reserve trước và đo: nó nhanh nhất. Vài phút đó cho bạn thấy phép màu amortize mà std::vector làm giùm bạn mỗi ngày: chuỗi hình học biến những lần copy lớn thành chi phí push trung bình O(1) — và vì sao cấp lại "từng chút một" là một trong những sai lầm hiệu năng âm thầm mà tai hại nhất.