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 vào đo để 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
Trong container gcc:13 (ARM AArch64), 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.
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.
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.
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.
Đo hớ: "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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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).
Hệ quả 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.
Hệ quả thứ ba là bài học đo lường của cả sê-ri: một cấu trúc ngôn ngữ không có một chi phí cố định — nó có nhiều cách biên dịch, và mỗi cách có một đường cong khác nhau. "switch nhanh vì O(1)" gộp ba cách lower thành một, và bỏ qua chi phí nhảy gián tiếp cùng sức mạnh của dự đoán nhánh. Con số mang theo: gcc dịch switch thành một trong ba (công thức / bảng nhảy khi case dày, O(1), nhảy gián tiếp / chuỗi cmp khi case thưa); bảng nhảy có chi phí cố định của nhảy gián tiếp khó đoán nên thua if-else khi case nóng ở đầu (0,937 so 1,143 ns), hòa khi nhánh đoán được (12 cmp ~ 1: 0,951 so 0,937), và chỉ nhỉnh khi nhiều case khó đoán (6,09 so 6,50, cả hai đều đắt). Đừng cho switch là O(1) miễn phí; xem objdump cách nó lower, rồi đo đúng phân bố case của bạn.
Thử ba mươi giây
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.
