Hình dung một dãy hộp thư chung cư. Muốn lấy thư ở ô số 200, có hai cách. Cách thứ nhất: hỏi lần lượt "ô này số 0 phải không? ô này số 1?" mãi tới ô 200 — càng nhiều ô càng lâu. Cách thứ hai: tủ đánh số sẵn, bạn nhìn số 200 và bước thẳng tới ô đó, một bước, bất kể tủ có 4 ô hay 400. Trong lập trình, cách thứ nhất là chuỗi if-else quét tuyến tính, cách thứ hai là bảng nhảy — và khác biệt tốc độ giữa chúng cũng đúng theo cái logic "hỏi từng ô" so với "đi thẳng tới ô".

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). Bảng nhảy thì 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. Đây là "hỏi từng ô hộp thư".

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. Đây là "đi thẳng tới ô số v".

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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, 50 triệu truy vấn, mỗi số lấy MIN sau warmup. Con số tuyệt đối đổi theo máy; cái cần nhìn là dáng O(N) của quét tuyến tính so với O(1) của bảng, và chỗ hai đường gần chạm nhau ở N nhỏ.)

Hai niềm tin đối nghịch, cùng sai

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". Con số 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 ngay đường nóng.

Nhưng niềm tin ngược lại, hình thành ngay sau khi thấy bảng thắng — "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. Chọn đúng phụ thuộc số nhánh và phân bố, không phải một quy tắc chết.

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

Điều đầ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.

Điều 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.

Chỗ này thú vị là các máy ảo ngôn ngữ cao cấp đã đấu tranh với đúng bài toán này ở quy mô lớn. Vòng lặp diễn dịch bytecode của CPython, JVM hay Lua đều là một switch khổng lồ trên opcode, và người viết chúng đặc biệt quan tâm chuyện nó phải biên dịch thành jump table chứ không phải chuỗi so — thậm chí dùng kỹ thuật "computed goto" (nhảy bằng bảng nhãn) để CPU đoán nhánh tốt hơn. Ở tầng biên dịch just-in-time, HotSpot của Java chọn giữa tableswitch (bảng nhảy, nhãn dày) và lookupswitch (tìm nhị phân, nhãn thưa) đúng theo mật độ nhãn — chính là điểm giao trong bài này, được nướng thẳng vào bytecode. Và khi dispatch theo kiểu thay vì theo số (gọi phương thức ảo trong Java/C++), bảng nhảy đổi tên thành vtable — vẫn là một mảng con trỏ hàm tra bằng chỉ số. Cùng một ý tưởng tủ-hộp-thư-đánh-số, lặp lại ở mọi tầng.

Muốn tự thấy thì 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. Vài phút đó 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.