Cùng O(n) mà chậm 442 lần: bí mật cache của mảng vs linked list

Hình dung một người đưa thư. Kịch bản thứ nhất: các nhà nằm liền nhau trên một con phố, số 1, 2, 3... — anh ta đi bộ dọc phố, phát xong nhà này bước sang nhà kế, và vì biết nhà kế ngay bên cạnh, anh còn rảo bước tới sẵn. Kịch bản thứ hai: mỗi nhà chỉ có một mẩu giấy ghi địa chỉ nhà tiếp theo, mà các nhà rải khắp thành phố — phát xong một nhà, anh phải mở giấy, lái xe tới một địa chỉ lạ ở đầu kia thành phố, rồi lại mở giấy tiếp. Cùng số nhà, nhưng một kịch bản là đi dạo, kịch bản kia là chạy vòng vòng cả ngày. Đó chính xác là khác biệt giữa duyệt một mảng và một danh sách liên kết.

Mở đầu sê-ri mới về cấu trúc dữ liệu, tôi bắt bằng câu hỏi kinh điển nhất: mảng hay danh sách liên kết? Sách giáo khoa nói duyệt cả hai đều là O(n) — đọc N phần tử tốn N thao tác, như nhau. Nếu bạn tin điều đó, bạn sẽ chọn cấu trúc dữ liệu theo ký hiệu Big-O trên giấy. Nhưng Big-O đếm số thao tác, không đếm giá mỗi thao tác — và giá đó có thể chênh nhau hàng trăm lần. Tôi đo duyệt 20 triệu phần tử qua cả hai cách trong container gcc:13, và con số buộc phải nhìn lại cả cách nghĩ về độ phức tạp.

Cùng O(n), nhưng khác chỗ trong bộ nhớ

Mảng: N phần tử nằm liền nhau trong bộ nhớ. Khi bạn duyệt tuần tự (for i: s += a[i]), CPU thấy mẫu đều và prefetch phần cứng nạp trước cache line kế tiếp — nên mỗi phần tử tới nơi đã có sẵn trong cache, gần như free. Đây là người đưa thư đi dọc phố.

Danh sách liên kết: mỗi node là một khối riêng (thường malloc từng cái), nối với nhau bằng con trỏ next. Duyệt nghĩa là theo con trỏ từ node này sang node kia — và địa chỉ node kế không đoán được (nó nằm ở bất cứ đâu malloc trả về). Prefetch bó tay: nó không biết next trỏ đi đâu để nạp trước. Mỗi bước p = p->next là một cache miss — CPU phải chờ RAM. Đây là người đưa thư mở mẩu giấy rồi lái đi khắp thành phố.

Cả hai cùng O(n): đọc N phần tử là N thao tác. Nhưng "một thao tác" của mảng (đọc từ cache, ~sub-ns) và "một thao tác" của linked list (đọc từ RAM sau cache miss, ~100 ns) là hai thứ khác hẳn nhau về giá. Tôi đo với các node của linked list được nối theo thứ tự ngẫu nhiên trong bộ nhớ (mô phỏng một danh sách "cũ" đã qua nhiều lần cấp/giải phóng, node rải rác — trường hợp rất thực tế).

Đo: 442 lần, cùng Big-O

Duyệt (sum) 20 triệu phần tử, CÙNG O(n):
  MẢNG liền mạch      : 0,24 ns/phần tử   (prefetch tuần tự)
  DANH SÁCH LIÊN KẾT  : 103,95 ns/phần tử (node ngẫu nhiên -> cache miss mỗi next)
  -> linked list CHẬM 442× dù cùng số phần tử, cùng Big-O

Duyệt mảng tốn 0,24 nano-giây mỗi phần tử — đúng con số "đọc RAM tuần tự" mà phần 41 của sê-ri hệ điều hành đo được, vì prefetch chạy trước bạn. Duyệt danh sách liên kết tốn 103,95 nano-giây mỗi phần tử — đúng con số "cache miss / đọc RAM ngẫu nhiên", vì mỗi next nhảy tới một địa chỉ CPU không đoán nổi. Chênh nhau 442 lần — dù đọc cùng số phần tử, dù cùng độ phức tạp O(n).

Con số này là lời cảnh báo mạnh nhất về Big-O: nó là công cụ tuyệt vời để so hai thuật toán khác bậc (O(n) vs O(n²)), nhưng nó cố ý bỏ qua hằng số — và hằng số đó, do bố cục bộ nhớ, có thể là 442. Hai cấu trúc "cùng O(n)" có thể chênh nhau gần ba bậc độ lớn trong thực tế. Nếu bạn chỉ nhìn Big-O, bạn thấy chúng bằng nhau; đo mới thấy một cái chậm gấp 442 lần.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, node linked list nối thứ tự ngẫu nhiên trong bộ nhớ, mỗi số lấy MIN sau warmup. Con số đổi theo máy; cái cần nhìn là khoảng cách hàng trăm lần giữa hai cấu trúc "cùng O(n)".)

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

Tôi vào đo với niềm tin sách vở: "duyệt mảng và linked list đều O(n), nên tốn như nhau". Con số phá tan: 442 lần. Big-O đúng về hình dạng (cả hai tuyến tính theo N — gấp đôi N thì gấp đôi thời gian) nhưng sai hoàn toàn về độ dốc: đường của linked list dốc hơn 442 lần. Lý do không nằm trong thuật toán mà trong phần cứng: mảng thân thiện với cache và prefetch, linked list thì phá cả hai.

Còn một niềm tin thứ hai hay gặp: "linked list tốt hơn vì chèn/xóa O(1)". Đúng là chèn/xóa giữa một danh sách (khi bạn đã có con trỏ tới chỗ đó) chỉ đổi vài con trỏ, còn mảng phải dịch phần tử. Nhưng nếu tác vụ chính của bạn là duyệt (rất phổ biến), linked list chậm 442 lần đè bẹp mọi lợi thế chèn. Phải chọn cấu trúc theo thao tác chính và đo thật, không chỉ nhìn ký hiệu: Big-O đếm số thao tác chứ không đếm giá mỗi thao tác, và bố cục bộ nhớ tạo ra hằng số ẩn có thể tới hàng trăm lần.

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

Điều đầu tiên: mặc định dùng mảng liền mạch, trừ khi có lý do mạnh để không. std::vector, ArrayList, mảng động — chúng cho cache locality và prefetch miễn phí. Danh sách liên kết chỉ đáng khi bạn thật sự chèn/xóa nhiều ở giữa và hiếm khi duyệt tuần tự, hoặc cần con trỏ ổn định (node không di chuyển khi cấu trúc đổi). Trong hầu hết code thực tế, mảng thắng — kể cả ở những chỗ Big-O bảo linked list "tốt hơn" — vì hằng số cache lấn át.

Điều thứ hai: đọc Big-O như hình dạng, không phải giá tuyệt đối. O(n) nói "gấp đôi dữ liệu thì gấp đôi thời gian", không nói "nhanh". Khi so hai cấu trúc cùng bậc, đừng dừng ở Big-O — hỏi mỗi thao tác chạm bộ nhớ thế nào (tuần tự hay nhảy), và đo. Một O(n log n) thân thiện cache có thể đánh bại một O(n) nhảy con trỏ ở kích thước thực tế.

Chỗ này chính là lý do các nền tảng cao cấp đã âm thầm dịch chuyển khỏi linked list qua nhiều năm. Tài liệu Java gần như luôn khuyên ArrayList thay LinkedList; Rust nói thẳng "hãy dùng Vec trừ khi bạn có lý do đo được để không". Ở tầng cao hơn, đây là nền tảng của cả data-oriented design trong game engine và của columnar storage trong database phân tích — gom dữ liệu liền mạch để prefetch và cache làm việc, thay vì đuổi con trỏ. Và chính hiện tượng này là lý do garbage collector kiểu compacting (Java, Go) cố dồn các đối tượng sống lại liền nhau: không chỉ để chống phân mảnh, mà để duyệt chúng sau đó thân thiện cache. Cùng một bài học người-đưa-thư-đi-dọc-phố, lặp lại ở mọi tầng — nơi nào chạm bộ nhớ nhiều, nơi đó locality là vua.

Muốn tự thấy thì viết hai cấu trúc chứa cùng vài triệu số nguyên: một mảng, và một danh sách liên kết (cấp mỗi node bằng một malloc riêng, hoặc trộn thứ tự node để chúng rải rác). Tính tổng cả hai và bấm giờ. Bạn sẽ thấy mảng nhanh hàng chục tới hàng trăm lần — dù cùng số phần tử, cùng vòng lặp O(n). Rồi thử một biến thể: tạo linked list mà các node tình cờ nằm liền nhau trong bộ nhớ (cấp một mảng node rồi nối tuần tự) — nó sẽ nhanh hơn hẳn linked list rải rác, vì prefetch bắt được. Vài phút đó dạy bạn điều mà ký hiệu O(n) giấu đi: tốc độ thật của một cấu trúc dữ liệu nằm ở cách nó chạm bộ nhớ, không chỉ ở số phép toán — và đó là lý do "cùng Big-O" gần như không bao giờ có nghĩa "cùng nhanh".