Ngăn xếp (stack) và hàng đợi (queue) là hai cấu trúc đơn giản nhất, và sách giáo khoa thường cài chúng bằng danh sách liên kết — mỗi phần tử một node, push thêm node, pop bỏ node. Cả hai thao tác đều O(1), gọn gàng. Nhưng bạn cũng có thể cài chúng bằng mảng (vector cho stack, ring buffer cho queue), cũng O(1). "Cùng O(1)" nghe như chọn cách nào cũng vậy. Tôi đo cả hai cách với 20 triệu thao tác trong container gcc:13, và con số cho thấy "cùng O(1)" giấu một khác biệt cả chục lần — vì một chi phí mà Big-O không bao giờ nhắc tới: malloc.
Cùng O(1), nhưng một cách gọi malloc mỗi lần
Cài bằng mảng: stack là một mảng động — push ghi vào ô kế tiếp và tăng chỉ số, pop giảm chỉ số. Queue là một ring buffer (mảng vòng) — hai chỉ số head và tail chạy vòng quanh mảng. Bộ nhớ liền mạch (cache tốt), và — điểm mấu chốt — không cấp phát gì mỗi thao tác. Khi mảng đầy, nó nhân đôi, nhưng đó là chi phí amortize O(1): trả một lần cho rất nhiều thao tác.
Cài bằng linked list: mỗi push là một malloc cấp một node mới, mỗi pop là một free. Mỗi node tốn 8 byte giá trị + 8 byte con trỏ next + overhead cấp phát. Và malloc/free không miễn phí — chúng phải quản lý danh sách vùng nhớ trống, đôi khi khóa, đôi khi đi tìm. Thêm nữa, các node nằm rải rác ở bất cứ đâu bộ nhớ cấp, nên chạm chúng dễ cache miss. "O(1)" của linked list đúng về số thao tác, nhưng mỗi thao tác kéo theo một lần cấp phát mà Big-O phẩy tay bỏ qua.
Đo: mảng nhanh hơn 13 lần
Tôi push 20 triệu phần tử rồi pop hết, đo cả stack lẫn queue theo hai cách:
N = 20 triệu thao tác (g++ -O2, min):
A. STACK:
MẢNG động : 0,0131 s | 0,3 ns/thao tác (không malloc mỗi lần)
LINKED LIST : 0,1606 s | 4,0 ns/thao tác (mỗi push=malloc, mỗi pop=free)
-> mảng nhanh hơn ~13 lần
B. QUEUE:
RING BUFFER : 0,0911 s | 2,3 ns/thao tác (mảng vòng, không malloc)
LINKED LIST : 0,1607 s | 4,0 ns/thao tác
-> ring buffer nhanh hơn ~1,7 lần
C. Chi phí malloc+free THUẦN:
malloc(24)+free : 5,5 ns/cặp (~chi phí ẩn linked list trả MỖI node)
Nhìn stack: mảng động chỉ 0,3 ns mỗi thao tác — gần như chỉ là một phép ghi ô nhớ và tăng chỉ số. Linked list tốn 4,0 ns — chậm hơn 13 lần, dù cùng O(1). Vì sao? Đo C trả lời: một cặp malloc+free thuần đã tốn 5,5 ns — và linked list trả cái giá đó mỗi thao tác. Cộng thêm cache miss khi chạm node rải rác, tổng thành 4,0 ns/thao tác. Mảng tránh sạch chi phí đó: nó chỉ ghi vào một vùng liền mạch đã cấp sẵn.
Queue cũng vậy: ring buffer 2,3 ns so với linked list 4,0 ns. (Ring buffer chậm hơn stack mảng vì mỗi push/pop làm một phép chia lấy dư % cap để chạy vòng — nếu chọn dung lượng là lũy thừa của 2 và dùng phép AND mặt nạ thay chia, nó còn nhanh hơn nữa.) Điểm chung: cấu trúc dựa trên mảng đánh bại linked list nhiều lần, và khoảng cách toàn bộ đến từ việc tránh malloc/free mỗi thao tác.
Một lần tôi đo hớ: "cùng O(1) thì như nhau"
Tôi vào đo với niềm tin Big-O phẳng: "stack/queue bằng linked list hay mảng đều O(1) push/pop, khác gì nhau". Đo phá tan: stack mảng 0,3 ns so với linked list 4,0 ns — nhanh 13 lần. "O(1)" đếm số thao tác, nhưng mỗi thao tác của linked list kéo theo một malloc+free (~5,5 ns) mà mảng không có — và đó là một hằng số khổng lồ mà ký hiệu O(1) cố tình che. Còn niềm tin thứ hai, hay được viện dẫn: "linked list tốt cho stack/queue vì không phải lo resize như mảng". Sai — mảng động nhân đôi khi đầy, và chi phí resize đó amortize O(1), rẻ hơn rất nhiều so với việc malloc một node cho mỗi phần tử. "Tránh resize" nghe như tiết kiệm, nhưng thực ra bạn đổi một vài lần resize hiếm hoi lấy hàng triệu lần malloc.
Bài học đo lường: stack/queue bằng MẢNG (vector/ring buffer) nhanh hơn bằng linked list nhiều lần dù cùng O(1) — vì linked list trả malloc+free (~5,5 ns) MỖI thao tác cộng cache miss, còn mảng chỉ ghi ô liền mạch + tăng chỉ số (stack mảng 0,3 ns vs list 4,0 ns = 13x); resize của mảng động là amortize O(1), rẻ hơn malloc mỗi node. Nếu tôi tin "cùng O(1) thì như nhau" và cài một stack/queue nóng bằng linked list vì nó "sạch" trong sách, tôi tự làm chậm nó cả chục lần — một chi phí ẩn không hiện trong độ phức tạp, chỉ hiện khi đo.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: mặc định dùng cấu trúc dựa trên mảng cho stack/queue. std::vector/std::stack (mặc định trên deque), ArrayDeque của Java, collections.deque của Python — tất cả dựa trên mảng/khối liền mạch, không phải một node-mỗi-phần-tử. Chúng nhanh hơn vì tránh cấp phát mỗi thao tác và thân thiện cache. Chỉ chọn linked list khi bạn thật sự cần thứ nó cho (con trỏ ổn định tới phần tử, ghép/tách danh sách O(1)), không phải cho một stack/queue thông thường.
Hệ quả thứ hai: malloc mỗi phần tử là một chi phí ẩn lớn — gộp cấp phát khi có thể. Đo cho thấy malloc+free ~5,5 ns/cặp; với hàng triệu phần tử, đó là giây. Bất cứ khi nào bạn cấp phát một-đối-tượng-mỗi-lần trong vòng lặp nóng (node, đối tượng nhỏ), hãy nghĩ tới cấp theo khối (arena/pool allocator) hoặc dùng cấu trúc mảng. Đây là cùng nguyên lý "trả phí cố định một lần thay vì mỗi lần" đã xuất hiện suốt sê-ri.
Hệ quả thứ ba là tinh thần đo lường: Big-O đếm thao tác, không đếm cái mỗi thao tác kéo theo — malloc là cái bị giấu. Con số mang theo: stack/queue bằng MẢNG nhanh hơn linked list nhiều lần dù cùng O(1): stack mảng 0,3 ns/thao tác vs linked list 4,0 ns (13x), queue ring buffer 2,3 ns vs list 4,0 ns; vì linked list trả malloc+free (~5,5 ns/cặp) MỖI thao tác + node rải rác cache miss, còn mảng chỉ ghi ô liền mạch. Resize mảng động là amortize O(1) (rẻ hơn malloc mỗi node). Mặc định dùng cấu trúc mảng (vector/deque/ring buffer). Cùng O(1) trên giấy không có nghĩa cùng tốc độ khi chạy.
Thử ba mươi giây
Cài một stack hai cách và push/pop vài triệu lần: một cái dùng std::vector (push_back/pop_back), một cái dùng linked list tự viết (malloc một node mỗi push, free mỗi pop). Bấm giờ — phiên bản vector nhanh hơn hàng chục lần, và toàn bộ khác biệt là chi phí malloc/free mà linked list trả cho mỗi thao tác. Rồi đo riêng: một vòng lặp chỉ malloc(24) rồi free vài triệu lần — bạn sẽ thấy nó ngốn đúng phần thời gian mà linked list bị chậm. Cuối cùng, thử queue bằng ring buffer so với linked list — cùng câu chuyện. Ba mươi giây đó cho bạn thấy điều mà "stack/queue là O(1)" giấu đi: O(1) nói mỗi thao tác là hằng số bước, nhưng không nói hằng số đó lớn bao nhiêu — và một malloc ẩn trong mỗi thao tác biến "hằng số nhỏ" thành "chậm gấp mười". Cấu trúc liền mạch thắng không nhờ Big-O tốt hơn, mà nhờ hằng số nhỏ hơn.
