Tìm nhị phân là một trong những điều đầu tiên ta học về tối ưu: O(log n) đánh bại O(n), nên tìm trên mảng đã sắp thì luôn dùng nhị phân. Bài mở sê-ri đã cảnh báo rằng big-O là hình dạng khi n lớn, không phải tốc độ ở n cụ thể — và bài này áp đúng cảnh báo đó vào một cặp thuật toán ai cũng thuộc lòng. Ở mảng nhỏ, tìm tuyến tính nhanh hơn tìm nhị phân, và lý do lần này không chỉ là hằng số hay cache, mà là một thứ hoàn toàn mới: dự đoán nhánh của CPU.
Ít bước không đồng nghĩa nhanh
Tìm tuyến tính quét mảng từ đầu, so từng phần tử — O(n) so sánh. Tìm nhị phân trên mảng đã sắp mỗi bước loại nửa còn lại — chỉ O(log n) so sánh. Với n = 256, tuyến tính có thể so tới 256 lần, nhị phân chỉ 8. Nghe như nhị phân phải thắng dễ dàng. Nhưng "số so sánh" không phải "thời gian": mỗi so sánh của hai thuật toán có giá rất khác nhau, và đó là chỗ big-O im lặng. Đây là một biến thể của bài học ở bài trước về cache — nơi cùng số phép truy cập nhưng khác locality cho tốc độ chênh hàng trăm lần. Lần này thủ phạm không phải cache mà là đường ống lệnh của CPU.
Tôi đo cả hai bằng C, tìm hàng triệu khóa ngẫu nhiên (có thật trong mảng) để lấy thời gian trung bình mỗi lần tìm, ở nhiều kích thước n. Dùng khóa ngẫu nhiên là cố ý: nếu tìm cùng một khóa mãi, CPU sẽ học thuộc đường đi và cả hai đều nhanh giả tạo — muốn đo đúng chi phí đoán nhánh, mỗi lần tìm phải là một câu hỏi mới. Kết quả:
n tuyến tính nhị phân nhanh hơn
64 14,5 ns 20,2 ns tuyến tính
128 23,7 ns 24,2 ns ~ giao nhau
256 40,7 ns 28,1 ns nhị phân
1024 138 ns 36,4 ns nhị phân
65536 8315 ns 72,5 ns nhị phân
262144 33268 ns 97,4 ns nhị phân
Một lần tôi đo hớ: nhánh 50/50 giết tìm nhị phân ở n nhỏ
Ở n = 64, tìm tuyến tính (14,5 ns) nhanh hơn tìm nhị phân (20,2 ns) — dù nó so tới 64 lần còn nhị phân chỉ 6. Tôi vào bài với niềm tin "O(log n) luôn thắng O(n)", nên con số này làm tôi khựng. Vì sao ít bước hơn lại chậm hơn?
Câu trả lời là dự đoán nhánh (branch prediction). CPU hiện đại không chờ biết kết quả một phép so sánh rồi mới chạy tiếp; nó đoán nhánh sẽ đi hướng nào và chạy trước theo hướng đoán. Đoán đúng thì không mất gì; đoán sai thì phải xả cả đường ống lệnh (pipeline flush) và làm lại — mất cả chục chu kỳ. Với tìm tuyến tính, nhánh trong vòng lặp là "chưa gặp, đi tiếp" — gần như luôn đúng cho tới đúng lúc gặp, nên CPU đoán trúng suốt và quét rất nhanh, lại thêm mảng nhỏ nằm gọn trong cache và được prefetch. Với tìm nhị phân, mỗi bước là câu hỏi a[mid] < key? — kết quả gần như ngẫu nhiên 50/50, nên CPU đoán sai khoảng một nửa số lần, mỗi lần sai một cú xả pipeline. Nhị phân ít bước, nhưng mỗi bước đắt vì cú đoán sai đó.
Cái sai của tôi là đếm số so sánh và tưởng đó là thời gian. Ở mảng nhỏ, sáu bước nhị phân với ba cú đoán sai tốn hơn sáu mươi bước tuyến tính mà CPU đoán trúng hết. Có một điểm giao quanh n = 128: dưới nó tuyến tính thắng, trên nó nhị phân thắng — và một khi n đủ lớn, nhị phân thắng áp đảo: ở n = 262144, tuyến tính mất 33 micro giây còn nhị phân chỉ 97 nano giây, nhanh 342 lần. Big-O của nhị phân là đúng — nó mô tả hình dạng khi n lớn — nhưng ở n nhỏ, chi phí mỗi bước (đoán nhánh) lật ngược kết quả.
Còn một chi phí ẩn: mảng phải được sắp
Có một điều big-O của "tìm nhị phân O(log n)" giấu hoàn toàn: nó đòi mảng đã sắp. Nếu dữ liệu chưa sắp và bạn chỉ tìm một lần, dùng nhị phân nghĩa là phải sắp trước — O(n log n) — chỉ để tiết kiệm một lần tìm. Một lần quét tuyến tính O(n) rẻ hơn nhiều. Nhị phân chỉ đáng khi bạn tìm nhiều lần trên cùng một mảng, để chi phí sắp một lần chia đều cho nhiều lần tìm. So sánh "O(log n) so với O(n)" bỏ qua cái O(n log n) đứng trước, và đó là một cái bẫy quyết định thường gặp. Trên thực tế nhiều thư viện chuẩn giải quyết cả hai vấn đề cùng lúc: chúng dùng tìm tuyến tính (hoặc một biến thể không nhánh) cho đoạn nhỏ, và chỉ chuyển sang chiến lược chia-đôi khi phần cần tìm đủ lớn — đúng cái điểm giao ta vừa đo, giống hệt cách các thư viện sắp xếp lai đã thấy ở bài mở đầu.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: với mảng nhỏ, tìm tuyến tính vừa đơn giản vừa nhanh. Nếu bạn tra trong vài chục phần tử, một vòng for quét thẳng thường nhanh hơn và ít lỗi hơn tìm nhị phân (vốn nổi tiếng dễ viết sai biên). Đừng thêm phức tạp của nhị phân cho những mảng bé. Có một sắc thái đáng biết: người ta có thể viết tìm nhị phân không nhánh (branchless) để né hẳn cú phạt đoán sai — dùng phép toán số học thay cho câu lệnh rẽ. Nhưng đó là kỹ thuật nâng cao, và ngay cả nó cũng không cứu được nhị phân khỏi việc truy cập bộ nhớ rải rác khi mảng lớn; điểm mấu chốt vẫn là đo, không đoán.
Hệ quả thứ hai: big-O đếm bước, nhưng thời gian là bước nhân giá mỗi bước. Con số mang theo: tìm tuyến tính O(n) và tìm nhị phân O(log n) có điểm giao quanh n=128 — dưới nó tuyến tính nhanh hơn (n=64: 14,5 so 20,2 ns) vì quét tuần tự cache-friendly và nhánh dễ đoán, trong khi mỗi bước nhị phân là nhánh 50/50 hay bị đoán sai (phạt pipeline); trên điểm giao nhị phân thắng áp đảo (n=262144 nhanh 342 lần); và nhị phân còn cần mảng đã sắp, nên tìm một lần thì tuyến tính thắng vì khỏi trả O(n log n). Ít bước hơn trong big-O không tự động nghĩa là nhanh hơn — hỏi mỗi bước đắt bao nhiêu, và n của bạn ở phía nào của điểm giao.
Thử ba mươi giây
Không cần code, chỉ cần một câu hỏi cho lần tới bạn định viết tìm nhị phân: mảng này bao lớn, và tôi tìm bao nhiêu lần? Nếu là vài chục phần tử, hoặc chỉ tìm một lần trên dữ liệu chưa sắp, một vòng quét tuyến tính gần như luôn thắng — đơn giản hơn, khó sai hơn, và trên mảng nhỏ còn nhanh hơn vì CPU đoán nhánh trúng và cache lo phần còn lại. Nhị phân dành cho khi mảng lớn và bạn tìm nhiều lần trên nó. Ba mươi giây tự hỏi hai con số đó — cỡ mảng và số lần tìm — sẽ cứu bạn khỏi tối ưu nhầm hướng nhiều hơn bất kỳ mẹo nào.
