Cùng O(1) mà chậm 13 lần: cái giá malloc ẩn trong stack/queue

Nghĩ về chồng khay ở căng tin. Có hai cách vận hành. Cách thứ nhất: một chồng khay lò xo có sẵn — lấy khay là nhấc từ trên xuống, trả khay là đặt lên trên, tức thì. Cách thứ hai: mỗi lần cần một khay, bạn gọi nhà cung cấp giao tới một chiếc mới, và mỗi lần trả thì có người tới khiêng đi. Cả hai đều cho bạn "một khay mỗi lần", nhưng cách hai kèm theo một cuộc điện thoại và một chuyến giao hàng cho mỗi chiếc khay. Trong lập trình, chồng khay có sẵn là stack/queue cài bằng mảng, còn gọi-giao-từng-cái là cài bằng danh sách liên kết — và cuộc gọi ẩn kia tên là malloc.

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. Đây là chồng khay lò xo có sẵn.

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 cuộc gọi giao hàng 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ôi trường đo: container gcc:13 trên host ARM AArch64, glibc malloc, g++ -O2, 20 triệu thao tác, mỗi số lấy MIN sau warmup. Con số đổi theo máy và allocator; cái cần nhìn là toàn bộ khoảng cách bằng đúng chi phí malloc+free mỗi thao tác.)

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

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". Con số 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.

Nhưng có một niềm tin thứ hai, hay được viện dẫn, cũng sai: "linked list tốt cho stack/queue vì không phải lo resize như mảng". Không — 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 cuộc gọi giao hàng.

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

Điều đầ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, 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. Điều này không riêng C++: chính vì lý do đó mà tài liệu Java khuyên ArrayDeque thay LinkedList cho stack/queue, và list của Python (mảng động) làm stack tốt hơn hẳn một linked list tự viết.

Điều 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à cả giây cộng dồn. 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 cũng là lý do các ngôn ngữ có GC như Java/Go tối ưu mạnh việc cấp đối tượng nhỏ (TLAB, bump allocation), nhưng ngay cả vậy, một cấu trúc mảng liền mạch vẫn thắng nhờ tránh cả cấp phát lẫn áp lực lên bộ thu gom rác.

Muốn tự thấy thì 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. Vài phút đó 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.