Vec<T> là cấu trúc bạn chạm nhiều nhất trong Rust — mảng động, cấp phát trên heap, đẩy thêm phần tử tuỳ ý. Nhưng "đẩy thêm tuỳ ý" đặt ra một câu hỏi hiệu năng: khi mảng đầy, nó phải xin một vùng nhớ lớn hơn và chép toàn bộ sang. Nếu làm vụng — xin thêm đúng một ô mỗi lần — thì chèn n phần tử tốn O(n²) lần chép. Bài này đo cách Vec tránh điều đó bằng chiến lược nhân đôi sức chứa, và đo luôn cái giá khi ta phá vỡ chiến lược ấy. Tất cả trong container rust:1 (rustc 1.99.1).
Ba con số của một Vec: len, capacity, con trỏ
Một Vec gồm ba word trên stack (như bài 3 đo với String, vốn là Vec<u8> có bọc): con trỏ tới vùng heap, độ dài (len) — số phần tử đang chứa, và sức chứa (capacity) — số phần tử vùng heap có thể chứa trước khi phải xin vùng mới. Khi len chạm capacity, lần push tiếp theo buộc cấp phát lại (reallocation): xin vùng lớn hơn, chép dữ liệu sang, trả vùng cũ. Câu hỏi then chốt là: vùng mới lớn hơn bao nhiêu?
Nhân đôi: 0 → 4 → 8 → … → 2048
Theo dõi capacity thay đổi khi push lần lượt từng phần tử:
ban đầu: len=0 cap=0
push thứ 1: cap 0 -> 4
push thứ 5: cap 4 -> 8
push thứ 9: cap 8 -> 16
push thứ 17: cap 16 -> 32
push thứ 33: cap 32 -> 64
push thứ 65: cap 64 -> 128
…
push thứ 513: cap 512 -> 1024
push thứ 1025: cap 1024 -> 2048
Vec nhân đôi sức chứa mỗi lần hết chỗ (lần đầu nhảy thẳng lên 4). Hệ quả định lượng: chèn 1025 phần tử chỉ kích hoạt khoảng 10 lần đổi sức chứa, không phải 1025. Vì mỗi lần nhân đôi, số phần tử phải chép tăng gấp đôi nhưng tần suất chép giảm một nửa, tổng số phần tử chép khi lớn tới n chỉ vào khoảng 2n — tức mỗi push tốn O(1) khấu hao (amortized). Đây là lý do bạn push thoải mái mà không lo: chiến lược nhân đôi biến một thao tác nghe có vẻ O(n) thành O(1) trung bình.
Một chi tiết thật: cấp phát lại không phải lúc nào cũng dời vùng nhớ
Khi đo, có một điều bất ngờ đáng ghi lại trung thực. Trong 10 lần capacity đổi, con trỏ heap chỉ thật sự thay đổi 2 lần; 8 lần còn lại địa chỉ giữ nguyên:
push thứ 1: cap 0 -> 4 (dời vùng nhớ: true)
push thứ 5: cap 4 -> 8 (dời vùng nhớ: true)
push thứ 9: cap 8 -> 16 (dời vùng nhớ: false) ← nới tại chỗ
… các lần sau: false
Lý do: lời gọi realloc của hệ cấp phát có thể nới khối hiện tại ngay tại chỗ nếu vùng nhớ liền sau còn trống, khỏi chép đi đâu. Nên "cấp phát lại" trên lý thuyết là n lần, nhưng số lần chép dữ liệu thật còn ít hơn nữa, tuỳ hệ cấp phát và độ phân mảnh. (Đo trong container trên tmpfs nên cấp phát khá "sạch", dễ nới tại chỗ; trên hệ phân mảnh nặng thì tỉ lệ dời sẽ cao hơn.) Con số capacity thì chính xác và không phụ thuộc máy; con số dời vùng nhớ là chi tiết của allocator.
Hình 1: Vec nhân đôi sức chứa mỗi lần đầy (0→4→8→…→2048) để push đạt O(1) khấu hao; và ba chiến lược cấp phát với chi phí đo được.
Phá vỡ chiến lược: grow-by-1 chậm gấp 4 lần
Để thấy chiến lược nhân đôi đáng giá, ta cố tình phá nó: ép Vec tăng sức chứa đúng một ô mỗi lần bằng reserve_exact(1) trước mỗi push. Giờ mỗi phần tử là một lần cấp phát, và tổng chép trở lại O(n²):
Chèn 200.000 phần tử:
(A) nhân đôi mặc định Vec::new() : 0,35 ms (~10 lần cấp phát)
(B) grow-by-1 (reserve_exact(1)) : 1,41 ms (200.000 lần cấp phát)
(C) with_capacity(n) 1 lần cấp phát : 0,34 ms
Cách grow-by-1 chậm gấp 4 lần cách mặc định, dù cho ra Vec y hệt — toàn bộ chênh lệch nằm ở chiến lược lớn. (Chênh "chỉ" 4 lần chứ không phải hàng trăm lần là nhờ chính hiện tượng nới-tại-chỗ ở trên làm nhẹ bớt phần chép; trên tập dữ liệu lớn hơn hoặc phần tử nặng hơn, khoảng cách giãn ra nhanh.) Bài học: đừng bao giờ tự tay ép Vec tăng từng ô — hãy để nó dùng chiến lược nhân đôi sẵn có.
with_capacity: khi biết trước cỡ
Chiến lược nhân đôi tốt khi bạn không biết sẽ có bao nhiêu phần tử. Nhưng rất thường bạn biết — đọc 1 triệu dòng, chuyển 1 mảng sang Vec, gom kết quả của một vòng lặp đã biết số lần. Khi đó Vec::with_capacity(n) cấp phát đúng một lần, khỏi mọi lần nhân đôi trung gian:
(A) nhân đôi mặc định : 0,35 ms
(C) with_capacity(n) : 0,34 ms
Trên tmpfs sạch, with_capacity chỉ nhanh hơn chút vì phần nhân đôi đã rẻ sẵn; nhưng nó loại bỏ hoàn toàn các lần cấp phát trung gian và các lần chép (dù ít), nên trên hệ thật và dữ liệu lớn, khoảng cách rõ hơn — và quan trọng, nó không bao giờ chậm hơn. Đây là tối ưu gần như miễn phí: chỉ cần đổi Vec::new() thành Vec::with_capacity(n) ở mọi chỗ bạn biết trước số phần tử. Cùng họ với nó là reserve(n) (nới thêm chỗ cho n phần tử nữa) và collect() — vốn tự gọi with_capacity khi iterator biết trước độ dài.
Hình 2: Số đo thật — bảng nhân đôi capacity tới 2048, ghi chú realloc nới tại chỗ, và benchmark ba chiến lược cấp phát.
Gói lại
Vec nhanh và dễ dùng nhờ một quyết định thiết kế bạn đo được: nhân đôi sức chứa biến push thành O(1) khấu hao, nên chèn 1025 phần tử chỉ tốn ~10 lần cấp phát và tổng chép ~2n. Phá chiến lược đó (grow-by-1) trả giá gấp 4 lần; còn khi biết trước cỡ, with_capacity xoá luôn các lần cấp phát trung gian. Một chi tiết trung thực đáng nhớ: "cấp phát lại" trên lý thuyết không đồng nghĩa "chép dữ liệu" trên thực tế, vì realloc hay nới khối tại chỗ — con số capacity thì chắc chắn, con số dời vùng thì tuỳ allocator. Bài sau rời cấu trúc dữ liệu để quay lại trừu tượng: trait, và sự khác nhau đo được giữa điều phối tĩnh (đơn hình) và điều phối động (dyn, qua bảng ảo).
