Có một mẹo tối ưu mà lập trình viên nào cũng từng nghe: "muốn nhân với 8 thì viết x << 3 cho nhanh". Đằng sau mẹo đó là một phép biến đổi thật của trình biên dịch — sức mạnh giảm (strength reduction): thay một phép đắt bằng một dãy phép rẻ tương đương. Câu hỏi tôi mang vào: compiler làm việc đó tới đâu, và trên CPU hiện đại thì "rẻ hơn" còn nhanh hơn được bao nhiêu? Tôi vào đo với hai niềm tin, và cả hai đều phải chỉnh lại.
Đắt thành rẻ, compiler tự làm
Sức mạnh giảm có ba dạng hay gặp. Nhân với hằng số biến thành dịch bit và cộng: x*8 thành x<<3, x*10 thành (x*5)<<1. Chia hoặc lấy dư cho hằng số biến thành một phép nhân với "số ma thuật" rồi dịch — tránh hẳn lệnh chia. Và trong vòng lặp, biểu thức a[i] với địa chỉ base + i*stride được thay bằng một con trỏ cộng dồn p += stride mỗi vòng (biến quy nạp — induction variable), bỏ phép nhân lặp đi lặp lại.
Tôi soi mã máy -O2 trong container gcc:13 (ARM AArch64) để xác nhận. Đúng từng dòng:
x*8 -> lsl w0, w0, 3 (một lệnh dịch, không mul)
x*10 -> add w0, w0, w0, lsl 2 (= x*5)
lsl w0, w0, 1 (rồi *2 — vẫn không mul)
x/7 -> mov w1, 0x92499363 (số ma thuật)
smull ...; lsr ...; asr ... (nhân + dịch, KHÔNG có sdiv)
x%10 -> umull ...; lsr ...; sub ... (magic, KHÔNG có udiv)
x*y -> mul w0, w0, w1 (y là biến -> mul thật, không giảm được)
Chỉ hằng số mới giảm được; x*y với y là biến vẫn phải là lệnh mul thật. Điểm quan trọng đầu tiên: compiler làm hết những thứ này ở -O2. Tự tay viết x<<3 thay x*8 không cho bạn gì ngoài một dòng code khó đọc hơn. Nhưng "giảm" xong thì nhanh hơn bao nhiêu? Đó là chỗ tôi đo hớ.
Đo hớ: "rẻ hơn" không có nghĩa "nhanh hơn rõ"
Niềm tin thứ nhất của tôi: thay nhân bằng dịch bit thì nhanh hơn hẳn. Tôi đo một chuỗi phụ thuộc — mỗi phép chờ kết quả phép trước, nên đo đúng độ trễ mỗi phép — so a*3 (lệnh mul) với a+(a<<1) (dịch cộng, cũng bằng a*3):
a*3 (mul) : 0,911 ns / phép
a+(a<<1) : 0,683 ns / phép
Dịch cộng có nhanh hơn, nhưng chỉ chừng 0,23 ns — không phải trời với vực. Lý do: trên ARM hiện đại (và mọi CPU cao cấp), nhân số nguyên rất rẻ — độ trễ khoảng 3 chu kỳ và bộ nhân có ống lệnh (pipelined), nên một phép nhân gần như không tốn hơn một phép cộng là mấy. Cái hình dung "nhân đắt kinh khủng, dịch bit cứu bạn" là di sản của những CPU cũ hàng chục năm trước. Hôm nay, x<<3 thay x*8 là tối ưu vi mô gần như vô nghĩa — và compiler đằng nào cũng tự làm.
Niềm tin thứ hai đổ theo cách bất ngờ hơn. Tôi tin chia-cho-hằng-số biến thành magic là luôn thắng phép chia. Đo chuỗi phụ thuộc:
a/7 biến (udiv thật) : 1,821 ns / phép
a/7 hằng (magic mul) : 2,047 ns / phép <- CHẬM hơn!
Trong chuỗi phụ thuộc, bản magic chậm hơn cả phép chia thật một chút. Vì phép udiv hiện đại không còn quá đắt, còn dãy magic (nhân + dịch + cộng + trừ) là một chuỗi lệnh dài hơn về độ trễ. Bất ngờ này buộc tôi hỏi: vậy khi nào magic thắng? Câu trả lời là thông lượng — khi có nhiều phép chia độc lập chạy song song trong ống lệnh, không phép nào chờ phép nào:
chia mảng, mỗi phần tử độc lập:
a[i]/7 biến (udiv) : 0,483 ns / phần tử
a[i]/7 hằng (magic) : 0,347 ns / phần tử -> nhanh 1,39 lần
Ở đây magic thắng rõ, vì hai lý do: bộ chia của CPU có thông lượng thấp (ít phép chia mỗi chu kỳ) trong khi bộ nhân chạy song song tốt; và quan trọng hơn, phép nhân magic vector hóa được trên NEON còn udiv thì không (ARM không có lệnh chia vector số nguyên). Nên lợi của sức mạnh giảm không phải một hằng số cố định — nó phụ thuộc phép nào (chia lợi nhiều hơn nhân) và hình dạng tải (thông lượng lợi, chuỗi phụ thuộc có khi không).
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng tự tay làm sức mạnh giảm. Viết x<<3 thay x*8, hay tự chế công thức magic để chia, chỉ khiến code khó đọc mà không nhanh hơn bản compiler tự sinh — nó đã làm, và làm đúng hơn bạn (xử lý cả số âm, tràn). Cái bạn đổi đi là sự rõ ràng; cái bạn nhận về thường là số không. Viết x*8 hay x/7 cho người đọc hiểu; để -O2 lo phần mã máy.
Hệ quả thứ hai: "phép đắt" là khái niệm phụ thuộc CPU và ngữ cảnh. Trên phần cứng hôm nay, nhân số nguyên đã rẻ ngang cộng, nên khoảng cách nhân–dịch gần như biến mất. Phép chia vẫn là phép đắt nhất trong nhóm số học, nên đó là chỗ sức mạnh giảm còn đáng giá — nhưng ngay cả nó cũng chỉ thắng ở thông lượng. Nếu bạn từng nghe "tránh nhân/chia bằng mọi giá", hãy đo trước: quy tắc đó đến từ một thế hệ CPU khác.
Hệ quả thứ ba nối sang các tối ưu vòng lặp: trong vòng nóng, chi phí thật thường không phải một phép nhân lẻ mà là phép nhân lặp lại triệu lần. Đó là lý do biến quy nạp (đổi base + i*stride thành p += stride) đáng giá — nó xóa phép nhân khỏi mỗi vòng, và kết hợp với bung vòng lặp cùng vector hóa thành phần lớn tốc độ của một vòng chặt. Con số mang theo: sức mạnh giảm thay phép đắt bằng phép rẻ (x*8→dịch, x/7→nhân magic bỏ sdiv/udiv) và compiler tự làm ở -O2; nhưng lợi tùy phép và hình dạng tải — trên ARM hiện đại nhân rẻ nên dịch chỉ nhanh hơn chút (0,683 so 0,911 ns), còn chia hằng thắng 1,39 lần ở thông lượng (0,347 so 0,483, lại còn vector hóa được) nhưng trong chuỗi phụ thuộc có khi còn chậm hơn udiv. Đừng tự tay giảm; và trước khi tin "phép này đắt", hãy đo đúng hình dạng tải của bạn.
Thử ba mươi giây
Viết một file t.c với int f(int x){ return x*8; } và int g(int x){ return x/7; }, rồi chạy gcc -O2 -S t.c -o - và tìm hai hàm. Bạn sẽ thấy f chỉ có một lsl (không hề có mul), và g không có sdiv nào cả — thay vào đó là một mov số ma thuật (kiểu 0x92499363) rồi smull. Thử đổi x*8 thành x*9, x*7, x*15 xem compiler chọn bao nhiêu lệnh dịch-cộng; rồi đổi x/7 thành x/8 (lũy thừa 2) và xem nó rút về một phép dịch duy nhất. Ba mươi giây đó cho bạn thấy trình biên dịch đã làm sẵn mọi mẹo bit mà người ta hay khuyên bạn tự viết.
