"Tính sẵn vào bảng tra" (lookup table) là một trong những mẹo tối ưu được dạy sớm nhất: thay vì tính một hàm mỗi lần cần, hãy tính trước mọi kết quả vào một mảng, lúc chạy chỉ tra — "đổi bộ nhớ lấy tốc độ". Nghe hiển nhiên đúng, và suốt mấy chục năm nó đúng thật.

Nhưng hãy nghĩ về nó như chuyện lấy một con số. Ngày xưa, tính nhẩm rất mệt còn cuốn sổ tra thì nằm ngay trên bàn — dở sổ ra chép nhanh hơn nhẩm nhiều. Bây giờ tình thế đảo ngược: cái máy tính bỏ túi bấm ra kết quả trong tích tắc, còn "cuốn sổ" thì dày tới mức phải chạy sang thư viện bên kia thành phố mới lấy được. Lúc này nhẩm — à không, bấm máy — lại nhanh hơn hẳn. CPU hiện đại đúng cảnh đó: cả sê-ri này đã đo đi đo lại rằng phép tính rất rẻ còn chạm bộ nhớ xa rất đắt (phần 5: RAM ~100 ns). Vậy cái mẹo "đổi bộ nhớ lấy tốc độ" có còn đúng? Tôi đo trong container gcc:13 trên host ARM, và câu trả lời lật ngược tùy đúng một điều: bảng có vừa cache hay không.

Bảng tra đổi phép tính lấy một lần chạm bộ nhớ

Khi bạn tra một bảng, bạn tránh được phép tính — nhưng thêm một lần đọc bộ nhớ. Chi phí lần đọc đó phụ thuộc bảng nằm ở tầng nào: bảng nhỏ nằm trong L1 thì đọc gần như miễn phí (cuốn sổ trên bàn); bảng lớn hơn cache mà bạn tra rải rác thì mỗi lần tra là một cú chạm RAM đắt đỏ (chạy sang thư viện bên kia thành phố). Trong khi đó, "tính lại" tốn một nhúm phép số học — mà phần 16/17 cho thấy các phép này rất rẻ và chạy song song tốt.

Để đo, tôi xử lý 8 triệu thao tác với chỉ số ngẫu nhiên (để lộ hành vi cache). Mỗi kết quả lấy bằng hai cách: tính lại một hàm băm f gồm 4 phép (nhân, xor, dịch bit), hoặc tra bảng f đã dựng sẵn — ở ba cỡ bảng khác nhau.

Đo: bảng chỉ thắng khi vừa L1

Stream 8M thao tác (chỉ số ngẫu nhiên), host ARM, g++ -O2 -fno-tree-vectorize:

   cách lấy kết quả          | ns/thao tác | so với tính lại
   --------------------------|-------------|----------------
   TÍNH LẠI f (4 phép hash)  |   0,330     | 1x (mốc)
   bảng tra 4KB   (trong L1) |   0,284     | 0,86x  (bảng nhỉnh hơn)
   bảng tra 1MB   (vào L2)   |   0,481     | 1,5x chậm
   bảng tra 64MB  (ra RAM)   |   2,499     | 7,6x chậm

Đọc theo cỡ bảng: khi bảng chỉ 4KB (nằm gọn trong L1), tra bảng (0,284 ns) nhỉnh hơn tính lại (0,330 ns) chút ít — đúng như trực giác "tra nhanh hơn tính". Nhưng khi bảng lớn lên 1MB (tràn xuống L2), tra bảng đã chậm hơn tính lại 1,5 lần. Và khi bảng 64MB (vượt mọi cache, mỗi lần tra ngẫu nhiên là một cú chạm RAM), tra bảng chậm 7,6 lần so với tính lại. Ngưỡng lật ngược nằm ở kích thước cache: bảng vừa L1 thì tra thắng; vượt L1, mỗi lần tra là một lần chạm bộ nhớ xa đắt hơn hẳn việc tính lại vài phép rẻ.

Và đây mới là stream độc lập, nơi MLP giấu bớt độ trễ. Nếu các lần tra nằm trên đường tới hạn — kết quả tra quyết định chỉ số tra kế tiếp (đuổi con trỏ, máy trạng thái) — thì bảng lớn còn tệ hơn nữa, trả trọn ~100 ns mỗi lần (phần 11/15). Bảng càng lớn, truy cập càng rải rác, thì "đổi bộ nhớ lấy tốc độ" càng thành "đổi tốc độ lấy bộ nhớ".

Hai châm ngôn đối nghịch, cùng sai

Tôi vào đo với câu thần chú tối ưu cũ: "tính sẵn vào bảng thì tra luôn nhanh hơn tính lại — đổi bộ nhớ lấy tốc độ". Con số cho thấy điều đó chỉ đúng khi bảng vừa L1. Bảng 1MB đã chậm hơn tính lại 1,5 lần, bảng 64MB chậm 7,6 lần. Lý do là mô hình chi phí đã đảo so với thời mẹo này ra đời: ngày xưa phép tính đắt và bộ nhớ tương đối nhanh, nên tra bảng thắng; nay phép tính cực rẻ còn chạm RAM cực đắt (chênh cả trăm lần), nên một bảng cache-miss thua xa việc tính lại. Tin "bảng luôn nhanh" rồi nhồi một bảng khổng lồ là tự làm code chậm nhiều lần.

Nhưng nếu vì thế mà quay sang tin "vậy tính lại luôn tốt hơn tra sẵn" thì cũng sai. Bảng 4KB vừa L1 vẫn nhỉnh hơn tính lại (0,284 vs 0,330), và nếu hàm đắt (nhiều phép, có chia, có hàm siêu việt) thì tra bảng nhỏ vẫn thắng đậm. Sự thật không nằm ở "tra" hay "tính" mà ở cân bằng: chi phí tính hàm so với chi phí chạm tầng bộ nhớ chứa bảng. Chọn mù theo một câu châm ngôn — dù là câu cũ hay câu mới — đều sai; phải cân hai chi phí và đo.

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

Việc đầu tiên: cân kích thước bảng theo cache, không theo châm ngôn. Một bảng vài KB vừa L1 vẫn là tối ưu tốt (bảng popcount 8-bit, bảng CRC nhỏ, bảng lượng giác thô). Nhưng nếu bảng lên hàng MB và bị tra rải rác, hãy đo lại: rất có thể tính lại nhanh hơn, mà còn tiết kiệm bộ nhớ lẫn băng thông cache cho phần việc khác.

Việc thứ hai: ưu tiên tính lại cho hàm rẻ, nhất là trong vòng nóng memory-bound. Nếu vòng lặp đã chạm nhiều bộ nhớ, thêm một bảng lớn nữa chỉ làm nghẽn thêm; tính lại bằng vài phép số học (thường chạy "miễn phí" trong khe trống của pipeline, phần 10) không tốn thêm băng thông. "Bớt tính, thêm tra" có thể phản tác dụng.

Điều thú vị là ở tầng cao, cái đánh đổi này đội lốt "cache" và người ta thường chỉ thấy một nửa câu chuyện. Memoization trong Python/JS, @Cacheable của Spring, hay một lớp cache Redis đặt trước một phép tính — tất cả là bảng tra ở quy mô lớn, và đúng cùng bài học áp dụng: nếu thứ được cache rẻ để tính lại mà cache lại nằm xa (một chuyến mạng round-trip tới Redis còn đắt hơn RAM nhiều bậc), thì cache có khi chậm hơn tính lại tại chỗ — cộng thêm phức tạp về hết hạn, nhất quán. Ngay cả HashMap Java làm bộ nhớ đệm cũng vậy: map nhỏ vừa cache thì tra nhanh, map khổng lồ tra ngẫu nhiên thì mỗi get() là một cú nhảy RAM. Nguyên tắc chung không đổi: đổi tính-toán lấy tra-cứu chỉ lời khi chỗ tra ở gần; càng xa, càng nên cân nhắc tính lại. Và cách duy nhất biết chắc là đo cả hai trên đúng quy mô thật.

Muốn tự thấy thì chọn một hàm rẻ f (vài phép nhân/xor/dịch), xử lý một mảng chỉ số ngẫu nhiên hai cách và bấm giờ ns mỗi thao tác. Một: tính lại acc ^= f(idx[i]). Hai: tra bảng acc ^= table[idx[i]], với table[j] = f(j) dựng sẵn. Chạy với bảng nhỏ (vài KB, vừa L1): tra bảng nhỉnh hơn hoặc ngang tính lại. Rồi tăng bảng lên hàng chục MB (vượt cache) và tra ngẫu nhiên: tra bảng chậm hẳn — mỗi lần tra giờ là một cú chạm RAM, đắt hơn nhiều việc tính lại f. Cuối cùng, thử để kết quả tra quyết định chỉ số kế tiếp (chuỗi phụ thuộc): bảng lớn còn thảm hơn, trả trọn độ trễ RAM mỗi bước. Ba mươi giây đó cho thấy điều mà "tính sẵn vào bảng cho nhanh" giấu đi: bảng chỉ nhanh khi nó ở gần (L1); một bảng lớn biến mỗi lần tra thành một chuyến đi xa tới RAM, và trên CPU hiện đại, tính lại vài phép rẻ thường về đích trước.