"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. Nhưng cả sê-ri này đã đo đi đo lại một sự thật: trên CPU hiện đại, 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 đánh đổ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 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: nếu bảng nhỏ và nằm trong L1, đọc gần như miễn phí; nếu bảng lớn hơn cache và bạn tra rải rác, mỗi lần tra là một cú chạm RAM đắt đỏ. 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 bảng theo cỡ: 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ớ".
Một lần tôi đo hớ: "bảng tra luôn nhanh hơn" và "tính lại luôn tốn hơn"
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 độ". Đo phá tan: đ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. Nếu tôi tin "bảng luôn nhanh" và nhồi một bảng khổng lồ, tôi tự làm code chậm nhiều lần.
Nhưng đo cũng phá niềm tin ngược — cái mà người vừa nghe "tính rẻ" dễ mắc: "vậy tính lại luôn tốt hơn tra sẵn". 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. 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.
Bài học đo lường: bảng tra đổi PHÉP TÍNH lấy một lần CHẠM BỘ NHỚ — lời hay lỗ tùy bảng nằm tầng nào. Đo (stream ngẫu nhiên): tính lại f (4 phép) 0,330 ns; bảng 4KB (L1) 0,284 (nhỉnh hơn); bảng 1MB (L2) 0,481 (chậm 1,5x); bảng 64MB (RAM) 2,499 (chậm 7,6x). Bảng CHỈ thắng khi vừa L1; vượt cache, tính lại vài phép rẻ hơn chạm RAM xa. 'Bảng luôn nhanh hơn' và 'tính lại luôn tốn hơn' đều SAI. Nếu tin "bảng luôn nhanh" tôi nhồi bảng lớn và chậm 7x; nếu tin "tính luôn rẻ hơn" tôi bỏ bảng nhỏ L1 vốn vẫn tốt.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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 là tối ưu tốt (như bảng popcount 8-bit, bảng CRC nhỏ). 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, và còn tiết kiệm bộ nhớ lẫn băng thông cache cho phần việc khác.
Hệ quả thứ hai: ưu tiên tính lại cho hàm rẻ, đặc biệt trong vòng nóng memory-bound. Nếu vòng lặp của bạn đã 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.
Hệ quả thứ ba là tinh thần đo lường: đánh đổi bộ-nhớ-lấy-tốc-độ chỉ đúng khi bộ nhớ đó nhanh — mà bộ nhớ lớn thì chậm. Con số mang theo: bảng tra thắng tính lại chỉ khi vừa L1 (4KB 0,284 vs tính 0,330); vượt L1 thì thua (1MB 1,5x, 64MB 7,6x). Trên CPU hiện đại tính rẻ, bộ nhớ xa đắt — dùng bảng khi nó nhỏ (vừa L1) hoặc hàm quá đắt để tính. Cùng một kết quả, lấy bằng cách tính hay cách tra, nhanh chậm gấp bảy lần tùy bảng có lọt vào cache hay không — đo mới biết ngưỡng.
Thử ba mươi giây
Chọn một hàm rẻ f (vài phép nhân/xor/dịch), rồi 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): bạn sẽ thấy 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 bạn 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.
