Chia cho 7 gần như miễn phí, chia cho một biến đắt gấp 2,7 lần — cùng một dấu gạch chéo

Hình dung một người bán hàng cần chia mọi con số cho 7. Cách chậm là đặt phép chia dài mỗi lần. Nhưng người bán khôn thì nhớ một mẹo: "nhân với 0,142857 rồi làm tròn" — vài bước nhân và dịch nhẩm, nhanh hơn hẳn phép chia dài. Mẹo này chỉ dựng được khi biết trước số chia là 7. Nếu mỗi khách lại chia cho một số khác nhau, không nhớ trước được, thì đành quay lại phép chia dài chậm chạp từng lần. Trình biên dịch làm y hệt người bán đó, và cùng một dấu / trong code hóa ra mang hai cái giá khác hẳn nhau.

Ở bài sức mạnh giảm ta thoáng thấy compiler thay phép chia cho hằng số bằng một phép nhân. Phép chia đáng một bài riêng, vì nó là phép số học đắt nhất — lệnh udiv/sdiv mất khoảng 10-20 chu kỳ và không chạy song song tốt, trong khi nhân chỉ vài chu kỳ và có đường ống đầy đủ. Câu hỏi: khi nào compiler tránh được phép chia, và tránh được bao nhiêu? Tôi đo trong container gcc:13 (ARM), tin rằng "chia là chia, tốn như nhau" — và thấy cùng một dấu / cho hai chi phí khác hẳn.

Số ma thuật: nhân thay cho chia

Mẹo nằm ở toán học: chia cho d giống nhân với 1/d. Máy không có 1/d dưới dạng số nguyên, nhưng nó dùng một xấp xỉ điểm cố định: chọn một hằng m ≈ 2^k / d, rồi x / d = (x * m) >> k với vài chỉnh nhỏ để làm tròn đúng. Vì m và k cố định (khi d là hằng biết lúc biên dịch), cả phép chia biến thành một phép nhân với hằng rồi dịch bit. Chính là mẹo "nhân với 0,142857" của người bán hàng.

Tôi soi mã máy. x / 7u (unsigned) biên dịch thành:

mov   w1, 18725
movk  w1, 0x2492, lsl 16     (m = 0x24924925)
umull x1, w0, w1             (nhân)
lsr   x1, x1, 32
... (dịch, cộng, trừ)         -> không một lệnh udiv nào

Không có phép chia; toàn nhân và dịch. x % 10u cũng thành một chuỗi magic (m = 0xcccccccd) rồi trừ. Số chia có dấu (x / 7) thêm một bước sửa dấu cho số âm. Và trường hợp đẹp nhất — chia cho lũy thừa 2 như x / 256u — chỉ còn một lệnh dịch lsr w0, w0, 8. Ngược lại, chia cho một biến (x / d với d không biết trước) vẫn là lệnh udiv thật, vì không có magic nào cố định được.

Đo: chia hằng nhanh 2,7 lần, nhưng chỉ ở thông lượng

Tôi đo chia trên 100 triệu phần tử, hai chế độ tải:

THÔNG LƯỢNG (mỗi phần tử chia độc lập, chạy song song được):
  x / 7  hằng (magic)        : 0,1715 ns/phần tử
  x / d  biến (udiv thật)    : 0,4668 ns/phần tử   -> chậm 2,7 lần
  x / 256 lũy thừa 2 (dịch)  : 0,1702 ns/phần tử

Chia cho hằng số nhanh 2,7 lần chia cho biến. Hai lý do. Thứ nhất, chuỗi magic tuy vài lệnh nhưng toàn nhân/dịch rẻ, còn udiv là một lệnh nhưng đắt và thông lượng thấp (bộ chia xử lý ít phép mỗi chu kỳ). Thứ hai — và quan trọng hơn — phép nhân magic vector hóa được: objdump xác nhận bản chia-hằng dùng umull trên thanh ghi NEON, xử lý nhiều phần tử một lúc; còn udiv không có bản vector trên ARM, nên vòng chia-biến chạy từng phần tử một. Chia cho lũy thừa 2 thì chỉ một lệnh dịch, nhanh ngang magic.

Nhưng khi tôi đổi sang chuỗi phụ thuộc — mỗi phép chia chờ kết quả phép trước, không song song được — câu chuyện lật:

CHUỖI PHỤ THUỘC (đo độ trễ):
  x / 7 hằng (magic)  : 2,048 ns/phép
  x / d biến (udiv)   : 1,820 ns/phép   -> magic KHÔNG thắng, còn chậm hơn chút

Đây là chỗ tôi nhầm, và nó nối thẳng với sức mạnh giảm. Tôi tưởng chia hằng luôn nhanh hơn. Nhưng trong chuỗi phụ thuộc, dãy magic (nhân + nhiều dịch/cộng) là một chuỗi lệnh dài hơn một udiv đơn, nên độ trễ của nó thực ra lớn hơn. Magic thắng ở thông lượng (nhiều phép độc lập chạy song song, cộng vector hóa), không phải ở độ trễ. Cùng một tối ưu, lợi hay không tùy hình dạng tải — đúng bài học lặp lại của sê-ri.

Modulo cũng vậy — và vì sao bảng băm thích lũy thừa 2

Phép lấy dư % chỉ là một phép chia rồi trừ, nên nó thừa hưởng đúng câu chuyện: x % 10 với 10 là hằng biến thành nhân magic rồi trừ (không udiv), còn x % n với n là biến là một udiv đắt. Đây là lý do ẩn đằng sau một quyết định thiết kế quen thuộc: nhiều bảng băm chọn số ô (bucket) là lũy thừa 2 để hash % size rút về hash & (size-1) — một phép AND một lệnh, rẻ hơn cả magic. Nếu số ô là một số nguyên tố (tốt cho phân bố băm) nhưng biến lúc chạy, mỗi lần định vị ô phải trả một udiv.

Đó là một đánh đổi thật giữa chất lượng băm và tốc độ định vị: số nguyên tố cho phân bố đều hơn nhưng buộc chia-biến đắt; lũy thừa 2 cho phép AND siêu rẻ nhưng dễ gom cụm nếu hàm băm yếu. Biết phép modulo tốn gì giúp bạn hiểu vì sao các thư viện chọn cách này hay cách kia.

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

Điều đầu tiên rất thực dụng: làm ước số thành hằng số lúc biên dịch khi có thể. Nếu bạn chia theo một tham số cố định (số cột của lưới, kích thước một khối, một hằng cấu hình biết trước), khai nó là hằng (const, #define, hay constexpr) để compiler thấy và thay udiv bằng magic. Ngược lại, một x / n với n đọc từ biến buộc phải là udiv đắt — nếu n thực ra ít giá trị, một switch trên vài n gọi với hằng có thể mở khóa magic.

Điều thứ hai: lũy thừa 2 là ước số rẻ nhất — nhưng để compiler làm, đừng tự viết >>. x / 256 với 256 là hằng đã thành một lệnh dịch; bạn không cần (và không nên) tự viết x >> 8, vì với số âm phép dịch phải khác phép chia (chia làm tròn về 0, dịch làm tròn xuống), compiler xử lý đúng còn bạn dễ sai. Chọn kích thước lũy thừa 2 cho những chỗ chia nóng là một quyết định thiết kế đáng giá; để trình biên dịch lo phần mã.

Và cái mẹo "biết trước hằng số thì biến chia thành nhân" này không riêng của C — nó có ở mọi tầng, cùng nguyên lý. JIT của JVM làm y hệt lúc chạy: một x / 7 trong vòng nóng được biên dịch thành nhân magic, và nếu ước số là hằng runtime ổn định, JIT còn chuyên biệt hóa theo nó. Nhưng đáng nhớ nhất là ở tầng thiết kế hệ thống: quyết định "lũy thừa 2 hay số nguyên tố" cho số bucket lặp lại khắp nơi — HashMap của Java cố định dùng lũy thừa 2 (và bù phân bố bằng cách trộn bit của hash), trong khi nhiều bảng băm C++/Python truyền thống chọn số nguyên tố và chấp nhận phép chia. Việc phân mảnh (sharding) dữ liệu theo id % N cũng vậy: chọn N lũy thừa 2 thì định tuyến rẻ nhưng resize khó, chọn linh hoạt thì trả giá chia. Mẫu số chung: một con số cố định biết trước luôn mở ra những đường tắt mà một con số tùy biến lúc chạy không có — và cái giá của phép chia là một trong những chỗ khác biệt đó lộ rõ nhất, từ mã máy tới thiết kế cấu trúc dữ liệu.

Muốn tự thấy thì viết unsigned f(unsigned x){ return x / 7; } và unsigned g(unsigned x, unsigned d){ return x / d; }, rồi gcc -O2 -S -o - t.c. Tìm f: bạn sẽ thấy một hằng lạ (kiểu 18725 / 0x24924925) rồi umull và vài lệnh dịch — không có udiv. Tìm g: chỉ một lệnh udiv trần. Đổi f thành x / 256 và biên dịch lại: nó rút về đúng một lệnh dịch lsr. Rồi nếu muốn thấy tác động thời gian, cho một mảng lớn và cộng a[i] / 7 so với a[i] / d (với d là volatile để buộc udiv) trong hai vòng, đo bằng clock_gettime — bản chia hằng nhanh hơn nhiều lần. Ba mươi giây đó cho bạn thấy vì sao một hằng số ở mẫu số lại đáng giá đến thế.