Một câu switch trông như một cấu trúc đơn giản, và có một niềm tin phổ biến rằng nó luôn biên dịch thành bảng nhảy (jump table) — một mảng địa chỉ, đánh chỉ số bằng giá trị, nhảy thẳng, O(1). Bài này biên dịch nhiều kiểu switch trong container và đọc assembly xem thực tế trình biên dịch làm gì — và niềm tin "switch là bảng nhảy" của tôi bị bốn phép đo lần lượt bác bỏ.
switch là ý định, không phải chiến lược
switch chỉ nói ý định: "chọn nhánh theo giá trị này". Trình biên dịch mới là bên quyết định chiến lược máy để thực hiện, và nó cân nhắc dựa trên hai thứ cụ thể: giá trị các case (dày đặc hay thưa thớt, có quy luật hay lộn xộn) và số lượng case. Nó có ít nhất bốn cách, mỗi cách hợp một tình huống — và một điều quan trọng: nó tránh bảng nhảy khi có cách rẻ hơn, vì bảng nhảy dùng một lệnh nhảy gián tiếp (nhảy tới địa chỉ tính lúc chạy) mà bộ dự đoán nhánh của CPU khó đoán, dễ phạt nặng.
Đo: bốn câu switch, bốn chiến lược khác nhau
Tôi viết bốn hàm switch, biên dịch -O2, và đếm lệnh dấu hiệu bằng objdump: br (nhảy gián tiếp = bảng nhảy), cmp (so sánh), ldr từ bảng, mul (công thức).
Một — dày đặc, giá trị trả có quy luật. case 0: return 10; case 1: return 21; ... (mỗi case trả 10 + 11×x):
mov w1, #11
mul w0, w0, w1 ; 11 * x
add w0, w0, #0xa ; + 10
Không bảng, không nhảy — gcc nhận ra các giá trị trả là cấp số cộng và gấp cả câu switch thành một công thức x<8 ? 11*x+10 : -1. br=0.
Hai — dày đặc, giá trị trả lộn xộn. case 0: return 17; case 1: return 3; ... (không quy luật):
cmp w0, #7
adrp x1, <bảng>
ldr w0, [x1, w0, uxtw #2] ; nạp giá trị từ bảng, đánh chỉ số bằng x
Đây là bảng tra cứu dữ liệu: một mảng hằng trong .rodata, nạp thẳng giá trị trả theo chỉ số x. O(1), một phép nạp, nhưng vẫn không phải "bảng nhảy" — nó nạp dữ liệu, không nhảy tới mã. br=0.
Ba — dày đặc, mỗi case chạy mã khác. case 0: return fa(x); case 1: return fb(x); ... (tám hàm khác nhau). Đây là câu tôi chắc chắn sẽ ra bảng nhảy. Đo được: bảy lệnh cmp, br=0 — một chuỗi so sánh / cây tìm nhị phân, không phải bảng nhảy. gcc thấy tám nhánh không đủ nhiều để đáng một lệnh nhảy gián tiếp, nên dựng một cây so sánh O(log n).
Bốn — thưa thớt. case 1, 100, 10000, 1000000: bốn lệnh cmp, cây tìm nhị phân — dĩ nhiên không bảng nhảy, vì một bảng từ 1 tới một triệu để chứa bốn case sẽ khổng lồ và phí.
Bảng nhảy thật — với lệnh br gián tiếp — chỉ xuất hiện khi tôi đẩy lên 20 case dày đặc chạy mã khác nhau: lúc đó br=1, cùng một bảng địa chỉ trong .rodata và một lệnh nhảy gián tiếp sau khi kiểm biên.
Một lần tôi đo hớ: "switch là bảng nhảy" sai nhiều mặt
Tôi vào bài với niềm tin gọn gàng của sách giáo khoa: "switch dày đặc biên dịch thành bảng nhảy, O(1), luôn thế". Tôi định lấy vài ví dụ dày đặc làm minh họa. Nhưng khi đọc assembly bốn ví dụ dày đặc của mình, không một cái nào ra bảng nhảy gián tiếp — br=0 ở cả bốn.
Từng cái một bác bỏ mô hình của tôi: cái thì gcc gấp thành công thức (vì tôi vô tình cho giá trị trả có quy luật), cái thì thành bảng tra cứu dữ liệu (giá trị trả lộn xộn), và cái mà tôi chắc chắn nhất sẽ là bảng nhảy — tám case gọi tám hàm khác nhau — lại thành một chuỗi so sánh. Tôi phải đẩy lên hai mươi case mới thấy lệnh br gián tiếp thật sự xuất hiện.
Bài học đo lường: mô hình "switch = bảng nhảy" sai trên nhiều trục cùng lúc. Thứ nhất, switch chỉ là ý định; trình biên dịch có nhiều chiến lược và chọn theo giá trị và số lượng case cụ thể, không theo cú pháp. Thứ hai, nó chủ động tránh bảng nhảy — nhảy gián tiếp bị bộ dự đoán nhánh của CPU đoán sai thường xuyên, phạt hàng chục chu kỳ, nên một chuỗi so sánh dự đoán tốt lại nhanh hơn cho ít nhánh. Thứ ba, giá trị trả cũng là một biến ẩn: cùng cấu trúc switch, đổi giá trị trả từ có-quy-luật sang lộn-xộn là đổi luôn chiến lược từ công thức sang bảng tra cứu. Tôi suýt viết cả bài dạy sai một mô hình quá đơn giản — chỉ đọc assembly mới thấy bức tranh thật gồm bốn chiến lược.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng cho rằng switch luôn O(1), và đừng "tối ưu" nó bằng tay theo linh cảm. Với các case dày đặc, gcc gần như luôn cho bạn thứ tốt nhất — công thức, bảng tra cứu, hay bảng nhảy — nên viết switch sạch, đọc dễ, rồi để trình biên dịch lo. Cái đáng để tâm là các case thưa thớt: một switch trên vài giá trị cách xa nhau (mã trạng thái HTTP, mã lỗi lớn) sẽ thành cây so sánh O(log n), không phải O(1) — nếu đó là đường nóng và bạn cần O(1) thật, hãy tự dựng một bảng băm hay ánh xạ, đừng trông đợi switch làm hộ.
Hệ quả thứ hai: giá trị trả và cách viết case ảnh hưởng tới mã sinh ra. Nếu các nhánh của bạn trả về hằng số, gcc có thể dựng bảng tra cứu — sạch và nhanh. Nếu bạn xếp các case dày đặc (0, 1, 2, ... liên tục) thay vì thưa, gcc dễ dùng bảng hơn là cây so sánh. Biết điều này giúp bạn viết switch mà trình biên dịch tối ưu được tốt, thay vì vô tình ép nó vào chuỗi so sánh chậm.
Hệ quả thứ ba là bài học mang theo: cấu trúc điều khiển cấp cao không quyết định mã máy — trình biên dịch quyết, theo dữ liệu cụ thể. Con số mang theo: cùng từ khóa switch sinh ra bốn kiểu mã hoàn toàn khác — công thức (giá trị trả có quy luật), bảng tra cứu (trả hằng lộn xộn), chuỗi/cây so sánh (thưa hoặc ít case), bảng nhảy gián tiếp (nhiều case dày đặc, mã khác nhau) — chọn theo giá trị và số case, và gcc còn cố tránh bảng nhảy vì nhảy gián tiếp dễ đoán sai nhánh. "switch là bảng nhảy" là một nửa sự thật; nửa còn lại chỉ hiện ra khi bạn đọc assembly thay vì đoán.
Thử ba mươi giây
Viết hai hàm switch: một hàm với case 0..9 liên tục, một hàm với case 1, 1000, 1000000 thưa thớt, mỗi case trả một hằng số. Biên dịch gcc -O2 -S và đọc assembly: hàm dày đặc rất có thể dùng một lệnh nạp từ bảng (ldr với chỉ số) hoặc một lệnh nhảy gián tiếp (jmp */br), còn hàm thưa sẽ là một chuỗi cmp nối tiếp. Thử đổi các giá trị trả của hàm dày đặc thành một cấp số cộng (0, 5, 10, 15, ...) rồi biên dịch lại: bạn có thể thấy cả bảng biến mất, thay bằng một phép nhân-cộng — gcc đã nhìn ra quy luật. Đó là toàn bộ điểm: switch là câu hỏi, còn assembly mới là câu trả lời, và câu trả lời đổi theo chính những con số bạn viết.
