Vòng O(n) trông cong như O(n log n): thủ phạm là cache

Suốt sê-ri này, Big-O luôn xuất hiện như một cái khung — nhưng nó là lý thuyết, một tuyên bố về hành vi khi n tiến tới vô cùng.

Big-O giống như dự báo "xe càng nặng càng tốn xăng theo tỉ lệ tuyến tính". Đúng — ở đường trường, tải lớn. Nhưng nếu bạn chỉ đo mức xăng trong bãi đỗ (quãng quá ngắn, máy còn nguội), hay đo đúng lúc leo một con dốc (cache miss), con số sẽ chẳng ra tỉ lệ nào cả, và bạn có thể vội kết luận "công thức sai rồi". Câu hỏi thực dụng ở đây: làm sao kiểm chứng độ phức tạp bằng đo, và tại sao đường cong thời gian thật thường không giống lý thuyết? Nhiều người tin "cứ chạy thử vài kích thước, nhìn thời gian là biết O mấy" — hoặc ngược lại, "thực tế khác lý thuyết nhiều nên Big-O vô dụng". Tôi đo cả hai trong container gcc:13: một phép tính tổng O(n), một std::sort O(n log n), và một phép truy cập ngẫu nhiên để lộ cache. Con số cho thấy đo ẩu thì lừa mắt, nhưng đo đúng cách thì Big-O khớp lý thuyết đẹp đến bất ngờ.

Tỉ số T(2n)/T(n), và cái bẫy cache

Cách kiểm chứng độ phức tạp bằng thực nghiệm là nhân đôi n và xem thời gian đổi thế nào — tỉ số T(2n)/T(n) tiết lộ bậc:

• O(n): nhân đôi n → thời gian gấp đôi → tỉ số → 2.
• O(n log n): tỉ số hơi hơn 2 (~2,05–2,15), vì thừa số log tăng nhẹ khi n gấp đôi.
• O(n²): tỉ số → 4. O(log n): tỉ số → ~1.

Nghe đơn giản, nhưng đường cong thật có hai cái bẫy khiến đo ẩu ra kết quả sai:

• n nhỏ: chi phí khởi động (cấp phát, làm nóng cache, độ phân giải thô của đồng hồ) lấn át thời gian thực của thuật toán — đúng cảnh đo xăng trong bãi đỗ. Ở n nhỏ, tỉ số nhảy lung tung, chưa "ra dáng" tiệm cận.
• Cache gãy khúc: khi vùng làm việc vượt L1 → L2 → L3 → RAM, chi phí mỗi phần tử NHẢY lên (truy cập RAM chậm ~100 lần L1) — con dốc bất ngờ trên đường. Một vòng lặp đúng là O(n) có thể trông dốc hơn tuyến tính khi n vượt cache — không phải sai bậc, mà hằng số thay đổi theo tầng bộ nhớ.

Đo: tỉ số hội tụ đúng — nếu đo đúng chỗ

Tôi đo ba thứ, mỗi thứ với n nhân đôi, lấy min của nhiều lần chạy:

g++ -O2:

A. O(n) tính tổng — tỉ số T(2n)/T(n):
   n nhỏ (1k–32k)  : 1,00 / 4,00 / 1,75   (nhiễu — overhead + timer thô lấn át)
   n lớn (>64k)    : 2,00 / 2,07 / 2,00 / 2,01 / 2,02 / 1,99   -> HỘI TỤ về 2

B. CACHE gãy khúc — ns mỗi truy cập ngẫu nhiên (đuổi con trỏ):
   32 KB (L1)  :  0,91 ns
   256 KB (L2) :  3,52 ns
   2 MB (L3)   :  6,42 ns
   16 MB (L3)  : 10,85 ns
   128 MB (RAM): 95,75 ns    -> nhảy ~100 lần từ L1 tới RAM

C. O(n log n) std::sort:
   ns / (n·log2 n) : ~2,0 (gần như HẰNG SỐ mọi n)   -> đúng O(n log n)
   T(2n)/T(n)      : ~2,07                            -> hơn 2 chút vì thừa số log

Nhìn A — kiểm chứng O(n): ở n nhỏ (1k–32k), tỉ số T(2n)/T(n) lung tung (1,00, rồi 4,00, rồi 1,75) — hoàn toàn không giống "2". Đó là vì thời gian quá nhỏ, độ phân giải đồng hồ và overhead khởi động lấn át. Nhưng từ n > 64k trở đi, tỉ số hội tụ về 2,00 (2,00, 2,07, 2,00, 2,01, 2,02, 1,99) — đúng như O(n) hứa. Bài học: phải đo ở n đủ lớn mới thấy tiệm cận.

Nhìn B — cái bẫy cache: đây là chỗ đường cong "lừa mắt". Cùng một thao tác "truy cập một phần tử", nhưng ns mỗi lần nhảy theo tầng cache: 0,91 ns khi dữ liệu ở L1, 3,52 ns ở L2, 6,42–10,85 ns ở L3, và 95,75 ns khi ra RAM — chậm hơn ~100 lần. Nghĩa là một vòng lặp "O(n)" đọc dữ liệu ngẫu nhiên sẽ có ns mỗi phần tử không hằng số: nó nhảy vọt khi n vượt cache. Nếu bạn đo thời gian tổng và vẽ đường cong qua các mốc cache, nó trông cong lên như siêu tuyến tính — dù bậc vẫn là O(n). Hằng số đổi, không phải bậc.

Nhìn C — kiểm chứng O(n log n): std::sort cho ns/(n·log₂n) gần như hằng số ~2,0 ở mọi n — dấu hiệu chắc chắn của O(n log n). Và tỉ số T(2n)/T(n) là ~2,07, đúng hơn 2 một chút như lý thuyết dự đoán (thừa số log). Đo đúng cách, số khớp lý thuyết đẹp không ngờ.

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

Tôi vào đo với sự tự tin: "cứ chạy vài kích thước, nhìn thời gian là biết O mấy". Con số bác ngay: ở n nhỏ, tỉ số T(2n)/T(n) nhảy lung tung (1,00, 4,00, 1,75) vì hằng số và overhead lấn át — nếu tôi kết luận từ đó, tôi sẽ đoán sai bậc. Tệ hơn, cache gãy khúc làm ns mỗi phần tử nhảy ~100 lần khi vượt L1/L2/L3 — một O(n) thẳng thớm trông cong lên như O(n log n) hay tệ hơn nếu tôi đo ngang qua các mốc cache. "Nhìn thời gian là biết độ phức tạp" là sai nếu đo ẩu: n phải đủ lớn, phải cùng tầng cache, phải lấy min nhiều lần.

Nhưng nếu vì đã vấp cache mà quay sang tin "thực tế lộn xộn thế này thì Big-O lý thuyết vô dụng, chỉ đo là đủ" thì cũng sai. Khi tôi đo đúng cách — tỉ số T(2n)/T(n) ở n đủ lớn, cùng tầng cache, min của nhiều lần — kết quả hội tụ chính xác về lý thuyết: O(n) → 2,00, O(n log n) → 2,07 với ns/(n log n) hằng số. Big-O đúng ở tiệm cận; nó chỉ không mô tả vùng n nhỏ và không nói về hằng số (cache). Vứt bỏ Big-O vì đường cong thô lộn xộn là vứt đi công cụ dự đoán bậc — thứ quyết định khi n lớn.

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

Việc đầu tiên: muốn kiểm chứng độ phức tạp, dùng tỉ số T(2n)/T(n) ở n đủ lớn — đừng đoán từ vài điểm nhỏ. Nhân đôi n vài lần, lấy min của nhiều lần chạy, và xem tỉ số hội tụ về đâu (2 → O(n), ~2 hơn chút → O(n log n), 4 → O(n²)). Bỏ qua các điểm n nhỏ (nhiễu) và để ý xem có gãy khúc cache không. Đây là cách xác nhận một thuật toán thực sự có bậc bạn nghĩ, hay có một O(n²) ẩn.

Việc thứ hai: khi đường cong thật "cong lên" bất thường, nghi cache trước khi nghi sai bậc. Một thao tác O(n) chậm dần khi dữ liệu lớn thường là do vượt cache (ns/phần tử nhảy tầng), không phải vì nó bí mật là O(n log n). Kiểm bằng cách đo trong cùng một tầng cache, hoặc nhìn kích thước dữ liệu so với L2/L3. Nhầm gãy khúc cache thành "sai độ phức tạp" dẫn tới tối ưu sai chỗ.

Cách tư duy "Big-O cho bậc, đo cho hằng số" này cứu bạn khỏi hai loại lỗi kinh điển ở tầng cao. Loại một: tin Big-O mù quáng và bỏ qua hằng số — một thuật toán O(n log n) "tốt hơn" có thể thua một O(n²) đơn giản ở mọi n thực tế vì hằng số lớn, đây là lý do std::sort chuyển sang insertion sort cho mảng con nhỏ, và Java Arrays.sort cũng vậy. Loại hai: đo một lần ở quy mô nhỏ rồi ngoại suy — một truy vấn database chạy nhanh trên 1.000 hàng test có thể là một JOIN O(n²) ẩn phát nổ ở 1 triệu hàng production; chính vì thế EXPLAIN cho bạn bậc của kế hoạch (index scan vs nested loop) chứ không chỉ thời gian một lần chạy. Cùng cặp công cụ ở mọi tầng: dùng phân tích tiệm cận để biết chuyện gì xảy ra khi dữ liệu lớn lên, dùng đo để biết hằng số ở quy mô hiện tại — và đừng bao giờ ngoại suy từ một điểm đo nhỏ.

Muốn tự thấy thì viết một phép tính tổng mảng và bấm giờ với n gấp đôi liên tục (1000, 2000, 4000, …, vài chục triệu), in tỉ số thời gian của mỗi bước so với bước trước. Bạn sẽ thấy ở n nhỏ tỉ số lung tung (đồng hồ quá thô, overhead lấn át), rồi từ một ngưỡng nào đó nó ổn định về ~2 — đó là O(n) hiện ra khi n đủ lớn. Rồi làm một thí nghiệm cache: tạo một hoán vị ngẫu nhiên và "đuổi con trỏ" (mỗi bước nhảy tới chỉ số ngẫu nhiên tiếp theo) với các vùng làm việc 32 KB, 256 KB, 2 MB, 128 MB, đo ns mỗi bước — bạn sẽ thấy nó nhảy vọt theo tầng cache, từ dưới 1 ns lên gần 100 ns. Cuối cùng, std::sort với n gấp đôi và in ns/(n·log₂n): nó gần như hằng số, xác nhận O(n log n). Ba mươi giây đó cho thấy điều mà cả "đo là biết ngay" lẫn "Big-O vô dụng" đều giấu đi: đo đúng cách thì lý thuyết và thực tế gặp nhau — Big-O nói bậc, đo nói hằng số, và cache là lý do đường cong thô không bao giờ mượt như sách vẽ.