Bốn mươi bốn bài, mỗi bài một phép đo, và gần như bài nào cũng có một khoảnh khắc "đo hớ" — nơi con số bác lại điều tôi tưởng. Bài kết này khép vòng bằng chính bài toán đơn giản nhất của cả sê-ri — "phần tử x có trong tập không?" — đo bốn cách trả lời ở nhiều quy mô, và cho thấy vì sao câu trả lời cho câu hỏi "nên dùng cấu trúc nào" luôn là đo trước đã. Đây là toàn bộ sê-ri gói trong một bảng.
Một bài toán, bốn lời đáp
Tra thành viên một tập số nguyên là bài toán nền tảng, và có ít nhất bốn cách quen thuộc. Quét tuyến tính: giữ một mảng, duyệt từng phần tử — O(n). Mảng sắp + nhị phân: sắp mảng rồi tìm nhị phân — O(log n). Bảng băm: băm khóa vào xô — O(1) trung bình. Bitset: nếu khóa nằm trong một miền bị chặn, một bit cho mỗi giá trị — O(1) với hằng số cực nhỏ.
Nếu chỉ nhìn ký hiệu big-O, bảng xếp hạng rõ ràng: quét O(n) tệ nhất, nhị phân O(log n) khá, hash và bitset O(1) tốt nhất. Ai học thuật toán cũng sẽ gạt quét tuyến tính đi và chọn một trong nhóm "logarit hoặc hằng số". Tôi đo, và bảng xếp hạng thật khác hẳn.
Đo: kẻ thắng đổi theo quy mô
Tôi đo thời gian mỗi truy vấn (ns) của cả bốn cách, với tập từ 8 tới 50.000 phần tử, khóa trong miền 2²⁰ (để bitset dùng được, cố định 128 KB):
Tra thành viên, ns mỗi truy vấn (lấy min):
n | quét O(n) | nhị phân | hash O(1) | bitset
8 | 2,5 | 8,5 | 6,6 | 1,1
64 | 16,8 | 17,8 | 6,7 | 0,4
512 | 130,8 | 30,5 | 6,8 | 0,4
4.096 | 998,8 | 44,1 | 6,9 | 0,4
50.000 | 11.788,9 | 61,3 | 5,4 | 0,4
Đọc theo hàng, ba điều bất ngờ hiện ra. Ở n = 8, quét tuyến tính nhanh nhất trong nhóm so sánh — 2,5 ns, nhanh hơn cả nhị phân (8,5) lẫn hash (6,6). Tám phần tử nằm gọn trong một dòng cache, CPU quét một mạch và đoán nhánh chuẩn, trong khi hash phải tính hàm băm và nhị phân phải nhảy lung tung — chi phí cố định của chúng lớn hơn cả việc quét tám số. Đây đúng bài học hằng số ẩn và điểm giao mà sê-ri mở màn.
Ở n lớn, hash thắng và giữ ~5-7 ns bất kể n (đúng O(1)), trong khi quét bùng lên 11.789 ns ở n = 50.000 — chậm hơn hash hơn hai nghìn lần. Và nhị phân O(log n) không bao giờ là kẻ nhanh nhất: ở n nhỏ nó thua quét, ở n lớn nó thua hash, luôn kẹt giữa. Cái "lựa chọn thông minh O(log n)" mà big-O gợi ý hóa ra là lựa chọn không bao giờ đúng trong bài toán này — vì mỗi bước nhị phân là một cú nhảy kém thân thiện cache, đắt hơn nhiều so với con số log n gợi ý.
Một lần tôi đo hớ: và bitset đè bẹp tất cả
Còn cột cuối. Bitset thắng mọi hàng — 0,4 ns, gần như miễn phí. Nếu bạn biết miền khóa (ở đây mọi khóa trong [0, 2²⁰)), một phép kiểm tra bit đơn lẻ nhanh hơn hash chục lần và nhanh hơn quét ở n = 50.000 tới hơn hai mươi bảy nghìn lần. Đây là chỗ đo hớ cuối cùng của tôi, và nó tóm gọn cả sê-ri: tôi đã định so bốn cấu trúc "công bằng" theo big-O, nhưng câu hỏi quyết định không nằm trong big-O — nó là "bạn có biết gì thêm về dữ liệu không". Biết miền khóa bị chặn mở khóa một cấu trúc mà big-O của ba cái kia không nói tới.
Cần thành thật về điều kiện, đúng tinh thần sê-ri: bitset thắng vì miền ở đây đủ nhỏ (128 KB). Nếu khóa là số 64-bit rải rác, bitset cần 2 exabyte — bất khả, và không gian trở thành bức tường. Kẻ thắng lại đổi. Đó chính là điểm: không có "cấu trúc tốt nhất" tồn tại tách khỏi dữ liệu; chỉ có cái hợp với n, mật độ, miền, mẫu truy cập, và phần cứng của bạn.
Cả sê-ri gói trong một bảng
Bảng nhỏ này là toàn bộ bốn mươi lăm bài. Mỗi lý do khiến kẻ thắng lệch khỏi dự đoán big-O là một bài đã đi qua: hằng số ẩn làm quét thắng ở n nhỏ (bài 1); cache làm nhị phân và danh sách liên kết chậm hơn con số lý thuyết (bài 2); điểm giao làm thuật toán "xịn hơn" thua ở quy mô nhỏ (introsort bài 15, suffix array bài 37, Karatsuba bài 40); miền và mật độ mở khóa bitset (bài 34) hay quyết định tỉ lệ nén; đua tranh đặt trần khi song song hóa và không khóa; đánh đổi thời gian–không gian (bài 43) làm merge sort nhanh hơn dù tốn RAM gấp đôi; và tất cả những con số ấy chỉ đáng tin sau khi vượt bốn cái bẫy đo lường. Big-O cho bạn hình dạng đường cong khi n tiến tới vô cùng; nó không cho bạn điểm mà dữ liệu của bạn đang đứng, cũng không cho hằng số, cache, hay miền. Những thứ đó phải đo.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, và là thông điệp của cả sê-ri: đừng chọn cấu trúc dữ liệu bằng cách so ký hiệu O trên giấy — đo trên dữ liệu và máy thật của bạn. Big-O là công cụ tuyệt vời để loại những lựa chọn thảm họa (một thuật toán O(n²) trên n triệu là hỏng, không cần đo). Nhưng giữa các ứng viên hợp lý, kẻ thắng phụ thuộc quy mô thật, mật độ thật, mẫu truy cập thật, và phần cứng thật — những thứ chỉ đồng hồ mới nói được. "Nên dùng cây hay hash?" không có câu trả lời chung; "hãy đo với n và dữ liệu của bạn" thì có.
Hệ quả thứ hai: biết về dữ liệu quý hơn biết thêm một cấu trúc. Cái mở khóa bitset không phải một thuật toán tinh vi, mà là một sự thật về dữ liệu — miền khóa bị chặn. Trước khi tối ưu, hỏi: n thường bao lớn, khóa nằm trong miền nào, truy cập tuần tự hay ngẫu nhiên, đọc nhiều hay ghi nhiều, một luồng hay nhiều luồng. Mỗi câu trả lời cắt bỏ vài lựa chọn và mở ra vài lựa chọn khác, và thường quyết định nhiều hơn cả việc bạn thuộc bao nhiêu cấu trúc.
Hệ quả thứ ba là lời chào tạm biệt của sê-ri: "nhanh" là một câu vô nghĩa cho tới khi bạn đo nó, trên dữ liệu của mình, đúng cách. Con số mang theo — con số cuối cùng: cùng một bài toán tra thành viên, quét tuyến tính nhanh nhất ở n=8 (2,5 ns), hash ở n lớn (5-7 ns cố định), bitset đè bẹp cả nếu biết miền khóa (0,4 ns), và nhị phân O(log n) không bao giờ nhanh nhất — big-O đơn thuần xếp hạng sai kẻ thắng. Suốt sê-ri, mỗi lần trực giác nói "cái này chắc nhanh hơn", một phép đo đã đứng ra bác lại: hằng số ẩn, cache, điểm giao, entropy, đua tranh, đánh đổi. Bài học không phải là "đừng tin big-O" — big-O vẫn là la bàn. Bài học là: la bàn chỉ hướng, không chỉ khoảng cách; muốn biết khoảng cách thật, hãy đo. Đo, đừng đoán. Cảm ơn bạn đã đi hết bốn mươi lăm phép đo.
Thử ba mươi giây
Lần tới khi bạn định chọn một cấu trúc dữ liệu vì "nó O(log n), tốt hơn O(n)", dừng lại ba mươi giây và hỏi bốn câu: n của tôi thực tế bao lớn? khóa có nằm trong một miền nhỏ không? tôi tra một lần hay hàng triệu lần? dữ liệu vừa cache hay tràn cache? Rồi, nếu có thể, viết mười dòng đo hai ứng viên trên chính dữ liệu của bạn — nhớ quan sát kết quả (volatile), bỏ warmup, lấy trung vị. Rất có thể con số sẽ làm bạn ngạc nhiên, như nó đã làm tôi ngạc nhiên bốn mươi lăm lần. Và đó chính là toàn bộ điều sê-ri này muốn để lại: cái ngạc nhiên ấy chỉ đến khi bạn đo — nên hãy đo, đừng đoán.
