switch luôn O(1) nhanh hơn if-else? Tôi đo và niềm tin đó sai ở ba chỗ khác nhau

Hình dung một phòng chia thư có lưới ô đánh số. Muốn bỏ thư vào ô số 7, bạn tính ngay ra vị trí và bước tới — không phải dò từng ô, O(1). Nhưng cái lưới đó chỉ hợp lý khi các số sát nhau: nếu địa chỉ nhảy cóc 0, 100, 9999 thì bạn phải dựng một lưới khổng lồ đầy ô trống, chi bằng cầm một danh sách ngắn dò cho xong. Và ngay cả khi có lưới, bạn vẫn phải đi bộ tới đúng ô — nếu ngày nào cũng chỉ bỏ vào ô số 0, thì thò tay đưa luôn còn nhanh hơn đi ra lưới. switch của compiler đúng là cái phòng chia thư này, và niềm tin "switch luôn nhanh hơn" bỏ quên cả ba chuyện đó.

Có một niềm tin phổ biến: viết switch thay cho một chuỗi if-else thì nhanh hơn, vì compiler biến switch thành một bảng nhảy (jump table) — tra thẳng địa chỉ theo giá trị và nhảy tới, O(1), không phụ thuộc số nhánh. Nghe rất gọn. Tôi đo trong container gcc:13 (ARM) để xác nhận, và phát hiện câu chuyện có tới ba lớp mà niềm tin đó bỏ qua.

Ba cách compiler dịch một switch

Tôi thử vài kiểu switch và soi objdump. Hóa ra compiler chọn một trong ba cách, tùy hình dạng của switch:

Công thức. Nếu các nhánh trả về theo quy luật — case 0: return 11; case 1: return 22; ... (tức 11*(x+1)) — gcc không làm bảng cũng không làm nhánh, nó tính thẳng bằng một lệnh madd (nhân-cộng). Đây là trường hợp nhanh nhất, và nó xảy ra khi nội dung các case có cấu trúc.

Bảng nhảy. Khi các case dày đặc (0, 1, 2, ..., 11) và mỗi case làm việc khác nhau (không rút thành công thức), gcc sinh một mảng địa chỉ trong .rodata, tra theo x, rồi nhảy gián tiếp (br x3 trên ARM). Một lần tra bảng, một lần nhảy — O(1), bất kể có 8 hay 800 nhánh. Đây là cái lưới ô đánh số.

Chuỗi so sánh. Khi các case thưa (0, 100, 1000, 33333, ...), làm bảng sẽ tốn một mảng khổng lồ đầy lỗ hổng, nên gcc bỏ bảng và sinh một chuỗi cmp nối tiếp — tôi đếm được 5 lệnh cmp cho switch 7 case thưa. Đây là O(số nhánh), y như if-else, đúng cảnh cầm danh sách ngắn dò cho xong thay vì dựng lưới rỗng.

Vậy niềm tin "switch = bảng nhảy" đã sai ở lớp đầu: switch chỉ thành bảng khi case dày; case thưa vẫn là chuỗi so sánh, và case có quy luật còn chẳng cần bảng. Nhưng ngay cả khi có bảng, nó có thật sự nhanh hơn không?

Đo: bảng nhảy có cái giá riêng

Tôi đo một switch 12 case dày (thành bảng nhảy thật) so với một chuỗi if-else tương đương, mỗi lần gọi 60 triệu lần, đổi giá trị x đưa vào:

tình huống                    bảng nhảy (br)   if-else (chuỗi cmp)   ai thắng
case nóng ở ĐẦU (x=0)            1,143 ns          0,937 ns           if-else
case nóng ở CUỐI (x=11)          0,936 ns          0,951 ns           hòa
case NGẪU NHIÊN (khó đoán)       6,090 ns          6,497 ns           bảng (nhẹ)

Ba dòng này lật niềm tin còn lại. Khi case nóng nằm ở đầu chuỗi (x=0 luôn), if-else chỉ cần một phép so sánh — và nó nhanh hơn bảng nhảy (0,937 so với 1,143 ns). Vì bảng nhảy không miễn phí: nó phải nạp một địa chỉ từ bảng rồi thực hiện một nhảy gián tiếp, mà nhảy gián tiếp là loại nhánh khó đoán hơn nhánh có điều kiện thường (như csel và dự đoán nhánh đã bàn). Cái chi phí cố định đó khiến bảng thua khi đối thủ chỉ là một if đơn — đúng cảnh thò tay đưa vào ô số 0 nhanh hơn đi ra lưới.

Dòng thứ hai còn bất ngờ hơn. Khi case nóng ở cuối (x=11, if-else phải đi qua cả 12 phép so sánh), nó vẫn gần bằng bảng nhảy: 0,951 so với 0,936 ns. Tức là 12 phép so sánh chỉ đắt hơn 1 phép so sánh chút xíu (0,951 so với 0,937). Lý do: khi x cố định, mọi nhánh trong chuỗi đều đoán được hoàn hảo, và CPU chạy chúng gần như miễn phí. "O(n) phép so sánh" trên giấy không thành "O(n) thời gian" trên đồng hồ khi các nhánh đoán được.

Cú vấp: "switch luôn O(1) nhanh hơn" sai ba lớp

Tôi vào bài tin "switch luôn thành bảng nhảy O(1), luôn nhanh hơn if-else". Đo xong, nó sai ở ba chỗ độc lập:

Một, switch không luôn thành bảng — chỉ khi case dày; thưa thì thành chuỗi cmp, có quy luật thì thành công thức. Hai, bảng nhảy O(1) có chi phí cố định (tra bảng + nhảy gián tiếp khó đoán), nên nó thua if-else khi case nóng ở đầu chuỗi. Ba, O(n) của if-else không thành O(n) thời gian khi nhánh đoán được — 12 so sánh gần bằng 1.

Vậy bảng nhảy thắng khi nào? Nhìn dòng cuối: chỉ khi case nhiều và khó đoán (ngẫu nhiên đều 12 giá trị), bảng mới nhỉnh hơn — nhưng cả hai lúc đó đều đắt (~6 ns), vì với phân bố ngẫu nhiên thì cả nhảy gián tiếp của bảng lẫn chuỗi nhánh của if-else đều đoán sai liên tục. Bảng thắng nhẹ vì một cú nhảy gián tiếp đoán sai vẫn rẻ hơn đi qua trung bình sáu nhánh có điều kiện đoán sai. Nhưng "thắng nhẹ khi cả hai đều tệ" khác hẳn "luôn O(1) nhanh hơn".

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

Điều đầu tiên: chọn switch hay if-else vì sự rõ ràng, không vì tốc độ tưởng tượng. Với vài nhánh, hai cách chạy gần như y hệt; compiler chọn cách lower phù hợp mà bạn không phải nghĩ. switch gọn và biểu đạt ý "phân nhánh theo giá trị" tốt hơn — đó mới là lý do dùng nó, không phải một huyền thoại O(1).

Điều thứ hai: hình dạng dữ liệu và phân bố case mới quyết định. Nếu một case chiếm 95% số lần (một "đường nóng" rõ), đặt nó thành một if kiểm tra sớm trước switch có thể nhanh hơn cả bảng — vì nhánh dễ đoán đó gần như miễn phí, tránh luôn cú nhảy gián tiếp. Nếu case rải đều và khó đoán, bảng nhảy là lựa chọn tốt hơn. Chỉ đo trên phân bố thật mới biết.

Và cái ý "switch không phải một thứ, mà là nhiều cách biên dịch" này lặp lại thú vị ở các ngôn ngữ khác. JVM có hẳn hai bytecode cho switch: tableswitch (bảng nhảy, dùng khi case dày) và lookupswitch (bảng khóa-giá trị đã sắp, tra bằng tìm nhị phân, dùng khi thưa) — javac chọn cái nào tùy độ dày, đúng logic gcc, và JIT còn tối ưu tiếp theo hồ sơ. Go thì thẳng thắn: spec nói switch chỉ là cú pháp gọn cho if-else, compiler tự quyết có làm bảng nhảy không — không có bảo đảm O(1) nào. Ngay cả CSDL cũng có tinh thần này: một CASE WHEN nhiều nhánh, hay việc chọn giữa index-scan và full-scan, đều là "cùng một truy vấn, nhiều cách thực thi tùy phân bố dữ liệu". Mẫu số chung: một cấu trúc rẽ nhánh cấp cao không có một chi phí cố định — tầng dưới dịch nó thành nhiều dạng tùy dữ liệu dày hay thưa, đoán được hay không, và cái nhanh nhất phụ thuộc phân bố thật của bạn chứ không phải độ phức tạp Big-O trên giấy.

Muốn tự thấy thì viết một switch 10 case dày (0..9), mỗi case trả một biểu thức khác nhau (để tránh gcc rút thành công thức), rồi gcc -O2 -S -o - t.c và tìm hàm: bạn sẽ thấy adrp/ldr nạp một bảng từ .rodata và một br nhảy gián tiếp — đó là bảng nhảy. Giờ đổi các case thành thưa (0, 50, 100, 500, ...) và biên dịch lại: bảng biến mất, thay bằng một chuỗi cmp. Rồi thử case 0: return 10; case 1: return 20; ... (có quy luật) — cả bảng lẫn chuỗi đều biến mất, chỉ còn một phép nhân. Ba lần biên dịch cho bạn thấy switch không phải một thứ, mà là ba, tùy bạn viết case thế nào.