Bốn mươi lăm phần, một luận điểm duy nhất: đo, đừng đoán. Suốt sê-ri này, mỗi phần lấy một cấu trúc dữ liệu, một niềm tin quen thuộc, và một chiếc container Linux để kiểm chứng — và gần như lần nào phép đo cũng nói khác với trực giác. Ở phần cuối này, tôi muốn khép lại bằng đúng cái đã mở ra: một phép đo. Một phép đo capstone gói trọn toàn bộ bài học — nơi cùng một dữ liệu, cùng một độ phức tạp Big-O, mà thực tế chênh nhau hàng chục lần vì những thứ Big-O không bao giờ nói. Đo trong container gcc:13, và con số là lời tổng kết gọn nhất tôi có thể đưa ra.

Cấu trúc dữ liệu: đo, đừng đoán

Cùng O(n), cùng dữ liệu, chênh 24 lần

Tôi lấy 10 triệu số nguyên và cất chúng ba cách khác nhau — ba cách mà một lập trình viên dễ coi là "tương đương, đều là một tập số". Rồi làm đúng một việc trên cả ba: tính tổng. Cả ba đều là O(n) — duyệt n phần tử, cộng lại. Big-O nói chúng bằng nhau.

Cùng 10 triệu số nguyên, 3 bố cục bộ nhớ, đều "tổng O(n)", g++ -O2:

   A. mảng liền mạch (vector<int>)        : 0,225 ns/phần tử
   B. mảng con trỏ rải rác (vector<int*>) : 5,481 ns/phần tử   (24 lần chậm hơn A)
   C. linked list (std::list<int>)        : 0,977 ns/phần tử   (4 lần chậm hơn A)

Cùng độ phức tạp, cùng dữ liệu, nhưng chênh tới 24 lần. Toàn bộ khác biệt là bố cục bộ nhớ: mảng liền mạch (A) đọc tuần tự, CPU prefetch giấu độ trễ, cache hoạt động hoàn hảo. Mảng con trỏ rải rác (B) — mỗi số nằm ở một chỗ ngẫu nhiên trên heap — buộc một cache miss cho gần như mỗi phần tử; linked list (C) cũng theo con trỏ nhưng các node ở đây khá liền trong bộ nhớ nên đỡ hơn. Big-O gọi cả ba là O(n) và im lặng hoàn toàn về khoảng cách 24 lần này. Đây là cả sê-ri trong một phép đo: thứ quyết định hiệu năng thật thường là thứ Big-O giấu đi.

Những gì Big-O giấu — và những con số của sê-ri

Bốn mươi lăm phần đo đi đo lại đúng bốn thứ mà trực giác Big-O bỏ qua:

Và những con số bất ngờ nhất mà phép đo lôi ra, tất cả đều thật: move so với copy một vector 40 MB nhanh hơn 42.554 lần (O(1) vs O(n)); LRU đúng cách so với naive nhanh 5.862 lần; chèn/xóa ở giữa list so với mảng nhanh 731 lần; interning tiết kiệm 24 lần bộ nhớ; arena cấp phát nhanh 10 lần và giải phóng cả lô O(1); phân mảnh giữ RSS cao gấp 12 lần dữ liệu sống; CAS-loop tự viết tệ hơn mutex 6,8 lần khi tranh chấp cao. Không con số nào trong đó đoán ra được — tất cả phải đo.

Một lần tôi đo hớ: "Big-O + trực giác là đủ" và "đo là chỉ bấm giờ"

Luận điểm của cả sê-ri, và cũng là cái "đo hớ" lớn nhất, là: tôi từng tin Big-O cộng trực giác là đủ để chọn cấu trúc dữ liệu. Đo phá tan điều đó bốn mươi lăm lần. Cùng 10 triệu số "tổng O(n)", mảng liền chạy 0,225 ns còn con trỏ rải rác 5,48 ns — chênh 24 lần mà Big-O không hé một lời. Trực giác lập trình sai theo cách có hệ thống: ta đánh giá thấp cache, đánh giá thấp hằng số, quên mất mẫu truy cập, và tin rằng bậc Big-O tốt hơn nghĩa là nhanh hơn. Cây thước duy nhất đáng tin không phải là suy luận — mà là phép đo trên chính workload của mình.

Nhưng sê-ri cũng dạy một điều thứ hai: đo không phải chỉ là bấm giờ. Chính việc đo cũng là một kỹ thuật có quy tắc, và làm sai thì con số còn lừa hơn cả trực giác. Bốn quy tắc tôi tuân suốt sê-ri: bỏ lần chạy đầu (warmup — cache lạnh làm nó chậm ~1,5 lần); lấy min chứ không lấy trung bình (nhiễu hệ điều hành chỉ làm chậm, min mới là tín hiệu CPU thật); ghi kết quả vào một volatile SINK (thiếu nó, -O2 xóa sạch vòng lặp và đo ra 0 — số bịa); và lặp N lần chia N khi thao tác nhỏ hơn độ phân giải đồng hồ (đo một lần cho 84 ns rác). Thiếu một trong bốn, con số có thể sai hàng trăm lần hoặc bằng 0 mà vẫn trông hợp lý.

Bài học đo lường — cho cả sê-ri: Big-O cho bạn cái KHUNG (bậc độ phức tạp), nhưng cache, hằng số ẩn, và mẫu truy cập mới quyết định hiệu năng thật — và chúng lật kèo hàng chục tới hàng nghìn lần (cùng O(n): mảng liền 0,225 vs con trỏ rải rác 5,48 ns = 24x). Trực giác lập trình sai theo cách hệ thống; chỉ phép đo là đáng tin. Và đo cho ĐÚNG cũng là kỹ thuật: warmup + min + volatile SINK + lặp-chia-N, thiếu một cái số sai trăm lần hoặc bằng 0. Đừng hỏi "cái nào nhanh hơn"; hỏi "ở workload của tôi, số nói gì" — rồi đo cho đúng.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên: khi hiệu năng quan trọng, đừng chọn cấu trúc bằng phản xạ — đo trên dữ liệu và workload thật của bạn. Big-O là điểm khởi đầu để loại các lựa chọn thảm họa (đừng chèn giữa vào mảng lớn, đừng tra khóa trong linked list), nhưng giữa các ứng viên hợp lý, hằng số và cache thường quyết định — và chúng khác nhau theo kích thước, kiểu khóa, mẫu truy cập của bạn. Một phép đo mười phút đáng giá hơn một giờ tranh luận về Big-O.

Hệ quả thứ hai: học đo cho đúng, hoặc dùng công cụ đã làm đúng. Google Benchmark, perf, Criterion tự lo warmup, lấy percentile/min, và có DoNotOptimize() chống DCE. Nếu tự viết, nhớ bốn quy tắc. Một benchmark sai còn tệ hơn không có — nó cho bạn sự tự tin sai lầm.

Hệ quả thứ ba, và là tinh thần khép lại sê-ri: trực giác về hiệu năng là giả thuyết, không phải kết luận — hãy để số liệu phán quyết. Con số mang theo từ 45 phần: cùng Big-O, thực tế chênh hàng chục–hàng nghìn lần vì cache, hằng số, mẫu truy cập (đo capstone: cùng "tổng O(n)" chênh 24x theo bố cục). Đừng đoán — đo, với warmup + min + SINK + lặp-chia-N. Cảm ơn bạn đã theo hết sê-ri. Nếu chỉ mang theo một câu: đừng đoán, hãy đo — và đo cho đúng.

Thử ba mươi giây

Làm lại phép đo capstone để tự thấy cả sê-ri trong một thí nghiệm. Tạo 10 triệu số nguyên ba cách: một vector<int> liền mạch; một vector<int*> với mỗi số malloc riêng rồi xáo trộn thứ tự con trỏ; và một std::list<int>. Rồi tính tổng cả ba, mỗi cái bấm giờ nhiều lần lấy min, nhớ ghi tổng vào một volatile để trình biên dịch không xóa vòng lặp. Bạn sẽ thấy vector chạy dưới một phần tư nano-giây mỗi phần tử, còn mảng con trỏ rải rác chậm hơn cả chục lần — dù cả ba đều là "tổng n số", đều O(n). Cái khoảng cách đó, mà Big-O gọi là "bằng nhau", chính là tất cả những gì sê-ri này nói suốt bốn mươi lăm phần: hiệu năng thật sống trong những chi tiết mà lý thuyết trừu tượng hóa đi — cache, con trỏ, hằng số, mẫu truy cập — và cách duy nhất để thấy chúng là đặt một chiếc đồng hồ lên đúng đoạn mã của bạn, đo cho cẩn thận, và tin vào con số thay vì cảm giác.