Bài slice header cho thấy append có thể phá vỡ chia sẻ mảng nền khi hết cap. Câu hỏi tự nhiên: khi hết cap, Go cấp mảng mới lớn bao nhiêu? Câu trả lời không phải một hệ số cố định như nhiều người tưởng — nó là một chiến lược thông minh chuyển dần giữa hai chế độ để cân bằng giữa số lần copy và bộ nhớ phí. Bài này đo trực tiếp tiến trình cap khi slice tăng trưởng và giải thích vì sao chiến lược đó tồn tại.
Vì sao append cần cấp mảng mới
Slice có ba trường {ptr, len, cap}. Khi bạn append mà len == cap (mảng nền đầy), runtime không thể ghi thêm — nó phải cấp một mảng nền mới lớn hơn, copy toàn bộ phần tử cũ sang, rồi trỏ slice vào mảng mới. Mỗi lần như vậy là một cấp phát + một lần copy toàn bộ.
Câu hỏi hiệu năng: cấp mảng mới lớn bao nhiêu? Nếu chỉ tăng 1 phần tử mỗi lần, append n phần tử sẽ tốn O(n²) copy — thảm hoạ. Nếu nhân theo hệ số (như x2), số lần cấp giảm về O(log n) và tổng copy về O(n) — tức khấu hao O(1) mỗi append. Nhưng hệ số bao nhiêu?
Hình 1: append vượt cap → cấp mảng mới + copy. Chiến lược: nhân đôi cho cap nhỏ, giảm dần về ~1.25x cho cap lớn.
Đo thật: tiến trình cap
Append từng phần tử, in ra mỗi khi cap đổi (mỗi lần đổi = một lần cấp mảng mới + copy):
Hình 2: Cap nhỏ nhân đôi (x2.00 tới cap 512), rồi giảm dần về ~1.25x cho cap lớn (1.66 → 1.51 → 1.40 → 1.33). Cap thực được làm tròn lên size class nên tỉ lệ dao động.
Kết quả cho thấy hai vùng rõ rệt:
- Cap nhỏ (tới ~512): nhân đôi. 1 → 2 → 4 → 8 → ... → 256 → 512, tỉ lệ luôn x2.00. Với slice còn bé, nhân đôi giúp tăng nhanh mà tổng copy vẫn nhỏ.
- Cap lớn (từ ~512): giảm dần về ~1.25x. 512 → 848 (x1.66) → 1280 (x1.51) → 1792 (x1.40) → 3408 (x1.33). Hệ số giảm dần, hướng tới ~1.25x. (Trước Go 1.18, ngưỡng và cách chuyển hơi khác; Go 1.18+ dùng công thức chuyển mượt.)
Chú ý cap thực (848, 1280, 1792...) không phải bội của 2x hay 1.25x chính xác — vì cap còn được làm tròn lên size class của allocator (bài size class). Đó là lý do tỉ lệ dao động (1.50 xen giữa) — kết hợp của công thức tăng trưởng và làm tròn size class.
Vì sao chuyển hệ số
Câu hỏi: sao không nhân đôi mãi? Vì lãng phí bộ nhớ ở quy mô lớn. Một slice 1GB nếu nhân đôi sẽ nhảy lên 2GB — phí nửa GB cho một lần append. Với slice lớn, Go giảm hệ số về ~1.25x: một slice 1GB chỉ nhảy lên ~1.25GB, đỡ phí nhiều. Cả hai vùng đều giữ khấu hao O(1) mỗi append (vì vẫn nhân theo hệ số > 1), nhưng hệ số nhỏ hơn ở vùng lớn cân bằng giữa số lần copy và bộ nhớ thừa. Đây là đánh đổi kinh điển của mảng động (như vector C++, ArrayList Java) — Go chọn chuyển mượt thay vì một hệ số cứng.
Ứng dụng thực tế
Prealloc vẫn là tối ưu lớn nhất khi biết cỡ. Dù chiến lược tăng trưởng thông minh, append từ nil tới n phần tử vẫn tốn O(log n) lần cấp + copy (mỗi dòng trong bảng là một lần). make([]T, 0, n) khi biết trước n cấp một lần đúng cỡ — không copy lần nào (bài giảm allocation đã đo nhanh 2.5 lần). Luôn prealloc khi biết hoặc ước lượng được cỡ cuối.
Hiểu vì sao cap không phải lúc nào cũng đúng 2x. Nếu bạn kiểm cap sau append và thấy con số "lạ" (848, 1280), đừng ngạc nhiên — đó là công thức tăng trưởng + làm tròn size class. Đừng dựa vào cap là bội chính xác của 2.
append một phần tử vào slice lớn thỉnh thoảng đắt. Đa số append rẻ (chỉ ghi vào cap thừa), nhưng thỉnh thoảng một append trigger cấp mảng mới + copy toàn bộ — với slice lớn, đó là copy hàng MB. Nếu độ trễ đuôi quan trọng và slice rất lớn, prealloc tránh các spike copy này.
Đánh đổi cần cân nhắc
Khấu hao O(1) không có nghĩa mọi append đều nhanh. Trung bình O(1), nhưng một số append đắt (cái trigger copy). Với hầu hết code không sao, nhưng workload nhạy độ trễ đuôi cần biết: append thứ N (khi vượt cap) có thể chậm hơn append thứ N-1 hàng nghìn lần. Prealloc làm phẳng điều này.
Chiến lược tăng trưởng là chi tiết cài đặt, có thể đổi. Con số cụ thể (ngưỡng 256, hệ số 1.25) là chi tiết của runtime Go, đã đổi giữa các phiên bản (Go 1.18 thay đổi lớn). Đừng viết code phụ thuộc con số chính xác; chỉ dựa vào tính chất "khấu hao O(1)" và "prealloc tốt hơn".
Slice cấp dư có thể phí bộ nhớ. Sau khi tăng trưởng, cap thường lớn hơn len (dư chỗ). Một slice có len=513 nhưng cap=848 đang giữ 848 ô nhớ. Nếu bạn giữ nhiều slice như vậy lâu dài, phần dư cộng lại đáng kể — slice[:len:len] (three-index) hoặc copy ra slice khít giúp giải phóng phần dư.
Ba ý mang về
- Chiến lược tăng trưởng slice không phải hệ số cố định: đo thật, cap nhỏ nhân đôi (x2.00 tới 512), rồi giảm dần về ~1.25x cho cap lớn (1.66 → 1.51 → 1.40 → 1.33) — cân bằng giữa số lần copy và bộ nhớ thừa.
- Cap thực được làm tròn lên size class: nên con số cap dao động (848, 1280, 1792) không phải bội chính xác của hệ số — kết hợp công thức tăng trưởng và allocator; đừng dựa vào cap là bội của 2.
- Prealloc vẫn thắng khi biết cỡ: dù tăng trưởng khấu hao O(1), append từ nil tốn O(log n) lần cấp + copy và có spike copy với slice lớn —
make([]T, 0, n)cấp một lần đúng cỡ, không copy, và làm phẳng độ trễ đuôi.
Phần sau ta chuyển sang cấu trúc dữ liệu phức tạp nhất của Go: Phần sau mổ xẻ map internals — cấu trúc hmap và bucket, cách Go băm khóa và giải quyết va chạm, và vì sao map không có thứ tự.
