Ở 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 được 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 vào đo, 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 nhau.
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ó có thể 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 số 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.
Tôi soi mã máy trong container gcc:13 (ARM AArch64). 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à đo hớ của tôi, 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à đo trên dữ liệu thật của mình để quyết, thay vì theo quy tắc chung.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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 hay lover gọi với hằng có thể mở khóa magic.
Hệ quả 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), và 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ã.
Hệ quả thứ ba là bài học đo lường: "đắt" của một phép phụ thuộc cả ước số lẫn hình dạng tải. Chia không phải một chi phí duy nhất: chia-hằng-thông-lượng gần như miễn phí, chia-biến đắt 2,7 lần, chia-hằng-trong-chuỗi-phụ-thuộc lại không hơn udiv. Con số mang theo: chia cho hằng số biến thành nhân magic + dịch (bỏ udiv, x/256 chỉ một lệnh dịch) và vector hóa được, nên ở thông lượng nhanh 2,7 lần chia cho biến (0,1715 so 0,4668 ns) vì udiv không có bản vector; nhưng trong chuỗi phụ thuộc magic KHÔNG thắng (2,048 so udiv 1,820 ns) vì dãy lệnh dài hơn — lợi ở thông lượng, không ở độ trễ. Muốn phép chia rẻ, cho compiler một ước số hằng; và đo đúng loại tải trước khi tin con số.
Thử ba mươi giây
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ế.
