Tìm nhị phân 6 bước thua tìm tuyến tính 64 bước — vì mỗi bước đắt khác nhau

Đi bộ mười bước trên nền phẳng nhanh hơn leo ba bước qua ba bức tường — số bước ít hơn không có nghĩa nhanh hơn, vì mỗi bước tốn công khác nhau. Tìm nhị phân với tìm tuyến tính đúng là câu chuyện đó. 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

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 đó — đúng cái "ba bước qua ba bức tường" ở đầu bài.

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.

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

Điều đầ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 — bug tràn số trong mid = (lo+hi)/2 nằm trong thư viện chuẩn Java suốt 9 năm mới bị phát hiệ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ều thứ hai: big-O đếm bước, nhưng thời gian là bước nhân giá mỗi bước. Và đây là chỗ hiểu biết này trả cổ tức trên code thật. Java Arrays.binarySearch, C++ std::lower_bound, Python bisect đều tồn tại cho mảng lớn đã sắp và tra nhiều lần — nhưng với một List vài chục phần tử, list.contains() (quét tuyến tính) thường nhanh ngang hoặc hơn mà khỏi phải giữ danh sách luôn sắp. Cơ sở dữ liệu cũng ra đúng quyết định này ở tầng bộ tối ưu: nó không dùng index (vốn là tìm-có-cấu-trúc kiểu B-tree) cho bảng nhỏ hay khi phải trả về phần lớn số dòng — nó quét tuần tự (seq scan), vì quét tuyến tính cache-friendly thắng việc nhảy lung tung qua index; và index chỉ đáng khi bảng lớn và truy vấn lọc rất chọn lọc, đúng logic "mảng lớn + tra nhiều lần" ở đây. Gói lại bằng số: tìm tuyến tính O(n) và nhị phân O(log n) giao nhau quanh n=128 — dưới nó tuyến tính nhanh hơn (n=64: 14,5 so 20,2 ns) nhờ 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; 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).

Muốn tự quyết thì 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.