Bạn cần làm một hành động khác nhau tùy giá trị v — một máy trạng thái, một bộ diễn dịch opcode, một dispatch theo loại. Cách quen thuộc là chuỗi if-else (hoặc switch). Nhưng có một cách khác: bảng nhảy — dùng chính v làm chỉ số vào một mảng (giá trị, con trỏ hàm, hay nhãn) và nhảy thẳng tới nhánh đúng. Nhiều người nghĩ "if-else nhiều nhánh cũng nhanh như nhau, compiler tự tối ưu". Nhưng khi tôi đo, chuỗi if-else quét tuyến tính chậm hơn bảng tới hàng trăm lần khi số nhánh lớn — và đồng thời, ở số nhánh nhỏ, if-else lại đủ tốt. Tôi đo cả hai trong container gcc:13, và con số cho thấy đây là một điểm giao, không phải một câu trả lời.
Quét tuyến tính O(N) so với tra bảng O(1)
Chuỗi if-else / quét tuyến tính: so v với 0, rồi 1, rồi 2… tới khi khớp. Trung bình N/2 lần so cho N nhánh — O(N). Mỗi lần so là một rẽ nhánh; nếu v khó đoán (phân bố đều), CPU đoán sai nhánh liên tục (branch misprediction), càng phạt.
Bảng nhảy (jump table / mảng tra / mảng con trỏ hàm): dùng v làm chỉ số nhảy thẳng tới nhánh/giá trị đúng — một lần truy cập bộ nhớ, O(1) bất kể N.
Một hiểu lầm phổ biến: "cứ viết switch/if-else, compiler tự chuyển thành jump table". Không hẳn — compiler chỉ chuyển switch sang jump table khi các nhãn dày và liền nhau (0, 1, 2, …). Nếu bạn viết chuỗi if-else rời rạc, điều kiện phức tạp, hay nhãn thưa (0, 100, 5000), compiler thường để nguyên chuỗi so tuyến tính O(N). "Compiler lo hết" không đúng với mọi cách viết.
Đo: 121 lần chậm ở N lớn, ngang nhau ở N nhỏ
Tôi làm 50 triệu truy vấn với v phân bố đều, đo quét tuyến tính so với tra bảng theo số nhánh N:
50 triệu truy vấn, v phân bố đều, g++ -O2:
N | if-else (quét tuyến tính) | bảng nhảy (tra bảng)
-------|---------------------------|----------------------
2 | 0,79 ns | 0,24 ns (bảng 3,2x)
16 | 2,86 ns | 0,24 ns (bảng 11,7x)
64 | 8,70 ns | 0,24 ns (bảng 36,8x)
256 | 35,57 ns | 0,29 ns (bảng 121x)
IF-ELSE VIẾT TAY 4 nhánh (branch trực tiếp, không quét): 0,29 ns ~ NGANG bảng (0,24)
Phân bố LỆCH (90% một nhánh): 0,29 ns (branch prediction gần như miễn phí)
Nhìn cột quét tuyến tính: thời gian tăng tuyến tính theo N — 0,79 ns ở N=2 lên 35,57 ns ở N=256. Còn bảng nhảy giữ ~hằng số 0,24 ns bất kể N. Ở N=256, bảng nhanh hơn 121 lần, và khoảng cách càng giãn khi N lớn — đúng dấu hiệu O(N) so với O(1). Với một dispatch nóng trên nhiều nhánh (bộ diễn dịch opcode, máy trạng thái nhiều trạng thái), chuỗi if-else quét là một nút cổ chai thật.
Nhưng nhìn phần dưới — điểm giao như phần 11: một if-else viết tay với ít nhánh (4) mất 0,29 ns, gần bằng bảng (0,24 ns). Ở số nhánh nhỏ, if-else không cần truy cập bộ nhớ bảng, và các nhánh dễ đoán; khác biệt gần như không đáng kể. Và nếu phân bố lệch (90% rơi vào một nhánh), branch prediction làm if-else gần như miễn phí (vẫn 0,29 ns, nhưng CPU đoán đúng gần như luôn). Với ít nhánh hoặc phân bố lệch, if-else đủ tốt — thậm chí có thể nhỉnh hơn nhờ không chạm bộ nhớ.
Một lần tôi đo hớ: "compiler lo hết" và "luôn dùng bảng nhảy"
Tôi vào đo với niềm tin: "viết bao nhiêu if-else cũng được, compiler tối ưu thành switch nhanh". Đo cho thấy chỉ đúng một phần: compiler chỉ biến switch nhãn dày thành jump table; một chuỗi if-else rời rạc hay điều kiện phức vẫn quét tuyến tính O(N) — ở 256 nhánh chậm 121 lần bảng. Nếu tôi cần dispatch nhiều nhánh nóng và tin "compiler lo", tôi để lại một O(N) ẩn. Còn niềm tin ngược, sau khi thấy bảng nhanh: "vậy luôn dùng bảng nhảy vì O(1)". Cũng sai — ở 2-4 nhánh, if-else viết tay ngang bảng (0,29 vs 0,24 ns), không cần truy cập bộ nhớ, và nếu phân bố lệch thì branch prediction làm nó gần miễn phí. Ép một bảng tra cho một cái if 3 nhánh là phức tạp hóa vô ích.
Bài học đo lường: phân nhánh theo giá trị — chuỗi if-else quét tuyến tính là O(N) (đo N=256: 35,57 ns) còn bảng nhảy (dùng giá trị làm chỉ số) là O(1) (~0,24 ns) = chậm 121x ở N lớn; NHƯNG N NHỎ (2-4) if-else viết tay ngang bảng (0,29 vs 0,24 ns) và phân bố LỆCH làm branch prediction gần miễn phí. Compiler chỉ chuyển switch nhãn DÀY sang jump table, không phải mọi if-else. Nếu tôi tin "compiler lo hết" tôi có thể để O(N) trên dispatch nóng; nếu tôi tin "luôn dùng bảng" tôi phức tạp hóa những nhánh nhỏ mà if-else đã đủ nhanh. Chọn theo số nhánh và phân bố.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: với dispatch nhiều nhánh, nóng, phân bố đều — dùng bảng tra tường minh (mảng giá trị hoặc con trỏ hàm), hoặc switch với nhãn dày. Bộ diễn dịch bytecode, máy trạng thái nhiều trạng thái, dispatch theo enum — đây là sân của bảng nhảy. Đảm bảo nhãn switch liền và dày để compiler sinh jump table (nếu thưa, ánh xạ về 0..N-1 trước). Với con trỏ hàm, một handlers[opcode]() là O(1) và rõ ràng.
Hệ quả thứ hai: với ít nhánh hoặc phân bố lệch — if-else đơn giản là đủ, đừng tối ưu sớm. Ở 2-4 nhánh, if-else viết tay nhanh ngang bảng và dễ đọc hơn. Nếu một nhánh chiếm đa số trường hợp (đường nóng), đặt nó trước trong chuỗi if-else để branch prediction và thoát sớm giúp bạn — đó là tối ưu đúng cho phân bố lệch. Đo trước khi thay if-else bằng bảng.
Hệ quả thứ ba là tinh thần đo lường: "compiler tự tối ưu" là niềm tin cần kiểm chứng, và cấu trúc dispatch là một điểm giao O(N) vs O(1). Con số mang theo: chuỗi if-else quét tuyến tính O(N) (N=2: 0,79 ns → N=256: 35,57 ns) vs bảng nhảy O(1) (~0,24 ns) = chậm 121x ở N=256; nhưng N nhỏ (2-4) if-else viết tay ~ngang bảng (0,29 vs 0,24 ns), phân bố lệch làm branch prediction gần miễn phí. Compiler chỉ chuyển switch nhãn DÀY LIỀN sang jump table — if-else rời rạc/điều kiện phức vẫn O(N). Chọn: nhiều nhánh + đều -> bảng nhảy; ít nhánh / lệch -> if-else. Nhiều nhánh và tin "compiler lo" là quả bom O(N); ít nhánh mà ép bảng là phức tạp thừa.
Thử ba mươi giây
Viết hai cách dispatch trên một giá trị 0..N-1: một chuỗi if-else (hay một vòng quét for i: if(v==i)) và một mảng tra (table[v]). Bấm giờ với N=4, 16, 64, 256 và nhiều truy vấn phân bố đều. Bạn sẽ thấy cách quét tăng tuyến tính theo N (chậm dần), còn bảng giữ nguyên tốc độ — ở N lớn, bảng nhanh hàng trăm lần. Rồi thử với N=2-4 và một if-else viết tay (không vòng): nó gần bằng bảng, đôi khi nhỉnh hơn vì không chạm bộ nhớ. Cuối cùng, làm truy vấn lệch (90% một giá trị) và xem if-else nhanh lên nhờ CPU đoán đúng nhánh. Ba mươi giây đó cho bạn thấy điều mà "cứ viết if-else, compiler lo" giấu đi: chuỗi if-else quét là O(N), bảng nhảy là O(1), và giữa chúng là một điểm giao phụ thuộc số nhánh và phân bố — không có câu trả lời duy nhất, chỉ có lựa chọn đúng cho tình huống.
